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

苏拉卡尔塔棋博弈技术分析 苏拉卡尔塔 规则 棋盘棋子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 引进扩展棋盘 ExtendedBoard 描述圆弧的连接关系 可以引进扩展棋盘 将棋盘坐标填入 即得 飞行着法描述 转入对应的圆弧变换后的棋位 继续飞行 转入对应的圆弧变换后的棋位 继续飞行 转入对应的圆弧变换后的棋位 继续飞行 转入对应的圆弧变换后的棋位 继续飞行 如果圆弧变换关系为 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个环 应用位棋盘 首先判断环上有无对方棋子 有则搜索 无则停止 如何通过位棋盘运算很快找到提址和落址 找到飞行着法 着法排序 每个棋子都可能有走行着法和飞行着法 二者之和构成该棋子的全部着法 在对阵平台上轮到棋手走棋时 应以绿点标出全部着法 对于搜索引擎需要给出着法排序 显然 吃子着法优于非吃子着法 对于能够吃掉同一个对方棋子的着法如何选择 什么情况下具备吃子条件也不吃子 占位分值 局面评估的深入研究会给出更好的着法排序 参考文献 1 NeillGraham ArtificialIntelligence Makemachines think TABBOOKS 1979 2 MurrayCampbell Algorithmsfortheparallelsearchofgametrees Master sthesis Canada DepartmentofComputingScience UniversityofAlberta August1981 3 T AnthonyMarsland Areviewofgametreepruning ICCAJournal March