Chopsticks in Prolog

Prolog

The Game

Chopsticks is a simple game of many variations played by children and college students. The variation I play is:

  1. two players start by each sticking both index fingers out to represent a count of one on each hand
  2. players alternate turns until someone loses by having a count of zero on both hands
  3. on a player’s turn, he must either:
    1. use one of his hands with positive count $H1$ to tap one of the other player’s hands $H2$. The other player updates the count on $H2$ to $(H1+H2) \bmod 5$ by changing the number of fingers sticking out
    2. redistribute aka “split” his fingers in one of two ways: $(4,0)–>(2,2)$ or $(2,0)–>(1,1)$

For example, we can visualize the first turn of the game like so:

  • each cell is a player’s hand
  • * designates whose turn it is
  • LL means top player used his left hand (wrt us, so actually his right hand) to tap bottom player’s left hand
First move of the game

Like many games, Chopsticks is well-suited to being modeled in Prolog. I was particularly interested in determining whether the first or second player has a forced win. Unfortunately, for the variation given above, there is no forced win for either player. Let’s see how I modeled this in Prolog (source code, run online).

My original vision was to test all possible variations to find rulesets (there is at least one) with forced wins. I actually got as far as implementing all the variations with configurable toggles everywhere, but the code was horribly bug-infested and I threw it in the garbage. I might return to this one day when I’m better at Prolog. In the meantime, this simple, straightforward code will have to suffice.

The Program

We first define helper predicate tap/3 that calculates new finger counts and some facts about valid split and lost states.

tap(From, To, ToNew) :-
	From \= 0,
	Total is From + To,
	ToNew is mod(Total, 5).

split(0, 4, 2).
split(4, 0, 2).
split(0, 2, 1).
split(2, 0, 1).

lost(0, 0).

There are five possible moves (LL, RR, LR, RL, split) on a player’s turn. get_next/3 is comprised of a rule for each move for each player for a total of ten rules.

% get_next(hand(TopLeft,TopRight,BottomLeft,BottomRight,Turn), Next, Seen)
% calculates the Next unSeen state given it is Turn's move
get_next(hand(TL,TR,BL,BR,bottom), Next, Seen) :- tap(BL,TL,TL_New), Next=hand(TL_New,TR,BL,BR,top), \+member(Next,Seen).
get_next(hand(TL,TR,BL,BR,bottom), Next, Seen) :- tap(BR,TR,TR_New), Next=hand(TL,TR_New,BL,BR,top), \+member(Next,Seen).
get_next(hand(TL,TR,BL,BR,bottom), Next, Seen) :- tap(BL,TR,TR_New), Next=hand(TL,TR_New,BL,BR,top), \+member(Next,Seen).
get_next(hand(TL,TR,BL,BR,bottom), Next, Seen) :- tap(BR,TL,TL_New), Next=hand(TL_New,TR,BL,BR,top), \+member(Next,Seen).
get_next(hand(TL,TR,BL,BR,top), Next, Seen) :- tap(TL,BL,BL_New), Next=hand(TL,TR,BL_New,BR,bottom), \+member(Next,Seen).
get_next(hand(TL,TR,BL,BR,top), Next, Seen) :- tap(TR,BR,BR_New), Next=hand(TL,TR,BL,BR_New,bottom), \+member(Next,Seen).
get_next(hand(TL,TR,BL,BR,top), Next, Seen) :- tap(TR,BL,BL_New), Next=hand(TL,TR,BL_New,BR,bottom), \+member(Next,Seen).
get_next(hand(TL,TR,BL,BR,top), Next, Seen) :- tap(TL,BR,BR_New), Next=hand(TL,TR,BL,BR_New,bottom), \+member(Next,Seen).

get_next(hand(TL,TR,BL,BR,bottom), Next, Seen) :- split(BL,BR,S), Next=hand(TL,TR,S,S,top), \+member(Next,Seen).
get_next(hand(TL,TR,BL,BR,top), Next, Seen) :- split(TL,TR,S), Next=hand(S,S,BL,BR,bottom), \+member(Next,Seen).

The final and most interesting predicate forced_win/2 has two base cases and one recursive case. I was proud of myself 😂 for figuring out the recursive case and feel that it nicely captures the expressive power of Prolog.

The \+ operator can be read as “not”. The ! operator is a “cut”, which means “don’t try to re-satisfy any of the previous clauses”. We use this because we are interested in only the first forced win.

% current player already won
forced_win(hand(TL,TR,_,_,bottom), _) :- lost(TL, TR), !.
forced_win(hand(_,_,BL,BR,top), _) :- lost(BL, BR), !.

% current player can win in a single move
forced_win(hand(TL,TR,BL,BR,bottom), Seen) :-
	\+ lost(BL, BR),
	get_next(hand(TL,TR,BL,BR,bottom), hand(TL_2,TR_2,BL,BR,top), Seen),
	lost(TL_2, TR_2),
	!.
forced_win(hand(TL,TR,BL,BR,top), Seen) :-
	\+ lost(TL, TR),
	get_next(hand(TL,TR,BL,BR,top), hand(TL,TR,BL_2,BR_2,bottom), Seen),
	lost(BL_2, BR_2),
	!.

% current player has a branch that always ends in a win
forced_win(H1, Seen) :-
	% can the current player choose a move...
	get_next(H1, H2, Seen),
	append(Seen, H1, NewSeen),

	% s.t. all of the opponent's possible moves result in a forced win?
	setof(H3, get_next(H2, H3, NewSeen), Hs),
	forall(member(H, Hs), forced_win(H, NewSeen)),
	!.

The Query

Finally we run our completed program to see if there exist forced wins for the first or second players.

?- forced_win(hand(1,1,1,1,top), []).
false.

?- forced_win(hand(1,1,2,1,bottom), []).
false.