• Create Account

Interested in a FREE copy of HTML5 game maker Construct 2?

We'll be giving away three Personal Edition licences in next Tuesday's GDNet Direct email newsletter!

We're also offering banner ads on our site from just \$5! 1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.

# whitenose

Member Since 17 Mar 2011
Offline Last Active Mar 19 2013 04:02 AM

### minimax with alpha beta pruning implementation stuck.

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

}

```

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 .

09 November 2011 - 12:02 PM

Hello,

I'm having some trouble , and no ideeas yet, on how to link different triangle NavMeshes (or make connections between them) .

Here is a screnshot with 3 triangle Navmeshes - first in wireframe view :

http://imageshack.us...reframepic.jpg/

... and here is the same scene from almost same point of view, ths time textured and lit :

http://imageshack.us...uredlitpic.jpg/

...and 2 more screnshots again , wireframe view , with neighbour connections drawn between triangles,
please take a good look and you can notice that between red , brown and gray Navmeshes - there are NO CONNECTIONS :

http://imageshack.us.../unledpov1.jpg/

and

http://imageshack.us.../unledpov2.jpg/

OK,now go back please, and look at the very first picture .

My problem is that : I dont have no ideea on how to connect these three NavMeshes between them ?!

I know that i have to somehow connect those two "last stair" triangles with --> some triangle (or both triangles) wich belong to the GrayNavMesh .
Same thing , dont know how to connect those two triangles wich belong to the RedNavmesh with "first stair" 2 triangles ?

Thank you.

PS: still continuing my hobby on this, http://www.gamedev.net/topic/560218-funnel-algorithm/ , but lost my pass and had trouble with my email .. anyways, thank you.

PARTNERS