国际跳棋AI

大一上学期作业项目，用C语言实现一个有一定棋力的国际跳棋AI。

首先：传 统 艺 能

：建议雇一批人日夜破坏嘉定电网

：建议连夜盗取某曾姓dl的代码

：大家好，我叫zch。其实我叫什么名字并不重要，你叫我神也可以，叫我渣男也可以，反正你知道我是同济大学2019级新生院最牛B的那个人就可以了。

知乎刚学了2个月C语言的萌新如何写出国际跳棋程序？

好了皮完了进入正题：

成绩

在dl们更新代码的间隙体验了一把榜一，蛮爽的:sleeping:。

最终只有Rank11，比较菜。

仓库

GitHub仓库地址

游戏规则与平台说明

下面一大大大大大段是俺抄的助教写的说明。

项目简介

该项目是个人项目，学生需要独立完成。学生需要使用 C 语言实现一个“国际跳棋”走子程序（以下称为大脑程序），使用 stdin 来接收对手落子情况、通过计算后使用 stdout 输出自己的落子（见输入输出格式）。算法不限，但有时间和内存上的限制（见比赛规则）。

学生需要将大脑程序的源码递交到指定的在线评测平台。平台会对所有同学的大脑程序两两进行机-机“国际跳棋”对抗比赛。比赛获胜方可获得积分。学生在该项目中取得的最终成绩取决于在平台上比赛总积分的名次（见排名和评分规则）。

对抗规则

1. 每个大脑程序都会与其他学生的大脑程序各进行一场比赛，每场比赛都有多局。
2. 为了确保公平性，每一场比赛都进行偶数局，对于一方来说，其中一半的局执黑、一半的局执白。

比赛规则

本规则是标准国际跳棋规则的简化版。

1. 对局采用 8 * 8 绿白棋棋盘，见“附录-棋盘”
2. 对局开始时，每方各12颗棋子，摆放在最下或者最上的三行中，每行仅在绿色格子中摆放棋子。见“附录-初始局面”。
3. 黑子先行，双方轮流操作。每次操作，可以移动自己的一枚棋子到周围的空棋位，移动的方向为向前的2个斜线方向，每次只能移动一格。示例见“附录-棋子移动”
4. 吃子的规则如下，具体的示例如附录所示：
   1. 吃掉棋子的移动是沿着对角线跨过被对手的棋子占领的方格直接跳到紧接着的空方格上。吃掉棋子的移动叫做“跳”。这个吃掉棋子的移动完成后，被吃掉（跨过）的棋子要从棋盘上拿掉。见“附录-吃子”
   2. 有吃必吃：如果遇到能吃掉对方棋子的机会，那么必须吃掉对方棋子。
   3. 有多吃多：对弈时如果出现一枚棋子(或多枚棋子)同时可以顺着两条(或多条)路线去吃对方棋子的情况时，吃子方必须选择吃子数量最多的路线行棋，而不能考虑哪条路线对自己有利。
   4. 一次取净：吃多枚棋子时，必须要在跳跃结束后，一次将被吃的棋子顺序或倒序逐个全部从棋盘上取走，不能跳一枚，取一枚。
   5. 不准重跳：当在对局中，如果遇到：一方可按两条(或多条)路线吃对方的棋子时，在吃子的过程中不能两次(也包括多次)吃掉和跳过一枚棋子。
5. 行棋过程中，在己方棋子到达对方侧的底线前，己方棋子只能向前移动；当一颗棋子到达了对方底线之后，这颗棋子可以向任意向的斜线移动，移动步数仍为1步。注意，此处与标准国际跳棋规则中不同
6. 吃子不受方向的限制。
7. 轮到己方走子时，大脑程序需要在2秒时间内给出落子方案。
8. 每一局游戏最多进行60个回合，
   1. 如果在60回合之前，有一方棋子都被吃掉，或者所有己棋都无法移动，则对方获胜。
   2. 如果达到60回合，则按棋盘上剩余棋子的局面判断胜负：
      1. 每个到达对方底线的棋子计3分，其余棋子计1分
      2. 分数高者获胜
9. 每一局中，己方不能使用超过 90 秒的总时间（对方走子时不算己方用时）。
10. 大脑程序任何时刻都不能使用超过 350 MB 的内存。
11. 在对方走子时，己方的程序会继续保持运行。

注意：

1. 若某一方首先超出时间限制或空间限制，或程序异常退出，则判该局这一方负。
2. 学生递交的代码会在云平台上运行，视平台任务压力不同，助教可能随时调整硬件配置调节压力，因此代码需要能在不同的 CPU 配置下都不超过时间限制。
3. 大脑程序将绑定在一个 CPU 核心上运行，因此使用多线程不会带来速度提升。
4. 大脑程序将运行在沙盒中，互相隔离，没有文件读写权限。调用被限制的函数可能会导致异常退出。

排名和评分规则

1. 项目截止时间为十六周周日（12月22日）晚23:59，答辩时间为第十七周
2. 对于每一场比赛，赢得局数较多的一方获得该场比赛胜利，另一方负，否则平。
3. 胜一场比赛获得 3 积分；平一场比赛获得 1 积分；负一场比赛不获得积分。
4. 一个同学的总积分是其大脑程序与其他同学最新大脑程序比赛的积分总和。
5. 学生可以递交多次大脑程序，每次递交都会重置总积分，即总积分会按照最新一次递交的程序累计。
6. 为了避免资源被滥用，每个学生有递交频率上限，包括每两次递交代码的最短间隔限制，和今日代码已消耗时间的限制。这些频率上限会随时调整，调整时会在 QQ 群公告；学生也可以在[在线评测平台][portal]的递交界面里看到当前递交频率限制。
7. 学生递交的代码不得超出 1 MB 大小。一般情况下代码不会长到超出这个限制。
8. 学生在该项目中的成绩取决于以下因素：
   • 主要因素：项目截止时的总积分排名（排名越高则成绩越高，反之亦然）
   • 次要因素：答辩情况
9. 学生需确保最终代码的美观、可读，包括拥有一致的缩进、一致的变量命名、良好的代码组织、尽可能避免重复代码等，否则将视情况至多扣除总分的 30% 分数。
10. 学生任何时刻不得抄袭网上现有代码或其他学生代码（包括非最终版代码），一经发现并核实，本门课将直接以作弊处理。

