牛角棋博弈程序分析与设计.ppt

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

•麻雀虽小，五脏俱全麻雀虽小，五脏俱全•从一个实例出发从一个实例出发——牛角棋牛角棋•最简单的机器博弈项目最简单的机器博弈项目——机器博弈入门课机器博弈入门课东北大学机器博弈研究室牛角棋牛角棋 •牛角棋广泛见于各地，别名较牛角棋广泛见于各地，别名较多，如多，如憋死牛憋死牛、、憋死井憋死井、、娃娃娃娃下山下山、、娘子下山娘子下山等•棋盘形状及棋位数目也稍有差棋盘形状及棋位数目也稍有差异但是棋子、棋规都相同但是棋子、棋规都相同东北大学机器博弈研究室牛角棋棋规牛角棋棋规•红子红子可上可下，可左可右，一次可上可下，可左可右，一次一步，只能走向空位，不得重合一步，只能走向空位，不得重合与跳跃；与跳跃；•蓝子蓝子只上不下，可左可右，一次只上不下，可左可右，一次一步，只能走向空位，不得重合一步，只能走向空位，不得重合与跳跃；与跳跃；•胜负判断胜负判断：憋死憋不死？：憋死憋不死？东北大学机器博弈研究室红先红胜红先红胜 (7步步)东北大学机器博弈研究室红先蓝胜红先蓝胜(18步步)为什么输赢？需要不断地摸索经验，试验所有的局面为什么输赢？需要不断地摸索经验，试验所有的局面东北大学机器博弈研究室博弈思维过程博弈思维过程展开博弈树展开博弈树红红方方走走棋棋红红方方走走棋棋蓝蓝方方走走棋棋红方先手红方先手东北大学机器博弈研究室现在要考虑的就是现在要考虑的就是计算机该如何实现这个博弈过程？计算机该如何实现这个博弈过程？•如何存储思维信息？棋盘、棋子、棋局、博弈树如何存储思维信息？棋盘、棋子、棋局、博弈树•如何判断局面的胜负？如何判断局面的胜负？•如何展开博弈树？如何展开博弈树？•如何选择当前的着法？如何选择当前的着法？东北大学机器博弈研究室如何存储思维信息？如何存储思维信息？• 编码编码 —— 数据结构数据结构• 棋盘编码（棋位编码）棋盘编码（棋位编码）• 棋子编码棋子编码• 初始局面的表示初始局面的表示• 棋位向量棋位向量：：(100000023)• 棋子向量棋子向量：：(089)2034567891１１２２３３东北大学机器博弈研究室棋局演化的形式化描述棋局演化的形式化描述• 状态变量状态变量 棋子向量表示棋子向量表示• 初始状态初始状态• 状态演化方程状态演化方程• 其中其中 为棋子为棋子i 第第n+1步的着法（算子）步的着法（算子）•着法规则着法规则：： 红子可上可下红子可上可下，可左可右，一次一步，只能走向空位，，可左可右，一次一步，只能走向空位，不得重合与跳跃；不得重合与跳跃； 蓝子只上不下蓝子只上不下，可左可右，一次一步，只能走向空位，，可左可右，一次一步，只能走向空位，不得重合与跳跃；不得重合与跳跃；东北大学机器博弈研究室着法的形式化描述着法的形式化描述通过扫描棋盘，如果通过扫描棋盘，如果“落址落址”为空位，便是合法着法（算子）。

为空位，便是合法着法（算子）2034567891东北大学机器博弈研究室如何判断局面的胜负？如何判断局面的胜负？•红胜红胜：：“逃出逃出”—— •蓝胜：蓝胜：“憋死憋死” —— •和棋和棋—— 局面的无限次重复局面的无限次重复2034567891东北大学机器博弈研究室如何展开博弈树？如何展开博弈树？红红方方走走棋棋红红方方走走棋棋蓝蓝方方走走棋棋红方先手红方先手东北大学机器博弈研究室牛角棋搜索引擎程序设计牛角棋搜索引擎程序设计深度优先搜索深度优先搜索•选择深度优先搜索方法，可以在搜索过程中的任何时候选择深度优先搜索方法，可以在搜索过程中的任何时候仅仅仅生成（仅生成（Make move）整棵树的一小部分，搜索过的部分）整棵树的一小部分，搜索过的部分被立即删去（被立即删去（Unmake move）显然，这个算法对内存的显然，这个算法对内存的要求极低，往往在内存只有几千字节的机器上也可以实现要求极低，往往在内存只有几千字节的机器上也可以实现并且同其他的选择相比，速度上也并不逊色并且同其他的选择相比，速度上也并不逊色东北大学机器博弈研究室如何选择当前的着法？如何选择当前的着法？•在展开的博弈树中搜索在展开的博弈树中搜索——博弈搜索引擎博弈搜索引擎•基本原则基本原则：考虑到对手的存在：考虑到对手的存在–我们想到的内容，对手也一样能想到我们想到的内容，对手也一样能想到–对手会阻止我们达到目的对手会阻止我们达到目的–而且，对手会想尽方法使其利益最大化而且，对手会想尽方法使其利益最大化•如果是我方（如果是我方（红方红方）走棋，那总要找到博弈树中最好的棋局，而）走棋，那总要找到博弈树中最好的棋局，而在考虑对方（在考虑对方（蓝方蓝方）走棋时，就要考虑最坏的局面，因为）走棋时，就要考虑最坏的局面，因为双方都双方都是理智的博弈者，不应该抱有任何侥幸的心理是理智的博弈者，不应该抱有任何侥幸的心理。

