基于WinCE应用程序的围棋游戏开发1

摘要 机器博弈，也称计算机博弈，即让计算机下棋。围棋是一种策略性二人棋类游戏，使用格状棋盘及黑白二色棋子进行对弈。文中计算机围棋游戏引擎的开发采用马尔科夫决策模型，使用人工智能的知识，含有大量计算，整个计算紧密依赖于系统资源，计算量越大，引擎的选点越精确，棋力越高。针对嵌入式系统软硬件的特定性，其资源和计算能力的局限性，本文主要完成了两个工作：一是将实验室适用于PC的游戏引擎移植到WinCE，开发适合嵌入式系统的围棋游戏引擎，实现大规模计算的移植，使游戏引擎在嵌入式有限的资源上，通过精简的计算量，达到不错的效果；二是实现WinCE上围棋游戏前台界面的开发。

关键词 机器博弈，UCT，蒙特卡洛树搜索，嵌入式

中图分类号 TP31 文献标识码A doi:10.3969/j.issn.1003-6970.2011.01.020

WinCE-based Go Game Development

CAO Hui-fang 1, LIU Zhi-qing 2

1(Beijing University of Posts and Telecommunications，100876，China) 2(Beijing University of Posts and Telecommunications，100876，China)

【Abstract 】 Game machines, also known as computer game that let the computer play game. Go is strategic two-person board game, and use the Grid board with black and white 2-color stones playing. Computer Go engine developed by Markov decision model, using artificial intelligence, and contains a lot of calculations closely dependent on system resources, the greater the computational, the point of engine selected more precise, the higher thinking depth.The specificity for hardware and software of the embedded system make limitations of its resources and computing power. There are two mainly work included this article: First, transplant Go Game engine used for PC developed by laboratory to WinCE system, and develop Game engine suitable for embedded system to achieve large-scale computing transplant. Let the game engine achieve good results by streamlining the amount of computation in the embedded finite resources; second, develop the Go game interface on WinCE.

【Key words】Computer game, UCT, Monte Carlo tree search, Embedded

0 引言

计算机围棋就是结合人工智能技术教计算机下围棋，以达到与人类棋手相抗衡的目的。老式的围棋程序编程时注重在围棋知识,文中使用的对弈引擎，采用了蒙特卡洛博弈树搜索的思想。UCT搜索是蒙特卡洛树搜索的核心，注重于海量的搜索和随机的下法搜索。因此整个过程是一个大规模的计算，需要大量资源的支持。

嵌入式设备正日益渗透到人们的日常生活中，默默地为我们提供连接和服务，嵌入式设备往往是一个资源有限的系统，它们追求的是在有限的价格上满足一定的功能性要求。通常它们采用那些功能并不强大的CPU，这也是开发者不得不尽可能地压缩嵌入式系统性能的原因。最初的嵌入式设备是单一用途的，它们拥有各自独特的显示方式和用户界面，而今天它们变成了类似PC的系统。它们可以运行很多相同的应用程序。

针对嵌入式资源的限制，如何将对资源有很大依赖性的大规模的计算，成功的移植到嵌入式系统中，并能使其达到类似与在PC上计算的效果。针对此问题，必须对原适用于PC上的游戏引擎做出修改，才能使其在嵌入式系统中成功的运行。

1 游戏设计及框架

Windows CE程序采用消息响应[1]工作方式。当有事件发生时，如触摸笔点击屏幕等，这些统称为事件，Windows CE操作系统产生相应的消息，并把消息发送到相应的窗口；窗口在收到消息后，通过一种所谓的“回调”[2]方式，指示Windows CE操作系统调用相应的消息处理过程，进而完成对事件消息的处理。

嵌入式系统软硬件的特定性，使其在资源和计算能力有很大的局限性，由此，本文开发了适合嵌入式系统的围棋游戏引擎。并根据消息响应的工作方式添加相应的消息处理，从而实现Wince平台上围棋游戏的开发。

1.1 PC围棋游戏引擎的嵌入式移植

围棋游戏[3]的设计中，包括了棋盘，对弈引擎，局面评估等。

游戏的实现中，最主要的是对弈引擎的设计，即在当前诸多可下点中选取出比较好的点，从而使落子位置的选择尽可能准确，提高引擎的棋力水平。

经典的博弈搜索算法[4]主要有minmax算法、negamax算法、alphabets算法、failsoft算法、negascout算法和mtdf算法等等。近年来又有抽象证据搜索、证据数搜索、分解搜索等算法出现。

博弈搜索算法的效率决定于几个因素：状态表示、候选走法产生、确定目标状态、确定相对优势状态的静态评估函数，另外死活搜索也可能是十分重要的影响因素。

文中对弈引擎的设计，采用了蒙特卡洛博弈树搜索的思想。UCT[6]搜索是蒙特卡洛树搜索的核心，在搜索过程中，通过不断对其子节点完成一个UCB1[7]选点的过程，来走完从根节点到叶子节点的一个路径，并完成对叶子节点的评估及展开。在UCT搜索过程中，UCB1是一个通常意义上不错的公式，当然，在实际中，可以根据自己的程序进行调整。

