Sarabet Chang Yuye

State transition graph for Chopsticks (the children's game)

I found myself at a location without a phone, and introduced my boyfriend to Chopsticks, a game I played in elementary school in Korea. (It appears to be Japanese in origin.) It’s a simple game, and I napkin-calculated it could have at most* 450 states.

Then I became curious what the full game state transition diagram would look like.

Blue is start. Green and red are starting player and nonstarting player win nodes.

As far as I can tell, the actual number of reachable states is 382, counting the 28 arguably-not-valid(-distinct) game states where loser is out of hands and the winner has one of 14 different hand states (01, 02, 03, 04, 12, 13, 14, 22, 23, 24, 33, 34, 44).

The diagram skips those 14 states – if a player can win in a game state, that state immediately goes to the player’s win node.

Python code below:

from collections import deque
from graph_tool.all import *

start = ((1, 1), (1, 1), 0) # p1hands, p2hands, turn. if turn is 0, p1 goes next. phands are always sorted
end = [2, 1] # p2 wins, p1 wins
q = deque([start])
mapping = {start: []}

# returns a deduped set of [(hand1, hand2), (hand1, hand2)]. hands will be sorted.
def getNextHands(activePlayer, passivePlayer): # tuple, tuple
    a, b = activePlayer
    c, d = passivePlayer
    
    moves = set()
    if a+b > 1 and a+b < 7:
        for i in range(max(0, a+b-4), min(5, a+b)):
            moves.add((
                tuple(sorted((i, a+b-i))),
                passivePlayer
            ))
        moves.discard((activePlayer, passivePlayer)) # discard state identical the one we started with

    if a > 0:
        if c > 0:
            moves.add((activePlayer, tuple(sorted((c+a if c+a < 5 else 0, d)))))
        if d > 0:
            moves.add((activePlayer, tuple(sorted((c, d+a if d+a < 5 else 0)))))
    if b > 0:
        if c > 0:
            moves.add((activePlayer, tuple(sorted((c+b if c+b < 5 else 0, d)))))
        if d > 0:
            moves.add((activePlayer, tuple(sorted((c, d+b if d+b < 5 else 0)))))
    return moves

# state => [state, ... state]
def getNextStates(state):
    if state[-1] == 0: # active player is first player
        hands = getNextHands(state[0], state[1])
        return [(h + (1,))for h in hands]
    else: # active player is second
        hands = getNextHands(state[1], state[0])
        return [(h[1], h[0], 0,) for h in hands]

def buildMapping():
    global q
    global mapping
    while len(q) > 0:
        gameState = q.popleft()
        if (0, 0) in gameState: # lose state; no successors
            mapping[gameState] = [end[gameState[-1]]]
        else:
            successors = getNextStates(gameState)
            mapping[gameState]= successors
            q.extend(filter(lambda s: s not in mapping, successors))

# graph tool wants nodes that are labeled 0 to N, where N is how many vertices there are. if there's a gap, it'll create an isolated vertex, so we need to remove gaps
def reduceNodes(m1): 
    keymap = {start: 0, 1: 1, 2: 2}
    nextNewKey = 3
    for k in m1:
        if k not in keymap:
            keymap[k] = nextNewKey
            nextNewKey += 1
    
    reducedMap = {}
    for k, vs in m1.items():
        reducedMap[keymap[k]] = list(map(lambda x: keymap[x], vs))
    return reducedMap

buildMapping()
rekeyed = reduceNodes(mapping)
g = Graph(rekeyed)
vcolor = g.new_vertex_property("vector<double>")
for v in g.vertices():
    vcolor[v] = [1, 0.2, 0.2, 0.5]
vcolor[g.vertex(0)] = [1, 0, 0, 1]
vcolor[g.vertex(1)] = [0, 0.7, 1, 1]
vcolor[g.vertex(2)] = [0, 0.7, 1, 1]

pos = sfdp_layout(g, K=1.7)
graph_draw(g, pos=pos, vertex_fill_color=vcolor)

Backlinks