在2KB内存的单片机上实现的超精简五子棋对战算法（原创）.doc

1、一. 综述 这是我两年前完成的一个小项目，它基于我开发的 XMOVE 动作感应系统平台。五子棋算 法网上随便一搜到处都是，不过值得自豪的是，我在 2KB 内存的单片机上不仅跑上了我自制的 嵌入式 OS，还能同时跑五子棋。这是界面截图： 以下是它的功能和特性： 内存占用极低，约 600byte 执行一次迭代过程，算法在初级水平（同学，这是单片机，不是电脑！） 在 8MHz 的 MSP430 上算法执行时间不超过 0.3s 支持人机对战，双人对战和无线对战（通过 NRF24L01 实现） 代码精简 嵌入式彩屏 GUI 实现 支持陀螺仪体感旋转放置棋子 下面我将简要的介绍系统实现过程，同时附上源代码

2、。不过因为我系统对低内存平台做了 特别的优化，如果你要纯粹往 PC 上移植的话，可能还不如去 PUDN 上面下代码来得快。当然 参考一下设计思路也是有价值的。 二. 分析和数据结构定义 我们要重点分析以下几个问题： 1.如何精简内存占用 为了简化代码，我做了如下的定义： #define unsigned char u8 /8bit #define unsigned intu16 /16bit 对于 2KB 内存的单片机，已经有将近 1KB 用于系统本身，可供使用的应用内存不超过 1 KB。如果不做优化， 内存必然不够用。可以简单做个计算，五 子棋盘大小 15*15，每格存在三种情况，黑子，白子

