Chopsticks (hand game)

Chopsticks 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 to tap one hand against another.^[1]^[2] 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.

Rules

This official set of rules is called roll-over where five fingers are subtracted should a hand's sum exceeds 5 as described below.

Each player begins with one finger raised on each hand. After the first player turns proceed clockwise.
On a player's turn, they must either attack or split, but not both.
To attack, a player uses one of their live hands to strike an opponent's live hand. The number of fingers on the opponent's struck hand will increase by the number of fingers on the hand used to strike.
To split, a player strikes their own two hands together, and transfers raised fingers from one hand to the other as desired. A move is not allowed to simply reverse one's own hands. If any hand of any player reaches exactly five fingers, then the hand is killed, and this is indicated by raising zero fingers (i.e. a closed fist).
A player may revive their own dead hand using a split, as long as they abide by the rules for splitting. However, players may not revive opponents' hands using an attack. Therefore, a player with two dead hands can no longer play and is eliminated from the game.
If any hand of any player reaches more than five fingers, then five fingers are subtracted from that hand. For instance, if a 4-finger hand strikes a 2-finger hand, for a total of 6 fingers, then 5 fingers are automatically subtracted, leaving 1 finger. Under alternate rules, when a hand reaches 5 fingers and above it is considered a "dead hand".
A player wins once all opponents are eliminated (by each having two dead hands at once).
There is no variation in which a player can kill their own hand.

Optimal strategy

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.

Using the cut-off variant, 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 in the list if there is more than one choice. Each configuration will be given as [a, b], [c, d] where [a,b] represents a player's two hands (ignoring order) and [c,d] represents their opponent's.

[2, 1], [1, 1] (starting here)
[?, ?], [1, 2] (winning immediately if possible)

Conversely, if tapping one's own hand is not allowed, but splitting two live hands into one is allowed, then the second player has a winning strategy.^[3]^[how?]

Abbreviation

A chopsticks position can be easily abbreviated to a four-digit code [ABCD]. A and B are the hands (in ascending order of fingers) of the player who is about to take their turn. C and D are the hands (in ascending order of fingers) of the player who is not about to take their turn. It is important to notate each player's hands in ascending order, so that a single distinct position isn't accidentally represented by two codes. For example, the code [1032] is not allowed, and should be notated [0123].

Therefore, the starting position is [1111]. The next position must be [1211]. The next position must be either [1212] or [1312]. Treating each position as a 4-digit number, the smallest position is 0000, and the largest position is 4444.

This abbreviation formula expands easily 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).

Moves

Under normal rules, there are a maximum of 14 possible moves:

Four attacks (A-C, A-D, B-C, B-D)
Four divisions (02-11, 03-12, 04-13, 04-22)
Six transfers (13-22, 22-13, 14-23, 23-14, 24-33, 33-24)

However, only 5 or less of these are available on a given turn. For example, the early position 1312 can go to 2213, 1313, 2413, 0113, or 1222.

Game lengths

The shortest possible game is 5 moves. There is one instance:

1111 1211 1312 0113 1401 0014

The longest possible game that gets farther from the starting point with each move is 9 moves. There are two instances:

1111 1211 1212 2212 2322 0223 0202 0402 0104 0001
1111 1211 1212 2312 2323 0323 0303 0103 0401 0004

The longest possible game with revisitation is indefinite.

Positions

Since the roll-over amount is 5, chopsticks is a base-5 game. Each position is four digits long. Counting from 0000 to 4444 (in base-5) gives us 625 positions. However, most of these positions are incorrect notations (e.g. 0132, 1023, and 1032). They appear different but are functionally the same in gameplay. To find the number of functionally distinct positions, we simply square the number of functionally distinct pairs. There are 15 distinct pairs (00, 01, 02, 03, 04, 11, 12, 13, 14, 22, 23, 24, 33, 34, and 44). Since either player could have any of these pairs, we simply multiply 15*15, which gives us 225 functionally distinct positions.

There are 625 positions, including redundancies.
There are 225 functionally distinct positions.
There are 204 reachable positions.

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.

15 of these are simply one player having each of the 15 distinct pairs, and the other player being dead. The problem is that the dead player is the player who just took his turn (hence the "00" on the right side). Since the player can't lose on their own turn, these positions are obviously unreachable.
4 of those pairs are where the player to move having [kk], and the other player having [0k], where $0<k<5$ . This is unreachable because the player who just went [0k] would not be able to split, so therefore that player must have attacked using his [0k]. But there's no way to use [0k] to attack an enemy so that they move to [kk]. That would require attacking a dead hand, which is illegal.
The remaining two positions are 3444 and 4444. 4444 is unreachable because a player cannot reach [44] from a split, and therefore had to already have [44]. The only possible pair that goes to [44] after being attacked by [44] is [04], which again requires that a dead hand be attacked. 3444 is actually reachable, but only from 4444. Since 4444 is not reachable from 4444, neither is 3444.

