Research projects

Project CEMAPRE internal

TitleCyclic games
ParticipantsAlda Carvalho (Principal Investigator), João P Neto, Carlos P Santos
SummaryCombinatorial Game Theory (CGT) is a branch of mathematics that studies sequential games (alternated
decisions) with perfect information (no hidden information, no chance devices, [1, 2, 3, 4]). In
CGT, an impartial game is a game in which the allowable moves depend only on the position and not on
which of the two players is currently moving; that is, in all situations, the sets of options are
exactly the same for both players.

Regarding finite games (games without cycles), 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. The Sprague-Grundy theory was extended to general finite games
with cycles by Cedric Smith [6] and by Aviezri Fraenkel and coauthors [6, 7]. This extension is
mainly a theoretical work, not presenting non-trivial applications. In this project, we will try to
analyze some non-trivial rulesets in the light of Smith-Fraenkel Theory.

[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.
[5] C. A. Smith. Graphs and composite games. J. Comb. Thy., 1(1):51–81, 1966.
[6] A. S. Fraenkel and U. Tassa. Strategy for a class of games with dynamic ties. Comput. Math.
Appl., 1(2):237–254, 1975.
[7] A. S. Fraenkel, Y. Perl. Constructions in combinatorial games with cycles. In Infinite and
Finite Sets (to Paul Erdõs on his 60th birthday), Volume 2, ed. A. Hajnal, R. Rado, and V. Sos,
pages 667-699. North-Holland, 1975.