Research projects

Project CEMAPRE internal

TitleCombinatorial Game Theory: Disjunctive Short Sum
ParticipantsAlda Carvalho (Principal Investigator), Carlos Santos
SummaryCombinatorial Game Theory is a branch of mathematics that studies sequential games (alternated
decisions) with perfect information (no hidden information, no chance devices, [1, 2, 3, 4]).

About disjunctive short sum (dss), John Conway defined the following: «The compound game ends as
soon as any one of the component games has ended» [1]. Also in [1], about impartial games played
with dss (the set of allowable moves depends only on the position and not on which of the two
players is moving, that is, Left options and Right options are the same for the game and all its
subpositions), John Conway wrote

«What we can do is foreclose the game by making a position illegal if the game has just ended, or
can be ended by a single winning move. Modern Chess is in fact the foreclosed version of primitive
Chess, in which the game ended when the loser's King was captured. In modern Chess, a position in
which the King has been captured is illegal, as is also any position in which the King can be
captured on the next move, and so a game ends two moves before, when one of the Kings is

So, if, by rules, it is not allowed to make a move that enables the opponent to finish a component,
we have a «pure» impartial combinatorial game. Sprague-Grundy Theory states that the values of
impartial combinatorial games are nimbers (*n={0,*,...,*(n-1)|0,*,...,*(n-1)}) and the Grundy value
of an impartial combinatorial game is the unique non negative integer n such that G=*n. Given an
impartial game, an important mathematical goal is to present a closed formula or a polynomial time
procedure fo find its Grundy value.

[1] J. Conway. On Numbers and Games. Academic Press, 1976.
[2] E. Berlekamp, J. Conway, R. Guy. Winning Ways. Academic Press, London, 1982.
[3] M. Albert, R. Nowakowski, D. Wolfe. Lessons in Play: An Introduction to Combinatorial Game
Theory. A. K. Peters, 2007.
[4] A. N. Siegel. Combinatorial Game Theory, American Math. Soc., 2013.