Implementing alpha beta pruning in a TicTacToe minimax algorithm
In my method newminimax49 I have a minimax algorithm that utilizes memoization and other general improvements which were suggested to me in this post. The method uses a simple heuristic board evaluation function. My question is basically regarding alpha beta pruning, namely whether or not my minimax method utilizes alpha beta pruning. To my knowledge I believe that it does, however what I've used to achieve it seems too simple to be true. Furthermore, others have suggested that I use alpha beta pruning which, as I said, I had thought my minimax method already does, which leads me to believe that what I'm doing here is something else. So here is my newminimax49:
//This method returns a 2 element int array containing the position of the best possible
//next move and the score it yields. Utilizes memoization and supposedly alpha beta
//pruning to achieve better performance. Alpha beta pruning can be seen in lines such as:
/*if(bestScore==-10)
break;*/
//This basically means that if the best score achieved is the best possible score
//achievable then stop exploring the other available moves. Doing thing I believe
//I'm applying the same principle of alpha beta pruning.
public int[] newminimax49(){
int bestScore = (turn == 'O') ? +9 : -9; //X is minimizer, O is maximizer
int bestPos=-1;
int currentScore;
//boardShow();
String stateString = "";
for (int i=0; i<state.length; i++)
stateString += state[i];
int[] oldAnswer = oldAnswers.get(stateString);
if (oldAnswer != null)
return oldAnswer;
if(isGameOver2()!='N'){
//s.boardShow();
bestScore= score();
}
else{
//s.boardShow();
int i=0;
for(int x:getAvailableMoves()){
if(turn=='X'){ //X is minimizer
setX(x);
//boardShow();
//System.out.println(stateID++);
currentScore = newminimax49()[0];
revert(x);
if(i==0){
bestScore = currentScore;
bestPos=x;
if(bestScore==-10)
break;
}
else if(currentScore<bestScore){
bestScore = currentScore;
bestPos=x;
if(bestScore==-10)
break;
}
}
else { //O is maximizer
setO(x);
//boardShow();
//System.out.println(stateID++);
currentScore = newminimax49()[0];
revert(x);
//boardShow();
if(i==0){
bestScore = currentScore;
bestPos=x;
if(bestScore==10)
break;
}
else if(currentScore>bestScore){
bestScore = currentScore;
bestPos = x;
if(bestScore==10)
break;
}
}
i++;
}
}
int[] answer = {bestScore, bestPos};
oldAnswers.put (stateString, answer);
return answer;
}
The fields and constructor used in my class State2:
private char [] state; //Actual content of the board
private char turn; //Whose turn it is
private Map<String,int[]> oldAnswers; //Used for memoization. It saves every state along with the score it yielded which allows us to stop exploring the children of a certain node if a similar node's score has been previously calculated. The key is the board state(i.e OX------X for example), the int array is a 2 element array containing the score and position of last placed seed of the state.
private Map<Integer, int []> RowCol; //A mapping of positions from a board represented as a normal array to a board represented as a 2d array. For example: The position 0 maps to 0,0 on a 2d array board, 1 maps to 0,1 and so on.
private static int n; //Size of the board
private static int stateID; //An simple incrementer used to show number of recursive calls in the newminiax49 method.
private static int countX, countO; //Number of placed Xs and Os
private static int lastAdded; //Position of last placed seed
private char [][] DDState; //A 2d array representing the board. Contains the same values as state[]. Used for simplicity in functions that check the state of the board.
public State2(int n){
int a=0;
State2.n=n;
state=new char[n*n];
RowCol=new HashMap<Integer, int []>();
countX=0;
countO=0;
//Initializing the board with empty slots
for(int i = 0; i<state.length; i++){
state[i]='-';
}
//Mapping
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
RowCol.put(a, new int[]{i, j});
a++;
}
}
a=0;
DDState=new char[n][n];
//Initializing the 2d array with the values from state[](empty slots)
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
DDState[i][j]=state[a];
a++;
}
}
oldAnswers = new HashMap<String,int[]>();
}
Complementary methods:
getAvailableMoves, returns an array with the empty slots on the board(ie the possible next moves).
public int[] getAvailableMoves(){
int count=0;
int i=0;
for(int j=0; j<state.length; j++){
if(state[j]=='-')
count++;
}
int [] availableSlots = new int[count];
for(int j=0; j<state.length; j++){
if(state[j]=='-')
availableSlots[i++]=j;
}
return availableSlots;
}
isGameOver2(), simply checks the current state of the board for whether the game is over. returns a char 'X', 'O', 'D' and 'N' which stand for X won, O won, Draw, and Not gameover respectively.
public char isGameOver2(){
char turnOpp;
int count;
if(turn=='X'){
count=countO;
turnOpp='O';
}
else {
count=countX;
turnOpp='X';
}
if(count>=n){
//^No win available if each player has less than n seeds on the board
//Checking begins
//DDState[RowCol.get(lastAdded)[0]][RowCol.get(lastAdded)[1]]=turn;
//Check column for win
for(int i=0; i<n; i++){
if(DDState[i][RowCol.get(lastAdded)[1]]!=turnOpp)
break;
if(i==(n-1)){
//DDState[RowCol.get(x)[0]][RowCol.get(x)[1]]='-';
return turnOpp;
}
}
//Check row for win
for(int i=0; i<n; i++){
if(DDState[RowCol.get(lastAdded)[0]][i]!=turnOpp)
break;
if(i==(n-1)){
//DDState[RowCol.get(x)[0]][RowCol.get(x)[1]]='-';
return turnOpp;
}
}
//Check diagonal for win
if(RowCol.get(lastAdded)[0] == RowCol.get(lastAdded)[1]){
//we're on a diagonal
for(int i = 0; i < n; i++){
if(DDState[i][i] != turnOpp)
break;
if(i == n-1){
//DDState[RowCol.get(x)[0]][RowCol.get(x)[1]]='-';
return turnOpp;
}
}
}
//check anti diagonal
for(int i = 0; i<n; i++){
if(DDState[i][(n-1)-i] != turnOpp)
break;
if(i == n-1){
//DDState[RowCol.get(x)[0]][RowCol.get(x)[1]]='-';
return turnOpp;
}
}
//check for draw
if((countX+countO)==(n*n))
return 'D';
}
return 'N';
}
boardShow, returns a matrix display of the current state of the board:
public void boardShow(){
if(n==3){
System.out.println(stateID);
for(int i=0; i<=6;i+=3)
System.out.println("["+state[i]+"]"+" ["+state[i+1]+"]"+" ["+state[i+2]+"]");
System.out.println("***********");
}
else {
System.out.println(stateID);
for(int i=0; i<=12;i+=4)
System.out.println("["+state[i]+"]"+" ["+state[i+1]+"]"+" ["+state[i+2]+"]"+" ["+state[i+3]+"]");
System.out.println("***********");
}
}
score, is a simple evaluation function which returns +10 for an O win, -10 for an X win and 0 for a draw:
public int score(){
if(isGameOver2()=='X')
return -10;
else if(isGameOver2()=='O')
return +10;
else
return 0;
}
The seed setters:
//Sets an X at a certain location and updates the turn, countX and lastAdded variables
public void setX(int i){
state[i]='X';
DDState[RowCol.get(i)[0]][RowCol.get(i)[1]]='X';
turn='O';
countX++;
lastAdded=i;
}
//Sets an O at a certain location and updates the turn, countO and lastAdded variables
public void setO(int i){
state[i]='O';
DDState[RowCol.get(i)[0]][RowCol.get(i)[1]]='O';
turn='X';
countO++;
lastAdded=i;
}
Revert, simply reverts a move. For example if an X has been placed in position 0 revert(0) sets a '-' in it's place and updates the variables changed by setX:
public void revert(int i){
state[i]='-';
DDState[RowCol.get(i)[0]][RowCol.get(i)[1]]='-';
if(turn=='X'){
turn = 'O';
countO--;
}
else {
turn = 'X';
countX--;
}
}
So does this look like alpha beta pruning to you guys and if not how can I make it happen?
You are already using some kind of "simplified" Alpha-Beta: currently, you are pruning whenever a player finds a winning position.
A proper AB would pass itself an Alpha and a Beta value, to determine the minimum respectively maximum the players will achieve. There, you prune whenever a score is worse or equal than the current "worst case" of the opposite player.
In your case, you will not only be able to prune at winning scores (as you do currently) but also at some scores that are 0.
链接地址: http://www.djcxy.com/p/56316.html上一篇: negaMax算法产生一些奇怪的结果