During my school years, we often filled the brief moments of respite between two class periods with a game we called chopsticks. This is a simple, two-player game that requires no more equipment than a pair of hands. A single game takes less than a minute, and it tends to go on forever, so you can simply call a draw when the next teacher gets in.
The way we played it was like this. Each player starts with one “chopstick” on each hand, represented with an extended finger.
Players can “add” their chopsticks from any of their hands, to any other hand – their own or those of their opponent’s. They do this by physically touching their hand to the other hand to which they want to add their chopsticks.
The key rule is – if a player’s hand has exactly five chopsticks, the hand is out of play. If a player’s hand would have more than five chopsticks, they “discard” five and keep what’s remaining (essentially, a sum modulo 5).
The game ends when a player has both hands out of play. In this case, the other player would be declared the winner.
We also played with a “split” mechanic. If a player’s hand is out of play, and their other hand has more than one chopstick, they can split that hand to revive the one out of play. So, if their hands are ${\phi, 2}$, they can split their right hand to make it ${1, 1}$.
With these rules, play tends to loop forever because the split mechanic tends to reset to the start position (or states close to it). There’s just enough tantalizing possibility of trying something new in the next loop, which, of course, makes the game perfect to keep playing until both players mutually agree to declare a draw, either due to boredom of because the teacher for the next period just arrived.
Having been reminded of the game a while ago, I wanted to try and solve the game. Given the possibility of looping, I limited the game in two ways —
- remove the splitting mechanic: players can’t split their hands, and a hand that is out of play remains that way for the rest of the game
- repetition limit: if the same state is repeated, the game ends in a draw (similar to chess' threefold repetition, but harsher to make solving the game easier)
I then created an engine to implement these rules of chopsticks. It is implemented as a PettingZoo AEC environment, which I find to be an elegant formulation of multi-agent games for reinforcement learning. Check out the repo on GitHub.
The environment models a game state using five variables — one for each player’s hands, and one for whose turn it is. A player’s hand consists of $[0, 4]$ chopsticks. There are a couple extra variables for tracking repetition as well.
The action space is usually six actions – any hand to any other hand (both your own, or the other player’s). This could be fewer if a hand is out of play. Hands are labeled min and max, for which hand contains fewer or more chopsticks, instead of left or right. This made it easier to implement the actions.
The solver is a standard DFS exploration of the reachable states, referenced directly from CLRS. It is then followed by retrograde analysis from the terminal states to deal with the issue of repetition better, and find the state values. It’s quite practical to enumerate all states and find their terminal values since there are only $450$ total states – $5$ for each of the four hands (with the min/max restriction), and two possible player turn options, gives $(\frac{5 \times (5 + 1)}{2})^2 \times 2 = 450$. In practice, there are only $392$ since not all states are reachable from the start state (e.g., you can’t reach the start state where it is P2’s turn instead of P1.)
The verdict is that my version of chopsticks is a draw with perfect play. P2 can always force a draw by repetition no matter what P1 does. Here’s a (fairly messy) graph that shows the optimal play.
The first key consideration is that P1 cannot make a self-move as their opening. This immediately loses the game after P2 adds on to their max hand, with the sequence ${(1, 1), (1, 1)} \rightarrow {(1, 2), (1, 1)} \rightarrow {(1, 3), (1, 1)}$. Now, no matter what P1 does, they are certain to lose. Here’s a graph showing P2’s optimal play for every P1 action.
After P1’s opener, P2’s optimal play pretty much looks like adding their min hand to the opponent’s max hand. This will loop until a draw is reached. If P2 deviates and makes a blunder, this graph shows how P1 can capitalize on it.
I’m not too surprised that this game is so simplistic and ends in a draw with perfect play. I suspect adding back the split rule will show there isn’t any winning combination possible, since every hand can just be split to get back to an earlier game state.