All but one of these positions in point 2 are reachable in the "Suicide" variant, as [1101] is still unreachable. [1101] is reachable if the "Suicide" variant is played with the "Meta" variant. The two positions in point 3 are reachable in the "Suns" variant, as 4444 is the starting position, but the two positions cannot be accessed mid-game. Therefore, if playing "Suicide", "Meta", and "Suns" together, there are a total of 15 unreachable positions and 210 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 amount of moves.

Variations

Misère: First player to have both of their hands killed wins.
Suicide: Players are allowed to kill one of their own hands with a split. For example, in the position [1201], a player could execute 12-03, thus bringing the game to [0103]. The opponent is forced to play B-D, bringing the game to [0401], at which point a quick win for the first player is possible.
Swaps: If players have two unequal live hands, they may swap them (though forfeiting their turn).
Sudden Death: Players lose when they only have one finger left (on both hands). Alternately, each player could begin with three lives, and every time they get down to [01], they lose a life.
Meta: If a player's hands add up to over five, they can combine them, subtract five from the total, and then split up the remainder. For example, [44] adds up to 8. Under Meta rules, 4 and 4 can be combined into 8, which becomes 3 after subtracting five; these can then be split into [12]. Therefore, it is possible to go from [44] to [12] in a single move. Meta unlocks 2 new possible moves (34-11, 44-12). If playing both Meta and Suicide, four additional moves are unlocked (24-01, 33-01, 34-02, 44-03), for a maximum of 20 possible moves in total.
Logan Clause: Players are allowed to suicide and swap, but only if doing both simultaneously (i.e. swapping a dead hand for a live one).
Cutoff: If a hand gets above five fingers, it is dead (as opposed to rollover, described in the official rules).
Zombies: With three or more players, if a player is knocked out, then they are permanently reduced to one finger on one hand. On their turn, they may attack, but may not split or be attacked (invented by Chris Bandy).
Transfers only: Divisions are not allowed. The only splits allowed are transfers.
Divisions only: Transfers are not allowed. The only splits allowed are divisions.
Halvesies: Splitting is only allowed when dividing an even number into two equal halves, or optionally, an odd number being divided as evenly as possible (using whole numbers). In this variation, the second player has a winning strategy (can always force a win).^[4]
Stumps: If a player is at [01], it is legal to split into [0.5 0.5].
More Hands: Each player has more than two hands. This is usually played in teams of multiple people, as people only have two hands.
Different Numbers: A hand dies when it reaches a positive number $r$ . $r=5$ is the standard Chopsticks variant. Different hand counting systems could be used for numbers greater than 5 such as Chinese hand numerals, senary finger counting, and finger binary. This variation often includes rollovers.
Suns: Both players start with a 4 in each of their hands ([4444]). This is a position that is unreachable in normal gameplay (i.e. from the opening position [1111]).
Integers: It is permitted to swap one of one's own hands by flipping it over, changing the +/- sign of the hand. This allows for negative and zero value hands, though a hand still dies at 5 or -5. With roll-over, this action becomes identical to replacing the value of the hand with 5 minus the value.
Cherri: It is permitted to swap the values of each hand. For example, the position [1231] can turn into [2131]. This variation commonly yields a draw by repetition or infinite loop for obvious reasons.

Generalisations

Chopsticks can be generalized into a (p,h,r)-type game, where p is the number of players, h is the number of hands each player has, and r is the roll-over amount.

Degenerate cases

A game with a roll-over amount of 1 is the trivial game, because all hands are dead at start as values of one become values of zero. A game with one or less players is not a game, but a puzzle or a cellular automaton.

A game with a roll-over amount of 2 is degenerate, because splitting is impossible and the roll-over and cutoff variations result in the same game. Hands are either 'alive' and 'dead', 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 $h^{p}-1$ reachable positions in the game, and a game length of $ph-1$ . The two player game is strongly solved as a first person win for any $h$ . Playing this degenerate variant with the "Stumps" variant yields a game that is isomorphic to a "Halvesies" variant with a roll-over amount of 4 and a starting position where all players have two fingers on every hand.

Two players

