<div class="notebook">
<div class="nb-cell markdown" name="md1">
# Nimbers
_Robert Laing_
This is my Prolog implementation of a technique for playing Nim explained by Harvard maths professor Charles Bouton in 1902 in a five page paper [Nim, A Game with a Complete Mathematical Theory](https://www.jstor.org/stable/1967631?seq=1).
Bouton introduced a system of valuing Nim game states that has come to be known as "nimber addition" which I've implemented as `nim_add(+HeapSizeList, -Nimber)`. Nimbers of 0 are "safe combinations", and once a player has moved to a safe combination, the opponent is toast. Provided the player makes no mistake (and computers don't), he will always have a safe combination in his options no matter what move his opponent makes, while the opponent will never get one.
This means if the starting state has a nimber of 0, the starting player can't win unless the second player makes a mistake. So from the nimber value of the starting state one can figure out if there's a first or second player advantage.
Bouton's technique has become a core part of the evolution of "the mathematics of games" and applied to a huge number in the encyclopedic four volume [Winning Ways for Your Mathematical Plays](https://annarchive.com/files/Winning%20Ways%20for%20Your%20Mathematical%20Plays%20V1.pdf) by Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy.
In the code below I've taken an example from Stanford Universitiy's online [General Game Playing](http://ggp.stanford.edu/) course, [nim1.kif](https://games.ggp.org/base/games/nim1/nim1.kif) and translated it from the lisp-dialect to SWI-Prolog, but in this case the init predicates are just place holders in my template.
nim1.kif equates to
```prolog
playgame([control(player1),heap(a,1),heap(b,5),heap(c,4),heap(d,2)], Moves).
```
but any starting state of Nim (ie any number of heaps and starting sizes) can be provided. Using Bouton's formula, whether player1 or player2 wins can be seen by who moves last, ie doesn't have a "noop" move in GGP parlance.
I've started a [thread](https://swi-prolog.discourse.group/t/ive-put-a-nim-player-on-swish/8853) on this code at the SWI-Prolog Discourse forum.
</div>
<div class="nb-cell program" data-background="true" name="p1">
:- dynamic true/1, does/2.
role(player1).
role(player2).
init(heap(a,1)).
init(heap(b,5)).
init(heap(c,4)).
init(heap(d,2)).
init(control(player1)).
legal(P, noop) :-
true(control(X)),
role(P),
X \= P.
legal(P, reduce(X,N)) :-
true(control(P)),
true(heap(X,M)),
L is M - 1,
between(0,L,N).
next(heap(X,N)) :-
does(_P,reduce(X,N)).
next(heap(X,N)):-true(heap(X,N)),does(_P,reduce(Y,_M)),X\=Y.
next(control(P2)):-true(control(P1)),next_player(P1,P2).
terminal :-
findall(N, true(heap(_,N)), L),
sum_list(L, 0).
goal(P,0):-true(control(P)).
goal(P,100):-true(control(P1)),next_player(P,P1).
next_player(player1, player2).
next_player(player2, player1).
update_true(State) :-
retractall(true(_)),
forall(member(Base, State), assertz(true(Base))).
update_does(DoesList) :-
retractall(does(_,_)),
forall(member(does(Role, Move), DoesList), assertz(does(Role, Move))).
cartprod(S, L) :-
findall(R, cart(S, R), L).
cart([], []).
cart([[A | _] | T], [A | R]) :-
cart(T, R).
cart([[_ | B] | T], R) :-
cart([B | T], R).
findlegals(Role, Legals) :-
findall(does(Role, Legal), legal(Role, Legal), Unsorted),
sort(Unsorted, Legals).
findedges(Edges) :-
findall(Role, role(Role), Roles),
maplist(findlegals, Roles, Legals),
cartprod(Legals, Edges).
findnext(DoesList, Next) :-
update_does(DoesList),
findall(Proposition, next(Proposition), Unsorted),
sort(Unsorted, Next).
int_to_binary_str(Int, BinStr) :-
format(string(BinStr), '~`0t~2r~*|', [Int ,8]).
binary_str_to_int(BinStr, Int) :-
string_chars(BinStr, Chars),
length(Chars, L),
Idx is L - 1,
chars_to_int(Chars, Idx, 0, Int).
chars_to_int([Char], 0, Sum, Int) :- !,
atom_number(Char, N),
Int is Sum + N.
chars_to_int([Char|Chars], Idx0, Sum0, Acc) :-
Idx0 > 0,
atom_number(Char, N),
Sum1 is Sum0 + ((2^Idx0) * N),
Idx1 is Idx0 - 1,
chars_to_int(Chars, Idx1, Sum1, Acc).
nimbin_add_(CharLsts, Idx, '0') :-
maplist(nth0(Idx), CharLsts, Ns),
maplist(atom_number, Ns, Numbers),
sum_list(Numbers, Sum),
0 is mod(Sum, 2), !.
nimbin_add_(CharLsts, Idx, '1') :-
maplist(nth0(Idx), CharLsts, Ns),
maplist(atom_number, Ns, Numbers),
sum_list(Numbers, Sum),
1 is mod(Sum, 2), !.
nimbin_add(CharLsts, [C0,C1,C2,C3,C4,C5,C6,C7]) :-
nimbin_add_(CharLsts, 0, C0),
nimbin_add_(CharLsts, 1, C1),
nimbin_add_(CharLsts, 2, C2),
nimbin_add_(CharLsts, 3, C3),
nimbin_add_(CharLsts, 4, C4),
nimbin_add_(CharLsts, 5, C5),
nimbin_add_(CharLsts, 6, C6),
nimbin_add_(CharLsts, 7, C7).
nim_add(NumList, Nimber) :-
maplist(int_to_binary_str, NumList, BinStrs),
maplist(string_chars, BinStrs, CharLsts),
nimbin_add(CharLsts, CharLst),
string_chars(BinStr, CharLst),
binary_str_to_int(BinStr, Nimber).
get_nimber(State, Nimber) :-
findall(N, member(heap(_, N), State), L),
nim_add(L, Nimber).
safe_combination(State) :-
get_nimber(State, 0).
best_move(State, SafeMove) :-
update_true(State),
findedges(Moves),
maplist(findnext, Moves, Nexts),
include(safe_combination, Nexts, SafeNexts),
SafeNexts \= [],
random_member(SafeNext, SafeNexts),
nth0(Idx, Nexts, SafeNext),
nth0(Idx, Moves, SafeMove), !.
best_move(State, RandomMove) :-
update_true(State),
findedges(Moves),
maplist(findnext, Moves, Nexts),
include(safe_combination, Nexts, SafeNexts),
SafeNexts == [],
random_member(RandomMove, Moves).
playgame(Init, Moves) :-
playgame_(Init, [], Reversed),
reverse(Reversed, Moves).
playgame_(State, Moves, Moves) :-
update_true(State),
terminal, !.
playgame_(State0, Moves, Acc) :-
update_true(State0),
\+terminal,
best_move(State0, Move),
findnext(Move, State1),
playgame_(State1, [Move|Moves], Acc).
</div>
<div class="nb-cell markdown" name="md6">
The first example uses the starting Nim state in [nim1.kif](https://games.ggp.org/base/games/nim1/nim1.kif) where `nim_add([1,5,4,2],Nimber).` produces 2, and as predicted by Bouton, player1 has an option to move to a "safe combination" by taking both pieces in heap d so always wins no matter what move player2 selects. I elaborate using this starting state as the default further down.
</div>
<div class="nb-cell query" name="q5">
playgame([control(player1),heap(a,1),heap(b,5),heap(c,4),heap(d,2)], Moves).
</div>
<div class="nb-cell markdown" name="md7">
Now for [nim2.kif](https://games.ggp.org/base/games/nim2/nim2.kif) where `nim_add([2,2,10,10],Nimber).` produces a safe combination of 0, so player1 can't win if player2 reacts correctly to any move. Bouton said in a theorem whose proof I can't claim to understand that "safe combinates" oscilate back to first player to move to one (or in this example starts in one), and there's nothing the opponent can do unless the player with "safe combination" advantage makes a mistake.
</div>
<div class="nb-cell query" name="q6">
playgame([control(player1),heap(a,2),heap(b,2),heap(c,10),heap(d,10)], Moves).
</div>
<div class="nb-cell markdown" name="md8">
Next [nim3.kif](https://games.ggp.org/base/games/nim3/nim3.kif) where `nim_add([11,12,15,25],Nimber).` produces 17, and player1 has a "safe combination" by reducing pile d to 8 from 25 pieces.
</div>
<div class="nb-cell query" name="q7">
playgame([control(player1),heap(a,11),heap(b,12),heap(c,15),heap(d,25)], Moves).
</div>
<div class="nb-cell markdown" name="md9">
Finally [nim4.kif](https://games.ggp.org/base/games/nim4/nim4.kif) where `nim_add([12,12,20,20],Nimber).` means a starting "safe combination" giving player2 a route to guaranteed victory.
</div>
<div class="nb-cell query" name="q8">
playgame([control(player1),heap(a,12),heap(b,12),heap(c,20),heap(d,20)], Moves).
</div>
<div class="nb-cell markdown" name="md2">
In the nim1.kif setup, player1 has a choice of 12 opening moves.
</div>
<div class="nb-cell query" name="q1">
State = [control(player1),heap(a,1),heap(b,5),heap(c,4),heap(d,2)],
update_true(State),
findedges(Moves).
</div>
<div class="nb-cell markdown" name="md3">
These lead to 12 possible states to hand to player2
</div>
<div class="nb-cell query" name="q2">
State = [control(player1),heap(a,1),heap(b,5),heap(c,4),heap(d,2)],
update_true(State),
findedges(Moves),
maplist(findnext, Moves, Nexts).
</div>
<div class="nb-cell markdown" name="md4">
Calculating the values of each of those states using Bouton's method of writing the size of each nim pile in binary, and then _aggregating_ them by the rule that if the number of 1s in a column is odd, that column is 1, and if even, the column is 0 (zero ones in a column is even).
</div>
<div class="nb-cell query" name="q3">
State = [control(player1),heap(a,1),heap(b,5),heap(c,4),heap(d,2)],
update_true(State),
findedges(Moves),
maplist(findnext, Moves, Nexts),
maplist(get_nimber, Nexts, Nimbers).
</div>
<div class="nb-cell markdown" name="md5">
A mistake I origally made was to misread Bouton's paper to think valuable states had nimbers of either 0 or 2, but only 0 equates to "safe combinations".
</div>
<div class="nb-cell query" name="q4">
State = [control(player1),heap(a,1),heap(b,5),heap(c,4),heap(d,2)],
best_move(State, SafeMove).
</div>
<div class="nb-cell markdown" name="md10">
About 30 years after Bouton published his paper, British mathematician [Patrick Michael Grundy](https://en.wikipedia.org/wiki/Grundy_number) and German mathematician [Roland Sprague](https://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem) independently figured out that Bouton's methods for Nim could abstracted to any [impartial game](https://en.wikipedia.org/wiki/Impartial_game), ie games which don't allocate specific pieces to players. This is in contrast with games such as chess, checkers etc where players are black or white which are called [partisan games](https://en.wikipedia.org/wiki/Partisan_game).
</div>
</div>