基于对局树算法的中国象棋游戏的设计与实现

《基于对局树算法的中国象棋游戏的设计与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、臣k生——型，“丽矿—l墨葡i万方数据基于对局树算法的中国象棋游戏的设计与实现陈应权(淮阴工学院赵文东淮安223001)摘要文章在研究分析对局树的基础上，先后运用极大极小查找和Of．一13修剪对查找下一步的算法进行了改进，并对中国象棋的对弈过程进行了有益的探讨。最后在此基础上，运用面向对象的技术，综合结构化程序设计方法，将所有的操作逻辑封装于类，实现基于对局树算法的中国象棋游戏系统。关键词对局树中国象棋查找对弈中图分类号TP311．52文献标识码A文章编号101022—5578TheDesignandPracticeModelontheBasisofGam

2、e——treeAlgorithminChineseChessChenYingquanZhaoWendong(HuaiyinInstituteofTechlonogyHuaiAn223003)AbstractAfteranalysingthegame-treealgorithmintheChinesechess，thisarticlerevisesthesearchingalgorithmwithMax-Minimumsearchingand仅一Btrimmingsearching，andmakesahelpfulreasearchonthegameproc

3、essoftheChinesechess．Finally，theauthordevelopesaChineseChessGameonthebasisofGame—Treealgorithm．KeywordsGame-treeAlgorithmChinessChessSearchingGame什么是“对局树”呢?为了说明这个问题，我们可以假设在象棋对奕中，轮到我方执棋，我们会考虑走哪一步会比较有利，而我们走了这一步之后，对方有几种走法，当对方走r某一步之后我方又该如何对应等。如果将这一连串的对弈过程绘制成图表，则町将这个图表称为“对局树”或称“游戏树”。您是

4、否觉得这个对局树真的那么重要吗?当然!因为一个棋力愈高的人能考虑的步数愈多、能杏找层数愈深的程序，其棋力也愈高。不过有一点必须要注意，那就是人类的思考模式是由上往下一步一步往下思考，而计算机的查找模式却是由下往上的，也就是说，计算机是先计算最底层盘面的优劣之后再往上传送，并且找出最有利的一个着手。一、树的基本查找为说明树的查找过程，我们绘制了一个如图1所示的树。假设上面图表是某一个局树的片断，其中A是B和c的“父节点”，B和C是A的“子节点”，B和C互为“邻近节点”或“兄弟节点”。我们可以利用两种方式来查找这个对局树：“先深后广”法依照ABDHDlDBEJ

5、EK⋯⋯的路线进行查找，也就是通过节点A获得节B，再通过节点B获得节点D，再通过节点D获得节点H，由于节点H已经是最底下一层，所以无法再往下查找了，必须要返回H的父节点D，然后再通过节点D获得节点H的邻近节点I，再进入节点I，如此一直进行到最后一个节点0。退出后，再一层一层往上返回到节点A为止。‘42‘办公自动化杂志图1对奕树示意图“先广后深”法则依照ABCDEFG⋯⋯的路线进行查找，也就是通过节点A获得节点B，再通过节点B获得邻近节点C，再到节点B的子节点D，再到节点D的邻近节点E，如此一直进行到节点0为止。那么这两种查找法对计算机虽然没有直接的帮助，但

6、我们来分析一下，假设某个盘面，我们走r代号A的走法，对方有代号B和C的对应走法，如果对方走了代号B的走法，那么我们又有代号D和E两咱走法⋯⋯，这不就是人类的对弈模式吗?我们可以利用审局函数根据代号H到0的走法计算，并返网盘面的优劣值到代号A，以决定是否要走代号A这一步。当然这两种查找法无法直接应用到我们的程序中，但是如果我们万方数据将“先深后广”法稍加改良，再以审局函数做配合，那么对我们就有很大的帮助了。1、极大极小查找由于棋类游戏是由双方一来一往对弈，所以不论是红方或黑方走棋，必定是走一步使自己一方最为有利的走法。这一步可能要等到几步以后才能看出效果，所

7、以我们必须先将盘面往前推几步之后，利用审局函数计算盘面，然后再一步一步往网推演，以求出哪一步对我方最有利，这就是计算机象棋的树状查找。请先参考下面对局树的示范，假设有这样一颗如图2所示的对局树。在图2所示的对局树图中可以假设B为某一个对弈中的图2红方先行对局树一盘面，现在轮到红方走棋，红方有D和E两种走法，如果红方走了D的走法，那么黑方有J和K两种走法。那么红方应该走哪一步才对红方有利呢?我们在设计时做r这样的设置：当审局函数计算出的数值愈大时，表示对红方愈有利，反之则对黑方愈有利。当查找函数进入第二层时，将盘面设成H，则审局函数计算盘面后的分数为3分，盘

8、面I的分数为4分。因为H和I为黑方的走法，如所以我们认为当红方走r