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的下棋策略。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180625G000PR00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

同媒体快讯

扫码关注云+社区

领取腾讯云代金券