天天看点

XMOVE3.0手持终端——软件介绍(四):在2KB内存的单片机上实现的超精简五子棋对战算法(原创)二. 分析和数据结构定义三.  其他模块的简单介绍四.  算法主流程(简化版) 五. 总结和改进

XMOVE3.0手持终端——软件介绍(四):在2KB内存的单片机上实现的超精简五子棋对战算法(原创)二. 分析和数据结构定义三.  其他模块的简单介绍四.  算法主流程(简化版) 五. 总结和改进

  

XMOVE3.0手持终端——软件介绍(四):在2KB内存的单片机上实现的超精简五子棋对战算法(原创)二. 分析和数据结构定义三.  其他模块的简单介绍四.  算法主流程(简化版) 五. 总结和改进
XMOVE3.0手持终端——软件介绍(四):在2KB内存的单片机上实现的超精简五子棋对战算法(原创)二. 分析和数据结构定义三.  其他模块的简单介绍四.  算法主流程(简化版) 五. 总结和改进

 以下是它的功能和特性:

内存占用极低,约600byte

执行一次迭代过程,算法在初级水平(同学,这是单片机,不是电脑!)

在8mhz的msp430上算法执行时间不超过0.3s

支持人机对战,双人对战和无线对战(通过nrf24l01实现)

代码精简

嵌入式彩屏gui实现

支持陀螺仪体感旋转放置棋子

    与xmove手持终端相关的介绍文章列表如下:

  下面我将简要的介绍系统实现过程,同时附上源代码。不过因为我系统对低内存平台做了特别的优化,如果你要纯粹往pc上移植的话,可能还不如去pudn上面下代码来得快。当然参考一下设计思路也是有价值的。

  我们要重点分析以下几个问题:

  为了简化代码,我做了如下的定义:

  #define unsigned char u8 //8bit

      #define unsigned intu16 //16bit

  对于2kb内存的单片机,已经有将近1kb用于系统本身,可供使用的应用内存不超过1kb。如果不做优化,内存必然不够用。可以简单做个计算,五子棋盘大小15*15,每格存在三种情况,黑子,白子,无子,若用byte型存储,就需要225byte,若加上中间迭代过程是完全不够的。

  因此我做了如下简化:每个子只占用两个bit,因此总共225个点,采用16bit的unsigned int存储,仅仅需要29大小的数组

XMOVE3.0手持终端——软件介绍(四):在2KB内存的单片机上实现的超精简五子棋对战算法(原创)二. 分析和数据结构定义三.  其他模块的简单介绍四.  算法主流程(简化版) 五. 总结和改进

  做了这样的简化,必须提供读取或写入某点是何情况的接口函数:

  ps:大三写的c代码,有点丑陋,大家随便看看吧

  系统在任意一方下棋之后,需要检测该方是否获胜,很简单,我们检测横竖,左斜和右斜四种情况是否满足五子连珠即可:

  如前所述,由于单片机的硬件和内存限制,我们需要在算法实现上做一些必要的妥协:

  按盘面分析填写棋型表:本程序核心模块之一,人工智能算法的根本依据。其具体实现方法如下:在下五子棋时,一定会先根据棋盘上的情况,找出当前最重要的一些点位,如“活三”、“冲四”等;然后再在其中选择落子点。但是,电脑不会像人一样分析问题,要让它知道哪是“活三”、哪是“冲四”,就得在棋盘上逐点计算,一步一步的教它。

先来分析己方的棋型,我们从棋盘左上角出发,向右逐行搜索,当遇到一个空白点时,以它为中心向左挨个查找,如果遇到己方的子则记录然后继续,如果遇到对方的子、空白点或边界就停止查找。左边完成后再向右进行同样的操作;最后把左右两边的记录合并起来,得到的数据就是该点横向上的棋型,然后把棋型的编号填入到computer[x][y][n]中就行了(x、y代表坐标,n=0、1、2、3分别代表横、竖、左斜、右斜四个方向)。而其他三个方向的棋型也可用同样的方法得到,当搜索完整张棋盘后,己方棋型表也就填写完毕了。然后再用同样的方法填写对方棋型表。

