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

1、东北大学机器博弈研究室,苏拉卡尔塔棋博弈技术分析,徐心和东北大学机器博弈研究室2009.5,东北大学机器博弈研究室,“苏拉卡尔塔”规则,棋盘棋子 1）横竖各6条边构成正方形棋盘，36个交叉点为棋位，各边由8段圆弧连接，通常用2种不同颜色表示。 2）红黑双方各12枚棋子。初始状态：棋子在各方底线排成2排。玩法 1）双方轮流走棋，每次走动一枚棋子； 2）除了吃子之外，每枚棋子只能沿着垂直或对角方向走动一格，只能走向空位； 3）吃对方子时必须经过至少一个完整的弧线。胜负：1. 吃掉所有对方棋子一方获胜； 2. 进入循环，剩余棋子多的一方获胜。,东北大学机器博弈研究室,东北大学机器博弈研究室,棋盘的数

2、字表示,用66的方阵只能表示棋位，没有表示相互的关系,东北大学机器博弈研究室,棋子的数字表示,兵种定义：黑子为-1，红字为1，无子为零。则初始局面为,东北大学机器博弈研究室,棋局表示,东北大学机器博弈研究室,着法表示,走行（前进一步的不吃子着法）： 横向（左、右） 竖向（上、下） 斜向（四个方向） 落址在棋盘内并为空位，才为有效的可行着法。可以采用预置表法实现着法生成吃子？这里关键是吃子！需要调整棋盘数据结构，因为没有表示出圆弧的连接关系。吃子可以定义为飞行，因为必须经过圆弧。,东北大学机器博弈研究室,飞行是有轨道的,轨道有两种：绿轨，圆弧在外圈，可以称之为外轨，用字母g表示。g=1，该棋位在

3、外轨；蓝轨，圆弧在内圈，可以称之为内轨，用字母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）,描述圆弧的连接关系，可以引进扩展棋盘,东北大学机器博弈研究室,将棋盘坐标填入，即得：,东北大学机器博弈研究室,飞行着法描述,转入对应的圆

4、弧变换后的棋位，继续飞行； 转入对应的圆弧变换后的棋位，继续飞行； 转入对应的圆弧变换后的棋位，继续飞行； 转入对应的圆弧变换后的棋位，继续飞行； 如果圆弧变换关系为（0,0），则为非法飞行；,东北大学机器博弈研究室,检查着法合理性,如果飞行到达的有子棋位为本方棋子，则为非法飞行；如果飞行到达的有子棋位为对方棋子，则为吃子着法;如果在飞行轨道上没有可以吃掉的对方棋子，则不能飞行，只能走子。,东北大学机器博弈研究室,飞行着法生成,判断是否在外轨或内轨上，如果不在，不考虑飞行；在，首先判断本轨线上是否有对方棋子，如果没有，不必飞行；有，吃子标识置0，向上下左右四个方向一步步地走行；每走一步，判断有

5、子无子？有子则止，改变飞行方向；无子则继续前行，到达边缘，延轨道改变前进方向，进入新的直线，吃子标识置1，并记载变向点；（有可能多次改变前进方向）每走一步，判断有子无子？有子，再判断是否是对方的子？是，则构成吃子，完成“提、动、落、吃”，着法完成；每走一步，判断有子无子？有子，再判断是否是对方的子？不是，则为非法着法。改变飞行方向。如果上下左右四个方向都搜索完成，则结束飞行着法生成。 凡是可行的飞行着法都是吃子着法！记载提、落址和变向点。,东北大学机器博弈研究室,着法格式,象棋着法构成：提址，动子，落址，吃子本棋不分兵种，动子无意义，提址对应动子；如果是飞行着法，落址便对应被吃掉的子（吃子）走

6、行着法：（提址，落址）飞行着法：（提址，变向点1，变向点2，落址）着法格式可以统一到 （提址，落址，吃子标识），（变向点集合），令吃子标识用S表示。如果吃子标识S=1，则调出变向点集合，并且在落址处清除对方棋子。变向点的作用是供对战平台演示棋子飞行路线的。,东北大学机器博弈研究室,着法描述协议,按右图编码给出： (提址落址S)(变向点)变向点仅记录飞出点坐标记录棋谱是按回合排列，并有回合序号。为了简单起见，棋谱中也可以省去变向点集合。,东北大学机器博弈研究室,棋谱举例,东北大学机器博弈研究室,一维数据结构方案,0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,

7、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,兵种编码：,Board36=,东北大学机器博弈研究室,1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 0, 0, 0, 0, 0, 0,

8、0, 0, 0, 0, 0, 0,13, 14, 15, 16, 17, 18,19, 20, 21, 22, 23, 24,IDBoard36=,Pieces24=,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,ExternalLoop24= 12, 13,

9、 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,

10、 31, 34,内轨棋位：,InternalLoop24= 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个环？应用位棋盘，首先判断环上有无对方棋子？有则搜索，无则停止；如何通过位棋盘运算很快找到提址和落址，找到飞行着法？,东北大学机器博弈研究室,着法排序

11、,每个棋子都可能有走行着法和飞行着法，二者之和构成该棋子的全部着法。在对阵平台上轮到棋手走棋时，应以绿点标出全部着法。对于搜索引擎需要给出着法排序。显然，吃子着法优于非吃子着法。对于能够吃掉同一个对方棋子的着法如何选择？什么情况下具备吃子条件也不吃子？占位分值？局面评估的深入研究会给出更好的着法排序。,东北大学机器博弈研究室,参考文献,1 Neill Graham. Artificial Intelligence-Make machines “think”.TAB BOOKS,19792 Murray Campbell.Algorithms for the parallel search of

12、 game trees.Masters thesis.Canada:Department of Computing Science,University of Alberta,August 19813 T.Anthony Marsland.A review of game tree pruning.ICCA Journal,March 1986,9(1):3194 Rivest,R.L.Game Tree Searching by MinMax Approximation.Artificial Intelligence, 1998, Vol.34,No.1,2018/10/15,23,东北大学机器博弈研究室,在游戏软件的编写中提高素质！让创新的火花在机器博弈中迸发！,联系：,