提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  硬件

当前栏目

XMOVE3.0手持终端——软件介绍(四):在2KB内存的单片机上实现的超精简五子棋对战算法（原创）

内存算法软件单片机 实现 介绍 终端 原创
2023-09-14 08:58:00 时间
一. 综述

这是我两年前完成的一个小项目，它基于我开发的XMOVE动作感应系统平台。五子棋算法网上随便一搜到处都是，不过值得自豪的是，我在2KB内存的单片机上不仅跑上了我自制的嵌入式OS，还能同时跑五子棋。这是界面截图：

 以下是它的功能和特性：

内存占用极低，约600byte 执行一次迭代过程，算法在初级水平（同学，这是单片机，不是电脑！） 在8MHz的MSP430上算法执行时间不超过0.3s 支持人机对战，双人对战和无线对战（通过NRF24L01实现） 嵌入式彩屏GUI实现 支持陀螺仪体感旋转放置棋子

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

硬件综述: 自制的彩屏手持动作感应终端

软件综述:手持终端功能介绍

软件介绍(一):精简型嵌入式系统的菜单实现和任务切换

软件介绍(二):在2KB内存单片机上实现的彩屏GUI控件库

软件介绍(三):在2KB内存单片机上实现的俄罗斯方块

软件介绍(四):在2KB内存单片机上实现的超精简五子棋算法

软件介绍(五):在2KB内存的单片机上实现的T9中文输入法

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

二. 分析和数据结构定义

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

如何精简内存占用

为了简化代码，我做了如下的定义：

#define unsigned char u8 //8bit

      #define unsigned intu16 //16bit

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

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

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

PS:大三写的C代码，有点丑陋，大家随便看看吧


//x,y是横纵坐标，Data是数组

//返回0：无子，1 ：黑子，2：白子

u8 ReadData(u8 x,u8 y,u16 Data[29])

 u8 t=y+x*15;

 u16 temp=0x03;

 temp=temp 2*(t%8);

 return ((Data[t/8] temp) (2*(t%8)));

//x,y是横纵坐标，Data是数组

// dat 0：无子，1 ：黑子，2：白子

void WriteData(u8 x,u8 y,u16 Data[29],u8 dat)

 u8 t=y+x*15;

 u16 Dat=dat;

 u16 temp=0x03;

 temp=temp 2*(t%8);

 temp=0xffff-temp;

 Dat=Dat 2*(t%8);

 Data[t/8]=(Data[t/8] temp)|Dat;

}

2. 判断胜负

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


u8 ResultCheck(u16 Data[29],u8 color) //成功测试 返回值：0：不成功，1 白方， 2黑方

 int x, y;

 // 判断横向

 for ( y = 0; y y++ )

 for ( x = 0; x x++ )

 if ( color ==ReadData(x,y,Data) 

 color == ReadData(x+1,y,Data) 

 color == ReadData(x+2,y,Data) 

 color == ReadData(x+3,y,Data) 

 color == ReadData(x+4,y,Data) )

 return color;

 // 判断纵向

 for ( y = 0; y y++ )

 for ( x = 0; x x++ )

 if ( color ==ReadData(x,y,Data) 

 color ==ReadData(x,y+1,Data) 

 color == ReadData(x,y+2,Data) 

 color ==ReadData(x,y+3,Data) 

 color == ReadData(x,y+4,Data) )

 return color;

 // 判断"\"方向

 for ( y = 0; y y++ )

 for ( x = 0; x x++ )

 if ( color == ReadData(x,y,Data) 

 color == ReadData(x+1,y+1,Data) 

 color ==ReadData(x+2,y+2,Data) 

 color ==ReadData(x+3,y+3,Data) 

 color == ReadData(x+4,y+4,Data) )

 return color;

 // 判断"/"方向

 for ( y = 0; y y++ )

 for ( x = 4; x x++ )

 if ( color == ReadData(x,y,Data) 

 color == ReadData(x-1,y+1,Data) 

 color == ReadData(x-2,y+2,Data) 

 color == ReadData(x-3,y+3,Data) 

 color == ReadData(x-4,y+4,Data) )

 return color;

 // 不满足胜利条件

 return 0;



  3. 核心算法


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



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


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


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



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


 4. 核心算法实现和内存优化


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



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



 






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







