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

《牛角棋博弈程序分析与设计.ppt》由会员分享，可在线阅读，更多相关《牛角棋博弈程序分析与设计.ppt（48页珍藏版）》请在优知文库上搜索。

1、牛角棋博弈程序分析与设计牛角棋博弈程序分析与设计 主要内容主要内容 民间棋类计算机博弈民间棋类计算机博弈 计算机该如何实现博弈过程的？计算机该如何实现博弈过程的？ 如何存储思维信息？如何存储思维信息？ 如何判断局面的胜负？如何判断局面的胜负？ 如何展开博弈树？如何展开博弈树？ 如何选择当前的着法？如何选择当前的着法？ 从极大极小搜索到负极大值从极大极小搜索到负极大值Alpha-bete搜索搜索 计算机引擎程序的编写（计算机引擎程序的编写（C） 用用C+编写牛角棋程序编写牛角棋程序 算法优化算法优化民间棋类计算机博弈民间棋类计算机博弈 民间棋类的特点民间棋类的特点 规则简单，很容易入门；规则简单

2、，很容易入门； 不受专业知识限制；不受专业知识限制； 棋盘小，棋子少，复杂度不高；棋盘小，棋子少，复杂度不高； 输赢容易识别，局面容易判断；输赢容易识别，局面容易判断； 完全信息，编程相对简单；完全信息，编程相对简单； 人工智能的人工智能的“果蝇果蝇”。 麻雀虽小，五脏俱全麻雀虽小，五脏俱全 从一个实例出发从一个实例出发牛角棋牛角棋 最简单的机器博弈项目最简单的机器博弈项目机器博弈入门课机器博弈入门课牛角棋牛角棋 牛角棋广泛见于各地，别名较牛角棋广泛见于各地，别名较多，如多，如憋死牛憋死牛、憋死井憋死井、娃娃娃娃下山下山、娘子下山娘子下山等。等。棋盘形状及棋位数目也稍有差棋盘形状及棋位数目也稍

3、有差异。但是棋子、棋规都相同。异。但是棋子、棋规都相同。牛角棋棋规牛角棋棋规红子红子可上可下，可左可右，一可上可下，可左可右，一次一步，只能走向空位，不得次一步，只能走向空位，不得重合与跳跃；重合与跳跃；蓝子蓝子只上不下，可左可右，一只上不下，可左可右，一次一步，只能走向空位，不得次一步，只能走向空位，不得重合与跳跃；重合与跳跃；胜负判断胜负判断：憋死憋不死？：憋死憋不死？红先红胜红先红胜 (7步步)红先蓝胜红先蓝胜(18步步)为什么输赢？需要不断地摸索经验，试验所有的局面。为什么输赢？需要不断地摸索经验，试验所有的局面。博弈思维过程博弈思维过程展开博弈树展开博弈树红方走红方走棋棋红方走棋红方

4、走棋蓝方走棋蓝方走棋红方先手红方先手现在要考虑的就是现在要考虑的就是计算机该如何实现这个博弈过程？计算机该如何实现这个博弈过程？ 如何存储思维信息？棋盘、棋子、棋局、博弈树如何存储思维信息？棋盘、棋子、棋局、博弈树 如何判断局面的胜负？如何判断局面的胜负？ 如何展开博弈树？如何展开博弈树？ 如何选择当前的着法？如何选择当前的着法？如何存储思维信息？如何存储思维信息？ 编码编码 数据结构数据结构 棋盘编码（棋位编码）棋盘编码（棋位编码） 棋子编码棋子编码 初始局面的表示初始局面的表示 棋位向量棋位向量：(100000023) 棋子向量棋子向量：(089)2034567891棋局演化的形式化描述棋

