Games Maths

These are notes I’m making as I work through Winning Ways for Your Mathematical Plays Volume 1 by John Conway, Elwyn Berlekamp and Richard Guy, and also an exercise in using Hugo’s maths markup.

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:

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).

https://en.wikipedia.org/wiki/Combinatorial_game_theory

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.

Roland Sprague

Peter Michael Grundy

nimber also called Grundy numbers

https://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem

https://archive.org/stream/winning-ways-for-your-mathematical-plays-v-1/Winning%20Ways%20for%20Your%20Mathematical%20Plays%20V1_djvu.txt

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: