五子棋的核心算法

五子棋是一种受大众广泛喜爱的游戏,其规则简单,变化多端,非常富有趣味性和消遣性。这里设计和实现了一个人机对下的五子棋程序,采用了博弈树的方法,应用了剪枝和最大最小树原理进行搜索发现最好的下子位置。介绍五子棋程序的数据结构、评分规则、胜负判断方法和搜索算法过程。 

一、相关的数据结构 
    关于盘面情况的表示,以链表形式表示当前盘面的情况,目的是可以允许用户进行悔棋、回退等操作。 
    CList StepList; 
    其中Step结构的表示为: 

    struct Step 
    { 
      int  m; //m,n表示两个坐标值 
      int  n; 
      char side; //side表示下子方 
    }; 
以数组形式保存当前盘面的情况, 
目的是为了在显示当前盘面情况时使用: 
  char FiveArea[FIVE_MAX_LINE][FIVE_MAX_LINE]; 

    其中FIVE_MAX_LINE表示盘面最大的行数。 

    同时由于需要在递归搜索的过程中考虑时间和空间有效性,只找出就当前情况来说相对比较好的几个盘面,而不是对所有的可下子的位置都进行搜索,这里用变量CountList来表示当前搜索中可以选择的所有新的盘面情况对象的集合: 

  CList CountList; 
    其中类CBoardSituiton为: 
  class CBoardSituation 
  { 
  CList  StepList; //每一步的列表 
  char FiveArea[FIVE_MAX_LINE][FIVE_MAX_LINE]; 
  struct Step machineStep;    //机器所下的那一步 
  double value;  //该种盘面状态所得到的分数 

二、评分规则 
    对于下子的重要性评分,需要从六个位置来考虑当前棋局的情况,分别为:-,¦,/,\,//,\\ 

    实际上需要考虑在这六个位置上某一方所形成的子的布局的情况,对于在还没有子的地方落子以后的当前局面的评分,主要是为了说明在这个地方下子的重要性程度,设定了一个简单的规则来表示当前棋面对机器方的分数。 

    基本的规则如下: 

判断是否能成5, 如果是机器方的话给予100000分,如果是人方的话给予-100000 分; 
判断是否能成活4或者是双死4或者是死4活3,如果是机器方的话给予10000分,如果是人方的话给予-10000分; 
判断是否已成双活3,如果是机器方的话给予5000分,如果是人方的话给予-5000 分; 
判断是否成死3活3,如果是机器方的话给予1000分,如果是人方的话给予-1000 分; 
判断是否能成死4,如果是机器方的话给予500分,如果是人方的话给予-500分; 
判断是否能成单活3,如果是机器方的话给予200分,如果是人方的话给予-200分; 
判断是否已成双活2,如果是机器方的话给予100分,如果是人方的话给予-100分; 
判断是否能成死3,如果是机器方的话给予50分,如果是人方的话给予-50分; 
判断是否能成双活2,如果是机器方的话给予10分,如果是人方的话给予-10分; 
判断是否能成活2,如果是机器方的话给予5分,如果是人方的话给予-5分; 
判断是否能成死2,如果是机器方的话给予3分,如果是人方的话给予-3分。 

    实际上对当前的局面按照上面的规则的顺序进行比较,如果满足某一条规则的话,就给该局面打分并保存,然后退出规则的匹配。注意这里的规则是根据一般的下棋规律的一个总结,在实际运行的时候,用户可以添加规则和对评分机制加以修正。 

三、胜负判断 
    实际上,是根据当前最后一个落子的情况来判断胜负的。实际上需要从四个位置判断,以该子为出发点的水平,竖直和两条分别为 45度角和135度角的线,目的是看在这四个方向是否最后落子的一方构成连续五个的棋子,如果是的话,就表示该盘棋局已经分出胜负。具体见下面的图示: 

四、搜索算法实现描述 
    注意下面的核心的算法中的变量currentBoardSituation,表示当前机器最新的盘面情况, CountList表示第一层子节点可以选择的较好的盘面的集合。核心的算法如下: 
void MainDealFunction() 

  value=-MAXINT; //对初始根节点的value赋值 
CalSeveralGoodPlace(currentBoardSituation,CountList); 
//该函数是根据当前的盘面情况来比较得到比较好的可以考虑的几个盘面的情况,可以根据实际的得分情况选取分数比较高的几个盘面,也就是说在第一层节点选择的时候采用贪婪算法,直接找出相对分数比较高的几个形成第一层节点,目的是为了提高搜索速度和防止堆栈溢出。 
pos=CountList.GetHeadPosition(); 
CBoardSituation* pBoard; 
for(i=0;ivalue=Search(pBoard,min,value,0); 
  Value=Select(value,pBoard->value,max);  
  //取value和pBoard->value中大的赋给根节点 

for(i=0;ivalue)  
//找出那一个得到最高分的盘面 
  { 
    currentBoardSituation=pBoard; 
    PlayerMode=min; //当前下子方改为人 
    Break; 
  } 

    其中对于Search函数的表示如下:实际上核心的算法是一个剪枝过程,其中在这个搜索过程中相关的四个参数为:(1)当前棋局情况;(2)当前的下子方,可以是机器(max)或者是人(min);(3)父节点的值oldValue;(4)当前的搜索深度depth。 

double Search(CBoardSituation& 
board,int mode,double oldvalue,int depth) 

  CList  m_DeepList; 
  if(deptholdvalue))==    TRUE) 
      { 
          if(mode==max) 
            value=select(value,search(successor 
          Board,min,value,depth+1),max); 
          else 
            value=select(value,search(successor 
            Board,max,value,depth+1),min); 
      } 
      return value; 
  } 
  else 
  { 
if ( goal(board)<>0)  
//这里goal(board)<>0表示已经可以分出胜负 
  return goal(board); 
else 
  return evlation(board); 
        } 
    } 

    注意这里的goal(board)函数是用来判断当前盘面是否可以分出胜负,而evlation(board)是对当前的盘面从机器的角度进行打分。 

    下面是Select函数的介绍,这个函数的主要目的是根据 PlayerMode情况,即是机器还是用户来返回节点的应有的值。 

