第一范文网 - 专业文章范例文档资料分享平台

Java版中国象棋项目设计论文

来源:用户分享 时间:2025/5/30 7:32:01 本文由loading 分享 下载这篇文档手机版
说明:文章内容仅供预览,部分内容可能不全,需要完整文档或者需要复制内容,请下载word后使用。下载word有问题请添加微信号:xxxxxxx或QQ:xxxxxx 处理(尽可能给您提供完整文档),感谢您的支持与谅解。

我们能用更为复杂的路线来作裁剪。我们知道N会返回10或更小(轮到棋手乙走棋,需要挑最小的)。我们不知道J能否返回10或更小,也不知道J的哪个子结点会更好。如果从J返回到C的是10或者更小的值,那么我们可以在结点C上作裁剪,因为它比兄弟结点B要好。因此在这种情况下,继续找N的子结点就毫无意义。考虑其他情况,J的其他子结点返回比10更好的值,此时搜索N也是毫无意义的。所以我们只要看到10,就可以放心地从N返回。 5.2.3 Alpha-Beta修剪算法的实现

Alpha-Beta修剪算法在搜索中传递两个值,第一个值是Alpha,即搜索到的最好值,任何比它更小的值就没用了,因为策略就是知道Alpha的值,任何小于或等于Alpha的值都不会有所提高。

第二个值是Beta,即对于对手来说最坏的值。这是对手所能承受的最坏的结果,因为我们知道在对手看来,他总是会找到一个对策不比Beta更坏的。如果搜索过程中返回Beta或比Beta更好的值,那就够好的了,走棋的一方就没有机会使用这种策略了。

在搜索着法时,每个搜索过的着法都返回跟Alpha和Beta有关的值,它们之间的关系非常重要,或许意味着搜索可以停止并返回。

如果某个着法的结果小于或等于Alpha,那么它就是很差的着法,因此可以抛弃。因为我前面说过,在这个策略中,局面对走棋的一方来说是以Alpha为评价的。

如果某个着法的结果大于或等于Beta,那么整个结点就作废了,因为对手不希望走到这个局面,而它有别的着法可以避免到达这个局面。因此如果我们找到的评价大于或等于Beta,就证明了这个结点是不会发生的,因此剩下的合理着法没有必要再搜索。

如果某个着法的结果大于Alpha但小于Beta,那么这个着法就是走棋一方可以考虑走的,除非以后有所变化。因此Alpha会不断增加以反映新的情况。有时候可能一个合

- 33 -

理着法也不超过Alpha,这在实战中是经常发生的,此时这种局面是不予考虑的,因此为了避免这样的局面,我们必须在博弈树的上一个层局面选择另外一个着法。算法代码如下,醒目斜体部分是在最小-最大算法上改过的:

int AlphaBeta(int depth, int alpha, int beta) { if (depth == 0) {

return Evaluate(); }

GenerateLegalMoves(); while (MovesLeft()) { MakeNextMove();

val = -AlphaBeta(depth - 1, -beta, -alpha); UnmakeMove();

if (val >= beta) { return beta; } if (val > alpha) { alpha = val; } }

return alpha; }

把醒目的部分去掉,剩下的就是最小-最大函数。可以看出现在的算法没有太多的改变。

这个函数需要传递的参数有:需要搜索的深度,负无穷大即Alpha,以及正无穷大即Beta:

val = AlphaBeta(5, -INFINITY, INFINITY);

这样就完成了5层的搜索。最终出现的情况是,在搜索树的很多地方,Beta是很容易超过的,因此很多工作都免去了。 5.2.4 可能的弱点

这个算法严重依赖于着法的寻找顺序。如果你总是先去搜索最坏的着法,那么Beta截断就不会发生,因此该算法就如同最小-最大一样,效率非常低。该算法最终会找遍整个博弈树,就像最小-最大算法一样。

如果程序总是能挑最好的着法来首先搜索,那么数学上有效分枝因子就接近于实际分枝因子的平方根。这是Alpha-Beta算法可能达到的最好的情况。

- 34 -

由于中国象棋的分枝因子在45左右,这就意味着Alpha-Beta算法能使国际象棋搜索树的分枝因子变成7左右。

这是很大的改进,在搜索结点数一样的情况下,可以使你的搜索深度达到原来的两倍。这就是为什么使用Alpha-Beta搜索时,着法顺序至关重要的原因。 5.3迭代加深

如果准备开始搜索一个中国象棋的局面,那么要搜索多深?事先预测搜索将进行多少时间,这有些困难,因为完成D层搜索所需要的时间取决于很多不确定的因素。在复杂的中局局面里,你可能不会搜索得很深,而在残局中你可能会搜索得非常深。

