13
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Oh man, I remember this from grade school! There were some minor rules differences though. Anything above 4 was "dead", and you could "transfer" any amount at any time. $\endgroup$ – Deusovi Feb 25 '16 at 3:06
  • $\begingroup$ At the start of the game players have one hand with no fingers up. Are they allowed to use this hand to tap with? $\endgroup$ – Gordon K Feb 25 '16 at 10:22
  • $\begingroup$ Is there anything to prevent stalemate? I can see loops, such as 4-4:3-2 then 4-4:2-2 then 1-4:2-2 then 1-4:3-2 and back to 4-4:3-2. $\endgroup$ – Gordon K Feb 25 '16 at 10:34
  • 1
    $\begingroup$ @GordonK at the start both players have two hands with one finger up each. There is nothing (in the rules) to prevent loops $\endgroup$ – Slepz Feb 25 '16 at 16:19
  • 1
    $\begingroup$ @costrom yea this is just an old game I used to play on road trips. The wikipedia claims it's solved, but I think that's referring to the basic version. $\endgroup$ – Slepz Feb 26 '16 at 16:31
3
$\begingroup$

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.

$\endgroup$
-3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Assuming this is correct would mean, that you just found a way to win every game where moves can be copied, e.g. chess, checkers, ... $\endgroup$ – Sleafar Feb 25 '16 at 19:07
  • 3
    $\begingroup$ [1 1 / 1 1] [1 2 / 1 1] [1 2 / 2 1] [1 4 / 2 1], then what could come next? You can't mirror if that happens. $\endgroup$ – Deusovi Feb 25 '16 at 19: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.