基于Alpha-beta剪枝树的揭棋算法的设计与实现

Design and Implementation of Revealed Chess Algorithm Based on Alpha-beta Pruning Tree

揭棋是中国象棋的一个变种玩法,相较于中国象棋策略、收益皆透明的模式,揭棋无法确定收益和后续策略,属于非完全信息博弈,需要开发新的算法才能实现揭棋人机对弈。文章设计并实现了基于Alpha-beta剪枝技术辅以启发式搜索的揭棋程序,通过创造极大层与极小层之间的暗子扩张层构建出适合揭棋使用的博弈树结构,基于中国象棋的分值评价标准设计了适用于揭棋的评分体系,解决了对暗子的评分与深层搜索问题,实现了对揭棋状态复杂度与揭棋算法的初步探索。

Revealed chess is a Chinese chess variant,and compared with the pattern of Chinese chess,where strategies and profits are transparent,revealed chess cannot determine profits and subsequent strategies,and belongs to incomplete information game,which requires the development of a new algorithm to enable a revealed chess man-machine game.This paper designs and implements a revealed chess program based on Alpha-beta pruning technology supplemented by heuristic searching to construct a game tree structure suitable for revealed chess by creating a dark matter expansion layer between the maximal layer and the minimal layer.And it designs a scoring system suitable for revealed chess based on the scoring standard of Chinese chess,which solves the problems of scoring dark matter and deep search,and realizes the initial exploration of the complexity of revealed chess state and revealed chess algorithm.