When each player has only one hand ( $h=1$ ), the game becomes degenerate, because splits cannot occur and each player only has one move. Given a roll-over of $r$ each position after $k$ moves in the game can be represented by the tuple $\left(F_{k+2}{\bmod {r}},F_{k+1}{\bmod {r}}\right)$ , where $F_{k}$ is the $k$ -th Fibonacci number with $F_{0}=0$ and $F_{1}=1$ . The number of positions is given by least positive number $k$ such that $r$ divides $F_{k+2}$ . This variant is strongly solved as a win for either side depending upon $r$ and the divisibility properties of Fibonacci numbers. The length of the game is $k+1$ .

When each player has more than one hand ( $h>1$ ), each hands, given a roll-over of $r$ ,

There are $r^{2h}$ positions, including redundancies.
There are ${r+h-1 \choose h}^{2}$ functionally distinct positions.
There are ${r+h-1 \choose h}^{2}-\left({r+h-1 \choose h}+(r-2)+(h-1)+2\right)$ reachable positions.

Since the roll-over amount is $r$ , chopsticks is a base- $r$ game. Each position is $2h$ digits long. Enumerating all numbers in base- $r$ with $2h$ digits gives us $r^{2h}$ positions. However, most of these positions are incorrect notations (e.g. 001210, 010120, and 100021 for $h=3$ ). They appear different but are functionally the same in gameplay. To find the number of functionally distinct positions, we square the number of functionally distinct pairs. For a roll-over of $r$ and $h$ hands, there are ${r+h-1 \choose h}$ distinct pairs, where ${r+h-1 \choose h}$ is the $r$ -th $h$ -simplex number. Since either player could have any of these pairs, we simply square the resulting value, which gives us ${r+h-1 \choose h}^{2}$ functionally distinct positions.

There are ${r+h-1 \choose h}+(r-2)+(h-1)+2$ unreachable positions.

${r+h-1 \choose h}$ of these are simply one player having each of the ${r+h-1 \choose h}$ distinct pairs, and the other player being dead. The problem is that the dead player is the player who just took his turn. Since the player can't lose on their own turn, these positions are obviously unreachable.
$(r-2)$ of those positions are when the player, whose turn it is, has $h$ hands of value $k$ for $0<k<r-1$ and the other player has only one alive hand of value $k$ . These positions are unreachable because the player who only has one alive hand of value $k$ would not be able to split, so therefore that player must have attacked using his sole alive head. But there is no way to use his sole alive hand to attack an enemy so that they have $h$ hands of value $k$ , as that would require attacking a dead hand, which is illegal.
$(h-1)$ of those positions are when the player, whose turn it is, has $h$ hands of value $r-1$ and the other player has $k$ alive hand of value $r-1$ , where $0<k\leq (h-1)$ . These position are unreachable because any player who only has hands of value $r-1$ would not be able to split, so therefore that player must have attacked using one of his value $r-1$ hands. But there is no way to use an $r-1$ valued hand so that they have $h$ hands of value $r-1$ , as that would require attacking a dead hand, which is illegal.
The position when both players have $h$ hands of value $r-1$ . This is unreachable for the same reason as point 3 above.
The position when the player whose turn it is has one hand of value $r-2$ and $h-1$ hands of value $r-1$ , and the other player has $h$ hands of value $r-1$ . This position is only reachable from the previous position, but the previous position is not reachable from the starting position, so this position isn't either.

All but one of these positions in points 2 and 3 are reachable in the "Suicide" variant, as the position where the player whose turn it is has $h$ hands of value 1 and the other player has only one alive hand of value 1 is still unreachable. That position is reasonable is reachable if the "Suicide" variant is played with the "Meta" variant. The two positions in points 4 and 5 are reachable in the "Suns" variant, as the position in point 4 is the starting position, but the two positions cannot be accessed mid-game. Therefore, if playing "Suicide", "Meta", and "Suns" together, there are a total of ${r+h-1 \choose h}$ unreachable positions and ${r+h-1 \choose h}^{2}-{r+h-1 \choose h}$ reachable positions.

Hands	Roll-over amount	Positions	Functionally Distinct Positions	Reachable Positions	With 'Suicide', 'Meta', and 'Suns'
2	3	81	36	26	30
3	3	729	100	85	90
4	3	6561	225	204	210
5	3	59049	441	413	420
6	3	531441	784	748	756
2	4	256	100	85	90
3	4	4096	400	374	380
4	4	65536	1225	1183	1190
5	4	1048576	3136	3072	3080
6	4	16777216	7056	6963	6972
2	5	625	225	204	210
3	5	15625	1225	1183	1190
4	5	390625	4900	4822	4830
5	5	9765625	15876	15741	15750
6	5	244140625	44100	43880	43890

More than two players

Given a roll-over of 5 and 2 hands.

With 2 players, there are 204 positions.
With 3 players, there are 3,337 positions.
With 4 players, there are over 25,000 positions.

