文件名称：选择性裁剪-it安全隐患排查系统
文件大小：3.75MB
文件格式：PDF
更新时间：2024-07-08 00:40:59
博弈 搜索算法 博弈树
稳定或容易产生分值起伏的着法进行延伸。 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]基于这样的思 路：如果本方不走棋，而让对方连续走棋时，在减少 深度的浅层搜索下也能使分值超过β的话，则进行剪 枝。空着搜索实现较为简单且对速度的提升十分明显， 现己被几乎所有博弈程序(除一些空着搜索没有意义 的棋类)所采用。 空着裁剪的思想也是在适当时机调整搜索层数，但 是它是通过相反的方式来表现的，即不是在复杂的局面 上做延伸，而是在简单的局面上使用减少深度的搜索。