输入输出格式

学生的国际跳棋大脑程序需要从标准输入 (stdin) 接收指令，并相应地做出响应，将响应输出到标准输出 (stdout)。每一个指令都独占一行。大脑程序的响应也需要独占一行（即跟随一个换行符 \n）。以下是大脑程序需要支持的指令：

START [FIELD]

在开始对局前，大脑程序一定会收到该指令，指令表明了己方有关的信息。FIELD 代表该己方大脑执子颜色，FIELD 为 1 时代表己方执黑棋，FIELD 为 2 时代表己方执白棋。

收到该指令后，大脑程序需要在1秒响应 OK，否则判负。

示例

平台发送指令：

START 1

大脑程序回复：

OK

PLACE N [X1,Y1] [X2,Y2] … [XN,YN]

该指令代表一次对手的行棋，N表示本次行棋中棋子共经过的格子数，X1、Y1 是对手要移动棋子的行列坐标（坐标从 0 开始），X2 、Y2是棋子要移动到的行列坐标，以此类推。

大脑程序不需要回复该指令。

对于一次棋子的移动，X和 Y用,（英文逗号）分隔；如果对手连续移动棋子，则每次落子之间用空格隔开。

示例

平台发送指令：

PLACE 3 1,1 3,3 1,5

大脑程序不需要回复。

TURN

该指令代表轮到己方操作。大脑程序收到该指令后，经过计算得出己方走子，并将要移动棋子经过的格子数，每个格子的行坐标、列坐标以逗号分割作为响应内容，如果连续移动棋子，则每次移动的指令间用空格隔开。大脑程序需要在指定时限内做出走子响应，否则判负。

该指令可能直接出现在 START 指令之后，即己方执黑棋开局；也可能出现在一次 PLACE 指令之后，即对手落子完毕轮到己方落子。注意，若对手落子完毕后游戏直接结束，则 PLACE 指令之后不会跟随有 TURN 指令。

示例

平台发送指令：

TURN

大脑程序回复：

3 7,7 5,5 3,3

END [FIELD]

代表该局比赛结束，其中 FIELD 代表获胜方，FIELD 为 0 时是平局，FIELD 为 1 时是己方获胜，为 2 时是对方获胜。在收到该指令后，大脑程序不需要做任何响应，可以自行决定是否要退出程序（在评测时，无论大脑程序是否主动退出，它最后都会被关闭）。该指令可能在任何时刻出现，例如出现在 BEGIN 前的话，可能是对手程序崩溃导致的这场比赛直接结束。

特别注意：在大脑程序启动后、没收到该指令前，大脑程序的自行提起退出将会导致被判负。

示例

平台发送指令：

END 1

大脑程序不需要回复。

调试指令

为了方便调试，大脑程序可以在任何时刻输出 DEBUG [MESSAGE]（需要独占一行，且不能超出一行）。该内容将会被记录到日志，而不会被平台处理。学生可以在平台上下载到完整的日志从而方便调试 bug。大脑程序可以调试输出任意多次，但单条 MESSAGE 不能大于 16 KB（超出部分会被截断）且所有 MESSAGE 累计不能超过 32 KB（超出部分会被忽略），而不会记录到日志。

注意：该输出不能替代其他任何指令的响应。例如收到 TURN 指令后，需要响应一个坐标，那么输出 DEBUG [MESSAGE] 后，大脑程序仍然需要继续输出坐标。

示例

大脑程序输出：

DEBUG Hello World!

直接终止判负的情况

以下是一部分可能导致比赛中途终止直接结束并判负的情况。

在不允许响应的情况下响应

例如，己方刚刚响应完 TURN 指令，需要等待下一个 TURN 之后再走子。若此时己方继续输出内容（调试输出除外），则直接判负。

响应内容格式不正确或无效走子

例如，对于 TURN 指令，己方需要响应一对空格分割的坐标和要移动的方向。若响应的内容格式不正确（调试输出除外），则直接判负。若响应的坐标在棋盘以外，或指定的位置处没有我方棋子，或者要移动后的新的位置不是空棋位，则也判负。

超出时间限制或空间限制

时间限制包括单个指令的时间限制和总时间限制。对于 START 指令，需要在 52秒内响应；对于 TURN 指令，需要在指定的单步走子时间内响应，见比赛规则。总时间限制同样见比赛规则，它的计算从 START 开始，到 END 结束，期间对方落子时不计时间。

程序自身崩溃

由于各种原因（如访问无效内存地址）程序崩溃了，则该局直接判负。

编程注意事项

1. scanf 函数在没有数据可供读取时会阻塞，因此请勿在不该读取指令的时候读取指令。例如轮到你的 AI 输出了，却执行了一句 scanf，那么你的程序就会无限等待下去直到超时。
2. 大多数情况下，printf 的输出会被缓存而不会立刻输出，这会导致超时。可以使用 fflush 函数解决这个问题：请在 printf 后紧跟语句 fflush(stdout) 来刷新缓冲区。
3. 若想利用对方走子的时间进行计算，你可能需要使用多线程技术。由于平台环境是 Windows，因此建议使用 Windows 平台下相关 API 以免出现不兼容情况。
4. 特别提醒：若要使用高级算法，请确保能在答辩时应对关于该算法的提问，否则将被视为抄袭。

在线评测平台操作说明

1. 在电脑上使用较新版本 Chrome 或 Firefox 浏览器打开平台地址http://202.120.167.41:99 。
2. 点击导航栏右上角 “Sign In” 按钮登录，用户名和密码都是你的学号（若无法登录，请联系群里的助教）。
3. 若你是第一次登录，会要求你修改到一个新密码，以免账号被别人冒用。另外还会要求你输入一个昵称。这个昵称会显示在首页的记分牌上，所有人都能看得见，且以后也可以随意修改。
4. 导航栏上点击 Scoreboard 可以看到记分牌，即当前的总积分排名。记分牌十分钟更新一次。
5. 导航栏上点击 Submission 后，右侧菜单中可以切换界面到你自己的递交记录（My Submissions）、别人的递交记录（All Submissions）或递交新代码（Submit New Brain）的页面。
6. 递交新代码时，请将你的代码合并到一个单一文件中进行递交，不支持递交多个文件。你还可以选择不同的编译器。

评测环境

计划于2019-11-17日前完成并上线，同时发布样例代码。

参考资料

