问题:

在九宫格棋盘上两位选手轮流在棋盘上摆各自的棋子,每次一枚,谁先取得三子一线的结果就算取胜。各自都希望每一步都是对自己最有利的。

 

设程序方MAX的棋子用X表示,对手方MIN的棋子用O表示。

启发函数设为h(p):

+∞     表示MAX赢

h(P)=    – ∞    表示MIN赢

(全部空格放X后三子成一线的总数) -(全部空格放O后三子成一线的总数)

 

例如:设格局p为


 

O

 
 

X

 
     

 


在这种格局下,程序方MAX放X可能方式有6种,对方MIN放O可能方式有4种。所以对于程序方MAX,h(P) = 6 – 4 = 2。

 

三子棋中,程序方仅提前考虑2步。


一共有9个空格,排除类似的位置,第一个X有三种可能放置的情况。

对每一种X的放置方式,O有相应的放置情况。可以计算出相应的函数h(p)。因为程序方MAX希望自己赢,对方MIN也希望自己赢,所以程序方MAX总是选择孩子中最大的函数值,对方MIN总是选择最小的函数值。

MIN方在孩子中选择最小的值,分别为-1、-2、1,MAX在这三个数字中选择最大的值 1,最终程序方MAX选择最大值为1的路径。

MAX走完第1步,该对方MIN选择走步,假设MIN选择了不利于自己的走步方式,将棋子O放到了X上方。


根据MAX的4种走步情况,给出了MIN方对应的走步情况,并计算出h(p)。每种情况下,MIN选择最小的函数值,分别为1、0、1、0。程序方MAX选择最大的一个1。

MAX走步后,假设MIN选择函数值为2的一个走步方式。

 

O

O

 

X

 

X

   

 

MAX有5中可能走步情况,给出了MIN方对应的走步情况,计算h(p)。

MAX走完第三步后,无论MIN怎么走,MAX都将胜利。

 

𝛂-𝛃剪枝算法:

MIN、MAX过程将生成后继与估计格局两个过程分开考虑,即先生成全部搜索树,然后再进行端点静态估计和倒推值计算。当预先考虑的棋步比较多时,计算量会大大增加。为了提高搜索的效率,引入了通过对评估值的上下限进行估计,从而减少需进行评估的节点范围的𝛂-𝛃剪枝算法。

 


𝛂剪枝法,设MAX节点的下限为a,则其所有的MIN子节点中,其评估值的 b上限小于等于𝛂的节点,其以下部分的搜索都可以停止了,即对这部分节点进行了𝛂剪支。

 


b剪支法,设MIN节点的上限为b,则其所有的MAX子节点中,其评估值的a下限大于等于b的节点,其以下部分的搜索都可以停止了,即对这部分节点进行了b剪支。

所以,𝛂-𝛃剪枝法,采用有界深度优先策略进行搜索,当生成节点达到规定的深度时(三子棋预判两步),就立即进行函数估计,一旦某个非端节点有条件确定倒推值时,就立即赋值。

例如在三子棋第一步时,进行𝛂剪枝。


 


 




0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注