Research On Strategy Search Algorithm In Two-player Zero-sum Games

Two-player zero-sum game problem is an important research direction of machine game,and its research content involves knowledge representation,game tree search algorithm,situation state evaluation function and so on.Among them,how to formulate efficient and accurate game tree search algorithm is the key technology to improve the quality of intelligent agents' decision-making in zero-sum game problems.As the most commonly used game tree search algorithm,minimax algorithm can theoretically search for the optimal solution of zero-sum game with complete information when the computing power is high enough to search the whole game tree.Due to the limited computing power,the minimax algorithm with heuristic evaluation function is usually used in practical applications.The existence of heuristic evaluation function inevitably leads to evaluation error.Some scholars have questioned the search quality of minimax algorithm with heuristic evaluation error.It has been found that for some types of game trees,a deeper minimax search can actually reduce the quality of the decision.They called this phenomenon "game tree pathology".Because most real game problems are not pathological on the whole,the research on minimax algorithm is still focused on improving the search depth by improving the search efficiency.However,pathological nodes are considered to exist in all game trees and affect the search quality of heuristic minimax algorithms.In this paper,by analyzing the pathological phenomenon of game tree and the reason of search deviation of minimax algorithm,a search algorithm after optimizing the backup rules of classical minimax algorithm was proposed and named as iterative optimum minimax algorithm(IOM).Experiments in artificial simulated game trees and real game problems show that the IOM has obvious advantages over the minimax algorithm in shallow search.When the search depth is deeper,the search results of the two algorithms tend to be similar.This search algorithm is more robust and provides a solution to the problem of large deviation of search results in shallow search by minimax algorithm.At the same time,the IOM is compared with the error minimax algorithm(EMM).The EMM is a search algorithm based on the idea of pre-distinguishing node types in order to reduce the influence of pathological nodes on search quality.But the error minimization algorithm is difficult to set the heuristic function error level and reduce the algorithmcomplexity.In order to reflect the advantage of IOM in complexity,this paper also proposes an alpha-beta pruning strategy for iterative optimum minimax algorithm.Finally,the comparison experiment in real game shows that the IOM also has higher decision quality.