1. 国际跳棋比赛规则
2. 国际跳棋试玩
3. 计算机博弈

思路

1. 实现一个能下棋的AI，首先得按规则下棋。
2. 按规则下棋这件事要怎么在程序中去模拟~~(款爷腔)~~？
3. 通过什么东西能让它好好下棋棋。

储存与着法

首先要实现能下棋，那就要解决这些问题：

1. 如何表示棋盘？
2. 如何枚举合法的走棋？
3. 如何更新棋盘？
4. 如何走子？
5. 如何连吃？

一旦解决了表示和枚举的问题，就会发现走子只是一个简单的更新棋盘，吃子则是一个稍微复杂一点的BFS模型。因此关键是解决前面的问题。

针对这个问题，在学习了xqbase中的数据结构和着法相关的做法后，我大概设计了两种方案，都写了一下，但是后期考虑到回溯和置换表的具体实现，最后选择了方案二。

方案一：

0x88判别数组

0x88判别是对naive版本的二维数组表示棋盘，数组取值表示棋子类型的改进版本，可以用一个位运算代替所有繁琐的关于棋子是否在棋盘内的判断，它的工作原理是对棋盘进行特定的间隔编号。除了在枚举的时候可以简化边界判断，其他的内容就比较常规了。这种做法在更新棋盘、枚举等操作上，花费的时间还是挺多的。

编号规则

设行号为row，列号为col的棋盘格子在数组中的索引为index

若使row和col取值为0到7，且index=(row<<4)|col

则易得：棋子在棋盘中等价于!(index&0x88)

证明

由index的定义易得合法的index从低到高第4位、第8位、符号位这三个位上的二进制恒为0。

现在对格子进行移动，设移动前的格子到移动后的格子的直观移动距离为delta格，则合法的delta取值为1到8。那么总共有两种情况：

1. 左右移动

   由规则，index变为index±delta，如果超出棋盘，后三位以外的二进制位就会参与运算，但是无论是进位或者借位都会使第4位成为1，因此可以借助二进制00001000判断左右移动情况。

2. 上下移动

   由规则，index变为index±(delta<<4)，如果超出棋盘，结果会符号位或者第8位为1，因此可以借助二进制10000000判断上下移动情况

综上所述，只需要位与二进制10001000，即0x88即可做出综合判断

方案二：

位棋盘

位棋盘。一听名字就很强。这种做法是把每一种类型的棋子占据的总棋盘看作整数，整数的每一位对应着这一位置上改类型棋子的占有情况。位棋盘可以大大减小整个模拟过程中的空间开销，在本规则下，每种特定的棋的局面用黑、白、王三个64位整数就可以完全表示出来。但是这种做法会让本来很显然的挪子变得比较复杂，我们来具体分析：

棋子有两种移动，一种是斜1格，一种是斜2格。如果能够提取出整个棋盘中我们想移动的确定的子，那么移动就会变成很简单的位移运算。但是这里有一点问题，有些处于边界的棋子不应该移动，否则位移后的棋盘并不是合法的，所以需要在移动之前考虑到这些棋子。由于棋盘的边界、死角和对应的移动我们都是可以提前推测的，所以可以预处理出针对某移动不合法的棋子，在使用的时候趁早排除。

强化版本

“还能不能再给力点呢？”

当然可以了。

本项目的跳棋非常特殊，整个棋盘只有一般的位置是有效的，以下是真正有用的格子连起来的图。

所以俺脑补了一个把64位棋盘搞成32位的变化。把棋盘中的没用格子全部去掉，然后左对齐，按照行数整除2的商分类，同商等齐，不同商依次突出1格。

发现这些黑色的连线还是自相似的。于是经过一点小小的运算，借助列的奇偶性和用来去除死角的常量数组，就能发现棋子的移动还是可以用非常优雅的位运算表示的。于是我们非常完美的把unsigned long long运算简化成了32位int运算。

搜索

我们已经摸清楚了怎样让程序按规则走棋，现在的任务是让他真正的会下棋。

怎样让他会下棋呢？

让他把能走的所有情况都走一遍，然后挑出最好的一步，称之为搜索。

由于这是博弈游戏，对方也一定会做出比较有利于他的判断，所以我们认为每一次对方也走出最好的一步，这就是MinMax搜索。

没错，就是这么粗暴。

因为给出了时间和空间限制，所以我们的搜索肯定是不完全的，或许只能搜索完几步后的结果。我们接下来的所有工作，都是围绕着怎样让他的搜索结果尽量准确进行。

估值

我们搜到最深的地方后，怎样评估局面的好坏呢？

就是用估值函数来评估。

这里写的估值比较菜，只考虑了子力和行的位置和边界死角区域对于棋子价值的影响。

但是考虑到我们的搜索一直在不停的交换执子方，所以我们的局面估计应该是相对于执子方的。为了方便的转换估值的参考，我们将估值函数设计为两方棋子打分之差，那么转换参考就是添加一个符号的事情了。

AlphaBeta剪枝

思考一下我们的搜索过程，会发现有一个优化的策略可以减少搜索量。

考虑一个情景：

你的死敌面前有很多口袋，他和你打赌赌输了，因此他必须从中给你一样东西，而挑选规则却非常奇怪：

每个口袋里有几件物品，你能取其中的一件，你来挑这件物品所在的口袋，而他来挑这个口袋里的物品。你要赶紧挑出 口袋并离开，因为你不愿意一直做在那里翻口袋而让你的死敌盯着你。

假设你一次只能找一只口袋，在找口袋时一次只能从里面摸出一样东西。

很显然，当你挑出口袋时，你的死敌会把口袋里最糟糕的物品给你，因此你的目标是挑出“诸多最糟的物品当中是最好的”那个口袋。

我们从第一个口袋开始，看每一件物品，并对口袋作出评价。比方说口袋里有一只花生黄油三明治和一辆新汽车的钥匙。你知道三明治更糟，因此如果你挑了这只口袋就会得到三明治。事实上只要我们假设对手也会跟我们一样正确评价物品，那么口袋里的汽车钥匙就是无关紧要的了。

现在你开始翻第二个口袋，这次你采取的方案就和最小-最大方案不同了。你每次看一件物品，并跟你能得到的最好的那件物品(三明治)去比较。只要物品比三明治更好，那么你就按照最小-最大方案来办——去找最糟的，或许最糟的要比三明治更好，那么你就可以挑这个口袋，它比装有三明治的那个口袋好。

