Thirty-one game. Prediction of the winner

Question

I have a problem with creating an algorithm to predict a winner of thirty-one game.

Players from a deck of cards, take the Ace, 2, 3, 4, 5, and 6 of each suit. These 24 cards are laid out face up on a table. The players alternate turning over cards and the sum of the turned over cards is computed as play progresses. Each Ace counts as one. 
The only limit is the sum value of stacked cards: it cannot exceed 31. The player who cannot make a move loses.

My task is to determine the winner in the game based on stack of cards put aside. We assume that both players play perfectly.

For example:

356656 means gameplay: player A puts down 3, player B puts down 5, player A puts down 6, player B puts down 6, player A puts down 5, finally player B puts down 6 and wins because player A cannot make any move.

356656 -> winner B
35665 -> winner B
3566 -> winner A
111126666 -> winner A
552525 -> winner A
2 -> winner A

Yuval Filmus · Answer

This kind of question can be answered using a simple recursive procedure.

A state of the game consists of:

a sequence $a_1,ldots,a_n$ describing how many cards of each value in $1,ldots,n$ remain (in your case, $n = 6$).
the number of "points" remaining $p$.

Your initial state is $vec{a}=(4,4,4,4,4,4)$ and $p = 31$.

For each state $(vec{a},p)$, there is a sequence of possible moves, which in this case is
$$
N(vec{a},p) = { (a_1,ldots,a_{i-1},a_i-1,a_{i+1},ldots,a_n),p-i : i in [n], a_i geq 1, i leq p }.
$$
Let us say that a position is winning if the first player wins when starting from it. A position is winning iff there is a next position which is losing, and so the winning predicate $W(vec{a},p)$ satisfies the recurrence
$$
W(vec{a},p) = bigvee_{vec{b},q in N(vec{a},p)} lnot W(vec{b},q).
$$ 
When $N(vec{a},p) = emptyset$, the disjunction is empty, and so $W(vec{a},p)$ is false.

In your case, you can easily calculate $W((4,4,4,4,4,4),31)$ to be true. The winning moves are $1,2,5$.

Here is sage code that calculates this:

@CachedFunction
def game(cards, target):
    return [i for i in range(len(cards)) if target >= i and cards[i] >= 1
    and len(game(cards[:i] + (cards[i]-1,) + cards[i+1:], target-i)) == 0]

This code also allows cards with value zero. You can run it like so:

sage: game((0,4,4,4,4,4,4),31)
[1, 2, 5]

It outputs the set of winning moves (if any).

Thirty-one game. Prediction of the winner

One Answer

Add your own answers!

Ask a Question