•如果给每个棋局打分，那如果给每个棋局打分，那红方红方可以称得上是可以称得上是MAX方，方，蓝方蓝方便是便是MIN方•基本方法基本方法：博弈树搜索（：博弈树搜索（Max-Min, α-β, 负负极大极大值值α-β））东北大学机器博弈研究室深度为深度为3的博弈树的博弈树局面（取极大值）局面（取极大值）局面（取极小值）局面（取极小值）着法着法RootRoot MovesLeavesPly = 0Ply = 1Ply = 2Ply = 3Depth = 3Depth = 2Depth = 1Depth = 0图例：图例：深度深度层数层数东北大学机器博弈研究室负极大值形式的负极大值形式的Alpha-beta搜索搜索•Alpha的含义的含义：当前方已经存在某个着法，其估值至：当前方已经存在某个着法，其估值至少为少为Alpha•Alpha为为最佳着法的下界最佳着法的下界；；•Beta的含义的含义：对手存在某个着法，令当前方的着法：对手存在某个着法，令当前方的着法的估值无论如何也超不过的估值无论如何也超不过Beta•Beta为为最佳着法的上界最佳着法的上界；；•负极大值形式负极大值形式的的Alpha-beta剪枝只有剪枝只有Beta剪枝。

剪枝东北大学机器博弈研究室人人机机对对弈弈信信息息流流程程棋棋 局局 演演 化化棋手棋手界面界面引擎引擎着法着法着法着法着法着法着法着法局面局面局面局面局面局面局面局面思思考考思思考考思思考考计计算算计计算算着法着法局面局面计计算算东北大学机器博弈研究室Human’s Move人机界面（人机界面（CHI））界面更新，胜负判定界面更新，胜负判定搜索引擎（递归搜索引擎（递归BEITA-剪枝）剪枝）Move GenerationMake/Unmake MoveEvaluation数据结构：棋子棋盘表示数据结构：棋子棋盘表示棋局序列，着法列表棋局序列，着法列表Root Move牛角棋软件结构软软件件部部分分东北大学机器博弈研究室计算引擎程序的编写计算引擎程序的编写•首先需要解决的首先需要解决的算法分析与设计算法分析与设计•然后考虑算法的然后考虑算法的实现与编程实现与编程 （编程语言，设计，编码，调试）（编程语言，设计，编码，调试）•遵照遵照软件工程学软件工程学的思想的思想•在在程序设计方法学程序设计方法学上下功夫上下功夫•学习学习人工智能人工智能的先进理论与技术的先进理论与技术 —— 这是所有专业所必需的！这是所有专业所必需的！东北大学机器博弈研究室东北大学机器博弈研究室棋子棋子的表示的表示#define REDSTONE 0#define BLUESTONE1 1#define BLUESTONE2 22034567891012东北大学机器博弈研究室局面局面的表示（一）的表示（一）•初始局面的表示初始局面的表示int board[10] = {REDSTONE, 0, 0, 0, 0, 0, 0, 0, BLUESTONE1, BLUESTONE2,}; 2034567891012东北大学机器博弈研究室局面局面的表示（二）的表示（二）•初始局面的表示初始局面的表示记录有子的交叉点编号记录有子的交叉点编号int si[3] ={0, 8, 9}; (注意注意off-by-one错误错误)2034567891012东北大学机器博弈研究室等价的等价的局面局面表示表示•等价的初始局面等价的初始局面int si[3] ={0, 8, 9};int si[3] ={0, 9, 8};2034567891012东北大学机器博弈研究室着法着法的表示的表示绝对着法绝对着法的三个要素的三个要素 Piece：哪个棋子：哪个棋子From：出发点编号：出发点编号To：： 目标点的编号目标点的编号2034567891012东北大学机器博弈研究室着法着法的表示的表示相对着法相对着法更方便更方便Piece：哪个棋子：哪个棋子To：： 目标点的编号目标点的编号涵义：涵义：Piece To位：位： 5 4 3 2 1 02034567891012东北大学机器博弈研究室着法生成着法生成•着法生成是着法生成是和棋类知识关系最为紧密和棋类知识关系最为紧密的部分的部分•着法生成是着法生成是博弈树展开博弈树展开和和搜索搜索的先决条件的先决条件•着法生成是博弈程序中一个着法生成是博弈程序中一个相当复杂相当复杂而且而且耗费运算时间耗费运算时间的部分的部分•通过良好的通过良好的数据结构数据结构（棋盘表示，着法表示），可以显（棋盘表示，着法表示），可以显著地提高生成的速度著地提高生成的速度•着法生成着法生成 、生成子节点、生成子节点(make move)、评估、选择之后，、评估、选择之后，还要恢复到父节点还要恢复到父节点(unmake move)东北大学机器博弈研究室着法生成（一）着法生成（一）棋盘扫描法棋盘扫描法 //以红子为例，可上可下以红子为例，可上可下for (each piecei){if((piecei+1<=9)&& NoStoneAt(piecei +1))*moveList++ = piecei +1;if((0<=piecei-1) && NoStoneAt(piecei -1))*moveList++ = piecei -1;… …}2034567891012东北大学机器博弈研究室着法生成（二）着法生成（二）预置表法预置表法int preTable[2][10][5] ={{/*red stone moves table*/{2, 1, INV},{2, 3, 0, INV}, {4, 3, 1, 0, INV},{5, 4, 2, 1, INV}, {6, 5, 3, 2, INV},{7, 6, 4, 3, INV},{8, 7, 5, 4, INV},{9, 8, 6, 5, INV}, {9, 7, 6, INV},{8, 7, INV},},{/*blue stone moves table*/{INV},{0, INV}, {3, 1, 0, INV},{2, 1, INV}, {2, 3, 5, INV},{3, 4, INV},{4, 5, 7, INV},{5, 6, INV}, {6, 7, 9, INV},{7, 8, INV},},};2034567891012东北大学机器博弈研究室着法生成（二）着法生成（二）使用预置表法使用预置表法须注意须注意：： 根据牛角棋的规则，从预根据牛角棋的规则，从预置表中提取的着法需做如下合置表中提取的着法需做如下合法性判断：法性判断：preTable[ color ][ from ][ i ] != si[ j ]; ( 其中，其中，0 <=ｉｉ<= 4; j = 0, 1, 2 )[piece, from]  [ piece, to]2034567891012东北大学机器博弈研究室博弈树的展开与恢复博弈树的展开与恢复生成子节点局面生成子节点局面MakeMove ( )撤销子节点局面撤销子节点局面（恢复到父节点）（恢复到父节点）UnmakeMove ( )2034567891012东北大学机器博弈研究室这是在中国象棋中标准的用深度这是在中国象棋中标准的用深度优先策略实现的优先策略实现的极大极小搜索算极大极小搜索算法法描述。