比方这个口袋里的第一件物品是一张20美元的钞票，它比三明治好。如果包里其他东西都没比这个更糟了，那么如果你选了这个口袋，它就是对手必须给你的物品，这个口袋就成了你的选择。

这个口袋里的下一件物品是六合装的流行唱片。你认为它比三明治好，但比20美元差，那么这个口袋仍旧可以选择。再下一件物品是一条烂鱼，这回比三明治差了。于是你就说“不谢了”，把口袋放回去，不再考虑它了。

无论口袋里还有什么东西，或许还有另一辆汽车的钥匙，也没有用了，因为你会得到那条烂鱼。或许还有比烂鱼更糟的东西(那么你看着办吧)。无论如何烂鱼已经够糟的了，而你知道挑那个有三明治的口袋肯定会更好。

这种情景下，我们得到了AlphaBeta剪枝。

由MinMax树轮流下子的性质和DFS的先序性，让Alpha代表当前能搜索到的对手认为最好的值，即我们看来最差的值，beta为能搜索到的我们认为最好的值。发现当敌人采取了某种着法后，我们进入了一个节点：

如果当前正节点的所有延申局面中存在一个比前面曾经搜索到的我们认为最好的局面还要好，那么我们至少都会选择当前延申局面，甚至更好的局面。

而我们的敌人当然不希望这样的情况发生，所以它一定会避免我们进入这个节点，所以这个节点中所有的延申都是不必要的。

这样的节点可以直接剪掉。

AlphaBeta剪枝非常依赖于已经得到的结果的好坏，换言之非常依赖于搜索树的结构。如果已经搜到了很好的值，那么剪枝会帮我们回避掉大部分的冗余搜索，最好的情况下可以缩减到根号级别的规模。但是如果我们迟迟搜不到好的值，整个树的展开就非常的庞大了。因此接下来的优化我们主要针对搜索树的结构，让更好的值倾向于更早的出现。

着法排序

最简单的优化搜索树的结构的办法，就是让生成的局面按照当前的估值做一个排序。但是这种对搜索树的组织是非常静态的，如果估值和我们开了个小玩笑，让真正好的深层局面藏在搜索树的非常后端，那这对我们的搜索是非常不利的。

置换表和迭代加深

所以考虑对搜索树动态的组织。通过迭代加深，我们进行深度递增的搜索，从而充分利用时间。但是迭代加深真正的妙处，是在一层搜索和另一层更深的搜索之间产生了联系。如果我们有办法基于浅层搜索的结果进行更深的搜索，那么整个树的组织就会是动态的了，每一次搜索都是对搜索树的重构。所以我们需要一个可以储存所有搜索结果的表，用来动态的排出相对好的搜索顺序。这就是置换表了。

但是现实其实是非常骨感的。置换表会带来非常严重的问题：

1. AlphaBeta剪枝下的搜索，往往会返回一些不够好或者过于好的值，我们只能知道这些值不是我们想要的，但是却不能知道他们到底是什么。在置换表中，这些模糊的值会和我们确切的搜到的值混淆，从而导致搜索顺序直接乱掉。因此置换表需要更加复杂的实现，来辨别各个值的情况。
2. 对每一个节点的每一个搜索结果都进行储存，题目中规定的内存明显是吃不消的。

因此，我们需要更简洁的解决方案。

主要变例和Pvs

不就是想要每次搜索的结果吗？我干嘛把所有搜索过程都存下来呢？

我们可以返回一个只通向结果的路径，这条路径称之为主要变例。有了浅层的主要变例，深层的搜索就有了指望。虽然和置换表相比，主要变例没有完美的记录每一个节点的决策顺序，但是他能用非常小的时间开销和空间开销，得到一个我们最满意的浅层结果。深层的搜索在这个结果的指引下至少不会非常的差，一旦有了新的结果，剩下的剪枝是很容易触发的。这样一层一层的搜索下去，整个搜索树甚至会有一种越搜越少的感觉。

解决了搜索树结构的问题，我们回过头来再看看搜索量。主要变例给我们提供了另一种减少搜索量的办法，叫做Pvs搜索。这种搜索的想法，是通过主要变例进行高效率的试探性搜索，以得知这个节点是否有完全搜索的必要。我们倾向于认为主要变例中的节点是每个节点最好的延伸局面，那让我们来验证到底是不是这样的。如果验证正确，那么这个节点最好也就是主要变例的结果了，可以进行一次AlphaBeta剪枝判断。如果试探失败，那么就老老实实的继续搜索。

未实现的想法

蒙特卡洛模拟

一种很有趣的不取决于规则的非对称式建树办法，通过模拟运行部分展开搜索树，通过选择函数兼顾未展开点和多次展开点的选择，但是考虑到内存和运行时间限制，没有进行具体的实现和测试。

更好的估值参数

据说估值是搜索的灵魂。

那么我的程序就是非常平庸的灵魂了

前面靠自己的下棋经验脑补出了一套兼顾子力，位置，杀手启发的估值。但是甚至还没有朴素估值厉害。调参数又费时间还麻烦，就没有再改进。所以估值函数非常的裸，没有一点点技术含量。

CNN自动调参

这个听说很厉害哦，可以用脚本语言写一个卷积神经网络，然后扒平台的对战数据自动调参。但是因为不会Python，也不会CNN，学习的时间不太够了，就没有继续研究。

自动横跳的更有效解决方案

因为规则简化的原因，这个游戏在进行到僵局的时候往往会发生地方我方反复横跳的问题。对于这个问题，解决方案是直接在结果已知反复横跳的情况下随机走一步，没有考虑到在搜索的过程中如何规避这种现象，这种解决显然不够成熟。

心路历程

这还是第一次写这么长的程序呢。

最直观的感受就是感觉写长程序和写算法题还是很不一样的，光变量命名就够让人头疼的了。这次的项目中坚决按照Google的StyleGuide写，虽然很不舒服，但是也算是稍微改掉了abc命名的坏习惯。

算法方面，这些计算机博弈算法的学习其实花了不少的时间，我自己对其中的一些算法也写了很多自己的理解。有些优化也是绞尽脑汁才脑补出来，非常的不容易，也很有成就感。

另外在这次项目中也学到了很多Debug的技巧，感觉收获还是很大的。

毕竟是大学时期的第一次大项目，有很多写的不够好的地方，希望下次写项目能有改进吧。

代码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
/*
CHESS is the type of the bitboard*/
typedef unsigned int CHESS;
/*
DEBUG=1 means the required chessboard while debugging will be printed.
DEBUG=0 means you are not debugging.*/
#define DEBUG 0
/*
MAXSIZE means the maximum size of the hash list.*/
#define MAXSIZE 2000010
/*
INFINITY means the maximum score you can get in the contest.*/
#define INFINITY 0x3f3f3f3f
/*
MOD is used in hash function.
Some other good mods:
1226959 1635947 2181271 2908361
3877817 5170427 6893911 9 191 891
12255871 16341163 21788233*/
#define MOD 1226959
/*
Make the rules of the chessboard side index as follows.*/
#define WHITE 0
#define BLACK 1
#define KING 2
/*
Make the rules of the absolute direction as follows.*/
#define UP 1
#define DOWN 0
#define OUTSIDE 1
#define INSIDE 0

/*
Make the rules of the relative direction as follows.*/
#define FORWARD 1
#define BACKWARD 0
#define LEFTWARD 1
#define RIGHTWARD 0
/*
Make the rules of the BFS queue index as follows.*/
#define MINE 0
#define ENEMY 1
#define POSITION 2

/*
Easily we know that <absolute direction>=<relative direction>^<side>.
Suppose that the chessboard in this program looks like this.
,,,,,,,,,,,,,,,,,,
| 0 x 0 x 0 x 0 x|7
| x 0 x 0 x 0 x 0|6
| 0 x 0 x 0 x 0 x|5
| x 0 x 0 x 0 x 0|4
| 0 x 0 x 0 x 0 x|3
| x 0 x 0 x 0 x 0|2
| 0 x 0 x 0 x 0 x|1
| x 0 x 0 x 0 x 0|0
''''''''''''''''''
  7 6 5 4 3 2 1 0
It is a reverse of the real chessboard.
Then delete all the useless position which labels 0.
,,,,,,,,,,
| x x x x|7
| x x x x|6
| x x x x|5
| x x x x|4
| x x x x|3
| x x x x|2
| x x x x|1
| x x x x|0
''''''''''
  3 2 1 0
In the end,make sure that the chessboard looks like this.
,,,,,,,,,
|xxxx   |7
|xxxx   |6
| xxxx  |5
| xxxx  |4
|  xxxx |3
|  xxxx |2
|   xxxx|1
|   xxxx|0
'''''''''
    3210
It can be represented with a 32 bit interger.
The bits goes like this:
31...28
27.....
.......
......4
3 2 1 0*/

/*
Receive a chessboard array and print it.*/
void Debug(const CHESS chessboard[])
{
    printf("DEBUG \nDEBUG ****************\nDEBUG ");
    for (int j = 0; j < 8; j++)
    {
        for (int i = 0; i < 4; i++)
        {
            if (!(j & 1))
                printf("0");
            printf("%d", (chessboard[1] & (1 << (CHESS)(4 * (7 - j) + 3 - i))) ? 2 : ((chessboard[0] & (1 << (CHESS)(4 * (7 - j) + 3 - i))) ? 1 : 0));
            if ((j & 1))
                printf("0");
        }
        printf(" %d", 7 - j);
        if (j == 7)
            printf("X");
        printf("\nDEBUG ");
    }
    printf("\nDEBUG ");
    for (int i = 7; i >= 0; i--)
        printf("%d", i);
    printf("\nDEBUG ");
    for (int i = 6; i >= 0; i--)
        printf(" ");
    printf("Y\nDEBUG ****************\nDEBUG\n");
    fflush(stdout);
}

/*
Parameters used to evaluate fuction*/
const int kEvaluateChess = 200;
const int kEvaluateKing = 125;
const int kEvaluateEdge = 20;
const int kEvaluateKingEdge = 50;
const int kEvaluateSide = 20;
/*
Constants used to generate moving method and evaluation.*/
const CHESS kCutMove[2][2] = {/**/{0xefefefe0, 0x0fefefef}, {0xf7f7f7f0, 0x07f7f7f7}/**/};
const CHESS kCutJump[2][2] = {/**/{0xeeeeee00, 0x00eeeeee}, {0x77777700, 0x00777777}/**/};
const CHESS kCutEdge = 0xf818181f;
const CHESS kCutSide[2] = {0xfff00000, 0x00000fff};
const CHESS kKing[2] = {0xf0000000, 0x0000000f};
const CHESS kEven = 0x0f0f0f0f;
/*
Variables used to control running time*/
long long clock_start;
long long clock_end;
long long time_limit;
/*
This array is used to save the output result.*/
CHESS output[150][3];
/*
This variable represents the color of gamer.*/
int my_side;
/*
Ths variable represents whether the time is about to running out.*/
int time_out;
/*
This variable counts the number of chess that ever fell on the chessboard.*/
int turn;
/*
This variable records the answer of last iteration.*/
int former_value;

typedef struct Methodlist
{
    CHESS chessboard[3];
    int value;
} METHOD;
METHOD method[2019];
/*
Array key saves the real index that point to the method array.
When sorting,we just swap the key instead of the whole chessboard.*/
int key[2019];
int method_index;

/*
Array queue is used to BFS and generate legal jumps.*/
CHESS queue[300][3];
int queue_head = 1;
int queue_tail = 0;

typedef struct Hashlist
{
    CHESS expect[3];
    int value;
    CHESS chessboard[3];
    int next;
} HASH;
/*
Array hash saves the most expected method of each chessboard node*/
HASH hash[MAXSIZE];
int hash_index;
int hash_head[2][MOD];

/*
Expect structure can bring back a most expected road after searching.*/
typedef struct Expect
{
    int size;
    CHESS chessboard[35][3];
} EXPECT;

/*
Receive a interger chessboard and return how many 1 in its binary.*/
int Count(CHESS chessboard)
{
    chessboard = ((chessboard >> 1) & 0x55555555) + (chessboard & 0x55555555);
    chessboard = ((chessboard >> 2) & 0x33333333) + (chessboard & 0x33333333);
    chessboard = ((chessboard >> 4) & 0x0f0f0f0f) + (chessboard & 0x0f0f0f0f);
    chessboard = ((chessboard >> 8) & 0x00ff00ff) + (chessboard & 0x00ff00ff);
    return (chessboard >> 16) + (chessboard & 0x0000ffff);
}

