The Finger Game

Question

There's a game called the finger game. It's played by two players who each start with one finger on each hand up. The players take turns using one of their hands to tap one of their opponent's hands.

1. When a player A taps player B's hand (or vice versa), B adds the number of fingers on A's hand to his own hand. Ex. A has one finger up, B has two. A taps B. A still has one finger up, B has three.
2. When either player has five fingers up on a hand, that hand is dead and out of the game. Dead hands have no fingers up.
3. When a player would have more than five fingers up on a hand, they subtract five from the number of fingers they should have up. Ex. A has three fingers up, B has four. A taps B. B now has two fingers up.
4. When a player only has one hand alive and their live hand has an even number of fingers up, they may skip their turn and pass half their fingers from the live hand to the dead hand, reviving it.
5. If either player has two dead hands, they lose.

With perfect play, who wins? The first player or the second?

Answer 1

I will assume that the active player does not have the option of tapping an opponent's dead hand.

With optimal play by both players the solution is that:

The game is indefinite, with no winner.

This may be shown by:

Backward induction (Ben Polack is right, this is almost always the answer!)

The current state of a Finger Game may be represented as the numbers of fingers showing on each of the four hands in some fixed order relative to the current turn, say:

$($activePlayer'sLeftHand, activePlayer'sRightHand, opponent'sLeftHand, opponent'sRightHand$)$

Thus if I am showing $(L,R) = (0,2)$ and you are showing $(L,R)=(3,1)$, then
if it is your turn to act the state would be $(3,1,0,2)$; whereas
if it is my turn to act the state would be $(0,2,3,1)$.

Optimal play by both players results from each player choosing an optimal action at each state reachable given optimal previous actions*. Thus, in the previous example with you to act, you would certainly choose $LR$ - to tap your left hand onto my right hand - and win.
But if were my turn to act what should I do?
I have three options: $split$, $RL$, or $RR$.
$RR$ would certainly be a blunder as it leads to $(3, 3, 0, 2)$ where you could play either $LR$ or $RR$ and win.
But what about $split$ and $RL$?

There are $5^{2^2}$ naive states the game could be in, but any of the form: $$(a,b,0,0)\lor(0,0,a,b)\ \forall\ a,b\in [0,4]$$ have already finished at some earlier point, leaving $(5^2-1)^2$ states

Now note that if the opponent has only one live hand showing $n\in[1,4]$ fingers then the current player to act cannot have two hands both showing $n$ fingers, since it would mean that the opponent previously tapped a dead hand.
This removes $2*4=8$ states:
$(1,1,0,1),(1,1,1,0),(2,2,0,2),(2,2,2,0),(3,3,0,3),(3,3,3,0),(4,4,0,4),(4,4,4,0)$

Also if the opponent has two live hands both showing $n\in[3,4]$ they could not have $split$ to get there and cannot have left the current player with two live hands both showing $n$ since it too means the opponent previously bought a dead hand back to life.
This removes another $2$ states:
$(3,3,3,3),(4,4,4,4)$

Furthermore if the opponent has two live hands both showing $n\in[3,4]$ the current player cannot have two live hands showing $n$ and $n-2$ since the only ways to reach such a state would be either the opponent having tapped a dead hand, or from one of the two states removed in the previous paragraph.
This removes a final $2*2=4$ states:
$(1,3,3,3),(3,1,3,3),(2,4,4,4),(4,2,4,4)$

So the total number of valid states is $(5^2-1)^2-8-2-4=562$

We can now work backwards to see if $(1,1,1,1)$ is a winning state, a losing state or neither as follows.

• Start with three empty sets: $states$, $winningStates$, and $losingStates$;

• Place all $562$ states into $states$;

• Move states from $states$ into $winningStates$ if any action results in a win;

• Repeatedly analyse $states$ twice:

  1. Move states from $states$ into $losingStates$ if all actions lead to states in $winningStates$

  2. move states from $states$ into $winningStates$ if any action leads to a state in $losingStates$

• Stop when no state is moved in either pass.
  - we could solve the problem at hand by also stopping if $(1,1,1,1)$ is moved.

If we do this we see that:

$(1,1,1,1)$ is not moved - it is not a winning or losing state given optimal play by both players.

We may also see things such as:

In the example with me to act neither $split$ nor $RL$ lead to a state in $winningStates$
- I could play either of them without putting you in a winning position.

* A full strategy for optimal play would provide the action (or set of actions) for any possible state.

Answer 2

The second player to move should win the game.

Explanation:

The second player can start out mirroring the moves of the first player, using the two hands not used by the first player. If this continues, either neither player will win or the first player will win as they are always one move ahead of the second. However, the second player can abandon this strategy when it benefits him, thereby gaining an advantage over player one. This will allow player two to win.