描述东北大学机器博弈研究室牛角棋的搜索算法负极大值形式的负极大值形式的alpha-beta搜索算法搜索算法=// // 生成子节点局面生成子节点局面// // 恢复父节点局面恢复父节点局面// Beta// Beta剪枝剪枝// // 找到更好的着法找到更好的着法// // 搜索到叶子节点搜索到叶子节点// // 已经决出胜负已经决出胜负东北大学机器博弈研究室基基本本搜搜索索流流程程叶节点评估搜搜 索索东北大学机器博弈研究室1012613641518-598716Ply=1Ply=2Ply=3层数层数 Ply=0深度深度 Depth=3Depth=3Depth=1Depth=0作业：试用各种算法求解下题作业：试用各种算法求解下题东北大学机器博弈研究室各种算法至少包括各种算法至少包括•宽度优先极大极小搜索宽度优先极大极小搜索•宽度优先负极大值搜索宽度优先负极大值搜索•α-β搜索搜索•负极大值形式的负极大值形式的α-β搜索搜索东北大学机器博弈研究室算法优化算法优化•博弈树是博弈树是根在上部向下递归产生根在上部向下递归产生的一棵包含所有可能的一棵包含所有可能的对弈过程的搜索树，是的对弈过程的搜索树，是完全搜索树完全搜索树，包含了所有可，包含了所有可能的博弈状态能的博弈状态•但是，有些情况我们但是，有些情况我们不希望重复搜索不希望重复搜索，比如重复出现，比如重复出现的局面（状态）的局面（状态）东北大学机器博弈研究室循环局面的处理循环局面的处理203456789100112169269279179169000000123645789Path搜索过程中循环局面的出现搜索过程中循环局面的出现东北大学机器博弈研究室循环局面的处理循环局面的处理169269279179169000000123645789Path若若 i<4 则无循环，注意则无循环，注意Path[i]与与Path[i-4]的关系的关系搜索过程中循环局面的出现搜索过程中循环局面的出现203456789100112东北大学机器博弈研究室循环局面的处理循环局面的处理–建立一个顺序表，命名为建立一个顺序表，命名为Path。

