alpha-beta算法 一字棋

#include<iostream> #include<stack> using namespace std; const int infinity=100; const int minfinity=-100; const int maxdepth=7; int r,c; int board[3][3]; int judge(){ int i,j; for(i=0;i<3;i++){ if(board[0][i]==1 &&board[1][i]==1&&board[2][i]==1) return 1; else if(board[0][i]==-1 &&board[1][i]==-1&&board[2][i]==-1) return -1; } for(i=0;i<3;i++){ if(board[i][0]==1 &&board[i][1]==1&&board[i][2]==1) return 1; else if(board[i][0]==-1 &&board[i][1]==-1&&board[i][2]==-1) return -1; } if(board[0][0]==1 &&board[1][1]==1&&board[2][2]==1) return 1; else if(board[0][0]==-1 &&board[1][1]==-1&&board[2][2]==-1) return -1; if(board[2][0]==1 &&board[1][1]==1&&board[0][2]==1) return 1; else if(board[2][0]==-1 &&board[1][1]==-1&&board[0][2]==-1) return -1; for(i=0;i<3;i++) for(j=0;j<3;j++) if(board[i][j]==0) return 0; return 2; } int hfunction(){ int e; e=judge(); if(e==1) return minfinity; else if(e==-1) return infinity; int tempmax[3][3]; int tempmin[3][3]; int max=0; int min=0; int i,j; for(i=0;i<3;i++) for(j=0;j<3;j++){ if(board[i][j]==0){ tempmax[i][j]=-1; tempmin[i][j]=1; } else{ tempmax[i][j]=board[i][j]; tempmin[i][j]=board[i][j]; } } for(i=0;i<3;i++){ if(tempmin[i][0]==1&&tempmin[i][1]==1&&tempmin[i][2]==1) min++; if(tempmax[i][0]==-1&&tempmax[i][1]==-1&&tempmax[i][2]==-1) max++; } for(j=0;j<3;j++){ if(tempmin[0][j]==1&&tempmin[1][j]==1&&tempmin[2][j]==1) min++; if(tempmax[0][j]==-1&&tempmax[1][j]==-1&&tempmax[2][j]==-1) max++; } if(tempmin[0][0]==1&&tempmin[1][1]==1&&tempmin[2][2]==1) min++; if(tempmax[0][0]==-1&&tempmax[1][1]==-1&&tempmax[2][2]==-1) max++; if(tempmin[0][2]==1&&tempmin[1][1]==1&&tempmin[2][0]==1) min++; if(tempmax[0][2]==-1&&tempmax[1][1]==-1&&tempmax[2][0]==-1) max++; return max-min; } int ab(int depth,int turn,int a,int b){ int result,i,j; if(depth==0) return hfunction(); if(judge()!=0) return hfunction(); if(turn==1){ for(i=0;i<3;i++) for(j=0;j<3;j++) if(board[i][j]==0){ board[i][j]=turn; result=ab(depth-1,-1,a,b); board[i][j]=0; if(result<b){ b=result; if(a>=b) return a; } } return b; } else { for(i=0;i<3;i++) for(j=0;j<3;j++){ if(board[i][j]==0){ board[i][j]=turn; result=ab(depth-1,1,a,b); board[i][j]=0; if(result>a){ if(depth==maxdepth){ r=i; c=j; } a=result; if(a>=b) return b; } } } return a; } } void printb(){ for(int i=0;i<3;i++){ for(int j=0;j<3;j++) cout<<board[i][j]<<"\t"; cout<<endl; } } void main(){ int i,j,result; for(i=0;i<3;i++) for(j=0;j<3;j++) board[i][j]=0; int op; do{ cin>>op; r=op/10-1; c=op%10-1; board[r][c]=1;//cout<<"computer1:\n"; printb(); result=judge(); if(result!=0)break; ab(maxdepth,-1,-100,100); board[r][c]=-1; cout<<"Computer2:\n"; printb(); result=judge(); if(result!=0)break; }while(1); if(result==1)cout<<"You win!\n"; else if(result==-1) cout<<"You lost!\n"; else cout<<"和局\n"; cin>>op; return; }