29 iunie 2010

X si 0

#include"stdio.h"
#include"stdlib.h"

#define B_SIZE 3
#define WIN 10000
#define LOSS -10000
#define DRAW 0
#define OCHAR(ch) ((ch=='X')?'O':'X')

char gameboard[3][3] =
{' ',' ',' ',
' ',' ',' ',
' ',' ',' '
};

int curX,curY;
int nodesSearched;

void clrscr(void)
{
#ifdef __linux__
system("clear");
#else
system("CLS");
#endif
}

// Draws the game board accourding to the accupancy matrix
void DrawBoard(char board[3][3])
{
printf("\n 0 1 2\n +-+-+-+\n");
for(int i=0; i < B_SIZE;i++)
{
printf("%d ",i);
for(int j=0; j < B_SIZE;j++)
printf("|%c",board[i][j]);
printf("|\n +-+-+-+\n");
}
}

// Evaluates the win
int CheckStatus(char board[3][3],char ch)
{
int i,j,ord;
for(i=0; i < B_SIZE;i++)
{
ord=0;
for(j=0; j < B_SIZE;j++)
{
if(board[i][j]==ch) ord++;
else break;
}
if(ord==3) return 1;
}
ord=0;
for(i=0; i < B_SIZE;i++)
{
ord=0;
for(j=0; j < B_SIZE;j++)
{
if(board[j][i]==ch) ord++;
else break;
}
if(ord==3) return 1;
}
ord=0;
for(i=0;i < B_SIZE;i++)
if(board[i][i]==ch) ord++;
if(ord==3) return 1;
else ord=0;
for(i=0; i < B_SIZE;i++)
if(board[i][B_SIZE-i-1]==ch) ord++;
if(ord==3) return 1;
return 0;
}

int Negamax(char board[3][3],int occ,int depth,char ch)
{
int score, max=LOSS;
int i,j;
nodesSearched++;
if(CheckStatus(board,ch)==1) return WIN*(10-depth); //*(10-depth) is there so we choose the shortest path to victory
else if(CheckStatus(board,OCHAR(ch))==1) return LOSS*(10-depth);
else if(occ>=9) return DRAW;
for(i=0; i < B_SIZE;i++)
for(j=0;j < B_SIZE;j++)
if(board[j][i]==' ')
{
board[j][i]=ch;
score=-Negamax(board,occ+1,depth+1,OCHAR(ch));
board[j][i]=' ';
if(score > max)
{
max=score;
if(depth==0)
{
curX=i;
curY=j;
}
}
}
return max;
}

int AlphaBeta(char board[3][3],int occ,int depth,int alpha,int beta,char ch)
{
int score,bestscore=LOSS;
int i,j;
nodesSearched++;
if(CheckStatus(board,ch)==1) return WIN*(10-depth); //*(10-depth) is there so we choose the shortest path to victory
else if(CheckStatus(board,OCHAR(ch))==1) return LOSS*(10-depth);
else if(occ>=9) return DRAW;
for(i=0; i < B_SIZE;i++)
for(j=0; j < B_SIZE;j++)
if(board[j][i]==' ')
{
board[j][i]=ch;
score=-AlphaBeta(board,occ+1,depth+1,-beta,-alpha,OCHAR(ch));
board[j][i]=' ';
if(score > beta) return score; // beta cutoff
if(score > bestscore)
{
bestscore=score;
if(depth==0)
{
curX=i;
curY=j;
}
if(score>alpha) alpha=score;
}
}
return bestscore;
}

int main()
{
int x,y,occ=0;
char mych='X',winner=0;
do
{
clrscr();
DrawBoard(gameboard);
printf("Previous move explored %d nodes\nIntroduce (x,y) coordinates:\n",nodesSearched);
scanf("%d",&y);
scanf("%d",&x);
if(x>=B_SIZE || x<0>=B_SIZE || y<0 || gameboard[y][x]!=' ') continue;

gameboard[y][x]=mych;
if(CheckStatus(gameboard,mych))
{
winner=mych;
continue;
}
if((++occ)>=9) break;

nodesSearched=0;
//Negamax(gameboard,occ,0,OCHAR(mych));
AlphaBeta(gameboard,occ,0,LOSS*11,WIN*11,OCHAR(mych));

gameboard[curY][curX]=OCHAR(mych);
if(CheckStatus(gameboard,OCHAR(mych)))
{
winner=OCHAR(mych);
continue;
}
if((++occ)>=9) break;

}while(!winner);
clrscr();
DrawBoard(gameboard);
printf("\n\nWinner is %c",winner);
return 0;
}

Niciun comentariu: