牛角棋博弈程序分析与设计课件

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

1、牛角棋博弈程序分析与设计徐心和徐长明东北大学机器博弈研究室2009.5东北大学机器博弈研究室东北大学机器博弈研究室主要内容民间棋类计算机博弈计算机该如何实现博弈过程的？—如何存储思维信息？—如何判断局面的胜负？—如何展开博弈树？—如何选择当前的着法？从极大极小搜索到负极大值Alpha-bete搜索计算机引擎程序的编写（C）用C++编写牛角棋程序算法优化东北大学机器博弈研究室民间棋类计算机博弈民间棋类的特点规则简单，很容易入门；不受专业知识限制；棋盘小，棋子少，复杂度不高；输赢容易识别，局面容易判断；完全信息，编程相对简单；人工智能的“果蝇”。麻雀虽小，五脏俱

2、全从一个实例出发——牛角棋最简单的机器博弈项目——机器博弈入门课东北大学机器博弈研究室牛角棋牛角棋广泛见于各地，别名较多，如憋死牛、憋死井、娃娃下山、娘子下山等。棋盘形状及棋位数目也稍有差异。但是棋子、棋规都相同。东北大学机器博弈研究室牛角棋棋规红子可上可下，可左可右，一次一步，只能走向空位，不得重合与跳跃；蓝子只上不下，可左可右，一次一步，只能走向空位，不得重合与跳跃；胜负判断：憋死憋不死？东北大学机器博弈研究室红先红胜(7步)东北大学机器博弈研究室红先蓝胜(18步)为什么输赢？需要不断地摸索经验，试验所有的局面。东北大学机器博弈研究室博弈思维过程展开博

3、弈树红方走棋红方走棋蓝方走棋红方先手东北大学机器博弈研究室现在要考虑的就是计算机该如何实现这个博弈过程？如何存储思维信息？棋盘、棋子、棋局、博弈树如何判断局面的胜负？如何展开博弈树？如何选择当前的着法？东北大学机器博弈研究室如何存储思维信息？编码——数据结构棋盘编码（棋位编码）棋子编码初始局面的表示棋位向量：(100000023)棋子向量：(089)2034567891１２３东北大学机器博弈研究室棋局演化的形式化描述状态变量棋子向量表示初始状态状态演化方程其中为棋子i第n+1步的着法（算子）着法规则：红子可上可下，可左可右，一次一步，只能走向空位，不得重合

4、与跳跃；蓝子只上不下，可左可右，一次一步，只能走向空位，不得重合与跳跃；东北大学机器博弈研究室着法的形式化描述通过扫描棋盘，如果“落址”为空位，便是合法着法（算子）。2034567891东北大学机器博弈研究室如何判断局面的胜负？红胜：“逃出”——蓝胜：“憋死”——和棋——局面的无限次重复2034567891东北大学机器博弈研究室如何展开博弈树？红方走棋红方走棋蓝方走棋红方先手东北大学机器博弈研究室牛角棋搜索引擎程序设计深度优先搜索选择深度优先搜索方法，可以在搜索过程中的任何时候仅仅生成（Makemove）整棵树的一小部分，搜索过的部分被立即删去（Unmak

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

6、ax-Min,α-β,负极大值α-β）东北大学机器博弈研究室深度为3的博弈树局面（取极大值）局面（取极小值）着法RootRootMovesLeavesPly=0Ply=1Ply=2Ply=3Depth=3Depth=2Depth=1Depth=0图例：深度层数东北大学机器博弈研究室负极大值形式的Alpha-beta搜索Alpha的含义：当前方已经存在某个着法，其估值至少为Alpha。Alpha为最佳着法的下界；Beta的含义：对手存在某个着法，令当前方的着法的估值无论如何也超不过Beta。Beta为最佳着法的上界；负极大值形式的Alpha-beta剪枝只有B

7、eta剪枝。东北大学机器博弈研究室人机对弈信息流程棋局演化棋手界面引擎着法着法着法着法局面局面局面局面思考思考思考计算计算着法局面计算东北大学机器博弈研究室Human’sMove人机界面（CHI）界面更新，胜负判定搜索引擎（递归BEITA-剪枝）MoveGenerationMake/UnmakeMoveEvaluation数据结构：棋子棋盘表示棋局序列，着法列表RootMove牛角棋软件结构软件部分东北大学机器博弈研究室计算引擎程序的编写首先需要解决的算法分析与设计然后考虑算法的实现与编程（编程语言，设计，编码，调试）遵照软件工程学的思想在程序设

8、计方法学上下功夫学习人工智能的先进理论与技术——这是