–每次搜索前将唯一表示当前局面的值存入表中每次搜索前将唯一表示当前局面的值存入表中–若当前层为若当前层为i，，判断判断Path[i]是否等于是否等于Path[i-4]–若相等，表示和棋，返回；不等则继续搜索若相等，表示和棋，返回；不等则继续搜索–搜索结束，将搜索结束，将Path[i] 赋值为赋值为0–较复杂棋类，如象棋，一般用较复杂棋类，如象棋，一般用hash表表实现循环局面的处实现循环局面的处理东北大学机器博弈研究室评估评估（一）（一）•胜利条件胜利条件红方胜的条件：红方胜的条件： (si[REDSTONE] == 8) || (si[REDSTONE] == 9))蓝方胜的条件：蓝方胜的条件： ((si[REDSTONE] == 0) &&((si[BLUESTONE1] + si[BLUESTONE2]) == 3))东北大学机器博弈研究室蓝走红胜蓝走红胜红走蓝胜红走蓝胜不难看出，短兵相接，谁动谁输不难看出，短兵相接，谁动谁输 可以整理判据，放到程序当中可以整理判据，放到程序当中棋局评估－胜负提前判别棋局评估－胜负提前判别东北大学机器博弈研究室评估评估（二）（二）•总结人类博弈知识总结人类博弈知识–影响胜负的重要条件影响胜负的重要条件–局势细微变化的条件局势细微变化的条件–举例（中途判定）举例（中途判定）1）红子突破，红胜）红子突破，红胜( (si[REDSTONE] > si[BLUESTONE1]) || (si[REDSTONE] > si[BLUESTONE2]) )2）蓝走红胜）蓝走红胜( (wtm == BLUE) && ((si[REDSTONE] & 1 == 0) &&((si[BLUESTONE1] == si[REDSTONE]+1) && (si[BLUESTONE2] == si[REDSTONE]+2) ||(si[BLUESTONE1] == si[REDSTONE]+2)&&(si[BLUESTONE2] == si[REDSTONE]+1))) )东北大学机器博弈研究室程序运行结果统计程序运行结果统计•通过博弈树展开，考虑到分枝数不大通过博弈树展开，考虑到分枝数不大4, 阶段数有限（阶段数有限（10步内步内可以分出胜负），可以分出胜负），可以采用穷尽搜索得到对局的解可以采用穷尽搜索得到对局的解。

•将博弈树展开将博弈树展开15层，如果不将无意义的循环走棋计算在内，层，如果不将无意义的循环走棋计算在内，那么那么 有效博弈树的有效博弈树的总节点数总节点数为为 7436771个，个， 在叶节点上在叶节点上红胜红胜为为 532274个，个， 黑胜黑胜为为 672个，个， 和棋和棋为为 4637870个东北大学机器博弈研究室如何编写机器博弈程序？如何编写机器博弈程序？ •会下棋，下好棋会下棋，下好棋——了解规则，懂得棋局的好坏，区分了解规则，懂得棋局的好坏，区分着法的好坏，如何能够克敌制胜，如何立于不败之地着法的好坏，如何能够克敌制胜，如何立于不败之地•掌握计算机博弈的基本知识掌握计算机博弈的基本知识——棋局与着法表示的数据棋局与着法表示的数据结构，着法生成与棋局评估，博弈树，极大极小算法，结构，着法生成与棋局评估，博弈树，极大极小算法，最佳路径与最佳着法等。

最佳路径与最佳着法等•按照软件工程编写程序按照软件工程编写程序——需求分析，总体设计，详细需求分析，总体设计，详细设计，编码调试，设计文档，软件维护，系统优化等等设计，编码调试，设计文档，软件维护，系统优化等等•通过反复地对战优化结构与参数通过反复地对战优化结构与参数——对战平台，大量试对战平台，大量试验，发现问题，提高棋力验，发现问题，提高棋力东北大学机器博弈研究室牛角棋是一个很好的练习牛角棋是一个很好的练习•棋局表示棋局表示•可行着法判别可行着法判别•生成着法，搏弈树展开生成着法，搏弈树展开•棋局评估棋局评估——胜负判别：红胜，黑胜，和棋胜负判别：红胜，黑胜，和棋•最佳路径的选择最佳路径的选择•当前着法当前着法•知识总结：短兵相接谁走谁输知识总结：短兵相接谁走谁输, 只好敬而远之只好敬而远之•继续研究，你会发现问题，欢迎提出改进意见继续研究，你会发现问题，欢迎提出改进意见东北大学机器博弈研究室在游戏软件的编写中在游戏软件的编写中提高素质！提高素质！让创新的火花让创新的火花在机器博弈中迸发！在机器博弈中迸发！联系：联系：computergames@。