苏拉卡尔塔博弈技术分析.ppt

东北大学机器博弈研究室,苏拉卡尔塔棋 博弈技术分析,东北大学机器博弈研究室2009.5,,东北大学机器博弈研究室,“苏拉卡尔塔”规则,棋盘棋子1）横竖各6条边构成正方形棋盘，36个交叉点为棋位，各边由8段圆弧连接，通常用2种不同颜色表示2）红黑双方各12枚棋子 初始状态：棋子在各方底线排成2排 玩法1）双方轮流走棋，每次走动一枚棋子；2）除了吃子之外，每枚棋子只能沿着垂直或对角方向走动一格，只能走向空位；3）吃对方子时必须经过至少一个完整的弧线 胜负：1. 吃掉所有对方棋子一方获胜；2. 进入循环，剩余棋子多的一方获胜东北大学机器博弈研究室,棋盘的数字表示,用6×6的方阵只能表示棋位，没有表示相互的关系,东北大学机器博弈研究室,棋子的数字表示,兵种定义：黑子为-1，红字为1，无子为零则初始局面为,,东北大学机器博弈研究室,棋局表示,,东北大学机器博弈研究室,着法表示,走行（前进一步的不吃子着法）：横向（左、右）竖向（上、下） 斜向（四个方向）落址在棋盘内并为空位，才为有效的可行着法 可以采用预置表法实现着法生成吃子？这里关键是吃子！ 需要调整棋盘数据结构，因为没有表示出圆弧的连接关系 吃子可以定义为飞行，因为必须经过圆弧。

东北大学机器博弈研究室,飞行是有轨道的,轨道有两种： 绿轨，圆弧在外圈，可以称之为外轨，用字母g表示g=1，该棋位在外轨； 蓝轨，圆弧在内圈，可以称之为内轨，用字母b表示b=1，该棋位在内轨；,东北大学机器博弈研究室,棋位的轨道属性,分析盘中的36个棋位： 外轨棋位：（i，j，1，0），边中心处8个，盘中心处4个，共12个； 内轨棋位：（i，j，0，1），近角处12个； 双轨棋位：（i，j，1，1），内外轨相交处8个； 轨外棋位： （i，j，0，0），四角处4个,此时每个棋位便有了轨道属性 （i，j，g，b）,东北大学机器博弈研究室,引进扩展棋盘（Extended Board）,描述圆弧的连接关系，可以引进扩展棋盘,,,东北大学机器博弈研究室,,将棋盘坐标填入，即得：,,,东北大学机器博弈研究室,飞行着法描述,转入对应的圆弧变换后的棋位，继续飞行； 转入对应的圆弧变换后的棋位，继续飞行； 转入对应的圆弧变换后的棋位，继续飞行； 转入对应的圆弧变换后的棋位，继续飞行；如果圆弧变换关系为（0,0），则为非法飞行；,东北大学机器博弈研究室,检查着法合理性,如果飞行到达的有子棋位为本方棋子，则为非法飞行； 如果飞行到达的有子棋位为对方棋子，则为吃子着法; 如果在飞行轨道上没有可以吃掉的对方棋子，则不能飞行，只能走子。

东北大学机器博弈研究室,飞行着法生成,判断是否在外轨或内轨上，如果不在，不考虑飞行； 在，首先判断本轨线上是否有对方棋子，如果没有，不必飞行； 有，吃子标识置0，向上下左右四个方向一步步地飞行； 每走一步，判断有子无子？有子则止，改变飞行方向； 无子则继续前行，到达边缘，延轨道改变前进方向，进入新的直线，吃子标识置1，并记载变向点；（有可能多次改变前进方向） 每走一步，判断有子无子？有子，再判断是否是对方的子？是，则构成吃子，完成“提、动、落、吃”，着法完成； 每走一步，判断有子无子？有子，再判断是否是对方的子？不是，则为非法着法改变飞行方向 如果上下左右四个方向都搜索完成，则结束飞行着法生成凡是可行的飞行着法都是吃子着法！记载提、落址和变向点东北大学机器博弈研究室,着法格式,象棋着法构成：提址，动子，落址，吃子 本棋不分兵种，动子无意义，提址对应动子； 如果是飞行着法，落址便对应被吃掉的子（吃子） 走行着法：（提址，落址） 飞行着法：（提址，变向点1，变向点2…，落址） 着法格式可以统一到 （（提址，落址，吃子标识），（变向点集合）），令吃子标识用S表示 如果吃子标识S=1，则调出变向点集合，并且在落址处清除对方棋子。