3、，无子，若用 byte 型存储，就需要 225 byte,若加上中间迭代过程是完全不够的。 因此我做了如下简化：每个子只占用两个 bit,因此总共 225 个点，采用 16bit 的 unsign ed int 存储，仅仅需要 29 大小的数组 做了这样的简化，必须提供读取或写入某点是何情况的接口函数： PS: 大三写的 C 代码，有点丑陋，大家随便看看吧 /x,y 是横纵坐标，Data 是数组 /返回 0：无子，1 ：黑子，2：白子 u8 ReadData(u8 x,u8 y,u16 Data29) u8 t=y+x*15; u16 temp=0x03; temp=temp(2*(t%8);

4、 /x,y 是横纵坐标，Data 是数组 / dat 0：无子，1 ：黑子，2：白子 void WriteData(u8 x,u8 y,u16 Data29,u8 dat) u8 t=y+x*15; u16 Dat=dat; u16 temp=0x03; temp=temp2*(t%8); temp=0xffff-temp; Dat=Dat2*(t%8); Datat/8=(Datat/8 2. 判断胜负 系统在任意一方下棋之后，需要检测该方是否获胜，很简单，我们检测横竖，左斜和右斜 四种情况是否满足五子连珠即可： u8 ResultCheck(u16 Data29,u8 color) /成功

5、测试 返回值：0：不成功，1 白方， 2 黑 方 int x, y; / 判断横向 for ( y = 0; y 15; y+ ) for ( x = 0; x 11; x+ ) if ( color =ReadData(x,y,Data) / 判断纵向 for ( y = 0; y 11; y+ ) for ( x = 0; x 15; x+ ) if ( color =ReadData(x,y,Data) / 判断“方向 for ( y = 0; y 11; y+ ) for ( x = 0; x 11; x+ ) if ( color = ReadData(x,y,Data) / 判断“

6、/“方向 for ( y = 0; y 11; y+ ) for ( x = 4; x 15; x+ ) if ( color = ReadData(x,y,Data) / 不满足胜利条件 return 0; 3. 核心算法 如前所述，由于单片机的硬件和内存限制，我们需要在算法实现上做一些必要的妥协： 按盘面分析填写棋型表：本程序核心模块之一，人工智能算法的根本依据。其具体实现方 法如下：在下五子棋时，一定会先根据棋盘上的情况，找出当前最重要的一些点位，如“活三” 、“冲四”等；然后再在其中选择落子点。但是，电脑不会像人一样分析问题，要让它知道哪是“ 活三”、哪是“冲四” ，就得在棋盘上逐点计

7、算，一步一步的教它。 先来分析己方的棋型，我们从棋盘左上角出发，向右逐行搜索，当遇到一个空白点时，以 它为中心向左挨个查找，如果遇到己方的子则记录然后继续，如果遇到对方的子、空白点或边 界就停止查找。左边完成后再向右进行同样的操作；最后把左右两边的记录合并起来，得到的 数据就是该点横向上的棋型，然后把棋型的编号填入到 Computerxyn中就行了（x、y 代表坐标，n=0、1 、2、3 分别代表横、竖、左斜、右斜四个方向）。而其他三个方向的棋型 也可用同样的方法得到，当搜索完整张棋盘后，己方棋型表也就填写完毕了。然后再用同样的 方法填写对方棋型表。 注意：所有棋型的编号都要事先定义好，越重要

8、的号数越大。经过我的测试，从 0 子到四 子连珠的评分标准可以用这个数组来表达：long MarkTransform5=0,100,400,2000,1 0000; 于是，电脑在下棋时，仅仅需要计算哪个点的评分最大，就在这点下棋。 4. 核心算法实现和内存优化 如果大家仔细的看了第三部分的内容，就不难得到算法核心了，但问题也来了。我们要存 储 Computer 和人这两个巨大的三维数组。所以必须制定自己的一套内存分配规则，来尽可能 减小内存占用花销。 每个空子的位置，从左右方向的己方的子不会超过 5 种，所以，我们可以用 4bit 来存储 （它可以储存 8 种情况）。 对每一方，例如计算机方，

9、我们定义一个数组 u16 Data829 ， u16 和 29 的来源在第一节就已经讲过，是 225 个点的存储。至于前面的 8 的来源：上下 左斜右斜攻击四类情况，每类需要 2bit，所以要定义 8 这样的大小。如下图： 以下是计算整个棋盘每个点的评价值，存储在 Data 的临时数组当中， a,b,c,d 四个寄 存器，分别存储 x,y 坐标，向左和向右两个方向的判断步数（最多到 4）,以及该空点在该线的 连子数目。 /Data：棋型表 TotalCheseData 当前全局的棋盘数据 void CalGameSatus(u16 Data29,u16 TotalCheseData29,u8

10、mood) /mood=2 黑方 判断，mood=1；白方判断 u8 a,b,c,d; for(a=0;a15;a+) for(b=0;b15;b+) if(ReadData(a,b,TotalCheseData)=0) d=0; for(c=1;c5;c+) if(ReadData(a-c,b,TotalCheseData)!=mood|a-c=0) /左边 break; else d+; for(c=1;c5;c+) if(ReadData(a+c,b,TotalCheseData)!=mood|a-c=14) /右边 break; else d+; WriteData(a,b,Data0

11、,d%4); /写入横向数据 WriteData(a,b,Data1,d/4); d=0; for(c=1;c5;c+) if(ReadData(a,b-c,TotalCheseData)!=mood|b-c=0) /上边 break; else d+; for(c=1;c5;c+) if(ReadData(a,b+c,TotalCheseData)!=mood|b+c=14) break; else d+; WriteData(a,b,Data2,d%4); /纵向数据 WriteData(a,b,Data3,d/4); /纵向数据 d=0; for(c=1;c5;c+) if(ReadDa

12、ta(a-c,b-c,TotalCheseData)!=mood|b-c=0|a-c=0) /左上 break; else d+; for(c=1;c5;c+) if(ReadData(a+c,b+c,TotalCheseData)!=mood|b+c=14|a+c=14) break; else d+; WriteData(a,b,Data4,d%4); /左斜数据 WriteData(a,b,Data5,d/4); d=0; for(c=1;c5;c+) if(ReadData(a-c,b+c,TotalCheseData)!=mood|a-c=0|b+c=14) /左下 break; e

13、lse d+; for(c=1;c5;c+) if(ReadData(a+c,b-c,TotalCheseData)!=mood|a+c=14|b-c=0) /右下 break; else d+; WriteData(a,b,Data6,d%4); /右斜数据 WriteData(a,b,Data7,d/4); 获取以上的评价规则后，我们得到对某一方的最核心的计算下子位置的函数： 在形参表中 x,y 通过指针的形式返回真正的计算结果， u16 Data1 和 Data2 分别是己 方和对方的棋型表， TotalCheseData 则是整个棋盘当前局势。算法挨个遍历每个点，计算 该点在四个方向上

14、的权值之和。分别计算己方和对方的值，最大评分点就是下子点。 其实完全可以这么理解，若己方的最大值大于对方的最大值，这显然对己方是有利的，己 方应该进攻大于防守； 反之，对方已占先机，我方应该放手大于进攻。 void CalPushPosition(u8 *X, u8 *Y,u16 Data129,u16 Data229,u16 TotalCh eseData29) long TotalMark,MaxMark=0; long MarkTransform5=0,100,400,2000,10000; u8 m,n,p,Mark; CalGameSatus(Data1,TotalCheseData

15、,1); for(m=0;m15;m+) for(n=0;n15;n+) TotalMark=0; for(p=0;pMaxMark) *X=m,*Y=n; MaxMark=TotalMark; CalGameSatus(Data2,TotalCheseData,2); for(m=0;m15;m+) for(n=0;n15;n+) TotalMark=0; for(p=0;pMaxMark) *X=m,*Y=n; MaxMark=TotalMark; /*void 三. 其他模块的简单介绍 要实现五子棋，除了核心算法还有其他外围模块作为支持，有以下的函数： 画棋盘，选择框 键盘输入 菜单选择

16、 无线对战（省略） 考虑到不同平台和硬件环境下，这些功能的实现可能完全不同，所以我仅仅贴一些示意性 代码： 其他模块的实现（仅供参考） 四. 算法主流程（简化版） 流程因为很简单，所以就不画了。 while(OS_func_state=0) /OS_func_state=0 是正常的下棋状态 if(func_state=0) /我方下棋 if(DrawKuang( else OS_func_state=10; /跳出态 if(ResultCheck(TotalCheseData,2)=2) /胜利，跳出到成功界面 OS_func_state=5; else func_state=1; /让给对

17、方下棋 else /对方下棋 GameSatusInit(myGameSatus); GameSatusInit(itGameSatus); CalPushPosition( PushChess(XAxi,YAxi,TotalCheseData,1); if(ResultCheck(TotalCheseData,1)=1) OS_func_state=5; else func_state=0; 五. 总结和改进 实现五子棋的算法有很多选项，比如基于博弈树的剪枝算法，和我这种比较简化的靠遍历 评分的算法。这个算法来自于网上，水平仅仅算是初级，缺点也很明显， 只顾眼前利益，不能顾全大局，这就和许多

18、五子棋初学者一样犯了“ 目光短浅”的毛病。要 解决这个问题，我们引入今后几步预测法 ，具体方法是这样的： 首先， 让电脑分析一个可 能的点， 如果在这儿下子将会形成对手不得不防守的棋型（例如：冲四、活三 ）；那么下一步对手就 会照您的思路下子来防守您，如此一来便完成了第一步的预测。这时再调用模块 4 对预测后的 棋进行盘面分析，如果出现了四三 、双三或 双四等制胜点，那么己方就可以获胜了（当然 对黑棋而言双三 、双四 是禁手，另当别论）；否则照同样的方法向下分析，就可预测出第二 步、第三步 不过，我做过实际的测试，加上两步迭代以后，计算时间变为原来的 10 倍左右（确实是 指数级的），但此时内存是不够用的。考虑到是 2KB 内存的超低功耗单片机，实现更复杂的算 法勉为其难，我也就没有在上面实现迭代，有兴趣的同学们可以尝试实现之，其实不难，用个 好点的 CPU，比如 STM32,（用电脑就别用我这个算法了），稍微改改代码就可以。这种情况 ，电脑的水平在中级左右。 系统没有随机性，换句话说，如果你每次下子的方式是一样的，那么系统演化的形式完全 一致。 顺便提一下，自从学习了 C#编程以后，看了两年前写的 C 代码，真是不堪入目。不过， 在单片机上实现的东西，效率比可读性和结构性更重要吧。 有任何问题，欢迎随时交流。