/*
Copy the from chessboard to the to chessboard.*/
void CopyChessboard(CHESS to[], const CHESS from[])
{
    to[WHITE] = from[WHITE];
    to[BLACK] = from[BLACK];
    to[KING] = from[KING];
}

/*
Receive the absolute direction and present chessboard then give the chessboard after a move.*/
CHESS Move(const CHESS position, const int horizontal, const int vertical)
{
    return vertical ? (position << (3 + horizontal + (1 ^ (!(kEven & position)))))
                    : (position >> (3 + (1 ^ horizontal) + (!(kEven & position))));
}

/*
Receive the absolute direction and present chessboard then give the chessboard after a jump.*/
CHESS Jump(const CHESS position, const int horizontal, const int vertical)
{
    return vertical ? (position << (7 + (horizontal << 1)))
                    : (position >> (7 + ((horizontal ^ 1) << 1)));
}

/*
Clear the queue.*/
void QueueReset(void)
{
    queue_head = 1;
    queue_tail = 0;
}

/*
Push a new chessboard into the queue.*/
void QueuePush(const CHESS state, const CHESS bridge, const CHESS position)
{
    ++queue_tail;
    queue[queue_tail][MINE] = state;
    queue[queue_tail][ENEMY] = bridge;
    queue[queue_tail][POSITION] = position;
}

/*
Pop a chessboard out of the queue.*/
void QueuePop(CHESS *state, CHESS *bridge, CHESS *position)
{
    (*state) = queue[queue_head][MINE];
    (*bridge) = queue[queue_head][ENEMY];
    (*position) = queue[queue_head][POSITION];
    queue_head++;
}

/*
Check out a jump in one position to one direction.*/
void OneDirectionJump(const CHESS enemy, const CHESS state, const CHESS bridge,
                      const CHESS position, const int horizontal, const int vertical)
{
    if (!((position & kCutMove[horizontal][vertical]) && (position & kCutJump[horizontal][vertical])))
    {
        return;
    }
    int move = Move(position, horizontal, vertical);
    int jump = Jump(position, horizontal, vertical);
    if ((move & (enemy ^ bridge)) && (jump & (~(state | enemy))))
    {
        QueuePush(state ^ (position | jump), bridge | move, jump);
    }
}

/*
Generate all jumps in all position and all direction.*/
int FindPossibleJump(const CHESS chessboard[], const int side)
{
    int start = method_index;
    CHESS generate = chessboard[side];
    CHESS state = chessboard[side];
    CHESS bridge = 0, position = 0;
    QueueReset();
    while (generate)
    {
        position = generate & ((~generate) + 1);
        QueuePush(state, 0, position);
        generate ^= position;
    }
    while (queue_head <= queue_tail)
    {
        QueuePop(&state, &bridge, &position);
        OneDirectionJump(chessboard[side ^ 1], state, bridge, position, side ^ LEFTWARD, side ^ FORWARD);
        OneDirectionJump(chessboard[side ^ 1], state, bridge, position, side ^ RIGHTWARD, side ^ FORWARD);
        OneDirectionJump(chessboard[side ^ 1], state, bridge, position, side ^ LEFTWARD, side ^ BACKWARD);
        OneDirectionJump(chessboard[side ^ 1], state, bridge, position, side ^ RIGHTWARD, side ^ BACKWARD);
    }
    if (!queue[queue_tail][ENEMY])
        return 0;
    while (Count(queue[--queue_head][ENEMY]) == Count(queue[queue_tail][ENEMY]))
        ;
    while ((++queue_head) <= queue_tail)
    {
        ++method_index;
        key[method_index] = method_index;
        method[method_index].chessboard[side] = queue[queue_head][MINE];
        method[method_index].chessboard[side ^ 1] = chessboard[side ^ 1] ^ queue[queue_head][ENEMY];
        method[method_index].chessboard[KING] = chessboard[KING] ^ (chessboard[KING] & queue[queue_head][ENEMY]);
        method[method_index].chessboard[KING] = method[method_index].chessboard[KING] & (chessboard[side] ^ queue[queue_head][MINE]) ? method[method_index].chessboard[KING] ^ (chessboard[side] ^ queue[queue_head][MINE]) : method[method_index].chessboard[KING];
        method[method_index].chessboard[KING] |= queue[queue_head][MINE] & kKing[side];
    }
    return method_index - start;
}

/*
Check out a move in one position to one direction.*/
void OneDirectionMove(const CHESS chessboard[], const CHESS position,
                      const int side, const int horizontal, const int vertical)
{
    if (!(position & kCutMove[horizontal][vertical]))
    {
        return;
    }
    CHESS move = Move(position, horizontal, vertical);
    if (!(move & (~(chessboard[side] | chessboard[side ^ 1]))))
        return;
    method_index++;
    move ^= position;
    key[method_index] = method_index;
    method[method_index].chessboard[side] = chessboard[side] ^ move;
    method[method_index].chessboard[side ^ 1] = chessboard[side ^ 1];
    method[method_index].chessboard[KING] = (chessboard[KING] & position) ? chessboard[KING] ^ move : chessboard[KING];
    method[method_index].chessboard[KING] |= method[method_index].chessboard[side] & kKing[side];
}

/*
Generate all moves in all position and all direction.*/
int FindPossibleMove(const CHESS chessboard[], const int side)
{
    int start = method_index;
    CHESS generate = chessboard[side];
    while (generate)
    {
        CHESS position = generate & ((~generate) + 1);
        OneDirectionMove(chessboard, position, side, side ^ LEFTWARD, side ^ FORWARD);
        OneDirectionMove(chessboard, position, side, side ^ RIGHTWARD, side ^ FORWARD);
        generate ^= position;
    }
    generate = chessboard[side] & chessboard[KING];
    while (generate)
    {
        CHESS position = generate & ((~generate) + 1);
        OneDirectionMove(chessboard, position, side, side ^ LEFTWARD, side ^ BACKWARD);
        OneDirectionMove(chessboard, position, side, side ^ RIGHTWARD, side ^ BACKWARD);
        generate ^= position;
    }
    return method_index - start;
}

