AI strategies for losing positions

Question

I have a card game that I am analyzing with Maple. Actually, it's a series of card games, one for every parameter k, where k is a natural number (representing the number of ranks of cards used in the game). For small k, it is feasible to completely solve the game by reverse induction. I am trying to create an AI that will play optimally from this.

Given a winning position (and it being the computer's turn) the computer can answer easily with any move that takes the position to a losing one for the player. However, what to do with a losing position? Of course, picking a random move is a terrible strategy. Is there some way to make life very difficult for the human player? One idea I had was to make it choose a move that maximizes the length of the minimum path needed for the player to win the game. That would seem to avoid getting into all the psychology of what human weaknesses are in the game etc.

I am aware that this problem is completely general (does not depend on the game). However, I had difficulty finding good references. Does anyone have any references for someone interested in learning about AI in this setting?

Answer 1

Let's assume all possible paths are finite to make the discussion simpler. This is the case for the vast majority of game actually played such as Chess (because of the 50-move rule) or Go (assuming superko is forbidden).

The idea you have about chosing the move maximizing the minimum path is actually an instance of the following more general idea. A proof tree for player P is a subtree of game tree starting at the current position such that for every node n of the tree

• if the position corresponding to n is terminal then P has won on that position
• if P is to play in the position corresponding to n, then n has exactly one child
• if the opponent of P is to play, then every opponent's move leads to a child of n A proof tree corresponds to a winning strategy for P, so if a position is a theoretical win, then it should be possible to find a proof tree.

Now, there may be several proof trees to choose from in a given won position. To decide which one should be chosen, you can define a cost for each proof tree. For instance, the fastest win is obtained by finding a proof tree of minimal depth. The simplest win is obtained by finding a proof tree of minimal size etc. After you have decided on the definition of cost, you get a strategy for the losing player: play the move leading to a position with maximal cost.

Now, the only things that remains is finding the minimum cost for won positions and finding the maximum cost for lost positions. As you have discovered, this can be done by retrograd analysis when the cost is the depth of a tree. It turns out it's not too hard to generalize this for other cost measures still using retrograd analysis.

If your game is too large to perform retrograd analysis or you are only interested in a specific starting position, the problem becomes a little bit harder but you can to use a kind of generalization of the A* algorithm. Shameless plug: I have a paper on this very topic.

Answer 2

(This is too long for a comment.)


Consider the following game:

The deck has an Ace and the nine other cards from 2 to 10.
The cards start out divided equally among the players' hands, and turns alternate.
During each player's turn, that player may choose (and reveal) a card from their hand.
Whenever a card is chosen (and revealed) that way, if
that card is the Ace then the player who revealed it wins.
The preceding sentence is the only way for the game to end.


In that game:

Every position is a winning position for the player who has the Ace in their hand.
In particular, there are no "tied" positions, and every position with the
Ace in the computer's hand is a winning position for the computer.
From any such position, the answer of not choosing a
card takes the position to a losing one for the player.
If the computer always does that, then the computer will never win.