//Data：棋型表 TotalCheseData当前全局的棋盘数据

void CalGameSatus(u16 Data[][29],u16 TotalCheseData[29],u8 mood) //mood=2黑方判断，mood=1；白方判断

 u8 a,b,c,d;

 for(a=0;a a++)

 for(b=0;b b++)

 if(ReadData(a,b,TotalCheseData)==0)

 d=0;

 for(c=1;c c++)

 if(ReadData(a-c,b,TotalCheseData)!=mood||a-c==0) //左边

 break;

 else

 d++;

 for(c=1;c c++)

 if(ReadData(a+c,b,TotalCheseData)!=mood||a-c==14) //右边

 break;

 else

 d++;

 WriteData(a,b,Data[0],d%4); //写入横向数据

 WriteData(a,b,Data[1],d/4); 

 d=0;

 for(c=1;c c++)

 if(ReadData(a,b-c,TotalCheseData)!=mood||b-c==0) //上边

 break;

 else

 d++;

 for(c=1;c c++)

 if(ReadData(a,b+c,TotalCheseData)!=mood||b+c==14)

 break;

 else

 d++;

 WriteData(a,b,Data[2],d%4); //纵向数据

 WriteData(a,b,Data[3],d/4); //纵向数据

 d=0;

 for(c=1;c c++)

 if(ReadData(a-c,b-c,TotalCheseData)!=mood||b-c==0||a-c==0) //左上

 break;

 else

 d++;

 for(c=1;c c++)

 if(ReadData(a+c,b+c,TotalCheseData)!=mood||b+c==14||a+c==14)

 break;

 else

 d++;

 WriteData(a,b,Data[4],d%4); //左斜数据

 WriteData(a,b,Data[5],d/4); 

 d=0;

 for(c=1;c c++)

 if(ReadData(a-c,b+c,TotalCheseData)!=mood||a-c==0||b+c==14) //左下

 break;

 else

 d++;

 for(c=1;c c++)

 if(ReadData(a+c,b-c,TotalCheseData)!=mood||a+c==14||b-c==0) //右下

 break;

 else

 d++;

 WriteData(a,b,Data[6],d%4); //右斜数据

 WriteData(a,b,Data[7],d/4); 

}



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



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



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







void CalPushPosition(u8 *X, u8 *Y,u16 Data1[][29],u16 Data2[][29],u16 TotalCheseData[29])

 long TotalMark,MaxMark=0;

 long MarkTransform[5]={0,100,400,2000,10000};

 u8 m,n,p,Mark;

 CalGameSatus(Data1,TotalCheseData,1);

 for(m=0;m m++)

 for(n=0;n n++)

 TotalMark=0; 

 for(p=0;p p++ ) //对四个方向，看连子的数目，总评价分由这四个方向的值之和所决定

 Mark=ReadData(m,n,Data1[2*p])+4*ReadData(m,n,Data1[2*p+1]); //读取在x,y坐标下，连子的数目，其存储过程见棋型表存储结构

 TotalMark+= MarkTransform[Mark];

 if(TotalMark MaxMark)

 *X=m,*Y=n;

 MaxMark=TotalMark;

 CalGameSatus(Data2,TotalCheseData,2);

 for(m=0;m m++)

 for(n=0;n n++)

 TotalMark=0;

 for(p=0;p p++)

 Mark= ReadData(m,n,Data2[2*p])+4*ReadData(m,n,Data2[2*p+1]);

 TotalMark+=MarkTransform[Mark]; 

 if(TotalMark MaxMark)

 *X=m,*Y=n;

 MaxMark=TotalMark;



三.  其他模块的简单介绍


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


画棋盘，选择框

无线对战（省略）


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







其他模块的实现（仅供参考）

