Project CEMAPRE internal
| Title | Combinatorial Game Theory: Disjunctive Short Sum |
| Participants | Alda Carvalho (Principal Investigator), Carlos Santos |
| Summary | Combinatorial 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 checkmated.» 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. References: [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. |