中国象棋机器博弈系统中哈希技术的应用探讨
发布时间：2014-09-16 16:00
【摘要】 论述了哈希技术在中国象棋人机博弈系统的搜索引擎和开局库中的应用以及实现原理,论证了基于哈希技术的编码方式的开局库的优越性,对基于哈希技术的置换表算法分析了使用单一的置换表所存在的缺陷,并通过数据证明了一种双置换表的优越性,使置换表这一启发式搜索算法在搜索引擎中的作用更加合理。
【关键词】 博弈树； 置换表； 搜索引擎； 开局库；
引言
在中国象棋的人机博弈的研究中，局面搜索算法是核心，中国象棋的博弈过程中，针对某一局面，平均着法达到60步，故减少搜索的节点，提高搜索的速度和节省搜索过程中内存开销，就成了中国象棋搜索研究一个终极目标。Alpha-Beta搜索算法是人机博弈的一个基本算法，但是该算法在搜索过程中，存在大量的冗余[1]。本文即在这一基本算法的基础上，加入置换表技术和Hash table技术，以提高搜索速度。
1 Alpha-Beta搜索算法
如图1所示，结点下面的数字为该节点所代表的局面评估值。在左图中，节点B的值为18，节点D的值为16，因为C节点要取其子节点的最小值，故可以判定节点C的值将小于或者等16，而A节点的值为B节点和C节点的最大值，这样无论E节点和F节点的值为多少，都不影响A节点的取值，因为A节点此时肯定会取B节点的值18本文由笔耕文化传播http://www.bigengculture.com/收集整理，这样将节点D的后继节点减去称Alpha剪枝。观察图1的右半部的极大极小树，A节点要取B节点和C节点的最小值，C节点要取其子结点的最大值，而D节点的值为18，故C节点的值最小为18，这个值已经大于B节点的值了，所以无论E节点和F节点的值为多少，都不影响A了点的取值，所以将节点D的后继节点减去称Beta剪枝。
原始的Alpha-Beta搜索算法略显繁琐，需要在奇数层进行Alpha剪枝，在偶数层进行Beta剪枝，利用负极大值搜索的思想，可以统一在任何一层进行Beta剪枝。
2 置换表的思想
Alpha-Beta 搜索算法的剪枝过程对搜索节点的排序顺序依赖很大，当搜索顺序的排列为最差情况时，其搜索效果与极大极小值相同[2]。其实在搜索的过程中，随着搜索层次的加深，会出现一些节点是原来搜索过的，如果能直接利用已经搜索过的节点局面评估值，而不重新搜索一次，这样相同于进行了很大程度的剪枝[3]。我们可以利用一个数组将已经搜索过和节点保存起来，在搜索新的节点时，先到数组中检查以前是否已经搜索过本节点，如果是，则直接用数组里保存的局面评估值，如果没有，则继续正常搜索，这就是置换表（Transposition Table）的思想。
3 哈希表来实现置换表搜索
因为在搜索的过程中，节点数量非常大，如果将每一个节点都与数组中的元素一一对应，内存开销太大，不可能实现。为了解决这一问题，可以利用哈希表技术。每一个搜索节点对应哈希表中一个节点，但是反过来，哈希表中的一个节点并不一定只对应一个搜索节点，这就是哈希冲突，在同一次搜索过程中，哈希冲空的可能性并不高，在实际的应用中这是一个可靠的办法。根据中国象棋搜索的特点，定义如下哈希数组。
对要搜索的每一节点，计算出它的一个哈希值（hashIndex，通常是一个32位数对哈希表大小取模）以确定此局面在哈希表中的位置。计算另一个哈希值checksum，来检验表中的数据项是否是所要的那一项。64位的哈希值checksum发生冲突的几率很小，几乎可以将其冲突忽略。即使因为哈希冲突导致没有获得原来搜索过的节点，也不会影响博弈系统的运行，因为还可以采用基础的alpha-beta算法进行搜索。
在对某一局面搜索之前，先查看哈希表项hashTable[hashIndex]， 如果hashTable[hashIndex].checksum == Checksum，并且hashTable[hashIndex].depth大于或者等于最大搜索深度减去当前层数，就返回hashTable[hashIndex].eval作为当前局面的估值。当对一个局面搜索完成后，将Checksum、当前层数和估值结果保存到hashTable[hashIndex]当中，以备后面的搜索使用。置换表与alpha-beta搜索协同工作的实现机制如下面的类C语言伪代码所示。
4 实验
基于以上核心算法，利用JAVA语言设计了一个实用系统。中国象棋的棋盘用一个10行9列的二维数组与之对应，而各棋子用对应的数字表示。棋局评估主要从剩余棋子基本值、棋子灵活性、棋子受攻击度、棋子受保护度，棋子位置附加值这几个方面来衡量。分别计算这几种类型的值，然后将它们的和作为棋局的优劣值，供搜索引擎使用。实验主要是比较alpha-beta+置换表算法与基本的alpha-beta算法在不同的搜索层次上搜索结点的个数，通过实验可知从第3层开始，alpha-beta+置换表评估的节点数目要少于alpha-beta搜索在同样深度搜索中评估的节点数。而且随着搜索的最大深度的增加，置换表的命中率也不断提高，表明重复的节点所点的比例随深度增加而增加。这表明alpha-beta+置换表评估的节点数同alpha-beta搜索评估的节点数相比的比例越来越低。由于置换表的操作对每一节点都要花费一定的时间，所以在较浅的搜索当中（例如3层），由于命中率较低，虽然alpha-beta+置换表评估的节点数比alpha-beta搜索少，但花费的时间仍多于alpha-beta搜索。但随着搜索深度的增加，alpha-beta+置换表开始显露出时间上的优势。当搜索的最大深度为5时，alpha-beta+置换表的搜索速度达到alpha-beta的2倍以上。
参考资料：
本文编号：9009
【关键词】 博弈树； 置换表； 搜索引擎； 开局库；
引言
在中国象棋的人机博弈的研究中，局面搜索算法是核心，中国象棋的博弈过程中，针对某一局面，平均着法达到60步，故减少搜索的节点，提高搜索的速度和节省搜索过程中内存开销，就成了中国象棋搜索研究一个终极目标。Alpha-Beta搜索算法是人机博弈的一个基本算法，但是该算法在搜索过程中，存在大量的冗余[1]。本文即在这一基本算法的基础上，加入置换表技术和Hash table技术，以提高搜索速度。
1 Alpha-Beta搜索算法
如图1所示，结点下面的数字为该节点所代表的局面评估值。在左图中，节点B的值为18，节点D的值为16，因为C节点要取其子节点的最小值，故可以判定节点C的值将小于或者等16，而A节点的值为B节点和C节点的最大值，这样无论E节点和F节点的值为多少，都不影响A节点的取值，因为A节点此时肯定会取B节点的值18本文由笔耕文化传播http://www.bigengculture.com/收集整理，这样将节点D的后继节点减去称Alpha剪枝。观察图1的右半部的极大极小树，A节点要取B节点和C节点的最小值，C节点要取其子结点的最大值，而D节点的值为18，故C节点的值最小为18，这个值已经大于B节点的值了，所以无论E节点和F节点的值为多少，都不影响A了点的取值，所以将节点D的后继节点减去称Beta剪枝。
原始的Alpha-Beta搜索算法略显繁琐，需要在奇数层进行Alpha剪枝，在偶数层进行Beta剪枝，利用负极大值搜索的思想，可以统一在任何一层进行Beta剪枝。
2 置换表的思想
Alpha-Beta 搜索算法的剪枝过程对搜索节点的排序顺序依赖很大，当搜索顺序的排列为最差情况时，其搜索效果与极大极小值相同[2]。其实在搜索的过程中，随着搜索层次的加深，会出现一些节点是原来搜索过的，如果能直接利用已经搜索过的节点局面评估值，而不重新搜索一次，这样相同于进行了很大程度的剪枝[3]。我们可以利用一个数组将已经搜索过和节点保存起来，在搜索新的节点时，先到数组中检查以前是否已经搜索过本节点，如果是，则直接用数组里保存的局面评估值，如果没有，则继续正常搜索，这就是置换表（Transposition Table）的思想。
3 哈希表来实现置换表搜索
因为在搜索的过程中，节点数量非常大，如果将每一个节点都与数组中的元素一一对应，内存开销太大，不可能实现。为了解决这一问题，可以利用哈希表技术。每一个搜索节点对应哈希表中一个节点，但是反过来，哈希表中的一个节点并不一定只对应一个搜索节点，这就是哈希冲突，在同一次搜索过程中，哈希冲空的可能性并不高，在实际的应用中这是一个可靠的办法。根据中国象棋搜索的特点，定义如下哈希数组。
对要搜索的每一节点，计算出它的一个哈希值（hashIndex，通常是一个32位数对哈希表大小取模）以确定此局面在哈希表中的位置。计算另一个哈希值checksum，来检验表中的数据项是否是所要的那一项。64位的哈希值checksum发生冲突的几率很小，几乎可以将其冲突忽略。即使因为哈希冲突导致没有获得原来搜索过的节点，也不会影响博弈系统的运行，因为还可以采用基础的alpha-beta算法进行搜索。
在对某一局面搜索之前，先查看哈希表项hashTable[hashIndex]， 如果hashTable[hashIndex].checksum == Checksum，并且hashTable[hashIndex].depth大于或者等于最大搜索深度减去当前层数，就返回hashTable[hashIndex].eval作为当前局面的估值。当对一个局面搜索完成后，将Checksum、当前层数和估值结果保存到hashTable[hashIndex]当中，以备后面的搜索使用。置换表与alpha-beta搜索协同工作的实现机制如下面的类C语言伪代码所示。
4 实验
基于以上核心算法，利用JAVA语言设计了一个实用系统。中国象棋的棋盘用一个10行9列的二维数组与之对应，而各棋子用对应的数字表示。棋局评估主要从剩余棋子基本值、棋子灵活性、棋子受攻击度、棋子受保护度，棋子位置附加值这几个方面来衡量。分别计算这几种类型的值，然后将它们的和作为棋局的优劣值，供搜索引擎使用。实验主要是比较alpha-beta+置换表算法与基本的alpha-beta算法在不同的搜索层次上搜索结点的个数，通过实验可知从第3层开始，alpha-beta+置换表评估的节点数目要少于alpha-beta搜索在同样深度搜索中评估的节点数。而且随着搜索的最大深度的增加，置换表的命中率也不断提高，表明重复的节点所点的比例随深度增加而增加。这表明alpha-beta+置换表评估的节点数同alpha-beta搜索评估的节点数相比的比例越来越低。由于置换表的操作对每一节点都要花费一定的时间，所以在较浅的搜索当中（例如3层），由于命中率较低，虽然alpha-beta+置换表评估的节点数比alpha-beta搜索少，但花费的时间仍多于alpha-beta搜索。但随着搜索深度的增加，alpha-beta+置换表开始显露出时间上的优势。当搜索的最大深度为5时，alpha-beta+置换表的搜索速度达到alpha-beta的2倍以上。
参考资料：
- [1] 岳金朋,冯速. 博弈树搜索算法在中国象棋中的应用[J]. 计算机系统应用. 2009(09)
- [2] 舒康元,胡福乔. 中国象棋计算机博弈引擎改进[J]. 微计算机信息. 2009(29)
- [3] 鲍鹏,高珩,王伟. 中国象棋的编程设计[J]. 电脑学习. 2009(05)
- [4] 邹竞. 基于MTD(f)的中国象棋人机博弈算法的设计与优化[J]. 计算机与数字工程. 2008(09)
- [5] 魏钦刚,王骄,徐心和,南晓斐. 中国象棋计算机博弈开局库研究与设计[J]. 智能系统学报. 2007(01)
本文编号：9009
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/9009.html
