Games Maths
I’ve put up Prolog code and notes on swish as I’ve struggled to figure out a five page paper, Nim, A Game with a Complete Mathematical Theory, that Harvard maths professor Charles Bouton wrote back in 1902.
https://swi-prolog.discourse.group/t/ive-put-a-nim-player-on-swish/8853
These notes are exercise in using Hugo’s maths markup as I try to figure out Winning Ways for Your Mathematical Plays.
\[ G=\left\{*1,*5,*4,*2|*1,*5,*4,*2\right\} \]Nim addition
https://games.ggp.org/base/games/nim1/nim1.kif
https://games.ggp.org/base/games/nim2/nim2.kif
https://games.ggp.org/base/games/nim3/nim3.kif
https://games.ggp.org/base/games/nim4/nim4.kif
\[ \begin{aligned} *1 + *2 = *3 \\ *1 + *3 = *2 \\ *2 + *3 = *1 \end{aligned} \]nim_add([1,2], 3).
nim_add([1,3], 2).
nim_add([2,3], 1).
https://wild.maths.org/play-win-nim
After developing DIY ways of valuing game trees for my AI hobby project, I discovered I could be standing on the shoulders of giants John Horton Conway, Patrick Michael Grundy, Roland Sprague, Emanuel Lasker… assuming I can understand any of it.
Combinatorial game theory has a jargon term nimber, a number refering to the game Nim which is used as a heuristic for any impartial game as opposed to a partisan game.
A handy way of remembering these four cases is just to describe the player who has the winning strategy—this is either Left, Right, or the first, or the second player to move from the start. In symbols, we have
G > 0 or Gis positive if player L (Left) can always win G < 0 or Gis negative if player R (Right) can always win G = 0 or G is zero if player 2 (second) can always win G || 0 or G is fuzzy if player 1 (first) can always win.
THE BOGUS NIM-HEAP PRINCIPLE
Every impartial game is just a bogus Nim-heap (that is, a Nim-heap with reversible moves added from some positions).
The Mex Rule gives the size of the heap for G as the least possible number that is not the size of any of the heaps corresponding to the options of G.
nim-addition, 58, 59, 73, 74, 90, 109, 110,
The sum of any two nimbers is another nimber:
191-196, 199, 246
Nim-Addition Rule, 60
Nim-Addtion Rule, 59
Nim-heaps, 41, 42, 56-59, 82
Nim-heaps, bogus, 56, 57
Nim-position, 41
nim-sequence, 82, 84, 86, 87, 94, 98, 99, 103-105, 107-109, 113, 114, 116
nim-sum, 59, 73, 74, 82, 90, 91, 109-112
nim-values, 82, 84, 86, 87, 90-96, 98, 99, 110— 117, 191-196
nim-values, doubling, 94
nim-values, duplication, 94, 98, 99, 114, 116
nim-values, halving, 195
nim-values, periodic, 84, 86, 91, 92, 94, 98, 99, 101, 103-105, 107-110, 112-117
nim-values, reflected, 109
nim-values, replication, 98
nimber, 231, 258
nimber arithmetic, 42
nimbers, 40-42, 56, 57, 65, 74, 84, 110, 119, 199, 200, 262
nimbers, adding, 42, 58
https://wild.maths.org/play-win-nim
https://games.ggp.org/base/games/nim1/nim1.kif
https://games.ggp.org/base/games/nim2/nim2.kif
https://games.ggp.org/base/games/nim3/nim3.kif
https://games.ggp.org/base/games/nim4/nim4.kif
https://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem
Games maths introduces a function called mex (minimum excluded value) which takes a list of positive integers starting from zero and returns the first missing number:
\[ \begin{aligned} mex(\left\{\right\})=0 \\ mex(\left\{1,2,3\right\})=0 \\ mex(\left\{0,2,4,6\right\})=1 \\ mex(\left\{0,1,2,3\right\})=4 \end{aligned} \]Translated to a Prolog unit test:
:- begin_tests(mex).
:- use_module([mex]).
test(empty_set, Mex == 0) :-
mex([], Mex).
test(missing_zero, Mex == 0) :-
mex([1,2,3], Mex).
test(missing_one, Mex == 1) :-
mex([0,2,4,6], Mex).
test(missing_end, Mex == 4) :-
mex([0,1,2,3], Mex).
:- end_tests(mex).
And my mex functions looks like:
:- module(mex, [mex/2]).
mex(OrdList, Mex) :-
mex_(OrdList, 0, Mex).
mex_(OrdList, Mex, Mex) :-
\+memberchk(Mex, OrdList), !.
mex_(OrdList, N0, Mex) :-
memberchk(N0, OrdList),
succ(N0, N1),
mex_(OrdList, N1, Mex).
In the 1930s, the Sprague–Grundy theorem showed that all impartial games are equivalent to heaps in Nim, thus showing that major unifications are possible in games considered at a combinatorial level, in which detailed strategies matter, not just pay-offs.
moves valued by counting edges
Can we really evaluate positions by adding up numbers of moves advantage, even when they are fractions? Is it wise to regard all positions in which the starter loses as having zero value? The answers are yes.
tree values
Figure 9. A Hackenbush Position worth 95. Figure 9 shows a Hackenbush position of value 93, since the tree has value 9, and the rest value 3. What are the moves here? Right has a unique red edge, and so a unique move, to a position of value 9+ 1 = 10, but Left can move either at the top of the tree, leaving 83, or by removing the 4 completely, which is a better move, since it leaves value 9. Since Left’s best move is to value 9, and Right’s to 10, we express this by writing {9|10} = 95 (“9 slash 10 equals 93”)
if neither player has a legal move the game has zero value.
Since Left’s man can move 5 times and Right’s only 3, the value is 5 — 3 = 2 spare moves for left.
Figure 11. Some Ski-Jumps Positions.
The book focuses on two-player games, Left and Right. Left is Blue and Right is Red.
Its convention for best value of Left and Right is:
\[ \left\{9|10\right\}=9\frac{1}{2} \]