牛角棋博弈程序设计 徐心和 徐长明东北大学机器博弈研究室 2009.5民间棋类计算机博弈• 民间棋类的特点规则简单，很容易入门；不受专业知识限制；棋盘小，棋子少，复杂度不高；输赢容易识别，局面容易判断；完全信息，编程相对简单；人工智能的“果蝇”• 麻雀虽小，五脏俱全 • 从一个实例出发——牛角棋 • 最简单的机器博弈项目——机器博弈入门课牛角棋 •牛角棋广泛见于各地，别名较 多，如憋死牛、憋死井、娃娃 下山、娘子下山等•棋盘形状及棋位数目也稍有差 异但是棋子、棋规都相同牛角棋棋规•红子可上可下，可左可右，一次 一步，只能走向空位，不得重合 与跳跃；•蓝子只上不下，可左可右，一次 一步，只能走向空位，不得重合 与跳跃；•胜负判断：憋死憋不死？红先红胜 (7步)红先蓝胜 (18步)为什么输赢？需要不断地摸索经验，试验所有的局面博弈思维过程 展开博弈树红方走棋红方走棋蓝方走棋红方先手现在要考虑的就是 计算机该如何实现这个博弈过程？• 如何存储思维信息？棋盘、棋子、棋局、博弈树 • 如何判断局面的胜负？ • 如何展开博弈树？ • 如何选择当前的着法？如何存储思维信息？• 编码 —— 数据结构 • 棋盘编码（棋位编码） • 棋子编码 • 初始局面的表示 • 棋位向量：(100000023) • 棋子向量：(089)2034567891１２３棋局演化的形式化描述• 状态变量 棋子向量表示 • 初始状态 • 状态演化方程 • 其中 为棋子i 第n+1步的着法（算子）• 着法规则：红子可上可下，可左可右，一次一步，只能走向空位 ，不得重合与跳跃；蓝子只上不下，可左可右，一次一步，只能走向空位 ，不得重合与跳跃；着法的形式化描述通过扫描棋盘，如果“落址”为空位，便是合法着法（算子）。
203 45 67 891如何判断局面的胜负？• 红胜：“逃出”—— • 蓝胜：“憋死” —— • 和棋——局面的无限次重复203 45 67 891如何展开博弈树？红方走棋红方走 棋蓝方走 棋红方先手如何表示博弈树？两种不同的展开方式广度 优先两种不同的展开方式深度 优先广度优先的展开与存储深度优先的展开与存储牛角棋搜索引擎程序设计 深度优先搜索• 选择深度优先搜索方法，可以在搜索过程中的任何时候仅 仅生成（Make move）整棵树的一小部分，搜索过的部分 被立即删去（Unmake move）显然，这个算法对内存的 要求极低，往往在内存只有几千字节的机器上也可以实现 并且同其他的选择相比，速度上也并不逊色如何选择当前的着法？•在展开的博弈树中搜索——博弈搜索引擎•基本原则：考虑到对手的存在 – 我们想到的内容，对手也一样能想到 – 对手会阻止我们达到目的 – 而且，对手会想尽方法使其利益最大化 •如果是我方（红方）走棋，那总要找到博弈树中最好的棋局，而 在考虑对方（蓝方）走棋时，就要考虑最坏的局面，因为双方都 是理智的博弈者，不应该抱有任何侥幸的心理 •如果给每个棋局打分，那红方可以称得上是MAX方，蓝方便是 MIN方。
•基本方法：博弈树搜索（Max-Min, α-β, 负负极大值值α-β）深度为3的博弈树局面（取极大值）局面（取极小值）着法RootRoot MovesLeavesPly = 0Ply = 1Ply = 2Ply = 3Depth = 3Depth = 2Depth = 1Depth = 0图例：深度层数MAXMAXMIN1298765433213极大极小搜索找到最佳路径与最佳着法MAXMAXMIN1298765433213从极大极小搜索到负极大值搜索找到最佳路径与最佳着法-3-2-1NegaMaxNegaMaxMAXMAXMIN45682434α（Alpha）剪枝α=4找到最佳路径与最佳着法α为最佳着法的下界β（Beta）剪枝174298MAXMINMIN77由此产生最佳路径和最佳着法 β为最佳着法的上界β =7负极大值形式的Alpha-beta搜索• Alpha的含义：当前方已经存在某个着法，其估值至 少为Alpha• Alpha为为最佳着法的下界；• Beta的含义：对手存在某个着法，令当前方的着法 的估值无论如何也超不过Beta• Beta为为最佳着法的上界；• 负极大值形式的Alpha-beta剪枝只有Beta剪枝。
博弈树搜索过程Move Generation Make MoveMove GenerationMake Move10Evaluation depth=01010UnMake Move1010 121210 12121210 12121210 12121212101212121061212612106121261210613121261210613Cut off121213121061312121312106131212131210613121213121061312121312106131812121312106131818121213121210613181812121312121061318181212131212106131818129998Cut off1212131212106131818129998Best PV人 机 对 弈 信 息 流 程棋 局 演 化棋手界面引擎着法着法着法着法局面局面局面局面思 考思 考思 考 计 算计 算着法局面 计 算Human’s Move人机界面（CHI） 界面更新，胜负判定搜索引擎（递归BEITA-剪枝） Move Generation Make/Unmake Move Evaluation数据结构：棋子棋盘表示 棋局序列，着法列表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局面的表示（二）• 初始局面的表示记录有子的交叉点编号 （stone Intersection---si）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)if((0<=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局面评估•简单评估：判断胜负和，并考虑搜索深度 •胜利条件红方胜的条件：(si[REDSTONE] == 8) || (si[REDSTONE] == 9))蓝方胜的条件：((si[REDSTONE] == 0) &&((si[BLUESTONE1] + si[BLUESTONE2]) == 3)) • 胜 win=200 • 负 lose=-200 • 平局 draw=0 •考虑到展开的层次 • 胜 evaluation=win-ply • 负 evaluation=lose+ply • 和 evaluation=draw+ply这是在中国象棋中标准的用深度 优先策略实现的极大极小搜索算 法描述。
牛角棋的搜索算法 负极大值形式的alpha-beta搜索算法=// 生成子节点局面// 恢复父节点局面// Beta剪枝// 找到更好的着法// 搜索到叶子节点// 已经决出胜负基 本 搜 索 流 程叶节点评估搜 索算法优化• 博弈树是根在上部向下递归产生的一棵包含所有可能 的对弈过程的搜索树，是完全搜索树，包含了所有可 能的博弈状态• 但是，有些情况我们不希望重复搜索，比如重复出现 的局面（状态）循环局面的处理203456789100112169 269 279 179 169 000000123645789Path搜索过程中循环局面的出现循环局面的处理169 269 279 179 169 000000123645789Path若 i<4 则无循环，注意 Path[i]与Path[i-4]的关系搜索过程中循环局面的出现 203456789100112循环局面的处理– 建立一个顺序表，命名为Path– 每次搜索前将唯一表示当前局面的值存入表中– 若当前层为i，判断Path[i]是否等于Path[i-4]– 若相等，表示和棋，返回；不等则继续搜索– 搜索结束，将Path[i] 赋值为0– 较复杂棋类，如象棋，一般用hash表实现循环局面的处理。
程序运行结果统计• 通过博弈树展开，考虑到分枝数不大4, 阶段数有限（10步内 可以分出胜负），可。