【文件属性】:
文件名称:选择性裁剪-it安全隐患排查系统
文件大小:3.75MB
文件格式:PDF
更新时间:2021-06-18 06:54:19
博弈 搜索算法 博弈树
稳定或容易产生分值起伏的着法进行延伸。
5.1 选择性裁剪
选择性裁剪是指不会影响结果正确性的剪枝。在实
际应用中主要包括:(1)重复裁剪,主要指如果当前路径
上出现重复局面就不再搜索下去;(2)和棋裁剪,主要指
如果双方都没有明显可以杀死对方的子力就不再搜索下
去并返回和棋分值;(3)如4.3 节所述的置换裁剪。
5.2 选择性延伸
一般来说,考虑的深度越深,犯错误的概率就越
小。所以可以考虑选择性延伸,有选择地增加感兴趣
节点的搜索深度,提高该节点评价的准确度。当然,
不能过度地对节点进行延伸,因为这样往往会造成搜
索树过于庞大,以至于降低了搜索的效率。
选择性延伸通常运用在强制着法上,强制着法的界
定在各个程序中有所不同,但主要有以下几种判断方法:
(1)将军,此时必须应将,属于强制着法;(2)单一着法,
走子的一方只有一种合理着法时,属于强制着法;(3)杀
棋威胁,当一方不走子时就会被对方在几步内杀掉,那
么解除杀棋威胁也属于强制着法,这种判断比较困难,
通常利用下面所介绍的“空着搜索”来做判断。(4)兑子
着法,大多数情况下将兑子着法也判断为强制着法。
一般极大极小方法用固定的深度进行搜索,每一
步棋都搜索到一个固定的深度,这个深度被称为“水
平线”。对于水平线以内发生的威胁,这个方法非常有
效,但是它不能检查到水平线以后的威胁,这样就产
生了水平线效应[11]。为了尽量减少水平线效应,我们
还要在叶节点的局面变化剧烈时,继续向下搜索一直
到局面相对平静为止(在中国象棋中,一般把由吃子走
法所产生的局面和将军的局面看成是变化剧烈的,其
余的局面则认为是相对静止的),这样可以对一些比较
混乱的局面做更精确的估计。这种延伸称为静止期搜
索(quiescence search)。
在中国象棋程序中使用的延伸主要包括:将军延
伸,兑子延伸。对于被将军的节点,一般将其搜索深
度增加 1 层,这是因为一方面将军延伸能比较显著的
提升棋力,另一方面可以解将的着法并不多;对于发
生兑子的节点,一般将其搜索深度增加 3/4 或 2/3,
这样的话我们可以接收小于 1 层的增量,当这些小于
1 层的增量累积起来,超过层数的整数表示值,便可
进行额外的延伸,这样的做法是因为一方面吃子延伸
在提升棋力方面不如将军延伸重要,另一方面吃子延
伸会比较明显的降低搜索速度,况且,静止期搜索已
经隐含了对叶子节点的吃子延伸。
5.3 空着裁剪
空着裁剪(Null-Move Pruning)[12]基于这样的思
路:如果本方不走棋,而让对方连续走棋时,在减少
深度的浅层搜索下也能使分值超过β的话,则进行剪
枝。空着搜索实现较为简单且对速度的提升十分明显,
现己被几乎所有博弈程序(除一些空着搜索没有意义
的棋类)所采用。
空着裁剪的思想也是在适当时机调整搜索层数,但
是它是通过相反的方式来表现的,即不是在复杂的局面
上做延伸,而是在简单的局面上使用减少深度的搜索。