Backward algorithm and abstract graphs in zero-sum games
Loading...
Date
2020-05-01
Authors
Iklassov, Zangir
Journal Title
Journal ISSN
Volume Title
Publisher
Nazarbayev University School of Sciences and Humanities
Abstract
With the beginning of the computer age, solving many problems in game theory has
become easier. However, there is a whole class of well-known problems such as chess,
checkers, go and so on, the methods of solving which use brute force technique to find
solutions of the game. This technique requires analysis of all states of the game and it has
the exponential complexity of running the algorithm due to which many games cannot
be solved on modern computers. Considered class of games include zero-sum games with
perfect information described in discrete space. For such problems, there is no smooth
solution that would allow solving problems without going through all the states of the
game. This work proposes a new algorithm for finding solutions to such problems. The
algorithm uses a new data structure, called abstract graphs and backwards analysis to
find solutions. The algorithm still has the exponential complexity of the analysis, however,
finding a solution does not require going through all the possible states of the game, which
reduces the complexity of analysis. For a clear example, the algorithm was used on a
tic-tac-toe game, for which brute force technique requires analysis of around 15k states,
while the Backwards algorithm analyzed just 5 states to find all existing solutions. In the
future, this study can be continued for a deeper study of the mathematical properties of
the algorithm and to use it on games such as chess and go.
Description
Keywords
Citation
Iklassov, Z. (2020). Backward algorithm and abstract graphs in zero-sum games (Master’s thesis, Nazarbayev University, Nur-Sultan, Kazakhstan). Retrieved https://nur.nu.edu.kz/handle/123456789/4786