Regularity in the G-sequences of Octal games

Specialeforsvar ved Mathis Elmgaard Isaksen

Titel: Regularity in the G-sequences of Octal games

Abstract: Octal games are a certain type of impartial games that can be defined by an octal numeral game code. By a classic theorem we know that all impartial games are equivalent to the classic game of Nim. As result of this, one can associate to every octal game what is known as the G-sequence of the game. This sequence allows one to infer a winning strategy for any position under the rules of the octal game. G-sequences can be computed recursively, and therefore it is known that many octal games have periodic G-sequences. It is however an open question whether or not all finite octal games have periodic G-sequences. The thesis focuses first on the theory of octal games based on the basic premises of combina-torial game theory. This includes the periodicity theorems, which allows one to determine the periodicity of the G-sequences, the theory of sparse spaces, and octal games in relation to arithmetic periodicity. We then perform an experimental study of octal games, focused on games without apparent sparse spaces. We also see a very interesting find regarding the periodic structure within finite octal games, which has not been mentioned elsewhere.

Vejleder:  Søren Eilers
Censor:    Lars Døvling Andersen, Aalborg Universitet