/*
Transform a single chess chessboard into the coordinate of the chess.*/
int ChessToCoordinate(const CHESS state)
{
    int temp = 0;
    while (!(state & (1 << temp)))
        temp++;
    return (temp << 1) + !(((temp >> 2) & 1));
}

/*
Transform a coordinate into a chessboard.*/
CHESS CoordinateToChess(const int x, const int y)
{
    return (1 << ((y << 2) | (x >> 1)));
}

/*
Check out a possible jump path in one position to one direction.*/
void OneDirectionOutput(CHESS *position, CHESS *bridge, const int horizontal, const int vertical)
{
    if (!(((*position) & kCutMove[horizontal][vertical]) && ((*position) & kCutJump[horizontal][vertical])))
    {
        return;
    }
    if (Move(*position, horizontal, vertical) & (*bridge))
    {
        (*bridge) ^= Move(*position, horizontal, vertical);
        (*position) = Jump(*position, horizontal, vertical);
        int end = ChessToCoordinate(*position);
        printf(" %d,%d", end >> 3, end & 7);
        fflush(stdout);
    }
    return;
}

/*
Output the jump path.*/
void Output(const CHESS chessboard[], int side)
{
    int cnt = 2;
    CHESS temp = chessboard[side] ^ output[turn][side];
    CHESS bridge = chessboard[side ^ 1] ^ output[turn][side ^ 1];
    int start = ChessToCoordinate(chessboard[side] & temp);
    int end = ChessToCoordinate(output[turn][side] & temp);
    if (bridge)
    {
        printf("%d %d,%d", Count(bridge) + 1, start >> 3, start & 7);
        fflush(stdout);
        CHESS position = chessboard[side] & temp;
        while (bridge)
        {
            OneDirectionOutput(&position, &bridge, OUTSIDE, UP);
            OneDirectionOutput(&position, &bridge, INSIDE, UP);
            OneDirectionOutput(&position, &bridge, OUTSIDE, DOWN);
            OneDirectionOutput(&position, &bridge, INSIDE, DOWN);
        }
        printf("\n");
    }
    else
        printf("%d %d,%d %d,%d\n", cnt, start >> 3, start & 7, end >> 3, end & 7);
    fflush(stdout);
    return;
}

/*
Input what the enemy moves and update the present chessboard.*/
void Input(CHESS chessboard[])
{
    int number;
    scanf("%d", &number);
    int y[40], x[40];
    for (int i = 1; i <= number; i++)
    {
        scanf("%d,%d", &y[i], &x[i]);
    }
    CHESS start = CoordinateToChess(x[1], y[1]);
    CHESS end = CoordinateToChess(x[number], y[number]);
    chessboard[my_side ^ 1] ^= start | end;
    chessboard[KING] = start & chessboard[KING] ? (chessboard[KING] ^ (start | end)) : chessboard[KING];
    chessboard[KING] |= end & kKing[my_side ^ 1];
    if ((x[1] - x[2]) * (x[1] - x[2]) * (y[1] - y[2]) * (y[1] - y[2]) != 1)
    {
        for (int i = 2; i <= number; i++)
        {
            int col = (y[i] + y[i - 1]) >> 1;
            int row = (x[i] + x[i - 1]) >> 1;
            chessboard[my_side] ^= CoordinateToChess(row, col);
            chessboard[KING] ^= chessboard[KING] & CoordinateToChess(row, col);
        }
    }
    CopyChessboard(output[turn], chessboard);
}

/*
Evaluate how good the present chessboard is.*/
int Evaluate(const CHESS chessboard[], const int side)
{
    int value = 0;
    value += Count(chessboard[side]) * kEvaluateChess;
    value += Count(chessboard[side] & chessboard[KING]) * kEvaluateKing;
    value += Count(chessboard[side] & kCutEdge) * kEvaluateEdge;
    value += Count(chessboard[side] & chessboard[KING] & kCutEdge) * kEvaluateKingEdge;
    value += Count(chessboard[side] & kCutSide[side]) * kEvaluateSide;
    return value;
}

/*
Sort the method.*/
void MethodSort(const int start, const int end)
{
    int i = start;
    int j = end;
    int mid = method[key[(start + end) >> 1]].value;
    while (i <= j)
    {
        while (method[key[i]].value > mid)
            i++;
        while (method[key[j]].value < mid)
            j--;
        if (i <= j)
        {
            int temp = key[i];
            key[i] = key[j];
            key[j] = temp;
            i++;
            j--;
        }
    }
    if (start < j)
        MethodSort(start, j);
    if (i < end)
        MethodSort(i, end);
    return;
}

/*
Hash the chessboard and return its hash.*/
int Hash(const CHESS chessboard[])
{
    return ((chessboard[WHITE] >> 3) ^ chessboard[KING] ^ (chessboard[BLACK] << 3)) % MOD;
}

/*
Find the chesssboard method and return the accurate index in the hash chain table.*/
int HashFind(const CHESS chessboard[], int side)
{
    int pos = Hash(chessboard);
    for (int i = hash_head[side][pos]; i; i = hash[i].next)
    {
        HASH *node = &hash[i];
        if (node->chessboard[WHITE] == chessboard[WHITE] && node->chessboard[BLACK] == chessboard[BLACK] && node->chessboard[KING] == chessboard[KING])
        {
            return i;
        }
    }
    return 0;
}

/*
Push a node into the hash table.*/
int HashPush(const CHESS chessboard[], const CHESS expect[], const int side)
{
    int pos = Hash(chessboard);
    ++hash_index;
    HASH *node = &hash[hash_index];
    CopyChessboard(node->chessboard, chessboard);
    CopyChessboard(node->expect, expect);
    node->next = hash_head[side][pos];
    hash_head[side][pos] = hash_index;
    return hash_index;
}

/*
Judge whether the time is about to running out.if it is,clear the method table to the start position.*/
int TimeControl(int start)
{
    clock_end = clock();
    if ((long long)clock_end - (long long)clock_start >= (long long)time_limit)
    {
        time_out = 1;
        method_index = start - 1;
        return 1;
    }
    return 0;
}

