<p>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).</p>

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

<ul>
<li>if the position corresponding to n is terminal then P has won on that position</li>
<li>if P is to play in the position corresponding to n, then n has exactly one child</li>
<li>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.</li>
</ul>

<p>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 <em>cost</em> for each proof tree. For instance, the <em>fastest</em> win is obtained by finding a proof tree of minimal depth. The <em>simplest</em> win is obtained by finding a proof tree of minimal size etc.
After you have decided on the definition of <em>cost</em>, you get a strategy for the losing player: play the move leading to a position with maximal cost. </p>

<p>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 <em>retrograd analysis</em> 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.</p>

<p>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 href="http://arxiv.org/abs/1207.1832" rel="nofollow">a paper</a> on this very topic.</p>

CC BY-SA 3.0
2013-10-12T12:14:46.457Z
2013-10-12T12:14:46.457Z
Abdallah
<p>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.</p>

<p>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.</p>

<p>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?</p>

CC BY-SA 3.0
2013-05-09T01:43:10.317Z
"that approach doesn't necessarily eventually win."  Yes it does, unless there are "tied" positions.  See: http://en.wikipedia.org/wiki/Game_tree.  Please, can no one point me to a reference? My searches have revealed very little of use.
Aron Samkoff
CC BY-SA 3.0
2013-05-09T05:18:55.273Z
You're assuming a priori that the game tree is finite; this is not always true, even for games that can be won with a finite number of moves with optimal play.  If your game tree _is_ finite, then moving down the game tree without losing counts as "making progress".
Jeffε
CC BY-SA 3.0
2013-09-14T18:50:16.020Z
@JɛﬀE if at any step there is a finite number of moves and each (infinite) path in the tree is labeled win for player 1 or win for player 2, then doesn't König's lemma imply that the computer can always win by making sure it never loses? (maybe I should not say computer, because it's not clear to me that the strategy will be computable)
Sasho Nikolov
CC BY-SA 3.0
2013-10-12T22:01:28.007Z
Are these games of perfect information? If not, what is it about the card games which enable us to find optimal strategies?
c.lorenz
CC BY-SA 3.0
2013-10-13T00:17:04.453Z
Maximizing the min length to a lost position is a common strategy for minimax-class algorithms used for e.g. Chess. This is implemented in the normal algo simply by assigning lost terminal positions a small value + the depth of the position. I'm however not aware of any more thorough treatise on what to do with lost positions. For Monte-Carlo algos, which might be useful when you have more cards, there has been some discussions on the computer-go mailing list where it is reported that the probabilistic nature of the algo is better at this and terminal positions are only assigned values 0 or 1.
c.lorenz
<ai.artificial-intel><gt.game-theory>
AI strategies for losing positions
Aron Samkoff
# AI strategies for losing positions

(Asked by: username_0 on 2013-05-08)

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?

**Tags:** ai.artificial-intel, gt.game-theory

> **Comments:**
> **username_0**: "that approach doesn't necessarily eventually win."  Yes it does, unless there are "tied" positions.  See: http://en.wikipedia.org/wiki/Game_tree.  Please, can no one point me to a reference? My searches have revealed very little of use.  
> **username_1**: You're assuming a priori that the game tree is finite; this is not always true, even for games that can be won with a finite number of moves with optimal play.  If your game tree _is_ finite, then moving down the game tree without losing counts as "making progress".  
> **username_2**: @JɛﬀE if at any step there is a finite number of moves and each (infinite) path in the tree is labeled win for player 1 or win for player 2, then doesn't König's lemma imply that the computer can always win by making sure it never loses? (maybe I should not say computer, because it's not clear to me that the strategy will be computable)  
> **username_3**: Are these games of perfect information? If not, what is it about the card games which enable us to find optimal strategies?  
> **username_3**: Maximizing the min length to a lost position is a common strategy for minimax-class algorithms used for e.g. Chess. This is implemented in the normal algo simply by assigning lost terminal positions a small value + the depth of the position. I'm however not aware of any more thorough treatise on what to do with lost positions. For Monte-Carlo algos, which might be useful when you have more cards, there has been some discussions on the computer-go mailing list where it is reported that the probabilistic nature of the algo is better at this and terminal positions are only assigned values 0 or 1.  

---

## 1 answers

### Answer by username_4 on 2013-10-12. Score: 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](http://arxiv.org/abs/1207.1832) on this very topic.


---