有一个思想,就是一开始只搜索一层,如果搜索的时间比分配的时间少,那么搜索两层,然后再搜索三层,等等,直到你用完时间为止。

这足以保证很好地运用时间了。如果你可以很快搜索到一个深度,那么你在接下来的时间可以搜索得更深,或许你可以完成。如果局面比你想象的复杂,那么你不必搜索得太深,但是至少有合理的着法可以走了,因为你不太可能连1层搜索也完不成。

这个思想称为“迭代加深”(Iterative Deepening),因为使用迭代搜索,每次都比一次前一次加深1层(多1层没有什么奥妙的,当然你可以试试多两层,但是1层比较好)。

代码如下:

for (depth = 1; ; depth ++) {

val = AlphaBeta(depth, -INFINITY, INFINITY); if (TimedOut()) { break; } }

这是一个非常有效的搜索方法。如果能增强Alpha-Beta使得它返回一条“主要变例”,那么便可以用主要变例中的着法来做下一次迭代搜索。这样做之所以有好的效果,是因为第一次搜索的线路通常是好的,而Alpha-Beta对着法的顺序特别敏感。如果着法顺序很坏,那么在中国象棋中“分枝因子”将接近45。如果着法很好,那么分枝因子将接近于7。前一次迭代的搜索函数得到的主要变例通常是非常好的着法。

迭代加深的思想给了你一个简单的方法,它可以在时间用完时中断搜索,并且会提高你的搜索效率。 5.4 置换表

中国象棋的搜索树可以用图来表示,而置换结点可以引向以前搜索过的子树上。置换表可以用来检测这种情况,从而避免重复劳动。置换表还有另一个更为重要的作用:每个散列项里都有局面中最好的着法,在“迭代加深”中,首先搜索好的着法可以大幅

- 35 -

度提高搜索效率。因此如果在散列项里找到最好的着法,那么首先搜索这个着法,这样会改进着法顺序,减少分枝因子。 5.4.1 置换表的实现

主置换表是一个散列数组,每个散列项如下:

class HashRecord { };

private static final int BookUnique = 1;//指示结点类型,就是下面Flag的值。 private static final int BookMulti = 2; private static final int HashAlpha = 4; private static final int HashBeta = 8; private static final int HashPv = 16; public HashRecord(){ Flag=0; Depth=0; Value=0; ZobristLock = 0; BestMove = new MoveStruct(); }

long ZobristLock; int Flag, Depth; int Value;

MoveStruct BestMove;

这个散列数组是以―Zobrist键值‖为指标的。当求得局面的键值,除以散列表的项数得到余数,这个散列项就代表该局面。由于很多局面都有可能跟散列表中同一项作用,因此散列项需要包含一个校验值,它可以用来确认该项就是要找的。通常校验值是一个64位的数,也就是上面的ZobristLock。

从搜索中得到结果后,要保存到散列表中。用散列表来避免重复工作,最重要的是记住搜索有多深。如果在一个结点上搜索了3层,后来又打算做10层搜索,就不能认为散列项里的信息是准确的。因此子树的搜索深度也要记录。

在Alpha-Beta搜索中,很少能得到搜索结点的准确值。Alpha和Beta的存在有助于裁剪掉没有用的子树,但是用Alpha-Beta有个小的缺点,就是通常不会知道一个结点到底有多坏或者有多好,只是知道它足够坏或足够好,从而不需要浪费更多的时间。

当然,这就引发了一个问题,散列项里到底要保存什么值,并且当你要获取它时怎样来做。答案是储存一个值,另加一个标志来说明这个值是什么含义。在我上面的例子中,比方说你在评价域中保存了16,并且在标志域保存了―HashPV‖,这就意味着该结点的评价是准确值16;如果你在标志域中保存了―HashAlpha‖,那么结点的值最多是16;如果保存了―HashBeta‖,这个值就至少是16。

- 36 -

搜索更多关于: Java版中国象棋项目设计论文 的文档
Java版中国象棋项目设计论文.doc 将本文的Word文档下载到电脑,方便复制、编辑、收藏和打印
本文链接:https://www.diyifanwen.net/c7qbr70tyqv0a0pl1tyxy_9.html(转载请注明文章来源)
热门推荐
Copyright © 2012-2023 第一范文网 版权所有 免责声明 | 联系我们
声明 :本网站尊重并保护知识产权,根据《信息网络传播权保护条例》,如果我们转载的作品侵犯了您的权利,请在一个月内通知我们,我们会及时删除。
客服QQ:xxxxxx 邮箱:xxxxxx@qq.com
渝ICP备2023013149号
Top