Semi-Strongly solved: a New Definition Leading Computer to Perfect Gameplay
Hiroki Takizawa · 2024
Read Semi-Strongly solved: a New Definition Leading Computer to Perfect Gameplay by Hiroki Takizawa (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-01029.txt.
Description
Abstract Solving combinatorial games has been a classic research topic in artificial intelligence because solutions can offer essential information to improve gameplay. Several definitions exist for ‘solving the game,’ but they are markedly different regarding computational cost and the detail of insights derived.
Catalog record
| CREATOR | Hiroki Takizawa |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 23 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2411-01029
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Semi-Strongly solved: a New Definition Leading Computer to Perfect Gameplay Hiroki Takizawa Abstract Solving combinatorial games has been a classic research topic in artificial intelligence because solutions can offer essential information to improve gameplay. Several definitions exist for ‘solving the game,’ but they are markedly different regarding computational cost and the detail of insights derived. In this study, we introduce a novel definition called ‘semi-strongly solved’ and propose an algorithm to achieve this type of solution efficiently. This new definition addresses existing gaps because of its intermediate computational cost and the quality of the solution. To demonstrate the potential of our approach, we derive the theoretical computational complexity of our algorithm under a simple condition, and apply it to semi-strongly solve the game of 6x6 Othello. This study raises many new research goals in this research area. K eywords Artificial Intelligence \cdot Game Informatics \cdot Combinatorial Games 1 Introduction Combinatorial games like chess have remained one of the leading research subjects in computer science, especially in the field of artificial intelligence (AI). The historical association between the ability to play combinatorial games and human intelligence [ 1 ] has driven significant interest in studying these games. Many non-trivial combinatorial games, including Connect Four [ 2 ] , Nine Men’s Morris [ 3 ] , and Checkers [ 4 ] , have already been solved. Research on solving games is related to making computers play games well but differs in some points. There are multiple definitions of game-solving. At least three definitions are known [ 2 ] . The most fundamental category is known as ultra-weakly solved games. In this type, we obtain the game-theoretic value of the starting position, but we do not have a concrete winning strategy. For example, it is known through proof by contradiction that in the game of Hex, the first player has a winning strategy regardless of the board size. Moving on, in weakly solved games, we not only know the game-theoretic value of the initial position but also have a strategy for both players to reach this value from the starting point using reasonable computational resources. At an even more detailed level, we encounter strongly solved games, where the outcomes are determined for every possible position that may arise during the game. The definitions of solving games can be viewed from the perspective of the perfection of the gameplay of AI. An ultra-weak solution provides no insights into playing. A weak solution enables AI to achieve the game-theoretic value from the initial position but does not guarantee the ability to capitalize on the opponent’s mistakes. A weak solution cannot guarantee a ‘perfect’ play in a certain sense. On the other hand, a strong solution ensures that the AI can accurately capitalize on the opponent’s mistakes in an arbitrary position that is reachable from the initial position. However, since a strong solution requires solving all possible positions, achieving this for large games is often intractable. There is a considerable and challenging gap between weak and strong solving in terms of difficulty. In the game of 6x6 Othello, for example, the game-theoretic value of the initial position (the first player loses by four points) can be determined within a few minutes to a few hours using the alpha-beta pruning algorithm [ 5 , 6 ] equipped with practical move-ordering. In other words, modern, inexpensive computers can quickly achieve ultra-weakly and weakly solving. However, since the alpha-beta pruning has the same worst-case computational complexity as exhaustive search and practical move-ordering cannot be guaranteed to function well in positions unlikely to occur in actual play [ 7 ] , it would be necessary to visit all reachable positions for the game to be strongly solved. In this study, we propose a class called ‘ semi-strongly solved ,’ where the game-theoretic value can be determined for all reachable board positions, assuming that at least one of the two players is AI. This class guarantees that the AI gameplay will appear perfect from the human opponent’s perspective. Furthermore, the proposed method can significantly reduce the computational cost of solving the game compared to strong solving by not providing guarantees for board positions that can only be reached if both human players make a mistake during play. To the best of our knowledge, this proposal is novel in this research. Furthermore, in this study, we propose the ‘reopening alpha-beta’ algorithm as a pruning method to achieve semi-strong solving efficiently. Under simple assumptions about the nature of the game, we derive that the computational complexity of the proposed algorithm is O(db^{\frac{d}{2}}) , where d is the depth of game-tree and b is branching factor (number of legal moves). To demonstrate the usefulness of the proposed method, we semi-strongly solved the game of 6x6 Othello. We showed that semi-strong solving requires considering far fewer positions than strong solving and, therefore, can be computed at a significantly lower cost. The programs for reproducing the experiments is available on GitHub (https://github.com/eukaryo/reopening-alphabeta-experiment ). 2 Methods 2.1 Definition of Semi-Strongly Solved The definition of ‘semi-strongly solved’ is that all of the following conditions are satisfied: 1. Assume that at least one of the players is an AI, which always makes the best move. 2. Assume that at most one of the players is a human who may make any possible move. 3. Under the above assumptions, the game-theoretic values are determined for all positions that are reachable for AI or humans under reasonable resources. In this context, "game-theoretic values are determined" ideally means that game-theoretic values of all non-trivial positions are stored, and they can be obtained simply by calculating the storage address from the position information and reading it. Under these conditions, the corresponding optimal move can always be found through a depth-one mini-max search. In practice, there are games like Othello where, despite many endgame positions, the number of moves remains until the end is fixed, and the endgame search always completes quickly. For such games, it is reasonable to adopt a method that does not store game-theoretic values of endgames but computes them as needed. 2.2 Reopening Alpha-Beta Algorithm Below, we described the proposed algorithm to achieve semi-strong solving. The algorithm is called the ‘reopening alpha-beta’ algorithm. The notation is as follows: Let D be the depth of the game tree. The initial position is at depth D=1 , and positions where d=D are terminal nodes. Any position with d<D is an internal node of the game tree, and we assume that the branching factor (i.e., the number of legal moves) is always b (where b\geq 2 ). Additionally, for simplicity, we assume there are no transpositions (i.e., reaching the same board position via different sequences of moves) or repetitions (i.e., returning to a previous board position via some sequence of moves). We assume that move-ordering is optimal. We also assume that any two distinct terminal positions have different game-theoretic values. 2.2.1 Kinds and Generation Rules of Nodes The types of search nodes in the reopening alpha-beta algorithm and their generation rules are described below. The first child is always the best move based on the assumption that move-ordering is optimal. 1. P-node: The initial position is a P-node. The first child of a