Jump to content

  • Log In with Google      Sign In   
  • Create Account

Banner advertising on our site currently available from just $5!

1. Learn about the promo. 2. Sign up for GDNet+. 3. Set up your advert!


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

Topics I've Started

minimax with alpha beta pruning implementation stuck.

08 October 2012 - 01:21 PM

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.
   // return alpha.
   return alpha;
	   // 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.
   // 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).
   team = renderer.TEAM_OPPONENT;
   game_status = (short) renderer.gOpponent.gGameStatus;
   team = renderer.TEAM_PLAYER;
   game_status = (short) renderer.gPlayer.gGameStatus;

  // according to current player's (computer/human) game-status:

	// 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.
		 // 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 );
}//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 .

linking navmeshes between them.

09 November 2011 - 12:02 PM


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 :


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


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




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.