/*
MinMax search AlphaBeta cut function.*/
int AlphaBeta(const int level, const int depth, int alpha, int beta, const CHESS chessboard[], const int side, EXPECT *father)
{
    father->size = 0;
    if (!chessboard[side]) /*Total lose situation.*/
        return -INFINITY;
    if (!chessboard[side ^ 1]) /*Total win situation.*/
        return INFINITY;
    if (turn + depth >= 120) /*Run out of steps situation.*/
        return (Count(chessboard[side]) - Count(chessboard[side ^ 1]) + ((Count(chessboard[side] & chessboard[KING]) - Count(chessboard[side ^ 1] & chessboard[KING])) << 1)) > 0 ? INFINITY : -INFINITY;
    EXPECT expect;
    int pvs = 0, start = method_index + 1, end = start, pos = HashFind(chessboard, side);
    HASH *node = &hash[pos];
    int flag = FindPossibleJump(chessboard, side);
    if (!flag) /*No jump situation.*/
    {
        if (depth >= level) /*Out of the searching range situation.*/
            return Evaluate(chessboard, side) - Evaluate(chessboard, side ^ 1);
        flag = FindPossibleMove(chessboard, side);
    }
    if (flag) /*Exist method to go situation.*/
    {
        end = method_index;
        for (int i = start; i <= end; i++)
            method[i].value = Evaluate(method[i].chessboard, side) - Evaluate(method[i].chessboard, side ^ 1);
        MethodSort(start, end);
    }
    else /*No method to go situation.*/
        return -INFINITY;
    if (pos) /*Exist the most expected method situation.*/
    {
        int value = -AlphaBeta(level, depth + 1, -beta, -alpha, node->expect, side ^ 1, &expect);
        if (value >= beta)
        {
            method_index = start - 1;
            return beta;
        }
        if (value > alpha)
        {
            pvs = 1;
            alpha = value;
            father->size = expect.size + 1;
            CopyChessboard(father->chessboard[0], node->expect);
            for (int i = 0; i < expect.size; i++)
                CopyChessboard(father->chessboard[i + 1], expect.chessboard[i]);
            if (!depth && former_value <= alpha)
                CopyChessboard(output[turn], node->expect);
        }
        if (TimeControl(start))
            return alpha;
    }
    for (int i = start; i <= end; i++)
    {
        int temp = key[i], value;
        if (temp && method[temp].chessboard[WHITE] == node->expect[WHITE] && method[temp].chessboard[BLACK] == node->expect[BLACK] && method[temp].chessboard[KING] == node->expect[KING])
            continue;
        if (pvs)
        {
            value = -AlphaBeta(level, depth + 1, -alpha - 1, -alpha, method[temp].chessboard, side ^ 1, &expect);
            if (value > alpha && value < beta)
                value = -AlphaBeta(level, depth + 1, -beta, -alpha, method[temp].chessboard, side ^ 1, &expect);
        }
        else
            value = -AlphaBeta(level, depth + 1, -beta, -alpha, method[temp].chessboard, side ^ 1, &expect);
        method[temp].value = value;
        if (value >= beta)
        {
            method_index = start - 1;
            return beta;
        }
        if (value > alpha)
        {
            pvs = 1;
            alpha = value;
            father->size = expect.size + 1;
            CopyChessboard(father->chessboard[0], method[temp].chessboard);
            for (int j = 0; j < expect.size; j++)
                CopyChessboard(father->chessboard[j + 1], expect.chessboard[j]);
            if (!depth && former_value <= alpha)
                CopyChessboard(output[turn], method[temp].chessboard);
        }
        if (TimeControl(start))
            return alpha;
    }
    method_index = start - 1;
    return alpha;
}

/*
Iterative deepening search fuction.*/
void Search(CHESS chessboard[], const int side)
{
    time_out = 0;
    time_limit = turn <= 80 ? 1650 : 3570 - 23 * turn;
    former_value = -INFINITY - 1;
    int depth;
    for (depth = 1; (turn + depth <= 120) && !time_out; depth++)
    {
        EXPECT expect;
        former_value = AlphaBeta(depth, 0, -INFINITY - 1, INFINITY + 1, chessboard, side, &expect);
        if (former_value == INFINITY) /*Already have good enough answer.*/
            break;
        if (DEBUG)
            printf("DEBUG level:%d expect:%d value:%d\n", depth, expect.size, former_value);
        for (int i = 0, chess_side = side; i < expect.size; i++, chess_side ^= 1)
        {
            int rank;
            if (i)
                rank = HashFind(expect.chessboard[i], chess_side);
            else
                rank = HashFind(chessboard, chess_side);
            if (!rank)
            {
                if (i)
                    rank = HashPush(expect.chessboard[i - 1], expect.chessboard[i], chess_side);
                else
                    rank = HashPush(chessboard, expect.chessboard[i], chess_side);
            }
            else
                CopyChessboard(hash[rank].expect, expect.chessboard[i]);
        }
    }
    if (turn >= 30 && output[turn][WHITE] == output[turn - 4][WHITE] && output[turn][BLACK] == output[turn - 4][BLACK] && output[turn][KING] == output[turn - 4][KING] && (Evaluate(output[turn], side) - Evaluate(output[turn], side ^ 1)) < 0)
    {
        int start = method_index;
        if (FindPossibleMove(chessboard, side))
        {
            int pos = start + 1 + rand() % (method_index - start);
            CopyChessboard(output[turn], method[pos].chessboard);
        }
        method_index = start;
    }
    Output(chessboard, side);
    CopyChessboard(chessboard, output[turn]);
    return;
}

/*
Receive command and respond.*/
void Work(void)
{
    CHESS chessboard[3] = {0x00000fff, 0xfff00000, 0};
    printf("OK\n");
    fflush(stdout);
    char order[10];
    while (1)
    {
        scanf("%s", order);
        clock_start = clock();
        if (order[0] == 'T')
        {
            Search(chessboard, my_side);
            turn++;
            clock_end = clock();
            if (DEBUG)
            {
                Debug(chessboard);
                printf("DEBUG time:%lld\n", clock_end - clock_start);
                printf("DEBUG hashlist:%d\n", hash_index);
                fflush(stdout);
            }
            continue;
        }
        if (order[0] == 'P')
        {
            Input(chessboard);
            turn++;
            if (DEBUG)
                Debug(chessboard);
            continue;
        }
        if (order[0] == 'E')
        {
            int whatever;
            scanf("%d", &whatever);
            return;
        }
    }
    return;
}

/*
main function.*/
int main(void)
{
    scanf("START %d", &my_side);
    if (my_side == 2)
        my_side = 0;
    Work();
    return 0;
}