# Thirty-one game. Prediction of the winner

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
• One obvious elimination, assuming the input is a valid stack, is that if the stack has 1 mod 4 cards, player B can’t be the winner; if it has 2 mod 4, player C can’t; etc. – Matthew C Dec 27 '19 at 13:16
• I'm confused about the rules of the game. Can you edit the question to explain it more clearly? What is present on the table and in the players hands at the start of the game? How do you decide which cards each player gets? When are cards laid out on the table? What do you mean by stacked cards? Can you explain the stack? I don't see any reference to creating a stack or modifying it, so I'm not sure what that is referring to. Does it have something to do with which cards are turned over? What do you mean by 'put aside'? After 356656 why can't A make any move? – D.W. Dec 27 '19 at 18:43
• – Yuval Filmus Dec 27 '19 at 20:14

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