Proefschrift

Imperfect information variants of combinatorial games

Combinatorial games are games for two competing players, moving in a turn-by-turn fashion, in which there is no chance nor hidden information⁠. Chess, checkers and the simpler tic tac toe are well-known examples of this class of games, as well as game of go⁠.

Auteur

Bergh, M.J.H. van den

Datum

01 juni 2023

Links

Thesis in Leiden Repository

Though these games are by no means simple, there does exist a beautiful mathematical framework for their analysis⁠. Using this theory, it is possible to efficiently determine the outcome of a given position of a game without having to explicitly compute the results for every possible move⁠. Moreover, the theory provides a measure of how profitable a given position is to either player, often denoted by the `value’ of a position⁠. An example application of the theory is research on endgames in go⁠.However, not all games are combinatorial games⁠. The game of poker, for example, introduces hidden information⁠. In practice, impressive results have been obtained for these non-combinatorial games using artificial intelligence, but theory and understanding are perhaps lacking⁠. In this thesis, the main question we address is whether the existing theory for combinatorial games can be adapted or extended to non-combinatorial ones⁠.