minimax.cpp

运用人工智能的极小极大博弈算法解决一字棋

#include<iostream>
using namespace std;
const int max=1000;//扩展生成状态节点的最大数目
const int min=-1000;
const int NO_BLANK=-1001;//表示没有空格
const int TREE_DEPTH=3;//深度
const int null=1001;//表示空
static int index;//当前节点的下标
struct State{
	int qipan[3][3];//棋盘格局
    int evaluate;//当前状态的评估函数值
    int child[9];//子节点的下标
    int parent;//双亲节点的下标
    int bestChild;//最优节点（评估函数值最大）的儿女节点下标
}States[20000];
int temp[3][3];
void input(){
	int x,y;
	while(1){
		cout<<"Please Input The Position of the chess(x,y):";
		cin>>x>>y;
		if(x>=0&&x<3&&y>=0&&y<3&&States[0].qipan[x][y]==0){
			States[0].qipan[x][y]=-1;break;
		}else cout<<"Input Error!";
	}
}
void print(){
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++)
			cout<<States[0].qipan[i][j]<<"   ";
		cout<<endl;
	}
}
int win(State s){
	for(int i=0;i<3;i++){
		if(s.qipan[i][0]==1&&s.qipan[i][1]==1&&s.qipan[i][2]==1)return 1;
		if(s.qipan[i][0]==-1&&s.qipan[i][1]==-1&&s.qipan[i][2]==-1)return -1;
	}
	for(i=0;i<3;i++){
		if(s.qipan[0][i]==1&&s.qipan[1][i]==1&&s.qipan[2][i]==1)return 1;
        if(s.qipan[0][i]==-1&&s.qipan[1][i]==-1&&s.qipan[2][i]==-1)return -1;
	}
	if((s.qipan[0][0]==1&&s.qipan[1][1]==1&&s.qipan[2][2]==1)||(s.qipan[2][0]==1&&s.qipan[1][1]==1&&s.qipan[0][2]==1))return 1;
    if((s.qipan[0][0]==-1&&s.qipan[1][1]==-1&&s.qipan[2][2]==-1)||(s.qipan[2][0]==-1&&s.qipan[1][1]==-1&&s.qipan[0][2]==-1))return -1;
	return 0;
}
int evaluate(State s){//f(p)=max-min
	bool flag=true;
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			if(s.qipan[i][j]==0)flag=false;
			if(flag)return NO_BLANK;
			if(win(s)==-1)return min;//如果计算机输了，返回最小值
            if(win(s)==1)return max;//如果计算机赢了，返回最大值
            int count=0;//该变量用来表示评估函数的值
			for(i=0;i<3;i++)
				for(int j=0;j<3;j++)
					if(s.qipan[i][j]==0)temp[i][j]=1;
					else temp[i][j]=s.qipan[i][j];
					for(i=0;i<3;i++)
						if(temp[i][0]==1&&temp[i][1]==1&&temp[i][2]==1)count++;//行
						for(i=0;i<3;i++)
							if(temp[0][i]==1&&temp[1][i]==1&&temp[2][i]==1)count++;//列
							if(temp[0][0]==1&&temp[1][1]==1&&temp[2][2]==1)count++;//斜行
                            if(temp[2][0]==1&&temp[1][1]==1&&temp[0][2]==1)count++;
							for(i=0;i<3;i++)
								for(int j=0;j<3;j++)
									if(s.qipan[i][j]==0)temp[i][j]=-1;
									else temp[i][j]=s.qipan[i][j];
									for(i=0;i<3;i++)
										if(temp[i][0]==-1&&temp[i][1]==-1&&temp[i][2]==-1) count++;//行
										for(i=0;i<3;i++)
											if(temp[0][i]==-1&&temp[1][i]==-1&&temp[2][i]==-1) count++;//列
											if(temp[0][0]==-1&&temp[1][1]==-1&&temp[2][2]==-1) count++;//斜行
                                            if(temp[2][0]==-1&&temp[1][1]==-1&&temp[0][2]==-1) count++;
											return count;
}//计算机通过该函数决定走哪一步，并对当前的棋局做出判断。
bool L2(){
 //取落子的位置，将x,y坐标保存在变量pos_x和pos_y中，并将根（当前）节点中的棋局设为最佳儿子节点的棋局
	
	int pos_x,pos_y;//保存计算机落子的位置 
	
	for(int x=0;x<3;x++){
  for(int y=0;y<3;y++){
   if(States[States[0].bestChild].qipan[x][y]!=States[0].qipan[x][y]){
    pos_x=x;
    pos_y=y;    
   }
   States[0].qipan[x][y]=States[States[0].bestChild].qipan[x][y]; 
  }
 }int MAX_F=States[0].evaluate;
 cout<<"The computer put a qizi at: "<<pos_x+1<<','<<pos_y+1<<'\n'<<"The QP now is:"<<endl;
 print();
 if(MAX_F==max){  //如果当前节点的评估函数为最大值，则计算机赢了
 cout<<"The computer WIN! You LOSE! GAME OVER."<<endl;
  return true;
 }
 if(MAX_F==NO_BLANK){  //否则，如果棋盘时候没空可放了，则平局。
  cout<<"DRAW GAME!"<<endl;
  return true;
 }
 return false;
}
bool move(){
	cout<<"begin:"<<endl;
	print();
 int 
  MAX_F=NO_BLANK, //保存对自己最有利的棋局（最大）的评估函数值
  parent=-1,  //以当前棋局为根生成搜索树，所以当前棋局节点无双亲节点
  count,   //用来计算当前生成的最后一个扩展节点的下标
  i,    //备用
  tag;   //标示每一层搜索树中最后一个节点的下标
 bool 
  max_min=TREE_DEPTH%2, //标识取下一层评估函数的最大值还是最小值？
        //max_min=1取下一层中的最大值，max_min=0取最小值
  IsOK=false;    //有没有找到下一步落子的位置？
 index=0;   //扩展生成的节点数初始值为0 
if(win(States[0])==-1){//如果人赢了
 cout<<"Conguatulations! You Win! GAME OVER."<<endl;
  return true;
 }
for(int t=0;t<TREE_DEPTH;t++){//依次生成各层节点
  count=index;//保存上一层节点生成的最大下标
  for(int k=parent+1;k<=count;k++){//生成一层节点
   int n_child=0;//该层节点的孩子节点数初始化为0
   for(int i=0;i<3;i++)
   for(int j=0;j<3;j++)
	   if(States[k].qipan[i][j]==0){//如果在位置(i,j)可以放置一个棋子
     index++;    //生成一个节点，节点数（最大下标）数加1
     for(int i1=0;i1<3;i1++) //该3×3循环将当前棋局复制到新节点对应的棋局结构中
      for(int j1=0;j1<3;j1++)
       States[index].qipan[i1][j1]=States[k].qipan[i1][j1];
     States[index].qipan[i][j]=t%2==0?1:-1;//根据是人下还是计算机下，在空位上落子
     States[index].parent=k;   //将父母节点的下标k赋给新生成的节点
     States[k].child[n_child++]=index; //下标为k的父母节点有多了个子女
     //如果下一步有一步期能让电脑赢，则停止扩展节点，转向结局打印语句
     if(t==0&&evaluate(States[index])==max){
      States[k].evaluate=max;
      States[k].bestChild=index;//最好的下一步棋所在的节点的下标为s_count
      return L2();
     }
    }
  }
  parent=count;   //将双亲节点设置为当前双亲节点的下一层节点
  cout<<index<<endl; //打印生成节点的最大下标
 }
 tag=States[index].parent;//设置最底层标志，以便从下到上计算最大最小值以寻找最佳解路径。
 for(i=0;i<=index;i++){
	 if(i>tag){ //保留叶节点的评估函数值
   States[i].evaluate=evaluate(States[i]);
  }
  else  //抹去非叶节点的评估函数值
   States[i].evaluate=null;
 }
 while(!IsOK){//寻找最佳落子的循环
   for(int i=index;i>tag;i--){
	   if(max_min){//取子女节点的最大值
    if(States[States[i].parent].evaluate<States[i].evaluate||States[States[i].parent].evaluate==null){
     States[States[i].parent].evaluate=States[i].evaluate; //设置父母节点的最大最小值
     States[States[i].parent].bestChild=i;   //设置父母节点的最佳子女的下标
    }
   }
	   else{//取子女节点的最小值
   if(States[States[i].parent].evaluate>States[i].evaluate||States[States[i].parent].evaluate==null){
     States[States[i].parent].evaluate=States[i].evaluate; //设置父母节点的最大最小值
     States[States[i].parent].bestChild=i;   //设置父母节点的最佳子女的下标
    }
   }
  }
  index=tag;  //将遍历的节点上移一层
  max_min=!max_min; //如果该层都是MAX节点，则它的上一层都是MIN节点，反之亦然。
  if(States[index].parent!=null)//如果当前遍历的层中不包含根节点，则tag标志设为上一层的最后一个节点的下标
   tag=States[index].parent;
  else
   IsOK=true;  //否则结束搜索
 }
	return L2();
} 
//主程序
int main(){
	int index=0;
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			States[0].qipan[i][j]=0; //将棋盘清空
		States[0].parent=null ;   //初始节点没有双亲节点
		cout<<"The QiPan is: "<<endl;
		print();
		char First;
		bool Finish;
		cout<<"welcome to the game,Do you want do first?(y/n)";
		cin>>First;
		do{
			if(First=='y'){
				input();
				Finish=move();
			}else{
				Finish=move();
				if(!Finish) input();
			}
		}while(!Finish);
		return 0;
}