Find content
Not Telling
Im new to this so please escuse my mistakes.
I'm trying to implement a 9Men's Morris game and i'm using minimax with alpha-beta pruning finding BestMove for "computer".
The problem is that if depth >= 3 then getBestMove() returns invalid move (board) , meaning that
it's returning a move (board) from other team sometimes - and I don't know where i go wrong.
Is my algorithm implementation done right ?! What i'm missing ?
Please Help !!
Here is my Java code , and getBestMove() function :
private int getBestMove(board board, int depth, int alpha, int beta, boolean bIsMax)
{
// is depth reached ? or do we have a winner ? (checkWinner() returns 0 if nobody is winning so far!)
if (depth == 0 || board.checkWinner()!=0)
{
// if depth reached, or we DO have a winner.
return board.evaluateBoard();
}
// is "computer" turn
if (bIsMax)
{
// generate all possible boards for "computer" (MAX).
ArrayList<board> boardsArray = board.generateNextPossibleBoards(bIsMax);
// loop thru all possible previously generated boards
for(board nextBoard: boardsArray)
{
// recurse
int score = Math.max(alpha, getBestMove(nextBoard, depth - 1, alpha, beta, !bIsMax));
nextBoard.showBoard("next-max[" + boardsArray.size() + "]"); // display to user current board.(debbuging purpose)
// found a better board ?
if ( score > alpha )
{
alpha = score;
chosenBoard = nextBoard; // save best board so far to "chosenBoard"
}
if(beta<=score) break; // prune
}
// clear boards array when done.
boardsArray.clear();
// return alpha.
return alpha;
}
else
{
// generate all possible boards for "player" (MIN).
ArrayList<board> boardsArray = board.generateNextPossibleBoards(bIsMax);
// loop thru all these possible boards.
for(board nextBoard: boardsArray)
{
// recurse
beta = Math.min(beta, getBestMove(nextBoard, depth - 1, alpha, beta, !bIsMax));
nextBoard.showBoard("next-min[" + boardsArray.size() + "]");
if(beta <= alpha) break; // prune.
}
// clear boards array when done.
boardsArray.clear();
// return beta.
return beta;
}
}
and the calling of this method is:
short depth = 2; // get best move for "computer" on this phase getBestMove(simulationBoard, depth , Integer.MIN_VALUE+1, Integer.MAX_VALUE-1, true);
and this is the evaluation function :
// evaluate current board.
public int evaluateBoard()
{
int score = 0;
score = score + (checkWinner()); // checkWinner() returns -1000000 if player wins, +1000000 if computer wins.
score = score + (checkMills()*1000); // checkMills() returns -10000*mills_count if player has some mills formed, or +10000*mills_count otherwise.
score = score + (checkBlockers()*500); // checkBlockers() returns -1000*block_count if player has bloked some tokens, or +1000*block_count otherwise
score = score + (checkFormers()*50); // etc.
score = score + (checkTokenDifference()*10);
return score;
}
and the generateNextPossibleBoards() function wich chooses "default" switch case here :
public ArrayList<board> generateNextPossibleBoards(boolean bIsMax)
{
// copy current board
board currentBoard = new board(this);
// instantiate a empty array.
ArrayList<board> boardsArray = new ArrayList<board>();
// current team is unknown.
short team = -1;
short game_status = -1;
// update current team (can be "computer" or "human" player).
if(bIsMax)
{
team = renderer.TEAM_OPPONENT;
game_status = (short) renderer.gOpponent.gGameStatus;
}
else
{
team = renderer.TEAM_PLAYER;
game_status = (short) renderer.gPlayer.gGameStatus;
}
// according to current player's (computer/human) game-status:
switch(game_status)
{
...
default:
// generate a move (a board) and save this new board to boardsArray.
// if no moves left, return all boards so far!
for(short i=0;i<24;i++)
{
// go thru all tokens in this board.
if(currentBoard.gNode[i].gOccupiedByTeam==team)
{
// check if any empty neighbours for this token
for(short n=0;n<4;n++)
{
// get neighborur node id
short id = currentBoard.gNode[i].gNeighbourId[n];
// check if neighbour is empty spot (empty node)
if(id!=-1 && currentBoard.gNode[id].gOccupiedByTeam==renderer.TEAM_NOTEAM)
{
// make move for this token to the empty neighbour found above.
currentBoard.makeMoveToken( i , id );
boardsArray.add(new board(currentBoard));
// undo previous move
currentBoard.undoMoveToken( id , i );
}
}
}
}
break;
}//end switch.
// return all possible boards so far.
return boardsArray;
}
thak you.
P.S: sorry for the bad view of some of the code.
just could not succeded making it "java" (using [source lang="java"]) because it was "eating" my code and the functions were displayed
partially .
