Disjunctive sums

Path: <= CGT path =>
    Keywords: EndGame, Theory

In combinatorial game theory (CGT), the (disjunctive) sum of two (or more) games is a game created by combining copies of the summands and allowing a player on their turn to play in one or the other game. This is ‘exclusive or’, whence the term ‘disjunctive’.

This straightforward idea is a fundamental concept in CGT, which was in fact inspired by Conway’s observation that in the endgame in go there are often many independent positions which the players have to combine as above.

Table of contents

Applications

The real depth of the concept can be seen in go when you start to wonder whether the endgame marks the point at which the game breaks up into a sum of several games (independent endgame positions). That's certainly not quite right:

  • as long as you can have ko fights, there may be plays in one part of the board that influence other regions[1];
  • there are some tricky endgame coupling effects that are standard if not that well-known, as neighbouring positions do interact beyond what one might guess.

Also, from a pro point of view, the endgame starts earlier than we think, before weak groups are settled but as soon as there isn't a reason for them to die or cause major swings in territory.

Is this because pros have a better thermometer? - Migeru

But this is still a useful start. See for example the stacks of coins model.

Formal definition

Here's the general (recursive) definition of addition. Given two games:

``G = { G_(L,1), G_(L,2), cdots | G_(R,1), G_(R,2), cdots }``
``H = { H_(L,1), H_(L,2), cdots | H_(R,1), H_(R,2), cdots }``

their sum is defined by

`` G + H = { G_(L,1)+H, G_(L,2)+H, cdots, G+H_(L,1), G+H_(L,2), cdots | G_(R,1)+H, G_(R,2)+H, cdots, G+H_(R,1), G+H_(R,2), cdots }``

Observe how, on both left and right, the options of ``G+H`` are found by adding ``H`` to all the relevant options of ``G`` and adding ``G`` to all the relevant options of ``H``.
This is because a move in the sum is either a move in ``G`` leaving ``H`` unchanged or vice versa.

If ``G`` and ``H`` are numbers, this yields the natural addition of numbers. For example

``1+1``
``={0|}+{0|}``
``={{0|}+0,{0|}+0|}``
``={{0|}+0|}``
``={{0|}+{|}|}``
``={{0|}|}``
``={1|}``
``=2``

Other types of sum

In ONAG, Conway briefly considers other forms of sum, but the disjunctive sum is far and away the most important.

The other sums are found by considering all twelve combinations of the following requirements:

  • The objective is to make the last move or to force your opponent to do so (misère play).
  • A player must move in one component game or some of them of their choice or all of them.
  • The sum ends when all component games end or when the first ends.

See also

Notes

[1] It is true that as long as kos remain on the board, the standard form of CGT cannot be used to treat the game as a sum. This is, however, not because one might have to think which part of the board to play in next, but rather because CGT does not deal with sums[2] of loopy games. After all, in a normal sum of games we have to make the choice too: in ``{10|-10}+{0|0}`` both players will want to move in the first game, but not in ``{10|-10}+{15|15}``.

[2] To model go, these sums would not be simply as defined above, but include a provision forbidding repetition while allowing it in summands.


Discussion

Migeru: I have a problem with associativity. Consider

`` {1|-1} + {2|-2} + {4|-4} = {3|-3} ``

We have (if ``n>m``)

`` {n|-n} + {m|-m} = {n-m|m-n} ``

so

`` {1|-1} + {2|-2} = {1|-1} ``

Then `` {{1|-1}+{2|-2}}+{4|-4}={1|-1}+{4|-4}={3|-3} ``

But also `` {1|-1}+{{2|-2}+{4|-4}}={1|-1}+{2|-2}={1|-1} ``

and `` {{1|-1}+{4|-4}}+{2|-2}={3|-3}+{2|-2}={1|-1} `` .

What's going on?


Bill: Dear Migeru,

`` {1 | -1} + {2 | -2} + {4 | -4}" || "{3 | -3} ``

They are confused.

`` {n | -n} + {m | -m} = {{n+m | n-m} | {m-n | -m-n}} ``

when ``m`` and ``n`` are numbers such that `` n >= m ``.


Migeru: Thanks. I definitely need to brush up on my surreal numbers, because I didn't remember the correct definition of addition.


Path: <= CGT path =>
Disjunctive sums last edited by PJTraill on January 30, 2019 - 02:19
RecentChanges · StartingPoints · About
Edit page ·Search · Related · Page info · Latest diff
[Welcome to Sensei's Library!]
RecentChanges
StartingPoints
About
RandomPage
Search position
Page history
Latest page diff
Partner sites:
Go Teaching Ladder
Goproblems.com
Login / Prefs
Tools
Sensei's Library