牛角棋博弈程序设计

《牛角棋博弈程序设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、牛角棋博弈程序设计徐心和徐长明东北大学机器博弈研究室2009.5东北大学机器博弈研究室民间棋类计算机博弈民间棋类的特点规则简单，很容易入门；不受专业知识限制；棋盘小，棋子少，复杂度不高；输赢容易识别，局面容易判断；完全信息，编程相对简单；人工智能的“果蝇”。麻雀虽小，五脏俱全从一个实例出发——牛角棋最简单的机器博弈项目——机器博弈入门课东北大学机器博弈研究室牛角棋牛角棋广泛见于各地，别名较多，如憋死牛、憋死井、娃娃下山、娘子下山等。棋盘形状及棋位数目也稍有差异。但是棋子、棋规都相同。东北大学机器博弈研究室牛角棋棋规红子可上可下

2、，可左可右，一次一步，只能走向空位，不得重合与跳跃；蓝子只上不下，可左可右，一次一步，只能走向空位，不得重合与跳跃；胜负判断：憋死憋不死？东北大学机器博弈研究室红先红胜(7步)东北大学机器博弈研究室红先蓝胜(18步)为什么输赢？需要不断地摸索经验，试验所有的局面。东北大学机器博弈研究室博弈思维过程展开博弈树红方走棋红方走棋蓝方走棋红方先手东北大学机器博弈研究室现在要考虑的就是计算机该如何实现这个博弈过程？如何存储思维信息？棋盘、棋子、棋局、博弈树如何判断局面的胜负？如何展开博弈树？如何选择当前的着法？东北大学机器博弈研究室

3、如何存储思维信息？编码——数据结构棋盘编码（棋位编码）棋子编码初始局面的表示棋位向量：(100000023)棋子向量：(089)2034567891１２３东北大学机器博弈研究室棋局演化的形式化描述状态变量棋子向量表示初始状态状态演化方程其中为棋子i第n+1步的着法（算子）着法规则：红子可上可下，可左可右，一次一步，只能走向空位，不得重合与跳跃；蓝子只上不下，可左可右，一次一步，只能走向空位，不得重合与跳跃；东北大学机器博弈研究室着法的形式化描述通过扫描棋盘，如果“落址”为空位，便是合法着法（算子）。2034567891东北大学

4、机器博弈研究室如何判断局面的胜负？红胜：“逃出”——蓝胜：“憋死”——和棋——局面的无限次重复2034567891东北大学机器博弈研究室如何展开博弈树？红方走棋红方走棋蓝方走棋红方先手东北大学机器博弈研究室如何表示博弈树？东北大学机器博弈研究室两种不同的展开方式广度优先东北大学机器博弈研究室两种不同的展开方式深度优先东北大学机器博弈研究室广度优先的展开与存储东北大学机器博弈研究室深度优先的展开与存储东北大学机器博弈研究室牛角棋搜索引擎程序设计深度优先搜索选择深度优先搜索方法，可以在搜索过程中的任何时候仅仅生成（Makemov

5、e）整棵树的一小部分，搜索过的部分被立即删去（Unmakemove）。显然，这个算法对内存的要求极低，往往在内存只有几千字节的机器上也可以实现。并且同其他的选择相比，速度上也并不逊色。东北大学机器博弈研究室如何选择当前的着法？在展开的博弈树中搜索——博弈搜索引擎基本原则：考虑到对手的存在我们想到的内容，对手也一样能想到对手会阻止我们达到目的而且，对手会想尽方法使其利益最大化如果是我方（红方）走棋，那总要找到博弈树中最好的棋局，而在考虑对方（蓝方）走棋时，就要考虑最坏的局面，因为双方都是理智的博弈者，不应该抱有任何侥幸的心理。如

6、果给每个棋局打分，那红方可以称得上是MAX方，蓝方便是MIN方。基本方法：博弈树搜索（Max-Min,α-β,负极大值α-β）东北大学机器博弈研究室深度为3的博弈树局面（取极大值）局面（取极小值）着法RootRootMovesLeavesPly=0Ply=1Ply=2Ply=3Depth=3Depth=2Depth=1Depth=0图例：深度层数东北大学机器博弈研究室MAXMAXMIN1298765433213极大极小搜索找到最佳路径与最佳着法东北大学机器博弈研究室MAXMAXMIN1298765433213从极大极小搜索到负

7、极大值搜索找到最佳路径与最佳着法-3-2-1NegaMaxNegaMax东北大学机器博弈研究室MAXMAXMIN45682434α（Alpha）剪枝α=4找到最佳路径与最佳着法α为最佳着法的下界东北大学机器博弈研究室β（Beta）剪枝174298MAXMINMIN77由此产生最佳路径和最佳着法β为最佳着法的上界β=7东北大学机器博弈研究室负极大值形式的Alpha-beta搜索Alpha的含义：当前方已经存在某个着法，其估值至少为Alpha。Alpha为最佳着法的下界；Beta的含义：对手存在某个着法，令当前方的着法的估值无论如

8、何也超不过Beta。Beta为最佳着法的上界；负极大值形式的Alpha-beta剪枝只有Beta剪枝。东北大学机器博弈研究室博弈树搜索过程MoveGenerationMakeMoveMoveGenerationMakeMove10Evaluationdepth=01010Un