An algorithm based on valuation forecasting for game tree search
- PDF / 1,475,858 Bytes
- 13 Pages / 595.276 x 790.866 pts Page_size
- 38 Downloads / 257 Views
ORIGINAL ARTICLE
An algorithm based on valuation forecasting for game tree search Guangyun Tan1,2 · Peipei Wei2 · Yongyi He1 · Huahu Xu3 · Xinxin Shi2 · Ping Yi2 Received: 12 March 2019 / Accepted: 10 October 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract This study proposes a novel best-first search algorithm, called Valuation Increment Search Algorithm (VIS), which applies the increment of exploratory value change to predict the valuation and guide the selection of the game tree. The proposed method can effectively use node valuation and game tree size information to solve the game tree by fewer exploration steps. The relevant assumptions and search principles of the proposed algorithm are detailed. Moreover, comparative experiments with Alpha–Beta Search (α–β search), Proof-Number Search (PNS) and Monte-Carlo Tree Search (MCTS) in the domain of Dou Dizhu has been performed to verify the performance. Result demonstrate that VIS is superior to α–β search, PNS and MCTS algorithm in solving the game tree and finding the best move for some game scenarios by consuming less time and few memory resources. The improvement effect of the average Increment, magnitude of Increment, and the number of visits to node on the original VIS was validated. Also, a new selection strategy is defined for the improved VIS algorithm combined with these factors. The experimental comparison results show that improved VIS has a better performance in solving game tree with less nodes generated and expanded than original VIS. Keywords Tree search algorithm · Best-first · Dou Dizhu · Artificial intelligence
1 Introduction As a touchstone to test the development level of artificial intelligence (AI), computer games has become a popular search field, in which the developed algorithms can be used to solve more complicated problems in real world [10, 34]. Search, as key technology, is often regarded as the core of AI, and plays a fundamental role in the problem-solving of AI [17, 19, 29]. Search algorithm is also the critical factor to determine the performance and efficiency of game system [22] and other application systems [1, 11, 21]. The search theory of the two-person zero-sum games has been developing for a long time. The Minimax algorithm [18, 26] is defined as the most fundamental and * Peipei Wei [email protected] 1
School of Mechatronic Engineering and Automation, Shanghai University, Shanghai, China
2
Shanghai Qiansi Network Technology Limited Liability Company, 800 Naxian Road, Pudong New District, Shanghai 201210, China
3
School of Computer Engineering and Science, Shanghai University, Shanghai, China
typical exhaustive search method, and it lays a theoretical foundation for computer game. It can find the optimal solution for both players of the game. However, the Minimax algorithm needs to visit all the nodes of the complete game tree, which consume a lot of time and memory resources. Alpha–Beta (α–β) pruning can effectively avoid meaningless search and increase the depth of search [3, 16,
Data Loading...