void DrawDesk()

 u8 m;

 Clear_Screen();

 SetPaintMode(0,COLOR_Black);

 Rectangle(23,28,205,210,1);

 SetPaintMode(0,COLOR_Yellow);

 Rectangle(20,25,202,207,1);

 SetPaintMode(0,COLOR_Black);

 for(m=0;m m++)

 Line(20,25+13*m,200,25+13*m);

 for(m=0;m m++)

 Line(20+13*m,25,20+13*m,207);

 //Lcd_disp(240,12,"五子棋");

 //Lcd_disp(65,36,"赵一鸣之作");

void Drawchess(u8 x,u8 y, u8 mood)

 if(mood==2)//黑方

 SetPaintMode(0,COLOR_Black);

 Circle(20+13*x,25+y*13,5,1);

 //Rectangle(2+x*4,1+y*4,4+x*4,3+y*4,1);

 else if(mood==1)

 SetPaintMode(0,COLOR_White);

 Circle(20+13*x,25+y*13,5,1);

 SetPaintMode(0,COLOR_Black);

 Circle(20+13*x,25+y*13,5,0);

void PushChess(u8 x,u8 y,u16 Data[29],u8 mood)

 Drawchess(x,y,mood);

 WriteData(x,y,Data,mood);


 Rectangle(14+*x*13,19+*y*13,26+*x*13,31+*y*13,0);

 if(GyroControlEN==1 back_light 1 GyroMenuEN)

 delay_ms(200);

 L3G4200DReadData();

 L3G4200DShowData();

 delay_ms(200);

 else

 InputControl(); 

 GyroKey=GyroKeyBoardInputMethod(0,0,300,300);

 if(GyroKey!=KEYNULL)

 myKey=GyroKey;

 else

 myKey=key_data;

 GyroKey=KEYNULL;

 SetPaintMode(0,COLOR_Yellow);

 Rectangle(14+*x*13,19+*y*13,26+*x*13,31+*y*13,0);

 SetPaintMode(0,COLOR_Black);

 PutPixel(20+(*x)*13,19+(*y)*13);

 PutPixel(20+(*x)*13,(*y)*13+31);

 PutPixel(14+(*x)*13,(*y)*13+25);

 PutPixel(26+(*x)*13,(*y)*13+25);

 switch(myKey)

 case KEYENTER_UP :

 if(ReadData(*x,*y,Data)==0)

 func_state=1;

 break;

 case KEYCANCEL_UP :

 return 0;

 default:

 FourDirectionInputMethod(myKey,1,1,1,1,0,14,0,14,0,0, x,y);

 myKey=KEYNULL;

 return 1;

}



四.  算法主流程（简化版）


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







while(OS_func_state==0) //OS_func_state==0是正常的下棋状态

if(func_state==0) //我方下棋

 if(DrawKuang( XAxi, YAxi,TotalCheseData))

 PushChess(XAxi,YAxi,TotalCheseData,2);

 else

 OS_func_state=10; //跳出态

 if(ResultCheck(TotalCheseData,2)==2) //胜利，跳出到成功界面

 OS_func_state=5; 

 else

 func_state=1; //让给对方下棋

 else //对方下棋

 GameSatusInit(myGameSatus);

 GameSatusInit(itGameSatus);

 CalPushPosition( XAxi, YAxi,myGameSatus,itGameSatus,TotalCheseData);

 PushChess(XAxi,YAxi,TotalCheseData,1);

 if(ResultCheck(TotalCheseData,1)==1) 

 OS_func_state=5;

 else

 func_state=0; 

}



 五. 总结和改进


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



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


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



      



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



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



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



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















  “Unity开发也能跟硬件联动”--快来看看吧(串口通信) 

 简单的串口通信工具，基于C#应用程序WinFrom实现

串行接口简称串口，也称串行通信接口或串行通讯接口（通常指COM接口），是采用串行通信方式的扩展接口。（至于再详细，自己百度）

工业领域使用较多，比如:数据采集，设备控制等等，好多都是用串口通信来实现！你要是细心的话，你会发现，目前家用国网智能电能表就具备RS485通信总线（串行总线的一种）与RS232可以相互转化（当然一般，非专业的谁也不会闲的蛋疼，趴电表上瞎看,最多也就看看走了多少度电）

相关文章