5、局演化的形式化描述 状态变量状态变量 棋子向量表示棋子向量表示 初始状态初始状态 状态演化方程状态演化方程 其中其中 为棋子为棋子i 第第n+1步的着法（算子）步的着法（算子） 着法规则着法规则： 红子可上可下红子可上可下，可左可右，一次一步，只能走向空位，可左可右，一次一步，只能走向空位，不得重合与跳跃；不得重合与跳跃； 蓝子只上不下蓝子只上不下，可左可右，一次一步，只能走向空位，可左可右，一次一步，只能走向空位，不得重合与跳跃；不得重合与跳跃；),(321nnnnPPPS )9 , 8 , 0(0S)9 , 8 , 0(0SinnnqSS11inq1着法的形式化描述着法的形式化描述9 ,

6、02, 1:1111111iiiiPPPPq9 , 02, 1:2212212iiiiPPPPqevenPPPiii22218 , 219 , 02, 1:3313313iiiiPPPPqevenPPPiii33318 , 21通过扫描棋盘，如果通过扫描棋盘，如果“落址落址”为空位，便是合法着法（算子）。为空位，便是合法着法（算子）。2034567891如何判断局面的胜负？如何判断局面的胜负？ 红胜红胜：“逃出逃出” 蓝胜：蓝胜：“憋死憋死” 和棋和棋 局面的无限次重复局面的无限次重复3121iiiiPPorPP) 1 , 2 , 0()2 , 1 , 0(),(321eeeePPPS2034

7、567891如何展开博弈树？如何展开博弈树？红方走棋红方走棋红方走红方走棋棋蓝方走蓝方走棋棋红方先手红方先手牛角棋搜索引擎程序设计牛角棋搜索引擎程序设计深度优先搜索深度优先搜索 选择深度优先搜索方法，可以在搜索过程中的任何时候选择深度优先搜索方法，可以在搜索过程中的任何时候仅仅仅生成（仅生成（Make move）整棵树的一小部分，搜索过的部分）整棵树的一小部分，搜索过的部分被立即删去（被立即删去（Unmake move）。）。显然，这个算法对内存的显然，这个算法对内存的要求极低，往往在内存只有几千字节的机器上也可以实现。要求极低，往往在内存只有几千字节的机器上也可以实现。并且同其他的选择相比，

8、速度上也并不逊色。并且同其他的选择相比，速度上也并不逊色。如何选择当前的着法？如何选择当前的着法？在展开的博弈树中搜索在展开的博弈树中搜索博弈搜索引擎博弈搜索引擎基本原则基本原则：考虑到对手的存在：考虑到对手的存在 我们想到的内容，对手也一样能想到我们想到的内容，对手也一样能想到 对手会阻止我们达到目的对手会阻止我们达到目的 而且，对手会想尽方法使其利益最大化而且，对手会想尽方法使其利益最大化如果是我方（如果是我方（红方红方）走棋，那总要找到博弈树中最好的棋局，而）走棋，那总要找到博弈树中最好的棋局，而在考虑对方（在考虑对方（蓝方蓝方）走棋时，就要考虑最坏的局面，因为）走棋时，就要考虑最坏的局

9、面，因为双方都双方都是理智的博弈者，不应该抱有任何侥幸的心理是理智的博弈者，不应该抱有任何侥幸的心理。如果给每个棋局打分，那如果给每个棋局打分，那红方红方可以称得上是可以称得上是MAX方，方，蓝方蓝方便是便是MIN方。方。基本方法基本方法：博弈树搜索（：博弈树搜索（Max-Min, -, 负极大值负极大值-）深度为深度为3的博弈树的博弈树局面（取极大值）局面（取极大值）局面（取极小值）局面（取极小值）着法着法RootRoot MovesLeavesPly = 0Ply = 1Ply = 2Ply = 3Depth = 3Depth = 2Depth = 1Depth = 0图例：图例：深度深度

10、层数层数负极大值形式的负极大值形式的Alpha-beta搜索搜索 Alpha的含义的含义：当前方已经存在某个着法，其估值至：当前方已经存在某个着法，其估值至少为少为Alpha。 Alpha为最佳着法的下界为最佳着法的下界； Beta的含义的含义：对手存在某个着法，令当前方的着法：对手存在某个着法，令当前方的着法的估值无论如何也超不过的估值无论如何也超不过Beta。 Beta为最佳着法的上界为最佳着法的上界； 负极大值形式负极大值形式的的Alpha-beta剪枝只有剪枝只有Beta剪枝。剪枝。人人机机对对弈弈信信息息流流程程棋棋 局局 演演 化化棋手棋手界面界面引擎引擎着法着法着法着法着法着法着

11、法着法局面局面局面局面局面局面局面局面思思考考思思考考思思考考计计算算计计算算着法着法局面局面计计算算Humans Move人机界面（人机界面（CHI）界面更新，胜负判定界面更新，胜负判定搜索引擎（递归搜索引擎（递归BEITA-剪枝）剪枝）Move GenerationMake/Unmake MoveEvaluation数据结构：棋子棋盘表示数据结构：棋子棋盘表示棋局序列，着法列表棋局序列，着法列表Root Move牛角棋软件结构软件部分软件部分计算引擎程序的编写计算引擎程序的编写 首先需要解决的首先需要解决的算法分析与设计算法分析与设计 然后考虑算法的然后考虑算法的实现与编程实现与编程 （编

12、程语言，设计，编码，调试）（编程语言，设计，编码，调试） 遵照遵照软件工程学软件工程学的思想的思想 在在程序设计方法学程序设计方法学上下功夫上下功夫 学习学习人工智能人工智能的先进理论与技术的先进理论与技术 这是所有专业所必需的！这是所有专业所必需的！棋子棋子的表示的表示#define REDSTONE 0#define BLUESTONE1 1#define BLUESTONE2 22034567891012局面局面的表示（一）的表示（一） 初始局面的表示初始局面的表示int board10 = REDSTONE, 0, 0, 0, 0, 0, 0, 0, BLUESTONE1, BLUES

13、TONE2,; 2034567891012局面局面的表示（二）的表示（二） 初始局面的表示初始局面的表示记录有子的交叉点编号记录有子的交叉点编号int si3 =0, 8, 9; (注意注意off-by-one错误错误)2034567891012等价的等价的局面局面表示表示 等价的初始局面等价的初始局面int si3 =0, 8, 9;int si3 =0, 9, 8;2034567891012着法着法的表示的表示绝对着法绝对着法的三个要素的三个要素Piece：哪个棋子：哪个棋子From：出发点编号：出发点编号To： 目标点的编号目标点的编号2034567891012着法着法的表示的表示相对着

14、法相对着法更方便更方便Piece：哪个棋子：哪个棋子To： 目标点的编号目标点的编号涵义：涵义：Piece To位：位： 5 4 3 2 1 02034567891012着法生成着法生成 着法生成是着法生成是和棋类知识关系最为紧密和棋类知识关系最为紧密的部分的部分 着法生成是着法生成是博弈树展开博弈树展开和和搜索搜索的先决条件的先决条件 着法生成是博弈程序中一个着法生成是博弈程序中一个相当复杂相当复杂而且而且耗费运算时间耗费运算时间的部分的部分 通过良好的通过良好的数据结构数据结构（棋盘表示，着法表示），可以显（棋盘表示，着法表示），可以显著地提高生成的速度著地提高生成的速度 着法生成着法生成

15、 、生成子节点、生成子节点(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 preTabl

16、e2105 =/*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, to2034