Chopsticks (hand game)

Chopsticks (sometimes called Splits, Calculator, or just Sticks) is a hand game for two or more players, in which players extend a number of fingers from each hand and transfer those scores by taking turns tapping one hand against another. Chopsticks is an example of a combinatorial game, and is solved in the sense that with perfect play, an optimal strategy from any point is known.
In Chopsticks, players tally points using the fingers of both hands, with each extended finger counting as one point. A hand with less than five points is considered to be "living"; if it collects five points or more, it is "knocked out" and becomes "dead." The goal of the game is to knock out both of the opponent’s hands; the winner is the last player with a living hand.
In the basic game for two players, each starts with two points—with one finger of each hand extended. Players then take turns, and on each turn must either:
(1) "Attack” by tapping either of the opponent's hands, adding points to it.
—OR—
(2) "Split" by tapping their own two hands together to redistribute points between the hands.
Due to the game's simple basic structure, there are many rule variations, as noted below. For example, in one variation a hand can only be knocked out by a sum of exactly five points; any points over five are "rolled over" as in modular arithmetic. For example, three points plus three becomes one point, and the tapped hand stays alive. In the "suicide" variation, a player may knock out their own hand by transferring all points from it, reducing it to zero. In other variations, and for multi-player or team play, more complex transfer and division moves are allowed.
Each position in a two-player game of Chopsticks can be encoded as a four-digit number, with each digit ranging from 0 to 4, representing the number of active fingers on each hand. This can be notated as [ABCD], where A and B are the hands of the player who is about to take their turn, and C and D are the hands of the player who is not about to take their turn. Each pair of hands is notated in ascending order, so every distinct position is represented by one and only one four-digit number. For example, the code 1023 is not allowed, and should be notated 0123.
The starting position is 1111. Unless any special transfers are used, the next position must be 1211. The next position must be either 1212 or 1312. During the game, the smallest position is 0001, and the largest is 4434.
This abbreviation can be expanded to games with more players. A three-player game can be represented by six digits (e.g. [111211]), where each pair of adjacent digits represents a single player, and each pair is ordered based on when players will take their turns. The leftmost pair represents the hands of the player about to take his turn; the middle pair represents the player who will go next, and so on. The rightmost pair represents the player who must wait the longest before his turn (usually because he just went).
Under normal rules, there are a maximum of 14 possible moves:
However, only 5 or fewer of these are available on a given turn. For example, the early position 1312 can become 2213, 1313, 2413, 0113, or 1222.
The shortest possible game is five moves. There is one instance:
Without revisitation (repeating a position), the longest possible game is nine moves. There are two instances:
With revisitation, the longest possible game is indefinite.
Since the roll-over amount is 5, Chopsticks is a base-5 game. In a two-player game, each position is four digits long. Counting from 0000 to 4444 (in base 5) yields 625 positions. However, this includes redundancies—most of these positions are incorrect notations (e.g. 0132, 1023, and 1032 are incorrect notations of 0123), which appear different but are functionally the same in gameplay.
To find the number of functionally distinct positions, note that each player can be one of 15 distinct pairs (00, 01, 02, 03, 04, 11, 12, 13, 14, 22, 23, 24, 33, 34, and 44). With two players, there are 15*15 = 225 functionally distinct positions. In general, for n {\displaystyle n} players, there are 15 n {\displaystyle 15^{n}} functionally distinct positions.
However, there are 21 unreachable positions: 0000, 0100, 0200, 0300, 0400, 1100, 1101, 1200, 1300, 1400, 2200, 2202, 2300, 2400, 3300, 3303, 3400, 3444, 4400, 4404, and 4444.
This gives a total of 204 unique, reachable positions.
There are 14 reachable endgames: 0001, 0002, 0003, 0004, 0011, 0012, 0013, 0014, 0022, 0023, 0024, 0033, 0034, 0044. Satisfyingly enough, these are all the 14 possible endgames; in other words, someone can win using any of the 14 distinct live pairs. Out of these 14 endgames, the first player wins 8 of them, assuming that the games are ended in the minimum number of moves.
Chopsticks can be generalized into a ( p , r ) {\displaystyle (p,r)} -type game, where p {\displaystyle p} is the number of players and r {\displaystyle r} is the rollover amount.
In a one-player game, the player trivially wins for virtue of being the last player in the game. A game with zero players is likewise trivial as there can be no winners.
Given p = 2 {\displaystyle p=2} and a rollover of r {\displaystyle r} ,
Thus, for r > 2 {\displaystyle r>2} , there are ( r + 1 2 ) p − ( ( r + 1 2 ) + ( r − 1 ) + 2 ) {\displaystyle {r+1 \choose 2}^{p}-\left({r+1 \choose 2}+(r-1)+2\right)} reachable positions.
Given a rollover of 5,
A game with a rollover amount of 1 is the trivial game, because all hands start dead.
A game with a rollover amount of 2 is degenerate, because splitting is impossible, and the rollover and cutoff variations result in the same game. Hands are either alive and dead, with no middle state, and attacking a hand kills the hand. In fact, one could simply keep count of the number of 'hands' a player has (by using fingers or some other method of counting), and when a player attacks an opponent, the number of hands that opponent has decreases by one. There are a total of 2 p − 1 {\displaystyle 2^{p}-1} reachable positions in the game, and a game length of 2 p − 1 {\displaystyle 2p-1} . The two player game is strongly solved as a first person win.
When two players have only one hand, the game becomes degenerate, because splits cannot occur and each player only has one move. Given a rollover of r {\displaystyle r} , each position after k {\displaystyle k} moves in the game can be represented by the tuple ( F k + 2 mod r , F k + 1 mod r ) {\displaystyle \left(F_{k+2}{\bmod {r}},F_{k+1}{\bmod {r}}\right)} , where F k {\displaystyle F_{k}} is the k {\displaystyle k} -th Fibonacci number with F 0 = 0 {\displaystyle F_{0}=0} and F 1 = 1 {\displaystyle F_{1}=1} . The number of positions is given by least positive number k {\displaystyle k} such that r {\displaystyle r} divides F k + 2 {\displaystyle F_{k+2}} . This variant is strongly solved as a win for either side depending upon r {\displaystyle r} and the divisibility properties of Fibonacci numbers. The length of the game is k + 1 {\displaystyle k+1} .
Using the rules above, two perfect players will play indefinitely; the game will continue in a loop. In fact, even very inexperienced players can avoid losing by simply looking one move ahead.
In the cutoff variation, the first player can force a win. One winning strategy is to always reach one of the following configurations after each move (preferentially choosing the first one):
Conversely, in the Division and Suicide only variation, then the second player has a winning strategy.