• Create Account

### #Actualwhitenose

Posted 08 October 2012 - 01:25 PM

Hello,
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 ?

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 );

// 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 .

### #4whitenose

Posted 08 October 2012 - 01:24 PM

Hello,
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 ?

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:

[source lang="java"]short depth = 2; // get best move for "computer" on this phase getBestMove(simulationBoard, depth , Integer.MIN_VALUE+1, Integer.MAX_VALUE-1, true);[/source]

and this is the evaluation function :

[source lang="java"]// 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;}[/source]

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 );

// 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 .

### #3whitenose

Posted 08 October 2012 - 01:24 PM

Hello,
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 ?

Here is my Java code , and getBestMove() function :

[source lang="java"]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; }}[/source]

and the calling of this method is:

[source lang="java"]short depth = 2; // get best move for "computer" on this phase getBestMove(simulationBoard, depth , Integer.MIN_VALUE+1, Integer.MAX_VALUE-1, true);[/source]

and this is the evaluation function :

[source lang="java"]// 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;}[/source]

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 );

// 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 .

### #2whitenose

Posted 08 October 2012 - 01:23 PM

Hello,
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 ?

Here is my Java code , and getBestMove() function :

[source lang="java"]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; }}[/source]

and the calling of this method is:

[source lang="java"]short depth = 2; // get best move for "computer" on this phase getBestMove(simulationBoard, depth , Integer.MIN_VALUE+1, Integer.MAX_VALUE-1, true);[/source]

and this is the evaluation function :

[source lang="java"]// 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;}[/source]

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 );

// 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 .

### #1whitenose

Posted 08 October 2012 - 01:21 PM

Hello,
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 ?

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;
}

}[/size]



and the calling of this method is:

[source lang="java"]short depth = 2; // get best move for "computer" on this phase getBestMove(simulationBoard, depth , Integer.MIN_VALUE+1, Integer.MAX_VALUE-1, true);[/source]

and this is the evaluation function :

[source lang="java"]// 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;}[/source]

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 );

// 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 .

PARTNERS