3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ "Given a winning position (and it being the computer's turn) the computer can answer easily $\hspace{.35 in}$ with any move that takes the position to a losing one for the player. However," that approach $\hspace{.08 in}$ doesn't necessarily eventually win. $\:$ The computer needs to eventually make progress. $\;\;$ $\endgroup$ – user6973 May 9 '13 at 0:01
  • $\begingroup$ "that approach doesn't necessarily eventually win." Yes it does, unless there are "tied" positions. See: en.wikipedia.org/wiki/Game_tree. Please, can no one point me to a reference? My searches have revealed very little of use. $\endgroup$ – Aron Samkoff May 9 '13 at 1:43
  • 3
    $\begingroup$ 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". $\endgroup$ – Jeffε May 9 '13 at 5:18
  • $\begingroup$ @JɛffE 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) $\endgroup$ – Sasho Nikolov Sep 14 '13 at 18:50
  • $\begingroup$ Are these games of perfect information? If not, what is it about the card games which enable us to find optimal strategies? $\endgroup$ – c.lorenz Oct 12 '13 at 22:01
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

(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.

$\endgroup$
  • $\begingroup$ Hmm, but this infinite sequence of moves you're describing is in fact a draw $\endgroup$ – Sasho Nikolov Sep 14 '13 at 18:46
  • $\begingroup$ I know. ${}{}\;$ $\endgroup$ – user6973 Sep 15 '13 at 1:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.