5子棋算法详细介绍

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

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

structStep
{
m;//m,n表示两个坐标值
n;
charside;//side表示下子方
};
以形式保存当前盘面情况
目是为了在显示当前盘面情况时使用:
charFiveArea[FIVE_MAX_LINE][FIVE_MAX_LINE];

其中FIVE_MAX_LINE表示盘面最大行数

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

CListCountList;
其中类CBoardSituiton为:
CBoardSituation
{
CListStepList;//每步列表
charFiveArea[FIVE_MAX_LINE][FIVE_MAX_LINE];
structStepmachineStep;//机器所下那步
doublevalue;//该种盘面状态所得到分数
}

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


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

基本规则如下:

判断是否能成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分； [Page]
判断是否能成死3如果是机器方话给予50分如果是人方话给予－50分；
判断是否能成双活2如果是机器方话给予10分如果是人方话给予－10分；
判断是否能成活2如果是机器方话给予5分如果是人方话给予－5分；
判断是否能成死2如果是机器方话给予3分如果是人方话给予－3分

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

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


4、搜索算法实现描述
注意下面核心算法中变量currentBoardSituation表示当前机器最新盘面情况,CountList表示第层子节点可以选择较好盘面集合核心算法如下:
voidMainDealFunction
{
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表示如下:实际上核心算法是个剪枝过程其中在这个搜索过程中相关 4个参数为:(1)当前棋局情况；(2)当前下子方可以是机器(max)或者是人(min)；(3)父节点值oldValue；(4)当前搜索深度depth

doubleSearch(CBoardSituation＆
board,mode,doubleoldvalue,depth)
{
CListm_DeepList;
(deptholdvalue))TRUE) [Page]
{
(modemax)
value=select(value,search(successor
Board,min,value,depth＋1),max);

value=select(value,search(successor
Board,max,value,depth＋1),min);
}
value;
}

{
(goal(board)<>0)
//这里goal(board)<>0表示已经可以分出胜负
goal(board);

evlation(board);
}
}

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

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

doubleSelect(doublea,doubleb,mode)
{
(a>b＆＆modemax)&brvbar;&brvbar;(a<b＆＆modemin)
a;

b;
}

5、小结
和国内许多只是采用规则或者只是采用简单递归而没有剪枝那些相比在智力上和时间有效性上都要好于这些同时所讨论思路方法和设计过程为用户设计其他游戏(如象棋和围棋等)提供了个参考

延伸阅读