double Select(double a,double b,int mode) 

  if(a>b && mode==max)&brvbar;&brvbar; (a< b && mode==min) 
return a; 
  else 
return b; 
}

时间: 2024-12-31 09:47:45

五子棋的核心算法的相关文章

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

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

搜索引擎核心算法:自然语言和布尔搜索

本人从事搜索引擎相关的工作已有十一年,今天与大家一起谈谈搜索引擎核心算法之:自然语言和布尔搜索.论述引出了如下结论:搜索爬虫和搜索引擎使用某种启发式方法给网页排名,并返回结果.爬虫观察模式,以确定某网页的内容,搜索引擎在搜索查询中查找模式,并与爬虫识别的模式进行比较,并返回结果. 这个理论的复杂性在于,我们使用的是活跃的.不断成长.不断演变的语言,这意味着语言的使用模式也在不断变化.为了跟上这种变化,搜索引擎也必须是活跃的.不断成长.不断演变的,所以在理解如何针对搜索引擎定位阿站时,启发式方法是

用户体验度终极分析 揭秘排名核心算法

关于用户体验度,你也许看过很多文章.但我觉得你需要仔细看完这篇文章,当你真正了解了这篇文章涉及的知识后,你会发现,原来你的认知还比较有限. 大家都知道用户体验度,也清楚用户体验度的重要性.而且用户体验度是百度核心算法,并且在非常长的时间内不会改变.下面给大家讲述用户体验度是怎样影响网站排名的. 一.百度所谓的用户体验度和网站的真实用户体验度是否一样? 答案是不一样.且听我细细道来,网站的用户体验度是网站真实存在的的一个东西,根据网站的跳出率就可以大致了解网站的用户体验度.但问题是,百度是无论如何

Javascript和HTML5利用canvas构建Web五子棋游戏实现算法

这只是一个简单的JAVAscript和HTML5小程序,没有实现人机对战. 五子棋棋盘落子点对应的二维数组.数组的元素对应落子点.比如数组元素值为0表示该元素对应的落子点没有棋子,数组元素值为1表示该元素对应的落子点有白棋子,数组元素值为2表示该元素对应的落子点有黑棋子: 判断五子棋赢棋的算法是通过对五子棋棋盘落子点对应的二维数组的操作来实现的. 判断五子棋赢棋算法 下边的函数可以实现判断五子棋赢棋的算法,也可以按照教材中相应的算法实现. 其中函数的参数xx.yy为数组下标,chess数组实现五

x264代码剖析(十八):核心算法之滤波

x264代码剖析(十八):核心算法之滤波           H.264/MPEG-4 AVC视频编码标准中,在编解码器反变换量化后,图像会出现方块效应,主要原因是:1)基于块的帧内和帧间预测残差的DCT变换,变换系数的量化过程相对粗糙,因而反量化过程恢复的变换系数有误差,会造成在图像块边界上的视觉不连续:2)运动补偿可能是从不是同一帧的不同位置上内插样点数据复制而来,因为运动补偿块的匹配不可能是绝对准确的,所以就会在复制块的边界上产生数据不连续:3)参考帧中的存在的不连续也被复制到需要补偿的图

x264代码剖析(十七):核心算法之熵编码(Entropy Encoding)

x264代码剖析(十七):核心算法之熵编码(Entropy Encoding)   熵编码是无损压缩编码方法,它生产的码流可以经解码无失真地恢复出原始数据.熵编码是建立在随机过程的统计特性基础上的.本文对熵编码中的CAVLC(基于上下文自适应的可变长编码)和CABAC(基于上下文的自适应二进制算术熵编码)进行简单介绍,并给出x264中熵编码对应的代码分析.     在H.264的CAVLC中,通过根据已编码句法元素的情况,动态调整编码中使用的码表,取得了极高的压缩比.CAVLC用于亮度和色度残差

x264代码剖析(十六):核心算法之宏块编码中的量化编码

x264代码剖析(十六):核心算法之宏块编码中的量化编码           为了进一步节省图像的传输码率,需要对图像进行压缩,通常采用变换编码及量化来消除图像中的相关性以减少图像编码的动态范围.本文主要介绍量化的相关内容,并给出x264中量化编码的代码分析.   1.量化编码           量化过程就是根据图像的动态范围大小确定量化参数,既保留图像必要的细节,又可以减少码流.在图像编码中,变换编码和量化从原理上讲是两个独立的过程.但在H.264中,将两个过程中的乘法合二为一,并进一步采用

x264代码剖析(十五):核心算法之宏块编码中的变换编码

x264代码剖析(十五):核心算法之宏块编码中的变换编码           为了进一步节省图像的传输码率,需要对图像进行压缩,通常采用变换编码及量化来消除图像中的相关性以减少图像编码的动态范围.本文主要介绍变换编码的相关内容,并给出x264中变换编码的代码分析.   1.变换编码           变换编码将图像时域信号变换成频域信号,在频域中图像信号能量大部分集中在低频区域,相对时域信号,码率有较大的下降. H.264对图像或预测残差采用4×4整数离散余弦变换技术,避免了以往标准中使用的通

业余草推荐阿里妈妈自研广告点击率预估核心算法MLR

业余草推荐阿里妈妈自研广告点击率预估核心算法MLR. 小编觉得CTR(广告点击率)预估的能力对于广告系统的意义和重要性,类似于在证券市场上预测股价的能力,优秀的CTR预测,通向美好和财富...(以下转载内容部分较为干货,文科生不易看懂是正常的,静静地欣赏数学之美即可...) 阿里妈妈国内领先的大数据营销平台,拥有阿里巴巴集团核心商业数据.在这里每天有超过50亿的推广流量完成超过3亿件商品的推广展现,覆盖高达98%的网民,实现数字媒体的一站式触达.在这些鲜亮数字背后,是什么样的核心算法在起作用?如