基于Alpha-Beta剪枝的局面搜索方法

1 Alpha-Beta剪枝算法

在计算机博弈中，需要对当前、未来的博弈局面进行合适的表达和判断。通过探索可能局面，来寻找合适的博弈着法。但是，久棋规则独特且复杂，导致其搜索空间巨大，比如在布局阶段，久棋博弈树的搜索深度就可以高达196步。因此，在比赛规定的有限时间内，想要遍历久棋博弈树的所有分枝，基本上是不可能完成的事情。故需要选择一定的方法，来帮助计算机尽可能“遍历”博弈树。

极大极小值算法是计算机博弈中传统的构建博弈树的方法 [1]。但是使用此算法的前提是必须完整列举出博弈流程中所有可能出现的博弈局面，这样一来，必然需要耗费大量的算力，必然无法胜任构建久棋博弈树的任务。

Alpha - Beta剪枝算法，是对极大极小值算法的一种优化和改进。相对于极大极小值算法，使用Alpha-Beta剪枝算法构建博弈树时，对于最深层的节点，有时是不需要全部构建出来的，因为当算法发现当前局面下无法找到最好的解就会停止这个节点以及其子节点的搜索，即剪枝。

2 Alpha-Beat剪枝的优化方法

2.1开局库的应用

在棋类博弈中，一个好的开局往往是赢棋的关键因素。大多时候，因计算机没办法识别基于人类经验的开局着法，从而导致落入“陷阱”。故需要一种方法在开局阶段对计算机的走子进行指导，这就是开局库，开局库是计算机博弈中知识库的一种具体形式。开局库存储了大量人类经验走法和经典布局[11]。开局时，将从图1中博弈树根节点展开，搜索开局库，如果开局库找到匹配的，就选择开局库中对应着法。这样，既可避免着法失误带来被动，又可加快搜索速度、提高博弈效率。

在久棋规则中，有“成方吃子”金条，即四子成方，指将四枚棋子走至一个棋格四角就可吃掉对方的任意一枚棋子，这是非常大的对弈“权利”，常常在对弈中能够起到力挽狂澜之效，因此，在久棋中常常围绕此条规则，想法用最少的棋子，构造出一些具有特殊权利的棋形，以增加赢得能力。比如图3单棋门棋形A，若能及时补齐相应位置棋子而同时形成两个“方”，那么黑方就拥有吃掉白方任意两枚棋子的特权。再如，双棋门棋形B，如果白方能及时成方，也能拥有明显的赢棋能力。这些棋形都是久棋计算机博弈知识库的重要棋形。

通过大量研究，作者发现在久棋中存在一些布局能快速“成方吃子”，甚至在行棋阶段提子后，仅需一步，便能成方。比如，在行棋开始阶段，会直接提掉A、B上的两个棋子，A、B这两个位置就空出来了，C棋子可以直接向上移动一步，直接成方。此外，

另外一种情况，在提掉A、B点的棋子后，C棋子可以向上一步跳吃，吃掉D棋子成方。由于棋盘是对称的，上述两种情形经过对称、旋转后，统计共有16种相应棋形案例。

完成上述布局后，通常至少需要十步。而教会计算机完成这样的布局，可以依靠传统的开局库方法，通过建立的数据库、哈希表等方式，先初始化并存储，并在行棋进程中，采用动态规划算法计算行棋位置，再结合Alpha-Beta剪枝技术，能提前4-6步预测并指导早期布局，从而提升开局久棋计算机博弈软件的棋力。

2.2置换表启发

多数博弈树搜索算法都不能仅仅依靠一次搜索，就达到目标。但是，如果每次都重复前次搜索，其效率将极其低下，因此，如果对重复搜索同一棵博弈树时，能利用以前的搜索结构，无疑将极大提高搜索效率。这就是置换表启发搜索技术的作用之一。

置换表是基于空间换取时间的思想，用表格将之前搜索过的信息保存下来[2]，在表中每项对应于博弈树一个节点以及该节点估值等。在搜索时，把已搜索过的节点相关信息记录下来，如果和置换表中有待搜索的节点的局面特征相匹配的话，就直接提取置换表对应结果，而不需再继续搜索。

但是，仅仅利用置换表，获得的搜索效率仍然有限，此时如与Alpha-Beta剪枝方法相结合，其搜索效率将显著提高。剪枝效率与子树节点搜索先后顺序存在密切关系，越早发现最优节点，剪枝就越多，进而节省大量搜索时间。Alpha-Beta搜索过程中，任意节点将出现三种情况：

（1）节点评估值≥beta。

（2）节点评估值≤alpha。

（3）alpha≤节点评估值≤beta。

置换表不仅可以保留搜索记录，同时还可以结合Alpha-Beta剪枝算法，改变其子树节点搜索顺序，从而达到加速剪枝的效果。搜索过程中。搜索中出现情况（3）时，可将当前节点的评估值存入置换表中，以备后续查询。尽管博弈空间巨大，搜索节点多，在置换表中直接找到相对应情况的可能性小，但是，情况（1）和情况（2）所对应的边界值却可以作为改变子树节点搜索顺序的参考值，从而尽早发现最优子节点，实现剪枝。

然而，置换表以哈希表作为基本数据结构，还存在一个重要问题：就是在数据量特别大时，如何处理哈希表中地址冲突问题。对这个问题，常用方法就是基于Zobrist 键值的哈希方法。久棋棋盘的14ⅹ14网格，共有196格，使用Zobrist方法可构造32位哈希值，使用Zobrist[2][N][N]数组保存32位随机数，Zobrist[0][N][N]表示黑子棋盘，Zobrist[1][N][N]表示白子棋盘，例如当棋盘上（2，2）和（3，3）上分别有黑子和白子时，棋盘的哈希值就如（1）式：

如果（3，3）黑子被吃掉，再异或计算即可，如（2）式：

另外，可增加一个32位的blackZobrist常量来区分先后手。若是黑子落子，计算完哈希值后异或上blackZobrist，如（3）式：

通过上述方式，就使得创建关键字的地址冲突概率极低。

参考文献

[1]汪坤兵. 六子棋博弈中搜索技术的研究与实现[D].安徽大学，2016.

[2] 焦尚彬，刘丁.博弈树置换表启发式算法研究[J]. 计算机工程与应用，2010，46（06）：42-45.

[3]王昕杨. 藏式围棋博弈软件及其教育应用技术研究[D].中央民族大学，2016.

作者简介：彭丽蓉，女，副教授，主要从事计算机应用方面的研究。