Artificial Intelligence
Game tree
Game trees represent a fundamental structure for the conceptualization of strategies in games such as chess. This strategic tool originated for the first time in the 19th century.
Game trees represent a fundamental structure for the conceptualization of strategies in games such as chess. This strategic tool originated for the first time in the 19th century, with Charles Babbage being attributed the first mathematical incursions in this field [Monnens, 2013]. However, it is to Von Neumann that credit is generally given for the creation of this concept [v. Neumann, 1928]. Nevertheless, the first rigorous analysis of competitive games using this method was developed by Emilie Borel [Borel, 1921]. In his work, Von Neumann demonstrated the minimax theorem (which will be explained in detail in the next section), suggesting that in theory, one could identify the best move in a chess position using this approach.
The main concept underlying the game tree is the exhaustive analysis of all possible moves from a given position, and in turn, all possible opponent responses in each of the possible resulting new positions. This iterative process is repeated until reaching a final state for each of the branches. Once this game tree is constructed, it is necessary to traverse it in a specific manner to determine the most optimal move in each of the positions; for this, the minimax algorithm will be employed.
Below, an illustrative example of a game tree is presented. This representation will be notably similar to that of a real chess game, which is no coincidence, since the game tree is, in essence, a simulation of a game that takes into consideration all possible moves.
In this scenario, only three potential White moves are considered, although in reality there are more options, such as Kf2, Qa2, Nf7, among others. Of the three White moves, only Qg8 is continued, while the other two moves allow various responses by Black. In contrast, faced with Qg8, Black must respond in a forced manner with Rxg8 (capturing the queen), and White will in turn respond with Nf7, which results in checkmate to the Black king (Black does not have a move that relieves the king from attack), granting victory to White.
The generation of this tree follows a procedure similar to the Backtracking presented in the first chapter. In each position, all possible resulting positions are enumerated and the same process continues recursively until reaching a final state. Due to the similarity with Backtracking, this method shares the problem of exponential growth of positions to review. In chess, this growth is particularly accentuated given the high number of possible moves from a given position. For example, in the initial position, White can execute 20 different moves and this figure can increase even more in the middlegame or opening. However, there are positions where only one move is possible (forced move). Due to these variations, calculating the complexity of the chess game tree is highly complex. Fortunately, the famous mathematician Shannon carried out this calculation for us, providing an estimate of the number of positions in the game tree (the Shannon number) and the number of different chess games, both intimately related.
According to Shannon, the number represents a lower bound for the number of distinct positions in chess (that is, the number of positions could be even greater, but not less than this limit). Regarding the lower bound of the number of chess games, it is estimated around , assuming there are thirty possible moves for each position and that each turn involves one move per side, that is , also assuming that the average duration of a game is 40 moves, obtaining the previous result [Claude E. Shannon, 1950].
Taking into account the complexity of this problem, it is clear that it is infeasible to generate the complete game tree, so the use of estimates or heuristics is employed. These heuristics will indicate how favorable a state is, allowing only a reduced fraction of the game tree to be generated.
Furthermore, for the game tree to offer useful information, it is necessary to traverse it in a specific way. The algorithm that will be used for this purpose is minimax, along with its improved version with alpha-beta pruning. These concepts will be addressed in the following sections.