在UCT对弈引擎中，对于整棵博弈树，记录root节点，之后，从跟节点开始，一层一层的运用UCB1公式进行选择，当到达某一叶子节点，对局面进行评估，这样便完成一次模拟。整个过程就是不断的进行模拟，直到到达某一终止条件为止，该终止条件可以是时间或模拟次数。针对嵌入式系统本身的局限性，选择适当的时间或模拟次数，使得程序在允许的资源条件内，最大的发挥计算能力，提高引擎的水平。

为了优化博弈树的搜索，同时采用逐渐扩展的算法，为了能进行逐渐扩展，就必须首先对其叶子节点有个排序，而何时引入这些新的节点，是在模拟的最后，通过对该叶子节点被访问的次数进行判断而决定是否进行扩展。

在博弈树节点的展开过程中，如果不采用任何先验的知识，其子节点在展开时多是随机的，为了避免这种盲目性，将适当的知识引入到节点展开过程中，来对各个节点的重要性有个大致认识，由此来指引其子节点的展开，使之在展开和搜索的过程中具有更高的效率。这个静态排序的工作，是在搜索节点需要展开之前完成的。在排序时，由于排序是为蒙特卡洛树搜索[9]来服务，所以在注重准确性的同时也要兼顾时间效率。但是，由于嵌入式系统内存的限制，不能一味的大量引入知识，选取知识的同时考虑效率。

博弈树搜索是个庞大的，耗内存的过程，为了使其在嵌入式系统上正常的、有效的实现，程序使用了大量剪枝。如在模拟过程中，对节点的选取和扩展。

1.2 DLL的编写

动态链接库（Dynamic Link Library，简称DLL）是一些编译过的可执行的程序模块，可以在应用程序中或其他DLL中被调用。DLL的应用非常广泛，可以实现多个应用程序的代码和资源共享，是WinCE程序设计中的一个非常重要的组成部分。作为一种基于Windows的程序模块，不仅可以包含可执行的代码，还可以包括数据和各种资源等，扩大库文件的使用范围。

本文主要针对9路围棋，实现围棋游戏需要的基本信息及游戏的基本规则，并将其封装为DLL，主要采用了蒙特卡洛树搜索实现每步棋最优点的选取，提高游戏引擎的水平。

DLL调用有两种调用方式，即静态调用方式和动态调用方式。静态调用方式由编译系统完成对DLL的加载和应用程序结束时DLL卸载的编码（如还有其它程序使用该DLL，则Windows对DLL的应用记录减1，直到所有相关程序都结束对该DLL的使用时才释放它），简单实用，能满足一般要求。动态调用方式是由编程者用API函数加载和卸载DLL来达到调用DLL的目的，使用上较复杂，但能更加有效地使用内存，是编制大型应用程序时的重要方式。

DLL的静态调用由编译系统完成对DLL的加载和应用程序结束时DLL卸载，在中静态调用DLL，首先将动态链接库的.LIB文件加入到应用程序的工程中，然后在使用DLL中的函数文件里引用DLL的头文件（.h）即可。

当采用静态方式编译并生成应用程序时，应用程序中的调用函数与LIB文件中的导出符号相匹配，这些符号或标示进入到生成的EXE文件中。当应用程序运行过程中需要加载DLL文件时，操作系统将根据这些信息查寻并加载DLL，然后通过符号或标示实现对DLL函数的动态链接。当加载应用程序的EXE文件时，所有被应用程序调用的DLL文件都被加载到内存中，这时可执行程序直接通过函数名调用DLL的输出函数，其调用方法与调用程序内部函数相同。

1.3 界面的绘制

针对围棋棋盘的特性，将棋盘看作由不同小块组合而成，从而采用分块的思想拼接棋盘。

首先针对拼接棋盘要用到的块元素，读取出每小块的各点像素值，如下图，Fig.2.1为棋盘上的星位处的像素描述：

Fig.2.2为对应像素点描述的位图图片：

根据读出的各个小块元素的像素描述矩阵，拼接出棋盘，添加消息处理，程序中添加响应函数OnPaint()，在OnPaint()中添加代码，实现棋盘及坐标的绘制，在相应的位置调用相应的块元素，拼接得到棋盘。

同时获得游戏棋子的像素描述矩阵。添加绘制棋子的函数drawGoStone()，调用棋子像素描述矩阵，实现棋子的绘制。

添加菜单，通过资源视图中的*.rc，选择“MENU”,然后“新建”在出现的空菜单条上选择第一个空处，修改它的Caption属性为“文件”，可以看到它自动变成了一个菜单项，同时可以看到字母O下面有下滑线，代表热键。

