Dissertation
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.
- Author
- Bergh, M.J.H. van den
- Date
- 01 June 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.