Backward algorithm and abstract graphs in zero-sum games

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.