OFFSET
0,3
COMMENTS
A combinatorial game tree has the form {A,B,... | C,D,...}, where A,B,C,D,... are game trees. We can define addition, negation and a preorder on the game trees as described in Winning Ways (or Wikipedia on surreal numbers). We can simplify a game tree by deleting dominated moves or bypassing reversible moves. Thus we say that a game tree is in normal form if there are no dominated or reversible moves at any node of the tree.
A move from G to A of Left is dominated if they have a move from G to B such that B >= A (B is better for Left than A).
A move from G to A of Left is reversible if Right can respond with a move from A to X such that X <= G (X is better for Right than G).
Dominated and reversible moves are defined symmetrically for Right.
In Winning Ways pp.76-77, Berlekamp et. al. prove that any two normal forms that are equal (x <= y and y <= x) are isomorphic; any move in x has an equivalent move in y and vice versa. Thus the normal forms are the simplest representative for each equivalence class of game trees under equality.
REFERENCES
E. R. Berlekamp, J. H. Conway and R. K. Guy, Winning Ways for Your Mathematical Plays (2nd ed./ vol. 1), A K Peters, 2001.
LINKS
Github Gist, spaanse/generate_normal_forms.cpp.
Wikipedia, Combinatorial Game Theory.
Wikipedia, Surreal Number
EXAMPLE
Up to n=5 we have the following game trees:
{|} = 0
.
{|{|}} = {|0} = -1
{{|}|} = {0|} = 1
.
{|{|{|}}} = {|-1} = -2
{{|}|{|}} = {0|0} = *
{{{|}|}|} = {1|} = 2
.
{|{|{|{|}}}} = {|-2} = -3
{{|}|{|{|}}} = {0|-1} = -1/2 +- 1/2
{{|}|{{|}|}} = {0|1} = 1/2
{{|{|}}|{|}} = {-1|0} = -1/2
{{{|}|}|{|}} = {1|0} = 1/2 +- 1/2
{{{{|}|}|}|} = {2|} = 3
.
{|{|{|{|{|}}}}} = {|-3} = -4
{{|}|{|{|{|}}}} = {0|-2} = -1 +- 1
{{|}|{{|}|{|}}} = {0|*} = up
{{|{|}}|{|{|}}} = {-1|-1} = -1*
{{{|}|}|{|{|}}} = {1|-1} = +-1
{{{|}|}|{{|}|}} = {1|1} = 1*
{{{|}|{|}}|{|}} = {*|0} = down
{{{{|}|}|}|{|}} = {2|0} = 1 +- 1
{{{{{|}|}|}|}|} = {3|} = 4
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Jelmer S. Firet, Jan 05 2025
STATUS
approved