在刚才的菜单下面的子菜单空处继续添加菜单项“新建”、“打开”和“保存”，可以看到由于制表符“\t”的作用，菜单标题中的“Ctrl+N”等快捷键标示都对齐了。选择它们下一个空处，不添加Caption属性，直接在Separator属性前打勾，下一项就变成了分割线。

依照上面的方法，依次添加自己需要的菜单项。

对这些菜单项建立消息映射本质与Button相同，都是接收系统的COMMAND消息，但是因为无法通过双击来简单的建立，VS2008，每个菜单的映射函数非常容易，如：添加 文件菜单下的打开映射，只需要，进入资源视图的菜单界面，在“打开”的地方，右键点击“添加事件处理程序”，然后跳出“事件处理程序向导”，选择COMMAND消息类型，修改函数处理程序名称，点击添加编辑按钮，进入了事件处理程序补充完整。

2 游戏的实现

2.1 布局及实现

该实验的的基本思想，绘制棋盘，连接后台游戏引擎所在的DLL，调用DLL中相应的引擎等接口，实现游戏的过程，同时添加相应界面的刷新，呈现相应游戏过程，游戏终局时，输出游戏结果，伪代码代码如下：

OnPaint()//add realize code to OnPaint

{

drawBoard();

drawCoordinate(X,Y);

drawStone(point,color);

}

doGame//play game , draw the situation at the same time

{

While(!gameEnd){

Engine->play(point,color);

drawGoStone(point,color);

if(deadStone>0){

CRect rect=UpadateRegion();

InvalidateRect(&rect,false);

}

}

Result();//compute result and output

outputResult();

}

Fig.3.1为拼接后的棋盘：

Fig.

Fig.3.2，Fig3.3分别为提取死子前后，界面的刷新：

Fig.Fig.

2.2 界面与DLL连接

本文采用静态调用DLL。配置主程序的属性，单击工程右键->属性->C/C++，添加要用的.h文件所在的路径，同时在Linker->Input添加DLL相对应的.lib，实现与DLL的连接。

在DLL连接时，时常会出现如下的错误，

Windows Mobile 6.0 Unable to start program"%CSIDL_PROGRAM_FILES%\XXX\XXX.exe

此时解决方法大致为两类：

1. 把MFC库动态连接变为静态连接。

Project-->priorities-->Configuration Properties--> General-->Use of MFC:选择Use MFC in a static Library

2. 把工程需要的DLL 拷贝到模拟器的 \Windows或是.Exe所在的文件夹下。具体方法，选择开始->所有程序->vs->remote Tools->remote file viewer选择连接的模拟器，将DLL导入到模拟器。

当DLL有修改后，重新build，此时debug，会发现DLL里的断点变为空心，这是因为rebuild DLL后,该DLL的.pdb（program debug database）版本变化，debug出现问题，断点不是实心，提示错误：

The Breakpoint will not currently be hit. No executable code is currently loaded at this location

解决方法:

在debug时，选debug->windows->modules，可以看到要用到的DLL,查看DLL是否是symbols loaded，若未连接，选择load symbol,选择相应的.pdb。

2.若出现如下错误提示：

此时需要将调用此DLL的主工程下的.lib替换成重新debug后新的.lib版本。

3.结论

本实验成功的将测试程序运行在WinCE模拟器中,得到了满意的结果。与PC比较，由于嵌入式系统软硬件的特定性，使其在资源和计算能力有很大的局限性，所以游戏中涉及到的大规模计算，不得不进行适当的精简，因此，游戏对弈引擎的水平还可以得到进一步提高，到达更好的棋力水平。

参考文献

[1] 张勇,曾炽祥,许波.Windows CE 应用程序设计[M]. 西安 西安电子科技大学出版社 2008 .

[2] 范跃华,张素琴,徐飞.基于WinCE平台的应用程序移植研究[J].西安工业大学学报,2007.

[3] 周振喜,戴国骏,陈晓峰,张国煊.Windows应用程序移植到Windows CE下的策略[J].计算机工程与设计,2004.

[4] 岳鹏 计算机围棋中的算法研究[D].西南大学，西南大学，2007.

[5] 王小春 PC游戏编程(人机博弈) [M].重庆大学出版社 2005.

[6] D.B.Benson Life in the game of GO[J]. Information Sciences 10, 1976, 2:203-213.

[7] E.Berlekamp and D. Wolfe Mathematical Go End-games, Nightmares for the Professional Go Player[J].Ishi press International, 1994: 78-84.

[8] Sylvain Gelly Yizao Wang Rémi Munos and Olivier Teytaud Modification of UCT with patterns in Monte-Carlo Go. Technical Report RR-6062, INRIA, 2006, 30-56.

[9] B.Bouzy and B.Helmstetter Monte Carlo go devElopments. Technical Report RR-6065, INRIA, 2006, 6-8.

[10] 岳鹏 计算机围棋中的算法研究[D]，西南大学，西南大学，2007.

[11] 王小春 PC游戏编程(人机博弈) [M].重庆大学出版社 2005.

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文