5子棋是
![](/icons/58237yi.gif)
种受大众广泛喜爱
![](/icons/58237de.gif)
游戏
![](/icons/58237dou.gif)
其规则简单
![](/icons/58237dou.gif)
变化多端
![](/icons/58237dou.gif)
非常富有趣味性和消遣性
![](/icons/58237dou2.gif)
这里设计和实现了
![](/icons/58237yi.gif)
个人机对下
![](/icons/58237de.gif)
5子棋
![](/icons/58237chengxu.gif)
![](/icons/58237dou.gif)
采用了博弈树
![](/icons/58237de.gif)
思路方法
![](/icons/58237dou.gif)
应用了剪枝和最大最小树原理进行搜索发现最好
![](/icons/58237de.gif)
下子位置
![](/icons/58237dou2.gif)
介绍 5子棋
![](/icons/58237chengxu.gif)
![](/icons/58237de.gif)
数据结构、评分规则、胜负判断思路方法和搜索算法过程
![](/icons/58237yi.gif)
、相关
![](/icons/58237de.gif)
数据结构
有关盘面情况
![](/icons/58237de.gif)
表示
![](/icons/58237dou.gif)
以链表形式表示当前盘面
![](/icons/58237de.gif)
情况
![](/icons/58237dou.gif)
目
![](/icons/58237de.gif)
是可以允许用户进行悔棋、回退等操作
CListStepList;
其中Step结构
![](/icons/58237de.gif)
表示为:
structStep
{
![](/icons/58237int.gif)
m;//m,n表示两个坐标值
![](/icons/58237int.gif)
n;
charside;//side表示下子方
};
以
![](/icons/58237shuzu.gif)
形式保存当前盘面
![](/icons/58237de.gif)
情况
目
![](/icons/58237de.gif)
是为了在显示当前盘面情况时使用:
charFiveArea[FIVE_MAX_LINE][FIVE_MAX_LINE];
其中FIVE_MAX_LINE表示盘面最大
![](/icons/58237de.gif)
行数
同时由于需要在递归搜索
![](/icons/58237de.gif)
过程中考虑时间和空间有效性
![](/icons/58237dou.gif)
只找出就当前情况来说相对比较好
![](/icons/58237de.gif)
几个盘面
![](/icons/58237dou.gif)
而不是对所有
![](/icons/58237de.gif)
可下子
![](/icons/58237de.gif)
位置都进行搜索
![](/icons/58237dou.gif)
这里用变量CountList来表示当前搜索中可以选择
![](/icons/58237de.gif)
所有新
![](/icons/58237de.gif)
盘面情况对象
![](/icons/58237de.gif)
集合:
CListCountList;
其中类CBoardSituiton为:
![](/icons/58237class.gif)
CBoardSituation
{
CListStepList;//每
![](/icons/58237yi.gif)
步
![](/icons/58237de.gif)
列表
charFiveArea[FIVE_MAX_LINE][FIVE_MAX_LINE];
structStepmachineStep;//机器所下
![](/icons/58237de.gif)
那
![](/icons/58237yi.gif)
步
doublevalue;//该种盘面状态所得到
![](/icons/58237de.gif)
分数
}
2、评分规则
对于下子
![](/icons/58237de.gif)
重要性评分
![](/icons/58237dou.gif)
需要从 6个位置来考虑当前棋局
![](/icons/58237de.gif)
情况
![](/icons/58237dou.gif)
分别为:-,¦,/,\\,//,\\\\
实际上需要考虑在这 6个位置上某
![](/icons/58237yi.gif)
方所形成
![](/icons/58237de.gif)
子
![](/icons/58237de.gif)
布局
![](/icons/58237de.gif)
情况
![](/icons/58237dou.gif)
对于在还没有子
![](/icons/58237de.gif)
地方落子以后
![](/icons/58237de.gif)
当前局面
![](/icons/58237de.gif)
评分
![](/icons/58237dou.gif)
主要是为了介绍说明在这个地方下子
![](/icons/58237de.gif)
重要性程度
![](/icons/58237dou.gif)
设定了
![](/icons/58237yi.gif)
个简单
![](/icons/58237de.gif)
规则来表示当前棋面对机器方
![](/icons/58237de.gif)
分数
基本
![](/icons/58237de.gif)
规则如下:
判断是否能成5,如果是机器方
![](/icons/58237de.gif)
话给予100000分
![](/icons/58237dou.gif)
如果是人方
![](/icons/58237de.gif)
话给予-100000分;
判断是否能成活4或者是双死4或者是死4活3
![](/icons/58237dou.gif)
如果是机器方
![](/icons/58237de.gif)
话给予10000分
![](/icons/58237dou.gif)
如果是人方
![](/icons/58237de.gif)
话给予-10000分;
判断是否已成双活3
![](/icons/58237dou.gif)
如果是机器方
![](/icons/58237de.gif)
话给予5000分
![](/icons/58237dou.gif)
如果是人方
![](/icons/58237de.gif)
话给予-5000分;
判断是否成死3活3
![](/icons/58237dou.gif)
如果是机器方
![](/icons/58237de.gif)
话给予1000分
![](/icons/58237dou.gif)
如果是人方
![](/icons/58237de.gif)
话给予-1000分;
判断是否能成死4
![](/icons/58237dou.gif)
如果是机器方
![](/icons/58237de.gif)
话给予500分
![](/icons/58237dou.gif)
如果是人方
![](/icons/58237de.gif)
话给予-500分;
判断是否能成单活3
![](/icons/58237dou.gif)
如果是机器方
![](/icons/58237de.gif)
话给予200分
![](/icons/58237dou.gif)
如果是人方
![](/icons/58237de.gif)
话给予-200分;
判断是否已成双活2
![](/icons/58237dou.gif)
如果是机器方
![](/icons/58237de.gif)
话给予100分
![](/icons/58237dou.gif)
如果是人方
![](/icons/58237de.gif)
话给予-100分; [Page]
判断是否能成死3
![](/icons/58237dou.gif)
如果是机器方
![](/icons/58237de.gif)
话给予50分
![](/icons/58237dou.gif)
如果是人方
![](/icons/58237de.gif)
话给予-50分;
判断是否能成双活2
![](/icons/58237dou.gif)
如果是机器方
![](/icons/58237de.gif)
话给予10分
![](/icons/58237dou.gif)
如果是人方
![](/icons/58237de.gif)
话给予-10分;
判断是否能成活2
![](/icons/58237dou.gif)
如果是机器方
![](/icons/58237de.gif)
话给予5分
![](/icons/58237dou.gif)
如果是人方
![](/icons/58237de.gif)
话给予-5分;
判断是否能成死2
![](/icons/58237dou.gif)
如果是机器方
![](/icons/58237de.gif)
话给予3分
![](/icons/58237dou.gif)
如果是人方
![](/icons/58237de.gif)
话给予-3分
实际上对当前
![](/icons/58237de.gif)
局面按照上面
![](/icons/58237de.gif)
规则
![](/icons/58237de.gif)
顺序进行比较
![](/icons/58237dou.gif)
如果满足某
![](/icons/58237yi.gif)
条规则
![](/icons/58237de.gif)
话
![](/icons/58237dou.gif)
就给该局面打分并保存
![](/icons/58237dou.gif)
然后退出规则
![](/icons/58237de.gif)
匹配
![](/icons/58237dou2.gif)
注意这里
![](/icons/58237de.gif)
规则是根据
![](/icons/58237yi.gif)
般
![](/icons/58237de.gif)
下棋规律
![](/icons/58237de.gif)
![](/icons/58237yi.gif)
个整理总结
![](/icons/58237dou.gif)
在实际运行
![](/icons/58237de.gif)
时候
![](/icons/58237dou.gif)
用户可以添加规则和对评分机制加以修正
3、胜负判断
实际上
![](/icons/58237dou.gif)
是根据当前最后
![](/icons/58237yi.gif)
个落子
![](/icons/58237de.gif)
情况来判断胜负
![](/icons/58237de.gif)
![](/icons/58237dou2.gif)
实际上需要从 4个位置判断
![](/icons/58237dou.gif)
以该子为出发点
![](/icons/58237de.gif)
水平
![](/icons/58237dou.gif)
竖直和两条分别为45度角和135度角
![](/icons/58237de.gif)
线
![](/icons/58237dou.gif)
目
![](/icons/58237de.gif)
是看在这 4个方向是否最后落子
![](/icons/58237de.gif)
![](/icons/58237yi.gif)
方构成连续 5个
![](/icons/58237de.gif)
棋子
![](/icons/58237dou.gif)
如果是
![](/icons/58237de.gif)
话
![](/icons/58237dou.gif)
就表示该盘棋局已经分出胜负
![](/icons/58237dou2.gif)
具体见下面
![](/icons/58237de.gif)
图示:
4、搜索算法实现描述
注意下面
![](/icons/58237de.gif)
核心
![](/icons/58237de.gif)
算法中
![](/icons/58237de.gif)
变量currentBoardSituation
![](/icons/58237dou.gif)
表示当前机器最新
![](/icons/58237de.gif)
盘面情况,CountList表示第
![](/icons/58237yi.gif)
层子节点可以选择
![](/icons/58237de.gif)
较好
![](/icons/58237de.gif)
盘面
![](/icons/58237de.gif)
集合
![](/icons/58237dou2.gif)
核心
![](/icons/58237de.gif)
算法如下:
voidMainDealFunction
{
value=-MAXINT;//对
![](/icons/58237chushi.gif)
根节点
![](/icons/58237de.gif)
value赋值
CalSeveralGoodPlace(currentBoardSituation,CountList);
//该
![](/icons/58237hanshu.gif)
是根据当前
![](/icons/58237de.gif)
盘面情况来比较得到比较好
![](/icons/58237de.gif)
可以考虑
![](/icons/58237de.gif)
几个盘面
![](/icons/58237de.gif)
情况
![](/icons/58237dou.gif)
可以根据实际
![](/icons/58237de.gif)
得分情况选取分数比较高
![](/icons/58237de.gif)
几个盘面
![](/icons/58237dou.gif)
也就是说在第
![](/icons/58237yi.gif)
层节点选择
![](/icons/58237de.gif)
时候采用贪婪算法
![](/icons/58237dou.gif)
直接找出相对分数比较高
![](/icons/58237de.gif)
几个形成第
![](/icons/58237yi.gif)
层节点
![](/icons/58237dou.gif)
目
![](/icons/58237de.gif)
是为了提高搜索速度和防止堆栈溢出
pos=CountList.GetHeadPosition
![](/icons/58237kh.gif)
;
CBoardSituation*pBoard;
for(i=0;ivalue=Search(pBoard,min,value,0);
Value=Select(value,pBoard->value,max);
//取value和pBoard->value中大
![](/icons/58237de.gif)
赋给根节点
}
for(i=0;ivalue)
//找出那
![](/icons/58237yi.gif)
个得到最高分
![](/icons/58237de.gif)
盘面
{
currentBoardSituation=pBoard;
PlayerMode=min;//当前下子方改为人
Break;
}
}
其中对于Search
![](/icons/58237hanshu.gif)
![](/icons/58237de.gif)
表示如下:实际上核心
![](/icons/58237de.gif)
算法是
![](/icons/58237yi.gif)
个剪枝过程
![](/icons/58237dou.gif)
其中在这个搜索过程中相关
![](/icons/58237de.gif)
4个参数为:(1)当前棋局情况;(2)当前
![](/icons/58237de.gif)
下子方
![](/icons/58237dou.gif)
可以是机器(max)或者是人(min);(3)父节点
![](/icons/58237de.gif)
值oldValue;(4)当前
![](/icons/58237de.gif)
搜索深度depth
doubleSearch(CBoardSituation&
board,
![](/icons/58237int.gif)
mode,doubleoldvalue,
![](/icons/58237int.gif)
depth)
{
CListm_DeepList;
![](/icons/58237if.gif)
(deptholdvalue))
![](/icons/58237dd.gif)
TRUE) [Page]
{
![](/icons/58237if.gif)
(mode
![](/icons/58237dd.gif)
max)
value=select(value,search(successor
Board,min,value,depth+1),max);
value=select(value,search(successor
Board,max,value,depth+1),min);
}
![](/icons/58237return.gif)
value;
}
{
![](/icons/58237if.gif)
(goal(board)<>0)
//这里goal(board)<>0表示已经可以分出胜负
![](/icons/58237return.gif)
goal(board);
![](/icons/58237return.gif)
evlation(board);
}
}
注意这里
![](/icons/58237de.gif)
goal(board)
![](/icons/58237hanshu.gif)
是用来判断当前盘面是否可以分出胜负
![](/icons/58237dou.gif)
而evlation(board)是对当前
![](/icons/58237de.gif)
盘面从机器
![](/icons/58237de.gif)
角度进行打分
下面是Select
![](/icons/58237hanshu.gif)
![](/icons/58237de.gif)
介绍
![](/icons/58237dou.gif)
这个
![](/icons/58237hanshu.gif)
![](/icons/58237de.gif)
主要目
![](/icons/58237de.gif)
是根据PlayerMode情况
![](/icons/58237dou.gif)
即是机器还是用户来返回节点
![](/icons/58237de.gif)
应有
![](/icons/58237de.gif)
值
doubleSelect(doublea,doubleb,
![](/icons/58237int.gif)
mode)
{
![](/icons/58237if.gif)
(a>b&&mode
![](/icons/58237dd.gif)
max)¦¦(a<b&&mode
![](/icons/58237dd.gif)
min)
![](/icons/58237return.gif)
a;
![](/icons/58237return.gif)
b;
}
5、小结
和国内许多只是采用规则或者只是采用简单递归而没有剪枝
![](/icons/58237de.gif)
那些
![](/icons/58237chengxu.gif)
相比
![](/icons/58237dou.gif)
在智力上和时间有效性上都要好于这些
![](/icons/58237chengxu.gif)
![](/icons/58237dou2.gif)
同时所讨论
![](/icons/58237de.gif)
思路方法和设计过程为用户设计其他
![](/icons/58237de.gif)
游戏(如象棋和围棋等)提供了
![](/icons/58237yi.gif)
个参考
Tags:
延伸阅读
最新评论