AI入门——三子棋（1）

数据科学和AI是不分家的，因为正经数据分析师，需要处理海量数据，这显然不是人干的活儿。

我们这一次就以动手写一个游戏AI的方式，来初步了解一下AI是怎么回事。

我们选的游戏，是三子棋，可以看作五子棋的简化版，它大概长成这个样子：

三子棋的规则是：在3x3的棋盘里，双方轮流下子（以X和O表示），先将3个子连成一条线（横竖斜都可以）的一方获胜。

棋盘描述

要让AI解决问题，首先得用AI能理解的方式，把问题描述出来。

对于三子棋来说，需要描述的是棋盘和棋子。

描述棋盘的方法有很多，我们选了一种经典的方法，Bitboards。

首先给棋盘的格子编号：

然后描述每个带编号的格子里，是X还是O。

比如这个我们封面上的例子可以描述1o2x3x4x5o6o7x8o9o。

如果我们按照1～9的正常顺序描棋盘，1～9的格子编号是可以不写的。这样棋盘的描述又简化成了oxxxooxoo，用9个字符描述棋盘和所有的棋子。

我们还可以进一步优化，比如把描述从字母换成数字，这会为写代码带来很多便利。我们用2表示x、用1表示o、用0表示空着的格子。这样棋盘的描述就可以写成122211211。这个数列是从低位(1)往高位(9)写的，而我们编程序的时候，一般默认数字从高位(9)往低位(1)写，这样就需要把数列倒过来，写成112112221，这个出学编程可能不适应，慢慢习惯了就好。

我们可以把这个112112221看成一个4进制数。因为棋盘总共只有9个格子，所以这个4进制数不会超过9位，换算成2进制不会超过18位。我们一般管这个18位2进制数，叫做游戏的状态空间。就是说棋盘上所有的情况，都可以用一个18位的2进制数描述出来。换一个角度看，棋局所有的变化数，不会超过2的18次方，这个数字计算出来大约是25万（0.25M）。

我们选三子棋当例子讲AI，最主要的原因，就是这个游戏的状态空间比较小。我们很容易为它编制全空间索引，有了这个索引，游戏的过程就可以完全被AI掌控。更复杂的游戏，因为状态空间很大，今天的计算机还没有能力存储全空间索引，AI对于掌控不了的状态空间，就只能蒙着来。

动手写代码（1）

接下来，我们先写一段能把0x165A9还原成下面这张图的代码：

代码写出来是这个样子：

#include

usingnamespacestd;

unsignedintmask[]={,3,3

charstate_to_char[]={' ','O','X','?'};

intshowBoard(constunsignedintboard){

charpieces[10];

for(inti=1;i

unsignedintstate=(board&mask[i])>>(2*i-2);

pieces[i]=state_to_char[state];

}

printf("board=0x%X\n",board);

printf("-------\n");

printf("|%c|%c|%c|\n",pieces[1],pieces[2],pieces[3]);

printf("-------\n");

printf("|%c|%c|%c|\n",pieces[4],pieces[5],pieces[6]);

printf("-------\n");

printf("|%c|%c|%c|\n",pieces[7],pieces[8],pieces[9]);

printf("-------\n");

return;

}

intmain(intargc,char* argv[]){

showBoard(0x165A9);

return;

}

截图看起来更舒服一点儿：

运行结果是这样子的：

第一行打出来棋盘的状态码，接下来用字符拼出来下面这张图：

我们没有画斜线，因为这在字符界面下是比较困难的，真需要告知玩家游戏结果的时候，我们可以用别的方法。

代码分析（1）

代码可以分成四个部分：

1、引用C语言的IO系统库、并且启用std命名空间

cstdio库提供了字符界面的基本交互功能，比如我们在13～20行大量使用的printf函数：

在《

DSA清华挑战001

》里，我们引用的是这个代码库的老版本stdio.h，新老版本功能是一样的。老版本的优点是在C/C++两种语言里写法是一样的，方便我们在C和C++之间切换。新版本的好处是和C++更多的代码库风格统一。我们写AI的时候，还是用新版本写代码更漂亮。

2、定义掩码表和状态映射表

“掩码”是一个非常古老，但是很炫酷的的技术。

那我想知道6号格里是X还是O，应该怎么计算呢？

我们来看二进制版本，112112221=10110010110101001，6号位的掩码，是mask[6]=3

我们把状态字和它的掩码用二进制形式对齐，因为掩码比较短，需要在前面补0：

对状态和掩码进行“按位与”操作（&算符）：

计算的效果，就是把状态中掩码为0的位，全部抹掉了，只剩下掩码为1的位，这也就是“掩码”这个名字的由来——掩盖我们不想看的东西。

这个结果给人看已经明白了，掩码对应的两位是01，按照2=x，1=o，0=空格的约定，这个位置是o。但是机器比人笨一些，我们还得把结果后面多的10个0抹掉：

这是完整的计算过程，先与掩码进行“按位与”，再抹掉后面多余的0。当i=6的时候，掩码是mask[6]，抹掉的0的个数是2x6-2=10。

我们描述棋盘的方法叫Bitboards，这种方法的精髓就在于可以用掩码轻松地完成很多复杂的判断。比如国际象棋的棋盘是8行8列64个格子，正好对应一个64bit无符号长整型。那么棋子的杀伤范围，就可以用64bit掩码预先写好：能杀伤到的位置标记成1，杀伤不到的位置标记成0。

通过掩码和抹零，我们已经计算出了6号位的状态是1，但是我们还需要把它展现成字符o，这时候“状态映射表”就用上了：

它也是一个数组，0号位是空格，1号位是o，2号位是x，3号位设为“？”，因为在我们的游戏里不应该出现3这种状态。

用“状态映射表”我们可以很简单地把用数字表示的状态，转换成给人看的字符：

3、将游戏状态转化为字符图案的函数：

函数的输入是参数表中的游戏状态：

int在C/C++里的意思是32bit整数，因为描述游戏的状态只需要18bit，而游戏的状态会有很多种（我们的估计是0.25M，或者说是25万），所以在存储游戏状态的时候，内存得省着用，32bit够用，就没必要用64bit。

unsigned修饰的意思是“无符号”。我们是拿int当作Bitboards用的，每个二进制位都对应棋盘上的某种状态。int自己的符号位对我们是没用的，同时负数编码可能会给我们找麻烦。所以在用Bitboards描述棋盘的时候，所有的整数都应该是“无符号”的。

const修饰的意思不可修改，这是一种我推崇的编程风格：参数就是给你参考用的，需要修改的时候，建立一个副本，在副本上做修改。代码能在电脑上确执行，是一个很低的标准。高水平程序员和编程初学者的区别，主要在于代码写出来，人能不能看明白。

说完了参数表，我们看函数体，这个函数的代码可以分成3部分：

3.1、声明描述棋盘格状态的数组pieces

3.2、通过掩码表和状态映射表，计算每一个格子的状态

3.3、把棋盘状态输出到屏幕上

3.1部分就是声明一个坐标位0～9的数组，数组的元素是字符，正好存储棋盘1～9号位置，展现给玩家看的状态。

3.2部分在前面讲“掩码表”和“状态映射表”的时候已经解释过了，通过掩码将board变量中每一位的状态信息读取出来，再通过“状态映射表”将2进制的状态转换成给人看的字符。

3.3部分是8行字符输出，第1行以16进制输出棋盘的状态值，第2、4、6、8行都是横分隔线，第3、5、7行是被竖分隔线隔开的棋盘状态。

3.3部分这种字符界面输出看起来很原始。但是很多同学可能不知道，40年前Dennis Ritchie 和 Brian Kernighan 发明C语言的时候，计算机都是联网的，只不过是通过“命令行”和“终端”的形式。而我们今天使用的Internet，这个概念，大约是此后20年，才被提出的（以Bill Gates的《未来之路》为代表）。所以字符界面，本来就是为网络应用设计的。下一篇教程，我们就会介绍怎么在《米OS》中用手机远程玩儿我们这个游戏。

好，我们接着看最后一段代码。

4、主函数：

这次的主函数，比我们之前在《DSA清华挑战001》中的要复杂一些，参数表里有两个参数。

其实主函数本来是有参数的，只不过在清华计算机系的Online Judge系统里，他们从来不用这些参数，那我们讲代码的时候也就不讲了。

这两个参数，argc是一个计数器，计算启动程序的命令行有多少项，argv是一个字符串数组，存储着命令行的每一项。

略微有一点绕的地方，是计数和编号规则：

argc的数值，比命令行参数的数量大1，因为程序的文件名是命令行的第一段，所以有一个参数的命令行，argc=2。

argv是从零开始编号的，文件名（可能包括完整路径）是argv[0]。

简单地记住，1个参数时，argc=2，参数是argv[1]，就可以了，更复杂的情况，以此类推。

这篇文章写的有一点儿长，细节写得比较多，这样安排，是希望完全没有编程基础的同学，也可以“照猫画虎”地把程序写出来，运行起来。

真没写过程序的同学，建议去看一下我之前发的《DSA清华挑战001》，那篇文章里，对从零开始写代码、运行代码，有更详细的介绍。

《AI入门——三子棋》的第一部分就先写到这里，下一部分，我们会介绍，怎么通过大量测试，保障代码是能正确运行的，以此为基础，我们再计算三子棋的全状态空间、设定AI的下棋策略。