研讨班_牛角棋

《研讨班_牛角棋》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

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

4、着法（算子）。2034567891东北大学机器博弈研究室如何判断局面的胜负？红胜：“逃出”——蓝胜：“憋死”——和棋——局面的无限次重复2034567891东北大学机器博弈研究室如何展开博弈树？红方走棋红方走棋蓝方走棋红方先手东北大学机器博弈研究室如何表示博弈树？东北大学机器博弈研究室两种不同的展开方式广度优先东北大学机器博弈研究室两种不同的展开方式深度优先东北大学机器博弈研究室广度优先的展开与存储东北大学机器博弈研究室深度优先的展开与存储东北大学机器博弈研究室如何选择当前的着法？在展开的博弈树中搜索——博弈搜索引擎如果红方走棋，他总要找到博弈树中最好的棋局，

5、而在考虑对方（蓝方）走棋时，就要考虑最坏的局面，因为双方都是理智的博弈者，不应该抱有任何侥幸的心理。如果给每个棋局打分，那红方可以称得上是MAX方，蓝方便是MIN方。东北大学机器博弈研究室深度为3的博弈树局面（取极大值）局面（取极小值）着法RootRootMovesLeavesPly=0Ply=1Ply=2Ply=3Depth=3Depth=2Depth=1Depth=0图例：深度层数东北大学机器博弈研究室MAXMAXMIN1298765433213极大极小搜索找到最佳路径与最佳着法东北大学机器博弈研究室MAXMAXMIN1298765433213从极大极小搜

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

7、着某个着法，令当前方的着法的估值无论如何也超不过beta。负极大值形式的alpha-beta剪枝只有beta剪枝。东北大学机器博弈研究室（alpha，beta）窗口A1A2A3An…（alpha，beta）Value=-Search()If(Value<=alpha)A1A2A3An…（alpha，beta）Value=-Search()负极大值条件下的（alpha，beta）窗口东北大学机器博弈研究室A1A2A3An…returnvalueIf(Value>=beta)A1A2A3An…（alpha，beta）Value=-Search()An（alpha，

8、beta）窗口东北大学机器博弈研究室博