博弈树启发搜索算法在五子棋游戏中的应用研究

博弈是启发式搜索的一个重要应用领域,博弈的过程可以用一棵博弈搜索树表示,通过对博弈树进行搜索求取问题的解,搜索策略常采用α-β剪枝技术。在深入研究α-β剪枝技术的基础上,结合五子棋游戏特征,设计了五成/双三、估值函数和α-β剪枝算法相结合的改进博弈树搜索算法,实现了人机智能对弈的五子棋游戏。

Research on the Application of Game-tree Search Algorithm in the Backgammon Game

Game is an important application field of heuristic search,and the game process can be expressed by a game search tree.The solution of the problem can be found through searching the game tree,and α-β pruning technique is often used in the searching strategy.Based on in-depth study on α-β pruning technique and connecting with the features of backgammon game,this paper designs the improved game-tree search algorithm that combines five even/double three,the valuation function and α-β pruning algorithm,and achieves a human-machine intelligent chess game of backgammon.