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

简介:

一. 综述

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

  

 以下是它的功能和特性:

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

  

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

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

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

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

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

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

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

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

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

二. 分析和数据结构定义

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

  1. 如何精简内存占用

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

  #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 < 15; y++ )
    {
        for ( x = 0; x < 11; 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 < 11; y++ )
    {
        for ( x = 0; x < 15; 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 < 11; y++ )
    {
        for ( x = 0; x < 11; 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 < 11; y++ )
    {
        for ( x = 4; x < 15; 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<15;a++) { for(b=0;b<15;b++) { if(ReadData(a,b,TotalCheseData)==0) { d=0; for(c=1;c<5;c++) { if(ReadData(a-c,b,TotalCheseData)!=mood||a-c==0) //左边 break; else d++; } for(c=1;c<5;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<5;c++) { if(ReadData(a,b-c,TotalCheseData)!=mood||b-c==0) //上边 break; else d++; } for(c=1;c<5;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<5;c++) { if(ReadData(a-c,b-c,TotalCheseData)!=mood||b-c==0||a-c==0) //左上 break; else d++; } for(c=1;c<5;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<5;c++) { if(ReadData(a-c,b+c,TotalCheseData)!=mood||a-c==0||b+c==14) //左下 break; else d++; } for(c=1;c<5;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<15;m++)
    {
        for(n=0;n<15;n++)
        {
            TotalMark=0;   
            for(p=0;p<4;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<15;m++)
    {
        for(n=0;n<15;n++)
        {
            TotalMark=0;
            for(p=0;p<4;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
复制代码

三.  其他模块的简单介绍

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

  • 画棋盘,选择框
  • 键盘输入
  • 菜单选择
  • 无线对战(省略)

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

  

其他模块的实现(仅供参考)
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<15;m++)
        Line(20,25+13*m,200,25+13*m);
    for(m=0;m<15;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);
    
    
    
}
u8 DrawKuang(u8 *x,u8 *y,u16  Data[29])
{
    
    u8 func_state=0;
     u8 GyroKey,myKey;
    while(func_state==0)
    {   
        SetPaintMode(0,COLOR_Black);
        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代码,真是不堪入目。不过,在单片机上实现的东西,效率比可读性和结构性更重要吧。

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


作者:热情的沙漠
出处:http://www.cnblogs.com/buptzym/
本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。


本文转自FerventDesert博客园博客,原文链接:http://www.cnblogs.com/buptzym/archive/2012/06/20/2556052.html,如需转载请自行联系原作者
目录
相关文章
|
5月前
|
数据采集 算法 机器人
软件体系结构 - 调度算法(3) 单调速率调度算法
【4月更文挑战第19天】软件体系结构 - 调度算法(3) 单调速率调度算法
136 0
|
16天前
|
算法 程序员 Python
程序员必看!Python复杂度分析全攻略,让你的算法设计既快又省内存!
在编程领域,Python以简洁的语法和强大的库支持成为众多程序员的首选语言。然而,性能优化仍是挑战。本文将带你深入了解Python算法的复杂度分析,从时间与空间复杂度入手,分享四大最佳实践:选择合适算法、优化实现、利用Python特性减少空间消耗及定期评估调整,助你写出高效且节省内存的代码,轻松应对各种编程挑战。
26 1
|
5月前
|
存储 监控 NoSQL
Redis处理大量数据主要依赖于其内存存储结构、高效的数据结构和算法,以及一系列的优化策略
【5月更文挑战第15天】Redis处理大量数据依赖内存存储、高效数据结构和优化策略。选择合适的数据结构、利用批量操作减少网络开销、控制批量大小、使用Redis Cluster进行分布式存储、优化内存使用及监控调优是关键。通过这些方法,Redis能有效处理大量数据并保持高性能。
80 1
|
2月前
|
存储 算法 大数据
小米教你:2GB内存搞定20亿数据的高效算法
你好,我是小米。本文介绍如何在2GB内存中找出20亿个整数里出现次数最多的数。通过将数据用哈希函数分至16个小文件,每份独立计数后选出频次最高的数,最终比对得出结果。这种方法有效解决大数据下的内存限制问题,并可应用于更广泛的场景。欢迎关注我的公众号“软件求生”,获取更多技术分享!
151 12
|
3月前
|
人工智能 算法 数据可视化
算法金 | 我最常用的两个数据可视化软件,强烈推荐
**算法金**分享数据可视化利器——Tableau与Python的Matplotlib。Tableau,BI界的精英,提供直观拖放界面,快速生成美观图表;Matplotlib,Python绘图库鼻祖,支持复杂图形定制,广泛应用于科学可视化。文中通过趋势图、频数图、结构图、分布图、相关图等多种图表实例,展示了两者在洞察数据、揭示模式和关系方面的强大功能。无论新手还是老将,都能借助这些工具提升数据分析和展示的技艺。
28 0
算法金 | 我最常用的两个数据可视化软件,强烈推荐
|
3月前
|
算法 Java
Java演进问题之标记-复制算法导致更多的内存占用如何解决
Java演进问题之标记-复制算法导致更多的内存占用如何解决
|
4月前
|
监控 算法 Java
Java虚拟机(JVM)使用多种垃圾回收算法来管理内存,以确保程序运行时不会因为内存不足而崩溃。
【6月更文挑战第20天】Java JVM运用多种GC算法,如标记-清除、复制、标记-压缩、分代收集、增量收集、并行收集和并发标记,以自动化内存管理,防止因内存耗尽导致的程序崩溃。这些算法各有优劣,适应不同的性能和资源需求。垃圾回收旨在避免手动内存管理,简化编程。当遇到内存泄漏,可以借助VisualVM、JConsole或MAT等工具监测内存、生成堆转储,分析引用链并定位泄漏源,从而解决问题。
50 4
|
4月前
|
存储 算法 安全
JVM-内存划分-垃圾回收器-回收算法-双亲委派-三色标记
JVM-内存划分-垃圾回收器-回收算法-双亲委派-三色标记
|
4月前
|
存储 运维 算法
社交软件红包技术解密(十三):微信团队首次揭秘微信红包算法,为何你抢到的是0.01元
本文中,我们将介绍几种主流的IM红包分配算法,相信聪明的你一定能从中窥见微信红包技术实现的一些奥秘。
77 0