变向点的作用是供对战平台演示棋子飞行路线的东北大学机器博弈研究室,着法描述协议,按右图编码给出：(提址落址S)(变向点…) 变向点仅记录飞出点坐标 记录棋谱是按回合排列，并有回合序号 为了简单起见，棋谱中也可以省去变向点集合东北大学机器博弈研究室,棋谱举例,东北大学机器博弈研究室,一维数据结构方案,0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,12, 13, 14, 15, 16, 17,18, 19, 20, 21, 22, 23,24, 25, 26, 27, 28, 29,30, 31, 32, 33, 34, 35,棋盘编码：,-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0,1, 1, 1, 1, 1, 1,1, 1, 1, 1, 1, 1,,兵种编码：,Board[36]=,东北大学机器博弈研究室,,1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,IDBoard[36]=,Pieces[24]=,0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35,初始局面棋子编码矩阵：,初始局面棋子位置矩阵：,东北大学机器博弈研究室,2, 3, 8, 9, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23,26, 27,32, 33,ExternalLoop[24]={12, 13, 14, 15, 16, 17, 3, 9, 15, 21, 27, 33, 23, 22, 21, 20, 19, 18,32, 26, 20, 14, 8, 2},0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,12, 13, 14, 15, 16, 17,18, 19, 20, 21, 22, 23,24, 25, 26, 27, 28, 29,30, 31, 32, 33, 34, 35,棋盘编码：,外轨棋位：,外轨回路：,1, 4, 6, 7, 8, 9, 10, 11,13, 16, 19, 22,24, 25, 26, 27, 28, 29,31, 34,内轨棋位：,InternalLoop[24]={6, 7, 8, 9, 10, 11,4, 10, 16, 22, 28, 34,29, 28, 27, 26, 25, 24,31, 25, 19, 13, 7, 1},内轨回路：,东北大学机器博弈研究室,需要考虑的问题,走行着法可以采用预置表法； 飞行着法生成采用棋盘扫描法可行，但是耗时太多，应该考虑更好的算法； 轨道最好采用环形数据结构来描述； 同一个轨道，有四个飞行方向，是否需要4个环？ 应用位棋盘，首先判断环上有无对方棋子？有则搜索，无则停止； 如何通过位棋盘运算很快找到提址和落址，找到飞行着法？,东北大学机器博弈研究室,着法排序,每个棋子都可能有走行着法和飞行着法，二者之和构成该棋子的全部着法。

在对阵平台上轮到棋手走棋时，应以绿点标出全部着法 对于搜索引擎需要给出着法排序显然，吃子着法优于非吃子着法 对于能够吃掉同一个对方棋子的着法如何选择？ 什么情况下具备吃子条件也不吃子？ 局面评估的深入研究会给出更好的着法排序东北大学机器博弈研究室,博弈技术总结,有没有和棋的可能？ 进攻与防卫 占轨策略 连续换子策略,东北大学机器博弈研究室,机器博弈需要进一步考虑的问题,棋局表述 着法表述“提-动-落-吃”？可以省略？ 对战平台，通信协议 棋局评估：固定子粒值？棋子位置值？灵活度值？相互配合值？…… 搜索算法的选用 棋谱保留与复盘 循环的判断 位棋盘技术的使用,东北大学机器博弈研究室,下一步如和进行？,选好棋种后，熟悉下棋，达到可以和现存软件进行对弈互有胜负的水平，从中摸索对弈技巧； 尽量查找相关参考文献； 学习C语言，掌握牛角棋博弈程序； 了解对阵平台，规范通信协议； 运用所学的知识，编写所选棋种的博弈程序（参照软件工程学）； 不断优化提高，要有推倒重来的思想准备东北大学机器博弈研究室,在游戏软件的编写中 提高素质！ 让创新的火花 在机器博弈中迸发！,联系：computergames@ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,IDBoard[36]=,Pieces[25]=,INVALID, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35,初始局面棋子编码矩阵：,初始局面棋子位置矩阵：,东北大学机器博弈研究室,2, 3, 8, 9, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23,26, 27,32, 33,ExternalLoop[24]={12, 13, 14, 15, 16, 17, 3, 9, 15, 21, 27, 33, 23, 22, 21, 20, 19, 18,32, 26, 20, 14, 8, 2},Mapping1[36]=,{ U, U, 23, 6, U, U, U, U, 22, 7, U, U, 0, 1, 2, 3, 4, 5, 17, 16, 15, 14, 13, 12, U, U, 19, 10, U, U,U, U, 18, 11, U, U},0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,12, 13, 14, 15, 16, 17,18, 19, 20, 21, 22, 23,24, 25, 26, 27, 28, 29,30, 31, 32, 33, 34, 35,。