An Adversarial Search Method Based on an Iterative Optimal Strategy

Mathematics

Junming Yan¹  Qiang Zhang²  Xiaopeng Wei²  Yuanye Ma²  Tianhao Zhao²  Chanjuan Liu² 

[1] CNGC North Automatic Control Technology Institute, Taiyuan 030000, China;School of Computer Science and Technology, Dalian University of Technology, Dalian 116024, China;

关键词: minimax;    zero-sum games;    game tree pathology;   

DOI  :  10.3390/math8091623

来源: DOAJ

【 摘 要 】

A deeper game-tree search can yield a higher decision quality in a heuristic minimax algorithm. However, exceptions can occur as a result of pathological nodes, which are considered to exist in all game trees and can cause a deeper game-tree search, resulting in worse play. To reduce the impact of pathological nodes on the search quality, we propose an iterative optimal minimax (IOM) algorithm by optimizing the backup rule of the classic minimax algorithm. The main idea is that calculating the state values of the intermediate nodes involves not only the static evaluation function involved but also a search into the future, where the latter is given a higher weight. We experimentally demonstrated that the proposed IOM algorithm improved game-playing performance compared to the existing algorithms.

【 授权许可】

Unknown