搜索,游戏和解决问题:与对手的比赛

点击打开微信,办理ETC

两个玩家的游戏,例如国际象棋,西洋棋棋子,奥赛罗和围棋,都是确定性的,因为每个动作(一个动作)都会在同一个父状态下产生相同的子状态。相反,步步高是非确定性的,因为它的子状态取决于它

关于掷骰子的结果。这些游戏都是可观察的,因为每个玩家总是知道完整的游戏状态。例如扑克等许多纸牌游戏只能部分观察,因为玩家不知道其他玩家的牌,或者只是对他们有部分了解。

本章到目前为止讨论的问题具有确定性和可观察性。在下文中,我们将研究那些确定性和可观察性的游戏。此外,我们将自己限制为零和游戏。这些游戏中,每个玩家获得的每一个获得意味着对手失去相同的价值。增益和损失之和总是等于零。上面提到的游戏国际象棋,西洋棋棋子,奥赛罗和围棋也是如此。

 

1.     Minimax搜索

每个球员的目标是做出最佳的动作,从而获得胜利。原则上,可以构建一个搜索树并完全搜索它(就像使用8-puzzle一样)进行一系列将导致胜利的动作。但是,有几个特点值得注意:

1. 国际象棋中的有效分支因子大约是3035.在每个玩家50次移动的典型游戏中,搜索树有超过30 100 10 148叶子节点。因此,没有机会完全探索搜索树。此外,国际象棋通常会有时间限制。由于这种实时要求,搜索必须限制在树中适当的深度,例如八个半移动。由于在这个深度限制树的叶节点中,通常没有解决节点(即终止游戏的节点)启发式评估函数B用于董事会职位。该计划的游戏水平在很大程度上取决于该评估功能的质量。因此,我们将在Sect中进一步对待这一主题。6.5

2. 在下面我们将调用我们希望优化Max和他的对手Min的游戏。对手的(Min)的移动事先不知道,因此实际的搜索树也不是。通过假设对手总能做出最佳动作,可以优雅地解决这个问题。较高的评价BS的位置小号,更好的位置小号是玩家最大和更糟糕的是他的对手民。Max试图最大限度地评估他的动作,而Min做出的动作导致评估尽可能低。

104 页的图 6.18 给出了一个具有四个半移动和所有叶片评估的搜索树。内部节点的评估作为其子节点的最大值或最小值递归导出,具体取决于节点的级别。

 

2.     α-β修剪

通过在最大化和最小化之间切换,我们可以在某些情况下为自己节省大量工作。Alpha-beta修剪与深度优先搜索一起使用,达到预设的深度限制。以这种方式,从左侧搜索搜索树

 

图片

图片

图片

图片

图片

图片

图片

图片

6.18 一个minimax游戏树,具有四个半移动的前瞻性

 

图片

图片

图片

图片

6.19 一个alpha-beta游戏树,具有四个半移动的前瞻性。不遍历树的虚线部分,因为它们对最终结果没有影响

 

对。与极小极大搜索一样,在最小节点中,最小值是从后继节点的最小值生成的,而最大节点中也是最大值。在图6.19中,该过程描绘了图6.18 中的树。在标记为a的节点处,在将第一个子项评估为值1之后,可以忽略所有其他后继者,因为最小值肯定为1.它甚至可能变得更小,但这是无关紧要的,因为最大值已经是3个等级以上。无论剩下的后继者的评估结果如何,最大值将保持值3.类似地,树将在节点b处被修剪。自从b的第一个孩子值为2,为b生成的最小值只能小于或等于2.但根节点的最大值已经确定为3.这不能通过值2更改。因此剩余的子树为b可以修剪。

相同的推理适用于节点c。但是,相关的最大节点不是直接父节点,而是根节点。这可以概括。

在每个叶节点处,计算评估。

对于每个最大节点,当前最大子值保存在α。对于每个最小节点,当前最小子值保存在β

§                          

如果在最小节点k处当前值βα,则k下的搜索可以结束。这里α是从根到k的路径中最大节点的最大值。

§                          

如果在最大节点l处当前值αβ,则在l下的搜索可以结束。这里β是从根到l的路径中最小节点的最小值。

 

 

LPHAETA中号AX(节点αβ

如果DepthLimitReachedNode返回(评级(节点))NewNodes =后继者(节点)

 

α =最大值(αA LPHA B ETA M IN(第一(NewNodes),αβ))

 

NewNodes = RestNewNodes)返回(α

 

LPHAETA中号IN(节点αβ

如果DepthLimitReachedNode返回(评级(节点))NewNodes =后继者(节点)

 

β =最小值( βA LPHA B ETA M AX(第一个(新节点), αβ))

 

NewNodes = RestNewNodes)返回(β

 

 

图片

图片

如果 β α 收益 α

NewNodes =

如果 α β 返回 β

NewNodes =

6.20具有两个函数A
LPHA
B
ETA
M
IN
A L alpha-beta搜索算法

PHA B ETA M AX

 

6.20中给出的算法是深度优先搜索的扩展,具有两个交替调用的函数。它使用上面定义的αβ

 

复杂性 alpha-beta修剪节省的计算时间在很大程度上取决于子节点遍历的顺序。在最坏的情况下,alpha-beta修剪不提供任何优势。对于恒定的分支因子b,在深度d处评估的叶节点的数量nd等于

 

nd = bd

在最好的情况下,当被递减排序的最大的节点的后继者,且m的继任 MUM节点递增排序,有效科顺

因子减少到b。在国际象棋中,这意味着大幅度降低效果

分支因子从35到约6.然后只有

图片

ND = b d = BD / 2

将创建叶节点。这意味着深度限制以及搜索范围都会被alpha-beta修剪加倍。但是,这仅适用于最佳排序的后继者,因为子节点的评级在创建它们时是未知的。如果子节点随机排序,然后将支化因子降低至b 3 / 4和叶节点与数

3 d

图片

nd
= b 4

例如,使用相同的计算能力,使用alpha-beta修剪的国际象棋计算机可以计算前方的八个半移动而不是六个,有效分支因子大约为14.通过推导这些参数可以找到完整的分析。 [Pea84]

如上所述,为了使搜索深度加倍,我们需要对子节点进行最佳排序,而实际情况并非如此。否则搜索将是不必要的。通过简单的技巧,我们可以获得相对较好的节点排序。我们将alpha-beta修剪与深度限制上的迭代加深联系起来。因此,在每个新的深度限制,我们可以访问先前级别的所有节点的评级

在每个分支机构订购继任者。从而我们达到有效b – [R 清因子

大约78,距理论最佳值35 [Nil98]不远。

 

 

3.    
非确定性游戏

 

Minimax搜索可以推广到所有具有非确定性动作的游戏,例如步步高。每个玩家在移动之前都会滚动,这会受到掷骰子结果的影响。因此,在游戏树中,序列中有三种类型的级别

最大,骰子,闽,骰子,

每个骰子滚动节点分支六种方式。因为我们无法预测模具的价值,所以我们对所有轧辊的平均值进行平均,并按照[RN10]的平均值进行搜索。

 

图片


 

点击打开微信,马上办理ETC


意见反馈

发表评论