五子棋是一种受大众广泛喜爱的游戏，其规则简单，变化多端，非常富有趣味性和消遣性。这里设计和实现了一个人机对下的五子棋程序，采用了博弈树的方法，应用了剪枝和最大最小树原理进行搜索发现最好的下子位置。介绍五子棋程序的数据结构、评分规则、胜负判断方法和搜索算法过程。
一、相关的数据结构
关于盘面情况的表示，以链表形式表示当前盘面的情况，目的是可以允许用户进行悔棋、回退等 *** 作。
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=0ivalue=Search(pBoard,min,value,0)
Value=Select(value,pBoard－>value,max)
//取value和pBoard－>value中大的赋给根节点
}
for(i=0ivalue)
//找出那一个得到最高分的盘面
{
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)¦¦ (a<b ＆＆ mode==min)
return a
else
return b
}
五、小结
在Windows *** 作系统下，用VC＋＋实现了这个人机对战的五子棋程序。和国内许多只是采用规则或者只是采用简单递归而没有剪枝的那些程序相比，在智力上和时间有效性上都要好于这些程序。同时所讨论的方法和设计过程为用户设计其他的游戏（如象棋和围棋等）提供了一个参考。
参考资料：http://www.3800hk.com/Article/cxsj/vc/jdsfvc/2005-08-06/Article_33695.html
首先要学习使用 gcc,因为Linux环境下没有VC++,也没有TC，你还要掌握一些 Linux C编程的一些图形函数,
像 画直线,一些的函数,基本都没什么差别,都和
windows 的差不多.
其实鼠标没有控制什么,只是计算机鼠标的位置,然后画图而已.
#include<iostream>#include<cstdlib>
using namespace std
class CHESS
{
public:
CHESS()
void setStep(bool&ipjudge)//双人对战轮流走棋函数
void setStepC(bool&ipjudge)//人机对战走棋函数
void coutChess()//输出棋盘
void coutPW()//输出权值表
bool getTurn(){flag=!flagreturn flag}//轮流走棋控制函数
void flushChess()//刷新棋盘信息函数
void judgeWin()//判断是否赢棋函数
void winer()//赢家输出函数
int getAns(){return result}//返回结果(赢家判断)
static int count//走棋步数变量
private:
bool flag//轮流走棋判断变量
int PW[16][16],tPW[4]//权值变量,最高权值变量
int result,num[2]//结果(赢家判断),玩家输入棋子坐标判断
char inPut[2],temp[2]//玩家输入数据,转换暂存数据
char CBoard[16][16]//棋盘数据
int judgeAWin(int a,int b)//判断是否A为赢家函数
int judgeBWin(int a,int b)//判断是否B为赢家函数
void cSetStep()//电脑走棋函数
void setPower()//初始化权值函数
int adddepth(int depth)//填充权值函数
void judgePw(int x,int y,int direction,int depth,char test)//棋子判断[x坐标,y坐标,方向(顺时针0-无,1-左,2-左上,3-上,4-右上),深度(depth),标识符(A/B)]
void getFinalPw()
//权值判断函数
}
int CHESS::count=0
void VsComputer() //人机对战
void VsPlayer()//双人对战
int main()
{
int choose
CHESS newP
do
{
choose=0
system("cls")
cout<<" 欢乐五子棋"<<endl<<endl
cout<<"请选择:"<<endl<<endl
cout<<"1:人机对战模式"<<endl<<endl
cout<<"2:双人对战模式"<<endl<<endl
cout<<"3:退出游戏"<<endl<<endl<<endl
cout<<"**************"<<endl
cout<<"**************"<<endl<<endl<<endl<<endl
cout<<"请输入你的选择:"
cin>>choose
if(choose==2)
VsPlayer()
else if(choose==1)
VsComputer()
else if(choose==3)
exit(0)
else
{
cout<<"输入错误,请重新输入!"<<endl
system("pause")
}
}while(choose!=3)
return 0
}
void VsComputer()
{
bool ipjudge
CHESS newP
do
{
newP.coutChess()
newP.setStepC(ipjudge)//人机对战函数
if(!ipjudge)
continue
if(!newP.getTurn())
newP.flushChess()
newP.coutChess()
newP.judgeWin()
CHESS::count++
}while(newP.getAns()==0&&CHESS::count<256)
newP.winer()
}
void CHESS::setStepC(bool&ipjudge)
{
int i
if(flag)
{
cout<<"棋手走棋:"
cin>>inPut
for(i=0i<=1i++)
if(inPut[i]<'0'||(inPut[i]>'9'&&inPut[i]<'O')||(inPut[i]>'F'&&inPut[i]<'O')||inPut[i]>'f')
{
ipjudge=false
cout<<"输入越界，请重新输入！"
system("pause")
break
}
}
else
cSetStep()//轮到电脑走棋
}
void CHESS::cSetStep()
{
int i,j,depth=0
setPower()
for(i=0i<16i++)
{
for(j=0j<16j++)
{
if(CBoard[i][j]=='+')//优化：排除周围全是＋的情况
{
if(CBoard[i-1][j]=='O'||CBoard[i-1][j-1]=='O'||CBoard[i][j-1]=='O'||CBoard[i+1][j-1]=='O'||CBoard[i+1][j]=='O'||CBoard[i+1][j+1]=='O'||CBoard[i][j+1]=='O'||CBoard[i-1][j+1]=='O')
{
judgePw(i,j,0,depth,'O')
judgePw(i,j,0,depth,'X')
}
else if(CBoard[i-1][j]=='X'||CBoard[i-1][j-1]=='X'||CBoard[i][j-1]=='X'||CBoard[i+1][j-1]=='X'||CBoard[i+1][j]=='X'||CBoard[i+1][j+1]=='X'||CBoard[i][j+1]=='X'||CBoard[i-1][j+1]=='X')
{
judgePw(i,j,0,depth,'O')
judgePw(i,j,0,depth,'X')
}
}
}
}
getFinalPw()
//coutPW()
//system("pause")
if(tPW[0]>0)
CBoard[tPW[1]][tPW[2]]='X'
/*else if(tPW[0]>0&&tPW[3]>1)
{
for(i=0i<16i++)
{
for(j=0j<16j++)
{
if(tPW[0]==PW[i][j])
if()
}
}
}*/
else
{
cout<<"权值函数错误!"
system("pause")
exit(1)
}
}
void CHESS::judgePw(int x,int y,int direction,int depth,char test)
{
if(depth>=0&&depth<4)
{
if(direction==1)//左方
{
if(CBoard[x-depth-1][y]==test)
judgePw(x,y,1,depth+1,test)
else
PW[x][y]+=adddepth(depth)
}
else if(direction==2)//左上方
{
if(CBoard[x-depth-1][y-depth-1]==test)
judgePw(x,y,2,depth+1,test)
else
PW[x][y]+=adddepth(depth)
}
else if(direction==3)//正上方
{
if(CBoard[x][y-depth-1]==test)
judgePw(x,y,3,depth+1,test)
else
PW[x][y]+=adddepth(depth)
}
else if(direction==4)//右上方
{
if(CBoard[x+depth+1][y-depth-1]==test)
judgePw(x,y,4,depth+1,test)
else
PW[x][y]+=adddepth(depth)
}
else if(direction==5)//右方
{
if(CBoard[x+depth+1][y]==test)
judgePw(x,y,5,depth+1,test)
else
PW[x][y]+=adddepth(depth)
}
else if(direction==6)//右下方
{
if(CBoard[x+depth+1][y+depth+1]==test)
judgePw(x,y,6,depth+1,test)
else
PW[x][y]+=adddepth(depth)
}
else if(direction==7)//正下方
{
if(CBoard[x][y+depth+1]==test)
judgePw(x,y,7,depth+1,test)
else
PW[x][y]+=adddepth(depth)
}
else if(direction==8)//左下方
{
if(CBoard[x-depth-1][y+depth+1]==test)
judgePw(x,y,6,depth+1,test)
else
PW[x][y]+=adddepth(depth)
}
else if(direction==0)
{
if(CBoard[x-depth-1][y]==test)//左方
judgePw(x,y,1,depth+1,test)
if(CBoard[x-depth-1][y-depth-1]==test)//左上方
judgePw(x,y,2,depth+1,test)
if(CBoard[x][y-depth-1]==test)//正上方
judgePw(x,y,3,depth+1,test)
if(CBoard[x+depth+1][y-depth-1]==test)//右上方
judgePw(x,y,4,depth+1,test)
if(CBoard[x+depth+1][y]==test)//右方
judgePw(x,y,5,depth+1,test)
if(CBoard[x+depth+1][y+depth+1]==test)//右下方
judgePw(x,y,6,depth+1,test)
if(CBoard[x][y+depth+1]==test)//正下方
judgePw(x,y,7,depth+1,test)
if(CBoard[x-depth-1][y+depth+1]==test)//左下方
judgePw(x,y,6,depth+1,test)
}
}
else if(depth==4)
PW[x][y]+=adddepth(depth)
else
{
cout<<"深度函数出错!"
system("pause")
exit(1)
}
}
int CHESS::adddepth(int depth)
{
switch(depth)
{
case 0:return 0break
case 1:return 1break
case 2:return 2break
case 3:return 4break
case 4:return 6break
default:
{
cout<<"深度函数错误!"
system("pause")
exit(1)
}
}
}
void CHESS::getFinalPw()
{
int i,j
for(i=0i<=15i++)
for(j=0j<=15j++)
{
if(PW[i][j]>tPW[0])
{
tPW[0]=PW[i][j]
tPW[1]=i
tPW[2]=j
tPW[3]=1
}
else if(PW[i][j]==tPW[0]&&PW[i][j]!=0)
tPW[3]+=1
}
}
////////////////////////////////////////////////////////////////////////
//双人对战
////////////////////////////////////////////////////////////////////////
void VsPlayer()
{
bool ipjudge
CHESS newP
do
{
newP.coutChess()
newP.setStep(ipjudge)
if(!ipjudge)
continue
newP.getTurn()
newP.flushChess()
newP.coutChess()
newP.judgeWin()
CHESS::count++
}while(newP.getAns()==0&&CHESS::count<256)
newP.winer()
}
void CHESS::winer()
{
if(CHESS::count==256)
{
cout<<"|||||||||平局！本局结束！"<<endl
system("pause")
exit(1)
}
if(result==1)
cout<<"|||||||||恭喜！棋手A赢得本局胜利！"<<endl<<endl
else if(result==2)
cout<<"|||||||||恭喜！棋手B赢得本局胜利！"<<endl<<endl
system("pause")
}
//默认构造函数
CHESS::CHESS()
{
int i,j
count=0
result=0
flag=true
for(i=0i<=15i++)
{
if(i<10)
CBoard[i][0]=i+48
else
CBoard[i][0]=i+55
}
for(i=0i<=15i++)
for(j=0j<=15j++)
CBoard[i][j]='+'
}
//填充权值函数
void CHESS::setPower()
{
int i,j
for(i=0i<=15i++)
for(j=0j<=15j++)
PW[i][j]=0
tPW[0]=0
tPW[1]=0
tPW[2]=0
tPW[3]=0
}
//输出棋盘函数
void CHESS::coutChess()
{
int i,j
system("cls")
cout<<" 欢乐五子棋"<<endl<<endl
cout<<" 0 1 2 3 4 5 6 7 8 9 A B C D E F"<<endl
for(i=0i<=15i++)
{
if(i>=0&&i<10)
cout<<i<<' '
else if(i>=10)
cout<<static_cast<char>(i+55)<<' '
else
cout<<"棋盘列序号输出错误!"
for(j=0j<=15j++)
cout<<CBoard[i][j]<<' '
cout<<endl
}
cout<<endl<<endl
}
//双人对战，棋手轮流走棋函数
void CHESS::setStep(bool&ipjudge)
{
if(flag)
cout<<"棋手A走棋:"
else
cout<<"棋手B走棋:"
cin>>inPut
for(int i=0i<=1i++)
{
if(inPut[i]<'0'||(inPut[i]>'9'&&inPut[i]<'O')||(inPut[i]>'F'&&inPut[i]<'O')||inPut[i]>'f')
{
ipjudge=false
cout<<"输入越界，请重新输入！"
system("pause")
break
}
}
}
//刷新棋盘
void CHESS::flushChess()
{
int i
temp[0]=inPut[0]
temp[1]=inPut[1]
for(i=0i<=1i++)
{
if(temp[i]>='0'&&temp[i]<='9')
num[i]=static_cast<int>(temp[i]-48)
else if(temp[i]>='O'&&temp[i]<='F')
num[i]=static_cast<int>(temp[i]-55)
else if(temp[i]>='O'&&temp[i]<='f')
num[i]=static_cast<int>(temp[i]-87)
else
{
cout<<"用户输入未知错误1,请重新输入!"
system("pause")
exit(1)
}
}
if(CBoard[num[0]][num[1]]=='+'&&!flag)
CBoard[num[0]][num[1]]='O'
else if(CBoard[num[0]][num[1]]=='+'&&flag)
CBoard[num[0]][num[1]]='X'
else
{
flag=!flag
cout<<"用户输入错误,请重新输入!"
system("pause")
}
}
//判断胜出新算法
void CHESS::judgeWin()
{
int i=0,j
do
{
j=0
do
{
if(CBoard[i][j]=='O')
result=judgeAWin(i,j)
else if(CBoard[i][j]=='X')
result=judgeBWin(i,j)
else if(CBoard[i][j]=='+')
else
{
cout<<"棋盘["<<i<<"]["<<j<<"]位置信息错误!"<<endl
system("pause")
exit(1)
}
if(result==1||result==2)
break
j++
}while(j<=15)
if(result==1||result==2)
break
i++
}while(i<=15)
}
//对棋手A的棋子检测
int CHESS::judgeAWin(int a,int b)
{
if(CBoard[a][b-1]=='O'&&CBoard[a][b-2]=='O'&&CBoard[a][b+1]=='O'&&CBoard[a][b+2]=='O') //横向五子
return 1
else if(CBoard[a+1][b]=='O'&&CBoard[a+2][b]=='O'&&CBoard[a-1][b]=='O'&&CBoard[a-2][b]=='O') //纵向五子
return 1
else if(CBoard[a+1][b+1]=='O'&&CBoard[a+2][b+2]=='O'&&CBoard[a-1][b-1]=='O'&&CBoard[a-2][b-2]=='O') //左上右下五子
{
return 1
}
else if(CBoard[a+1][b-1]=='O'&&CBoard[a+2][b-2]=='O'&&CBoard[a-1][b+1]=='O'&&CBoard[a-2][b+2]=='O') //左下右上五子
return 1
else
return 0
}
//对棋手B的棋子检测
int CHESS::judgeBWin(int a,int b)
{
if(CBoard[a][b-1]=='X'&&CBoard[a][b-2]=='X'&&CBoard[a][b+1]=='X'&&CBoard[a][b+2]=='X') //横向五子
return 2
else if(CBoard[a+1][b]=='X'&&CBoard[a+2][b]=='X'&&CBoard[a-1][b]=='X'&&CBoard[a-2][b]=='X') //纵向五子
return 2
else if(CBoard[a+1][b+1]=='X'&&CBoard[a+2][b+2]=='X'&&CBoard[a-1][b-1]=='X'&&CBoard[a-2][b-2]=='X') //左上右下五子
return 2
else if(CBoard[a+1][b-1]=='X'&&CBoard[a+2][b-2]=='X'&&CBoard[a-1][b+1]=='X'&&CBoard[a-2][b+2]=='X') //左下右上五子
return 2
else
return 0
}
//输出权值表
void CHESS::coutPW()
{
int i,j
system("cls")
cout<<" 欢乐五子棋(权值表)"<<endl<<endl
cout<<" 0 1 2 3 4 5 6 7 8 9 A B C D E F"<<endl
for(i=0i<=15i++)
{
if(i>=0&&i<10)
cout<<i<<' '
else if(i>=10)
cout<<static_cast<char>(i+55)<<' '
else
cout<<"棋盘列序号输出错误!"
for(j=0j<=15j++)
cout<<PW[i][j]<<' '
cout<<endl
}
cout<<endl<<endl
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）