注意:所有棋型的编号都要事先定义好,越重要的号数越大。经过我的测试,从0子到四子连珠的评分标准可以用这个数组来表达:long marktransform[5]={0,100,400,2000,10000};

  于是,电脑在下棋时,仅仅需要计算哪个点的评分最大,就在这点下棋。

  如果大家仔细的看了第三部分的内容,就不难得到算法核心了,但问题也来了。我们要存储computer和人这两个巨大的三维数组。所以必须制定自己的一套内存分配规则,来尽可能减小内存占用花销。

  每个空子的位置,从左右方向的己方的子不会超过5种,所以,我们可以用4bit来存储(它可以储存8种情况)。 对每一方,例如计算机方,我们定义一个数组u16 data[8][29], u16 和29的来源在第一节就已经讲过,是225个点的存储。至于前面的8的来源:上下左斜右斜攻击四类情况,每类需要2bit,所以要定义8这样的大小。如下图:

XMOVE3.0手持终端——软件介绍(四):在2KB内存的单片机上实现的超精简五子棋对战算法(原创)二. 分析和数据结构定义三.  其他模块的简单介绍四.  算法主流程(简化版) 五. 总结和改进

   以下是计算整个棋盘每个点的评价值,存储在data的临时数组当中, a,b,c,d四个寄存器,分别存储x,y坐标,向左和向右两个方向的判断步数(最多到4),以及该空点在该线的连子数目。

  获取以上的评价规则后,我们得到对某一方的最核心的计算下子位置的函数:

  在形参表中x,y通过指针的形式返回真正的计算结果, u16 data1和 data2分别是己方和对方的棋型表, totalchesedata则是整个棋盘当前局势。算法挨个遍历每个点,计算该点在四个方向上的权值之和。分别计算己方和对方的值,最大评分点就是下子点。

  其实完全可以这么理解,若己方的最大值大于对方的最大值,这显然对己方是有利的,己方应该进攻大于防守; 反之,对方已占先机,我方应该放手大于进攻。

  要实现五子棋,除了核心算法还有其他外围模块作为支持,有以下的函数:

画棋盘,选择框

键盘输入

菜单选择

无线对战(省略)

  考虑到不同平台和硬件环境下,这些功能的实现可能完全不同,所以我仅仅贴一些示意性代码:

  流程因为很简单,所以就不画了。

  实现五子棋的算法有很多选项,比如基于博弈树的剪枝算法,和我这种比较简化的靠遍历评分的算法。这个算法来自于网上,水平仅仅算是初级,缺点也很明显,      

      只顾眼前利益,不能顾全大局,这就和许多五子棋初学者一样犯了“目光短浅”的毛病。要解决这个问题,我们引入‘今后几步预测法’,具体方法是这样的: 首先, 让电脑分析一个可能的点,

如果在这儿下子将会形成对手不得不防守的棋型(例如:‘冲四’、‘活三’);那么下一步对手就会照您的思路下子来防守您,如此一来便完成了第一步的预测。这时再调用模块4对预测后的棋进行盘面分析,如果出现了‘四三’、‘双三’或‘双四’等制胜点,那么己方就可以获胜了(当然对黑棋而言‘双三’、‘双四’是禁手,另当别论);否则照同样的方法向下分析,就可预测出第二步、第三步……

  不过,我做过实际的测试,加上两步迭代以后,计算时间变为原来的10倍左右(确实是指数级的),但此时内存是不够用的。考虑到是2kb内存的超低功耗单片机,实现更复杂的算法勉为其难,我也就没有在上面实现迭代,有兴趣的同学们可以尝试实现之,其实不难,用个好点的cpu,比如stm32,(用电脑就别用我这个算法了),稍微改改代码就可以。这种情况,电脑的水平在中级左右。

  系统没有随机性,换句话说,如果你每次下子的方式是一样的,那么系统演化的形式完全一致。

  顺便提一下,自从学习了c#编程以后,看了两年前写的c代码,真是不堪入目。不过,在单片机上实现的东西,效率比可读性和结构性更重要吧。

  有任何问题,欢迎随时交流。

继续阅读