References

^ http://www.wikihow.com/Play-Chopsticks
^ "Chopsticks Game". Activity Village. Retrieved 2014-03-27.
^ http://www.wikihow.com/Always-Win-Chopsticks
^ Japanese games – Chopsticks (hand game), 2008

External links

Unbeatable Chopsticks AI Bot. This bot plays the game with remainders and transfers.

[1] ttp://www.wikihow.com/Play-Chopsticks

[VA-2] "Chopsticks Game". Activity Village. Retrieved 2014-03-27.

[3] ttp://www.wikihow.com/Always-Win-Chopsticks

[4] Japanese games – Chopsticks (hand game), 2008

[1]

[2]

[3]

[4]

v t e Hand games
Endurance	Red hands Mercy Thumb war
Clapping games	Down Down Baby Mary Mack Miss Lucy had a baby Miss Susie Pat-a-cake, pat-a-cake, baker's man Pease Porridge Hot
Finger-counting	Chopsticks Morra Odds and evens
Other	Johnny Whoop Rock paper scissors

v t e Topics of game theory
Definitions	Congestion game Cooperative game Determinacy Escalation of commitment Extensive-form game First-player and second-player win Game complexity Graphical game Hierarchy of beliefs Information set Normal-form game Preference Sequential game Simultaneous game Simultaneous action selection Solved game Succinct game Mechanism design
Equilibrium concepts	Bayes correlated equilibrium Bayesian Nash equilibrium Berge equilibrium Core Correlated equilibrium Coalition-proof Nash equilibrium Epsilon-equilibrium Evolutionarily stable strategy Gibbs equilibrium Mertens-stable equilibrium Markov perfect equilibrium Nash equilibrium Pareto efficiency Perfect Bayesian equilibrium Proper equilibrium Quantal response equilibrium Quasi-perfect equilibrium Risk dominance Satisfaction equilibrium Self-confirming equilibrium Sequential equilibrium Shapley value Strong Nash equilibrium Subgame perfection Trembling hand equilibrium
Strategies	Appeasement Backward induction Bid shading Collusion Cheap talk De-escalation Deterrence Escalation Forward induction Grim trigger Markov strategy Pairing strategy Dominant strategies Pure strategy Mixed strategy Strategy-stealing argument Tit for tat
Classes of games	Auction Bargaining problem Global game Intransitive game Mean-field game n-player game Perfect information Large Poisson game Potential game Repeated game Screening game Signaling game Strictly determined game Stochastic game Symmetric game Zero-sum game
Games	Go Chess Infinite chess Checkers All-pay auction Prisoner's dilemma Gift-exchange game Optional prisoner's dilemma Traveler's dilemma Coordination game Chicken Centipede game Lewis signaling game Volunteer's dilemma Dollar auction Battle of the sexes Stag hunt Matching pennies Ultimatum game Electronic mail game Rock paper scissors Pirate game Dictator game Public goods game Blotto game War of attrition El Farol Bar problem Fair division Fair cake-cutting Bertrand competition Cournot competition Stackelberg competition Deadlock Diner's dilemma Guess 2/3 of the average Kuhn poker Nash bargaining game Induction puzzles Trust game Princess and monster game Rendezvous problem
Theorems	Aumann's agreement theorem Folk theorem Minimax theorem Nash's theorem Negamax theorem Purification theorem Revelation principle Sprague–Grundy theorem Zermelo's theorem
Key figures	Albert W. Tucker Amos Tversky Antoine Augustin Cournot Ariel Rubinstein Claude Shannon Daniel Kahneman David K. Levine David M. Kreps Donald B. Gillies Drew Fudenberg Eric Maskin Harold W. Kuhn Herbert Simon Hervé Moulin John Conway Jean Tirole Jean-François Mertens Jennifer Tour Chayes John Harsanyi John Maynard Smith John Nash John von Neumann Kenneth Arrow Kenneth Binmore Leonid Hurwicz Lloyd Shapley Melvin Dresher Merrill M. Flood Olga Bondareva Oskar Morgenstern Paul Milgrom Peyton Young Reinhard Selten Robert Axelrod Robert Aumann Robert B. Wilson Roger Myerson Samuel Bowles Suzanne Scotchmer Thomas Schelling William Vickrey
Search optimizations	Alpha–beta pruning Aspiration window Principal variation search max^n algorithm Paranoid algorithm Lazy SMP
Miscellaneous	Bounded rationality Combinatorial game theory Confrontation analysis Coopetition Evolutionary game theory Glossary of game theory List of game theorists List of games in game theory No-win situation Topological game Tragedy of the commons