中国象棋程序设计探索(二)：棋盘结构和着法生成器

中国象棋程序设计探索
　
象棋百科全书网 (webmaster@xqbase.com)
2005年6月初稿，2007年12月修订
　
(二) 棋盘结构和着法生成器
　
　　在阅读本章前，建议读者先阅读象棋百科全书网中《对弈程序基本技术》专题的以下几篇译文：
　　(1) 数据结构——简介(David Eppstein)；
　　(2) 数据结构——位棋盘(James Swafford)；
　　(3) 数据结构——旋转的位棋盘(James Swafford)；
　　(4) 数据结构——着法生成器(James Swafford)；
　　(5) 数据结构——0x88着法产生方法(Bruce Moreland)；
　　(6) 数据结构——Zobrist键值(Bruce Moreland)；
　
2.1 局面和着法的表示
　
　　局面是象棋程序的核心数据结构，除了要包括棋盘、棋子、哪方要走、着法生成的辅助结构、Zobrist键值等，还要包含一些历史着法，来判断重复局面。ElephantEye的局面结构很庞大(见<position.h>)，其中大部分存储空间是用来记录历史局面的。: 　; struct PositionStruct {; 　……; 　int nMoveNum;; 　MoveStruct mvMoveList[MAX_MOVE_NUM]; 　// MAX_MOVE_NUM = 256; 　unsigned char ucRepHash[REP_HASH_LEN]; // REP_HASH_LEN = 1024; 　……; }
　
　　其中MoveStruct这个结构记录了四个信息：(1) 着法的起始格(Src)，(2) 着法的目标格(Dst)，(3) 着法吃掉的棋子(Cpt)，(4) 着法是否将军(Chk)。有意思的是，每个部分都只占一个字节，后两个部分(Cpt和Chk)与其说有特殊作用，不如说是为了凑一个32位整数。在MoveStruct出现的很多地方(置换表、杀手着法表、着法生成表)里，这两项都是没作用的，而只有在PositionStruct结构的记录历史着法的堆栈中才有意义。
　　Cpt一项主要用在撤消着法上，它可以用来还原被吃的棋子，而Chk一项则可以记录当前局面是否处于将军状态。ElephantEye是用MakeMove()函数来走棋的，每走完一步棋就做两次将军判断：第一次判断走完子的一方是否被将军，即Checked(sdPlayer)，如果被将则立即撤消着法，并返回走子失败的信息；第二次判断要走的一方是否被将军，由于交换了走子方(即执行了sdPlayer = 1 - sdPlayer)，所以仍旧是Checked(sdPlayer)，如果被将则Chk置为TRUE，这个着法被压入历史着法堆栈。因此LastMove().Chk就表示当前局面是否被将军。
　
2.2 循环着法的检测
　
　　Cpt和Chk的另一个作用就是判断循环着法：ElephantEye判断循环着法时，依次从堆栈顶往前读，读到吃过子的着法(Cpt不为零)就结束；而是否有单方面长将的情况，则是通过每个着法的Chk一项来判断的。
　　在循环着法的检测中，我们感兴趣的不是Cpt和Chk，而是RepHash结构，这是一个微型的置换表，用来记录历史局面。ElephantEye在做循环着法的判断这之前，先去探测这个置换表，如果命中置换表，则说明可能存在重复局面(由于置换表可能有冲突，所以只是有这个可能)，因而做循环检测(即比较当前Zobrist键值与前2步、4步、6步等等的一系列局面是否一致)；如果没有命中则肯定没有重复局面。
　
2.3 棋盘-棋子联系数组
　
　　众所周知，棋盘的表示有两种方法。一是做一个棋盘数组(例如Squares[10][9])，每个元素记录棋子的类型(包括空格)；二是做一个棋子数组(例如Pieces[2][16])，每个元素记录棋子的位置(包括被吃的状态)。如果一个程序同时使用这两个数组，那么着法生成的速度就可以快很多。这就是“棋盘-棋子联系数组”，它的技术要点是：
　　(1) 同时用棋盘数组和棋子数组表示一个局面，棋盘数组和棋子数组之间可以互相转换。
　　(2) 随时保持这两个数组之间的联系，棋子移动时必须同时更新这两个数组。
　　根据这两个原则，棋盘-棋子联系数组可以定义为：: 　; struct PositionStruct {; 　int Squares[90];; 　int Pieces[32];; };
　
　　在棋盘上删除一个棋子，需要做两个操作(分别修改棋盘数组和棋子数组)。同样，添加一个棋子时也需要两个操作。执行一个着法时有三个步骤：
　　(1) 如果目标格上已经有棋子，就要先把它从棋盘上拿走(吃子的过程)；
　　(2) 把棋子从起始格上拿走；
　　(3) 把棋子放在目标格上。
　　ElephantEye用一个函数MovePiece()来完成这项任务，它除了修改棋盘数组和棋子数组外，还修改Zobrist键值、位行和位列等信息。
　　“棋盘-棋子联系数组”最大的优势是：移动一步只需要有限的运算。对于着法产生过程，可以逐一查找棋子数组，如果该子没有被吃掉，就产生该子的所有合理着法，由于需要查找的棋子数组的数量(每方只有16个棋子能走)比棋盘格子的数量(90个格子)少得多，因此联系数组的速度要比单纯的棋盘数组快很多。可以说，“棋盘-棋子联系数组”是所有着法生成器的基础，位行和位列、位棋盘等其他方法都只是辅助手段。
　
2.4 扩展的棋盘数组和棋子数组
　
　　如今，很少有程序使用Squares[90]和Pieces[32]这样的数组了，浪费一些存储空间以换取速度是流行的做法，例如ElephantEye就用了ucpcSquares[256]和ucsqPieces[48]。把棋盘做成16x16的大小，得到行号和列号就可以用16除，这要比用9或10除快得多。16x16的棋盘还有更大的好处，它可以防止棋子走出棋盘边界。

　　在中国象棋里，短程棋子(短兵器)指的是除车和炮以外的其他棋子，它们的着法都有固定的增量(行的增量，列的增量)，因此处理起来非常简单，也是着法生成技术的基础。例如马有8个着法，增量分别是±0x0e、±0x12、±0x1f和±0x21，红方的过河兵有3个着法，增量分别是-0x10和±0x01。
　　16x16的扩展棋盘如上图所示，底色是红色的格子都被标上“出界”的标记，目标格在这些格子上就说明着法无效。这样，马的着法产生就非常简单了：: 　; const int cnKnightMoveTab[8] = {-0x21, -0x1f, -0x12, -0x0e, +0x0e, +0x12, +0x1f, +0x21};; const int cnHorseLegTab[8] = {-0x10, -0x10, -0x01, +0x01, -0x01, +0x01, +0x10, +0x10};; 　; for (i = MyFirstHorse; i < MyLastHorse; i ++) {; 　// 在ElephantEye的Pieces[48]中，红方的MyFirstHorse为21，MyLastHorse为22。; 　SrcSq = ucsqPieces[i];; 　if (SrcSq != 0) {; 　　for (j = 0; j < 8; j ++) {; 　　　DstSq = SrcSq + cnKnightMoveTab[j];; 　　　LegSq = SrcSq + cnHorseLegTab[j];; 　　　if (cbcInBoard[DstSq] && (ucpcSquares[DstSq] & MyPieceMask) == 0 && ucpcSquares[LegSq] == 0) {; 　　　　MoveList[MoveNum].Src = SrcSq;; 　　　　MoveList[MoveNum].Dst = DstSq;; 　　　　MoveNum ++;; 　　　}; 　　}; 　}; }
　
　　上面的代码是着法生成器的典型写法，用了两层循环，第一层循环用来确定要走的棋子，第二层循环用来确定棋子走到的目标格。如果要加快程序的运行速度，第二个循环可以拆成顺序结构。这个代码还加入了蹩马腿的判断，马腿的位置增量由ccHorseLegTab[j]给出。
　　其它棋子的着法也同样处理，只要注意帅(将)和仕(士)把InBoard[DstSq]改为InFort[DstSq]就可以了。而对于兵和象等需要考虑是否能过河的棋子，判断是否过河的方法非常简单：红方是(SrcSq/DstSq & 0x80) != 0，黑方是(SrcSq/DstSq & 0x80) == 0。
　　Pieces[48]这个扩展的棋子数组比较难以理解，实际上用了“屏蔽位”的设计，即1位表示红子(16)，1位表示黑子(32)。因此0到16没有作用，16到31代表红方棋子(16代表帅，17和18代表仕，依此类推，直到27到31代表兵)，32到47代表黑方棋子(在红方基础上加16)。这样，棋盘数组Squares[256]中的每个元素的意义就明确了，0代表没有棋子，16到31代表红方棋子，32到47代表黑方棋子。这样表示的好处就是：它可以快速判断棋子的颜色，(Piece & 16)可以判断是否为红方棋子，(Piece & 32)可以判断是否为黑方棋子。
　　“屏蔽位”的设计不仅仅限制在判断红方棋子还是黑方棋子，如果在棋子数组上再多加7个屏蔽位，就可以对每个兵种作快速判断，例如判断是否是红兵，不需要用(Piece >= 27 && Piece <= 31)，而只要简单的(Piece & WhitePawnBitMask)即可。这样的话，棋子数组的大小就增加到2^12=4096个了，其中9个屏蔽位，还有3位表示同兵种棋子的编号(注意兵有5个，所以必须占据3位)。事实上，确实有象棋程序是使用Pieces[4096]的。
　
2.5 着法预生成数组
　
　　上面提到的着法生成技术，在速度上并不是最快的。我们仍旧以马的着法为例，在很多情况下，马会处于棋盘的边缘，所以往往着法只有很少，而并不需要对每个马都作8次是否出界的判断。因此，对于每个短程子力，都给定一个[256][4]到[256][9]不等的数组，它们保存着棋子可以到达的绝对位置，这些数组称为“着法预生成数组”。例如，ElephantEye里用了ucsqKnightMoves[256][12]和ucsqHorseLegs[256][8]，前一个数组的第二个维度之所以大于8，是因为着法生成器依次读取数组中的值，读到0就表示不再有着法(12则是为了对齐地址)。程序基本上是这样的：: 　; for (i = MyFirstHorse; i <= MyLastHorse; i ++) {; 　SrcSq = ucsqPieces[i];; 　if (SrcSq != 0) {; 　　j = 0;; 　　DstSq = ucsqKnightMoves[SrcSq][j];; 　　while (DstSq != 0) {; 　　　LegSq = ucsqHorseLegs[SrcSq][j];; 　　　if (!(ucpcSquares[DstSq] & MyPieceMask) && ucpcSquares[LegSq] == 0) {; 　　　　MoveList[MoveNum].Src = SrcSq;; 　　　　MoveList[MoveNum].Dst = DstSq;; 　　　　MoveNum ++;; 　　　}; 　　　j ++;; 　　　DstSq = ucsqHorseMoves[SrcSq][j];; 　　}; 　}; }
　
　　和前一个程序一样，这个程序也同样用了两层循环，不同之处在于第二个循环读取的是着法预生成数组，DstSq从ucsqHorseMoves[256][12]中读出，LegSq从ucsqHorseLegs[256][8]中读出。
　
2.6 位行和位列
　
　　车和炮的着法分为吃子和不吃子两种，这两种着法生成器原则上是分开的，因此分为车炮不吃子、车吃子和炮吃子三个部分。不吃子的着法可以沿着上下左右四条射线逐一生成(即并列做4个循环)。我们感兴趣的是吃子的着法，因为静态搜索只需要生成这种着法，能否不用循环就能做到？ElephantEye几乎就做到了。
　　“位行”和“位列”是目前比较流行的着法生成技术，但仅限于车和炮的着法，它是否有速度上的优势还很难说，但是设计程序时可以减少一层循环，这个思想就已经比较领先了。以“位”的形式记录棋盘上某一行所有的格子的状态(仅仅指是否有子)，就称为“位行”(BitRank)，与之对应的是“位列”(BitFile)，棋盘结构应该包含10个位行和9个位列，即：: 　; struct PositionStruct {; 　……; 　unsigned short wBitFiles[16];; 　unsigned short wBitRanks[16];; 　……; };
　
　　值得注意的是，它仅仅是棋盘的附加信息，“棋盘-棋子联系数组”仍旧是必不可少的。它的运作方式有点和“棋盘-棋子联系数组”类似：
　　(1) 同时用位行数组和位列数组表示棋盘上的棋子分布信息，位行数组和位列数组之间可以互相转换；
　　(2) 随时保持这两个数组之间的联系，棋子移动时必须同时更新这两个数组。
　　因此，移走或放入一颗棋子时，必须在位行和位列上置位：: 　; void AddPiece(int Square, int Piece) {; 　……; 　x = Square % 16;; 　y = Square / 16;; 　wBitFiles[x] = 1 << (y - 3);; 　wBitRanks[y] = 1 << (x - 3);; 　……; }
　
　　车和炮是否能吃子(暂时不管吃到的是我方棋子还是敌方棋子)，只取决于它所在的行和列上的每个格子上是否有棋子，而跟棋子的颜色和兵种无关，因此这些信息完全反映在位行和位列中。预置一个“能吃到的格子”的数组，以位行或位列为指标查找数组，就可以立即知道车或炮能吃哪个子了。预置数组到底有多大呢？: 　; // 某列各个位置的车或炮(10)在各种棋子排列下(1024)能走到的最上边或最下边的格子; unsigned char ucsqFileMoveNonCap[10][1024][2];　　// 不吃子; unsigned char ucsqFileMoveRookCap[10][1024][2]; 　// 车吃子; unsigned char ucsqFileMoveCannonCap[10][1024][2]; // 炮吃子; // 某列各个位置的车或炮(9)在各种棋子排列下(512)能走到的最左边或最右边的格子; unsigned char ucsqRankMoveNonCap[9][512][2];; ……
　
　　数组中的值记录的是目标格子的偏移值，即相对于该行或列第一个格子的编号。产生吃子着法很简单，以车吃子位例：: 　; for (i = MyFirstRook; i <= MyLastRook; i ++) {; 　SrcSq = ucsqPieces[i];; 　if (SrcSq != -1) {; 　　x = SrcSq % 16;; 　　y = SrcSq / 16;; 　　DstSq = ucsqFileMoveRookCap[y - 3][wBitFiles[x]][0]; // 得到向上吃子的目标格; 　　if (DstSq != 0) {; 　　　DstSq += x * 16; // 注意：第x列的第一个格子总是x * 16。; 　　　MoveList[MoveNum].Src = SrcSq;; 　　　MoveList[MoveNum].Dst = DstSq;; 　　　MoveNum ++;; 　　}; 　　…… // 再把FileMoveRookCap[...][...][0]替换成[...][...][1]，得到向下吃子的着法; 　　DstSq = ucsqRankMoveRookCap[x - 3][wBitRanks[y]][0]; // 得到向左吃子的目标格; 　　if (DstSq != 0) {; 　　　DstSq += y; // 注意：第y行的第一个格子总是y。; 　　　MoveList[MoveNum].Src = SrcSq;; 　　　MoveList[MoveNum].Dst = DstSq;; 　　　MoveNum ++;; 　　}; 　　…… // 再把RankMoveRookCap[...][...][0]替换成[...][...][1]，得到向右吃子的着法; 　}; }
　
2.7 着法合理性的判断
　
　　ElephantEye搜索每个结点时，着法都有四个来源：(1) 置换表，(2) 吃子着法生成器，(2) 杀手着法表，(3) 不吃子着法生成器。这四种来源分别代表了四种启发式算法：(1) 置换表启发，(2) 吃子启发，(3) 杀手着法启发，(4) 历史表启发，这会在以后的章节中介绍。
　　我们感兴趣的是杀手着法，它是以前搜索过的局面遗留下来的着法，当前的局面如果要使用这些着法，只需要做合理性的判断就可以了，如果杀手着法能产生截断，那么着法生成就没有必要了。因此，如何快速判断着法合理性，其意义可能比着法生成器还大。
　　ElephantEye判断着法合理性的程序包含在<position.cpp>中，它分为三个步骤：
　　(1) 判断棋子是否在棋盘上存在，如果不存在那么肯定不是合理着法；
　　(2) 判断是否吃到自己一方的棋子，吃到自己棋子的着法肯定是不是合理着法；
　　(3) 分兵种作额外的判断。
　　我们感兴趣的是相(象)马车炮四子的判断，其中相(象)的判断最简单，只需要满足3个条件：
　　(1) 走成象步，ElephantEye里用了一个ccLegalMoveTab的数组；
　　(2) 没有过河，即((SrcSq ^ DstSq) & 0x80) == 0；
　　(3) 没有被塞象眼，即ucpcSquares[(SrcSq + DstSq) / 2] == 0。
　　ElephantEye在马的判断上用了一个诀窍：构造了一个巧妙的数组：: 　; const char ccHorseLegTab[512] = {; 　……; 　0, 　0, 　0, 　0, 　0, 　0, -16, 　0, -16, 　0, 　0, 　0, 　0, 　0, 　0, 　0,; 　0, 　0, 　0, 　0, 　0,　-1, 　0, 　0, 　0, 　1, 　0, 　0, 　0, 　0, 　0, 　0,; 　0, 　0, 　0, 　0, 　0, 　0, 　0, 　0, 　0, 　0, 　0, 　0, 　0, 　0, 　0, 　0,; 　0, 　0, 　0, 　0, 　0,　-1, 　0, 　0, 　0, 　1, 　0, 　0, 　0, 　0, 　0, 　0,; 　0, 　0, 　0, 　0, 　0, 　0,　16, 　0,　16, 　0, 　0, 　0, 　0, 　0, 　0, 　0,; 　……; };
　
　　上面的数组中，正中心的数代表马步的起始格(红色表示)，±33、±31、±18和±14是马步的增量(蓝色表示)(能被程序读到的就是这些位置)，它们记录了马腿的增量(马腿的位置用绿色表示)。这样，判断合理性只需要符合两个条件：
　　(1) 走成马步，即(Disp = ccHorseLegTab[DstSq - SrcSq + 256]) != 0；
　　(2) 没有被绊马腿，即ucpcSquares[SrcSq + Disp] == 0。
　　车和炮的判断就需要用到前面所说的位行和位列，这就需要首先要判断是否是吃子着法，然后根据不同情况作相应的判断。ElephantEye中有专门的判断着法合理性的数组，也由<pregen.cpp>生成，结构跟前面提到的着法预产生数组类似，以车在列上吃子的着法为例，只要把FileMoveRookCap[...][...][0]和[...][...][1]合并成位列FileMaskRookCap[...][...]，判断着法合理性的时候，只要判断该位列是否包含目标格的位列(1 << (y - 3))即可。
　
2.8 位棋盘
　
　　尽管ElephantEye已经摈弃了“位棋盘”的设计，但是作为一个新兴的数据结构，尤其是“折叠位棋盘”的设计思路，还是值得一提的。“折叠位棋盘”的思想是由湖北襄樊铁路分局计算机中心的章光华提出的，首先于2004年底发表在象棋百科全书网的论坛上，该技术主要用来获得马和相(象)的着法。
　　这个思想的要点是：
　　(1) 棋盘必须按照列的方式对每个格子编号(如下图所示)，格子的编号代表96位位棋盘中的第几位；

09	19	29	39	49	59	69	79	89
08	18	28	38	48	58	68	78	88
07	17	27	37	47	57	67	77	87
06	16	26	36	46	56	66	76	86
05	15	25	35	45	55	65	75	85
04	14	24	34	44	54	64	74	84
03	13	23	33	43	53	63	73	83
02	12	22	32	42	52	62	72	82
01	11	21	31	41	51	61	71	81
00	10	20	30	40	50	60	70	80

　　(2) 初始化数组一个“马腿数组”，以表示某个格子上的马可能存在的马腿，例如：: 　; BitBoard HorseLegTable[90];; HorseLegTable[0] = BitMask[1] | BitMask[10];; HorseLegTable[1] = BitMask[11] | BitMask[20]; // BitMask[0]没必要加上去，而加上去也没错。; ……
　
　　注意，这里仅仅是拿两个格子举例子，写在程序里的时候要用循环语句来生成马腿数组，以精简代码。
　　(3) 产生绊马腿的棋子的位棋盘，以红方左边未走过的马为例：: 　; HorseLeg = HorseLegTable[10] & AllPieces;
　
　　(4) 根据马的位置和绊马腿的位棋盘，就可以知道马可以走的格子，因此可以构造这样的函数：: 　; BitBoard KnightPinMove(int KnightSquare, BitBoard HorseLeg);
　
　　为了增加运算速度，应该用查表代替运算，即把函数变成数组。那么位棋盘HorseLeg如何转化成整数呢？这就引出了“折叠位棋盘”的技术，这可以称得上是一个炫技。折叠位棋盘实际上就是位棋盘的8位校验和(CheckSum)，有了折叠位棋盘后，上面的函数就可以用数组表示：: 　; BitBoard KnightPinMove[90][256];
　
　　例如第10个格子上马的所有着法，用位棋盘表示为：: 　; KnightMoveBitBoard = KnightPinMove[10][CheckSum(HorseLegTable[10] & AllPieces)];
　
　　相(象)的着法可以采用同样的原理，首先初始化象眼数组：: 　; BitBoard ElephantEyeTable[90];
　
　　随后折叠象眼的位棋盘ElephantEye，再从相(象)的着法预产生数组BishopPlugMove[90][256]中找到着法。

1	3	5	7	1	3	5	7	1
0	2	4	6	0	2	4	6	0
7	1	3	5	7	1	3	5	7
6	0	2	4	6	0	2	4	6
5	7	1	3	5	7	1	3	5
4	6	0	2	4	6	0	2	4
3	5	7	1	3	5	7	1	3
2	4	6	0	2	4	6	0	2
1	3	5	7	1	3	5	7	1
0	2	4	6	0	2	4	6	0

1	2	3	4	5	6	7	0	1
0	1	2	3	4	5	6	7	0
7	0	1	2	3	4	5	6	7
6	7	0	1	2	3	4	5	6
5	6	7	0	1	2	3	4	5
4	5	6	7	0	1	2	3	4
3	4	5	6	7	0	1	2	3
2	3	4	5	6	7	0	1	2
1	2	3	4	5	6	7	0	1
0	1	2	3	4	5	6	7	0

按纵线编号的棋盘

按横线编号的棋盘

　　看到这里，可能有的读者就会怀疑“折叠位棋盘”的合理性，如果折叠成4位的整数(甚至更少)，把马的着法预产生数组了缩小到90x16，这显然是不合理的，为什么8位就一定合理呢？
　　要说明这个问题，首先来看折叠的本质——校验和(CheckSum)，棋盘上的很多格子对应着校验和上固定的一位。根据这个性质，我们对棋盘重新编号，就如左图所示。假如河界下面蓝色的格子是马，那么相邻的红色格子就是马腿，4条马腿对应4个不同的编号，所以任何一种组合(一共有2⁴=16种组合)是不重复的。需要指出的是，这个棋盘当中所有的格子，其相邻的四个格子都有不同的编号。有趣的是，象眼同样符合这个规律(注意河界上面蓝色的格子，斜相邻的四个格子是象眼)。
　　折叠位棋盘的唯一性是建立在“按纵线编号”的基础上的。如果按横线编号，情况就不那么幸运了，如右图所示，无论是河界下面的马，还是河界上面的象，马腿或象眼都存在编号重复的格子。
　　位棋盘必须按纵线编号，就是这个原因。
　　当然，初始化KnightPinMove[18][256]这个庞然大物，也不是一件容易的事。其实折叠位棋盘使用起来需要“折叠”，生成起来却需要“展开”(即CheckSum()函数对应的Duplicate()函数，参阅<bitboard.h>)。当8位的整数展开成位棋盘后，再和某个格子的HorseLegTable作“与”运算，就可以还原为HorseLeg了。

上一篇　中国象棋程序设计探索(一)：引言

下一篇　中国象棋程序设计探索(三)：搜索和置换表

返　回　象棋百科全书——电脑象棋

www.xqbase.com

09	19	29	39	49	59	69	79	89
08	18	28	38	48	58	68	78	88
07	17	27	37	47	57	67	77	87
06	16	26	36	46	56	66	76	86
05	15	25	35	45	55	65	75	85
04	14	24	34	44	54	64	74	84
03	13	23	33	43	53	63	73	83
02	12	22	32	42	52	62	72	82
01	11	21	31	41	51	61	71	81
00	10	20	30	40	50	60	70	80

09	19	29	39	49	59	69	79	89
08	18	28	38	48	58	68	78	88
07	17	27	37	47	57	67	77	87
06	16	26	36	46	56	66	76	86
05	15	25	35	45	55	65	75	85
04	14	24	34	44	54	64	74	84
03	13	23	33	43	53	63	73	83
02	12	22	32	42	52	62	72	82
01	11	21	31	41	51	61	71	81
00	10	20	30	40	50	60	70	80

09	19	29	39	49	59	69	79	89
08	18	28	38	48	58	68	78	88
07	17	27	37	47	57	67	77	87
06	16	26	36	46	56	66	76	86
05	15	25	35	45	55	65	75	85
04	14	24	34	44	54	64	74	84
03	13	23	33	43	53	63	73	83
02	12	22	32	42	52	62	72	82
01	11	21	31	41	51	61	71	81
00	10	20	30	40	50	60	70	80