关键词: 博弈树, 极小树, 空窗探测, 迭代深化, 广度优先, 五子棋

Abstract:

A new search method was given for a game-tree with breadth-firstin the first layer nodes and continuously minimal window test by deep analysis on game-tree search algorithms. It was good for the application and the processof search was easier for control, and may build a smaller search tree than the minimalgame-tree in theory. Comparison experiments indicate that the efficiency of thistechnique outperforms the PVS and MTD(f) method. Another speriority is tooptimize a game-tree by an iterative-deepening search, and to make the overall efficiency of iterative-deepening exceed a one-off game tree search.

Key words: game-tree;  minimal tree; null window search; iterative-deepening search; breadth-first; gobang