Jump to content

  • Log In with Google      Sign In   
  • 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!

Sign up from the right-hand sidebar on our homepage and read Tuesday's newsletter for details!


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

Topics I've Started

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

linking navmeshes between them.

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