如何使用Alpha Beta修剪来纠正这个井字游戏程序 [英] How Can I Correct This Tic-Tac-Toe Program Using Alpha Beta Pruning
本文介绍了如何使用Alpha Beta修剪来纠正这个井字游戏程序的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
#include<iostream>
using namespace std;
enum player{
comp,user
};
void print();
char grid[3][3]={{' ',' ',' '},{' ',' ',' '},{' ',' ',' '}};
int evaluateLine(int,int,int,int,int,int,int);
int evaluate(int);
void move(int*);
void minimax(int,int,int,int,int*);
bool has_won();
void play(int);
bool IsFull(){//tests if there is no empty cell in the grid
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
if(grid[i][j]==' ')
return false;
}
}
return true;
}
int main(){
play(user);
}
void print(){//prints the current state of the grid on console
for(int i=0;i<3;i++){
for(int j=0;j<3;j++)
cout<<grid[i][j]<< " | ";
cout<<"\n -- -- -- \n";
}
}
void play(int player)
{
int x,y;
if(player==user){
cout<<"Enter your move\n";
cin>>x>>y;
if(grid[x-1][y-1]!=' '){
cout<<"enter a valid move\n";
play(player);
}
grid[x-1][y-1]='X';
print();
if(has_won())
exit(0);
else
play(comp);
}
else{//comp uses move method to determine next best move
int* x=new int[2];
x[0]=0;
x[1]=0;
move(x);
cout<<x[0]<<x[1]<<endl;
grid[x[0]][x[1]]='0';
print();
if(has_won())
exit(0);
else
play(user);
}
}
bool has_won()//checks if any one of the players-comp,user has won
{
char win=' ';
for (int i = 0; i <3; i++) {
if(grid[i][0]==grid[i][1] && grid[i][1]==grid[i][2])
{
win=grid[i][1];
break;
}
else if(grid[0][i]==grid[1][i] && grid[1][i]==grid[2][i]){
win=grid[0][i];
break;
}
}
if(grid[1][1]==grid[0][0] && grid[1][1]==grid[2][2])
win=grid[0][0];
else if(grid[0][2]==grid[1][1] && grid[1][1]==grid[2][0])
win=grid[1][1];
if(win==' ')
return false;
if(win=='0'){
cout<<"You lost\n";
return true;
}
if(win=='X'){
cout<<"You win\n";
return true;
}
}
void move(int* x){//minimax function returns row and col for next move of comp
int z[]={0,0,0};
int alpha=-1000,beta=1000;
minimax(3,comp,alpha,beta,z);//3 is the depth upto which comp checks possible grid
x[0]=z[1]; //states to make best move
x[1]=z[2];
}
void minimax(int level,int player,int alpha,int beta,int* x)
{
int score=0;
int row=-1,col=-1;
if(level==0){
score=evaluate(comp)-evaluate(user);
}else{
int count=0;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
if(grid[i][j]==' '){//check all empty cells for player's next move
count++;
if(player==0){//maximising player(comp)
grid[i][j]='0';
score=alpha;
minimax(level-1,1-player,score,beta,x);
int v=x[0];
if(level==1)
cout<<v<<endl<<i<<j<<endl;
if(v>=score){
score=v;
row=i;
col=j;
}
if(score>=beta){
i=3;
j=3;
}
}
else if(player==1){//minimising player-user
grid[i][j]='X';
score=beta;
minimax(level-1,1-player,alpha,score,x);
int v=x[0];
if(v<=score){
score=v;
row=i;
col=j;
}
if(score<=alpha){
i=3;
j=3;
}
}
grid[i][j]=' ';
}
}
}
if(count==0){
score=evaluate(comp)-evaluate(user);
}
}
// cout<<score<<row<<col<<endl;
x[0]=score;
x[1]=row;
x[2]=col;
}
int evaluate(int player)
{
int score = 0;
// Evaluate score for each of the 8 lines (3 rows, 3 columns, 2 diagonals)
//score is 1 if player has a possible path to win in a row(in future)
//score is 0 if both player and opponent can't win in a row
//score is 1000 if player wins in a row
//score is -1000 if opponent wins in a row
score += evaluateLine(0, 0, 0, 1, 0, 2,player); // row 0
score += evaluateLine(1, 0, 1, 1, 1, 2,player); // row 1
score += evaluateLine(2, 0, 2, 1, 2, 2,player); // row 2
score += evaluateLine(0, 0, 1, 0, 2, 0,player); // col 0
score += evaluateLine(0, 1, 1, 1, 2, 1,player); // col 1
score += evaluateLine(0, 2, 1, 2, 2, 2,player); // col 2
score += evaluateLine(0, 0, 1, 1, 2, 2,player); // diagonal
score += evaluateLine(0, 2, 1, 1, 2, 0,player); // alternate diagonal
return score;
}
int evaluateLine(int row1,int col1,int row2,int col2,int row3,int col3,int player)
{
char o;//opponent
char p;//player
if(player==0){
p='0';
o='X';
}
else{
o='0';
p='X';
}
int score=0;
if (grid[row1][col1] == p) {
score = 1;
} else if (grid[row1][col1] == o) {
score = -1;
}
// Second cell
if (grid[row2][col2] == p) {
if (score == 1) { // cell1 is p
score = 10;
} else if (score == -1) { // cell1 is o
return 0;
} else { // cell1 is empty
score = 1;
}
} else if (grid[row2][col2] == o) {
if (score == -1) { // cell1 is o
score = -10;
} else if (score == 1) { // cell1 is p
return 0;
} else { // cell1 is empty
score = -1;
}
}
// Third cell
if (grid[row3][col3] == p) {
if (score > 0) { // cell1 and/or cell2 is p
score *= 10;
} else if (score < 0) { // cell1 and/or cell2 is o
return 0;
} else { // cell1 and cell2 are empty
score = 1;
}
} else if (grid[row3][col3] == o) {
if (score < 0) { // cell1 and/or cell2 is o
score *= 10;
} else if (score > 1) { // cell1 and/or cell2 is p
return 0;
} else { // cell1 and cell2 are empty
score = -1;
}
}
if(score==-1000)
return score;
else if(score==1000)
return score;
else if(score>=0)
return 1;
else
return 0;
}
这是我为使用alpha beta修剪的3x3 Tic Tac Toe游戏编写的一个程序。每次它的动作都会移动它从网格中选择最后一个空单元格。我甚至尝试过将alpha beta修剪更改为简单的minimax,但它也有同样的问题。请帮我找到我的解决方案的问题。
谢谢。
This is a program i wrote for a 3x3 Tic Tac Toe game using alpha beta pruning.Every time its comp's turn to make a move it selects last empty cell from the grid.I have tried even changing alpha beta pruning to simple minimax,but it also has the same problem.Please help me to find the problem with my solution.
Thanks.
推荐答案
这篇关于如何使用Alpha Beta修剪来纠正这个井字游戏程序的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文