Jump to content

  • Log In with Google      Sign In   
  • Create Account


#Actualwhitenose

Posted 11 October 2012 - 11:21 PM

Hello,

I'm so sorry for the late reply. I had a car accident, all it's ok...
Thanks for all your answers !

As i said first, i'm trying to do a simple 9Men's Morris game (for Android).
This game has 3 phases: PlacingTokens, PlayGame, EndGame as you well know.

I have switched to negaMax() but the problem persists, and i think I know where/when it happens (i will explain) but dont know how to fix it. Posted Image
The problem is returning final "bestMove" to the main calling function .

Had some time today to implemeent negaMax() and i hope didn't made mistakes - and it seems that at "depth=1" when PlacingTokens phase is active -> all it's OK. (meaning that the "computer" plays good enough).
The calling code for this looks like this now for negaMax():




// as you can see "depth=1" (MAX = "computer" turn !)
case renderer.GAMESTATUS_PLACETOKEN:
  
					 //PARAMETERS:   simulationBoard, depth, alpha, beta,  sign (or color wich wil alternate between +1 or -1)
					negaMax(simulationBoard, 1,		Integer.MIN_VALUE+1, Integer.MAX_VALUE-1,   1);

My "negaMax()" function looks like this:


private int negaMax(board board, int depth, int alpha, int beta, int sign)
{
		// if depth reached or we DO have a winner on "this" board
		if(depth<=0 || board.checkWinner(sign))
		{	
			// evaluateBoard() evaluates board from "sign"'s point of view and returns a positive or negative score.
			return sign*board.evaluateBoard(sign);  
		}
		
		int max = Integer.MIN_VALUE+1; // -VERY SMALL value.
		
		// generate all available possible moves
		ArrayList<board> boardsArray = board.generateNextPossibleBoards(sign);
	
		// loop thru all generated boards
		for(board nextBoard: boardsArray)
		{
			// recurse and store result to "x" .
			int x = -negaMax(nextBoard, depth-1, -beta, -alpha,  -sign); // sign alterantes between +1 & -1 (computer & human)
			
			// got a "better/best" move ?
			if (x>max)
			{
				// save the "best" move so far.
				max = x;
				chosenBoard = nextBoard;
				chosenBoard.showBoard("FOUND BEST MOVE");
			}
			
			// alpha-beta pruning
			if (x>alpha) alpha = x;
			if (alpha>=beta) return alpha;
		}

		// clear boards when done.
		boardsArray.clear();
		
		// return best move so far.
		return max;
	}


allright, and now the checkWinner(sign) method (wich returns true or false if a team is Winning)


public boolean checkWinner(int sign)
{
  board board = this;

  // ---------------------------------------------------------------------------------
  // 0. get current team
  // ---------------------------------------------------------------------------------
  int team = renderer.TEAM_NOTEAM;
  int opponent = renderer.TEAM_NOTEAM;

  if(sign==1)
  {
   // if "computer" turn
   team = renderer.TEAM_OPPONENT;
   opponent = renderer.TEAM_PLAYER;
  }
  else
  {
   // if "human" turn
   team = renderer.TEAM_PLAYER;
   opponent = renderer.TEAM_OPPONENT;
  }


  // ---------------------------------------------------------------------------------
  // 1. check if only 2 tokens (from opponent team!) are left  on current board.
  // ---------------------------------------------------------------------------------
  int counter = 0;

  for(short i=0;i<24;i++)
  {
   if(board.gNode[i].gOccupiedByTeam!=renderer.TEAM_NOTEAM && board.gNode[i].gOccupiedByTeam==opponent) counter++; // count opponent tokens
  }

  switch(team)
  {
   case renderer.TEAM_OPPONENT:
	if(counter<=2 && renderer.gPlayer.gTokensToPlaceOnTable==0)
	{
	 return true;  // opponent has won.
	}
	break;
   case renderer.TEAM_PLAYER:
	if(counter<=2 && renderer.gOpponent.gTokensToPlaceOnTable==0)
	{
	 return true; // player has won.
	}
	break;
  }


  // ---------------------------------------------------------------------------------
  // 2. all opponent tokens are blocked! (no more possible moves, all tokens are blocked)
  // ---------------------------------------------------------------------------------
  for(short i=0;i<24;i++)
  {
   // go thru all tokens in this board, if opponent is not blocked -> return false.
   if(board.gNode[i].gOccupiedByTeam==opponent)
   {
	// check if any empty neighbours for this token
	for(short n=0;n<4;n++)
	{
	 // get neighborur id
	 int id = board.gNode[i].gNeighbourId[n];
	
	 // check if neighbour is empty space.
	 if(id!=-1 && board.gNode[id].gOccupiedByTeam==renderer.TEAM_NOTEAM)
	 {
	  // still having empty spaces to move. (NOT BLOCKED!)
	  return false;
	 }
	}
   }
  }

  // opponent is BLOCKED! so this team is winning -> return true!
  return true;
}



and this is the evaluateBoard(sign) function wich evaluates current board from --> "sign" ("computer" or "human") point of view :


  // evaluate current board.
	public int evaluateBoard(int sign)
	{
		int score 		= 0;
		int formers 	= checkFormers(sign);	// if 2 tokens on same row/column has been found, then a former has been found.
		int blockers 	= checkBlockers(sign);	// if 1 token blocks a token form other team, then we have a blocker.  
		int mills 		= checkMills(sign);		// if a mill has been formed (3 tokens in a row/column), then we have a mill.
		int tkcount 	= checkTokenCount(sign);// count token (team - opponent) difference on this board.
		
		score = score + formers*250;			// multiplier is 10 here for the "formers"
		score = score + blockers*500;			// multiplier is 500 here for the "blockers"
		score = score + mills*1000;				// etc.
		score = score + tkcount*10;

		if(sign==1) // is it "computer" turn?
		{
			return -score; 	// return score for "computer"
		}
		else
		{
			return +score;	// return score for "human"
		}
		
	}



OK, now generating boards in 1st phase (PlacingTokens) is done like so:


public ArrayList<board> generateNextPossibleBoards(int sign)
	{
		// copy current board
		board currentBoard 	= new board(this);
		
		// instantiate a empty array.
		ArrayList<board> boardsArray = new ArrayList<board>();
		
		// current team is unknown.
		int team = -1;
		int opponent = -1;
		int game_status = -1;
		
		// update current team (can be "computer" or "human" player).
		if(sign==1)
		{
			team = renderer.TEAM_OPPONENT;
			opponent = renderer.TEAM_PLAYER;
			game_status = renderer.gOpponent.gGameStatus;
		}
		else
		{
			team = renderer.TEAM_PLAYER;
			opponent = renderer.TEAM_OPPONENT;
			game_status = renderer.gPlayer.gGameStatus;
		}
		
		// according to current player's (computer/human) game-status:
		switch(game_status)
		{	
			case renderer.GAMESTATUS_PLACETOKEN:
				// simulate a single place token (on this board) and save this new board to boardsArray.
				for(short i=0;i<24;i++)
				{
					// go thru all empty spaces on this board , and if not occupied by any token
					if(currentBoard.gNode[i].gOccupiedByTeam==renderer.TEAM_NOTEAM)
					{
						// place (a opponent) token to the empty neighbour found
						currentBoard.makePlaceToken( i , opponent ); // place a opponent token !!!

						boardsArray.add(new board(currentBoard));
						
						// undo previous move
						currentBoard.undoPlaceToken( i , renderer.TEAM_NOTEAM);
					}
				}
				
				break;
...
... return boardsArray; // return all generated boards.

OK , all it's good so far, the "computer" finds best moves and plays good against "human" .
--------------------------------------------------------------------------------------------------------------------------------------------------


The problem is when swithcing to phase2 -> i.e the "PlayGame" phase !
The code doesn't change EXCEPT generating "moves" when in "PlayGame" phase.
Now, generating "moves" is done like so:

public ArrayList<board> generateNextPossibleBoards(int sign)
	{
		// copy current board
		board currentBoard	 = new board(this);
	  
		// instantiate a empty array.
		ArrayList<board> boardsArray = new ArrayList<board>();
	  
		// current team is unknown.
		int team = -1;
		int opponent = -1;
		int game_status = -1;
	  
		// update current team (can be "computer" or "human" player).
		if(sign==1)
		{
			team = renderer.TEAM_OPPONENT;
			opponent = renderer.TEAM_PLAYER;
			game_status = renderer.gOpponent.gGameStatus;
		}
		else
		{
			team = renderer.TEAM_PLAYER;
			opponent = renderer.TEAM_OPPONENT;
			game_status = renderer.gPlayer.gGameStatus;
		}
	  
		// according to current player's (computer/human) game-status:
		switch(game_status)
		{
			 ....
			 ....
case renderer.GAMESTATUS_PLAYNORMAL:
  
	// 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 id
	   int id = currentBoard.gNode[i].gNeighbourId[n];
	  
	   // check if neighbour is empty spot.
	   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 PLAYNORMAL.

....
}   // end function generateNextPossibleBoards()
	

I have done a picture for you to see what happens when depth>1 and why the chosenBoard is not correctly chosen.

http://imageshack.us...0/mistaker.jpg/

step1) As you can see, token from node=3 (depth=3) generates a new "move" to node=4 (depth=2).
step2) After that negaMax() recurses itself again and the token from node=4 generates again a new move to node=7(depth=1).
step3) Similar, from node=7 a token is generated again and set to node=8 (when negaMax() recurses again).

Now token from node=8 is selected as the "chosen" best move --> and return it to main function, right ? (because we have Win or good score)
But...when moving from starting node=3 to node=8 there's a problem (because node=8 token is "far" away from token=3)
This is what i must solve, how do i return best move when depth > 1 ?



Im sorry for the long post.
I hope you accept my appologies !

LE:
@alvaro : OK, ill try that and get back to you. THANKS!

#6whitenose

Posted 11 October 2012 - 12:37 PM

Hello,

I'm so sorry for the late reply. I had a car accident, all it's ok...
Thanks for all your answers !

As i said first, i'm trying to do a simple 9Men's Morris game (for Android).
This game has 3 phases: PlacingTokens, PlayGame, EndGame as you well know.

I have switched to negaMax() but the problem persists, and i think I know where/when it happens (i will explain) but dont know how to fix it. Posted Image
The problem is returning final "bestMove" to the main calling function .

Had some time today to implemeent negaMax() and i hope didn't made mistakes - and it seems that at "depth=1" when PlacingTokens phase is active -> all it's OK. (meaning that the "computer" plays good enough).
The calling code for this looks like this now for negaMax():




// as you can see "depth=1" (MAX = "computer" turn !)
case renderer.GAMESTATUS_PLACETOKEN:
  
					 //PARAMETERS:   simulationBoard, depth, alpha, beta,  sign (or color wich wil alternate between +1 or -1)
					negaMax(simulationBoard, 1,		Integer.MIN_VALUE+1, Integer.MAX_VALUE-1,   1);

My "negaMax()" function looks like this:


private int negaMax(board board, int depth, int alpha, int beta, int sign)
{
		// if depth reached or we DO have a winner on "this" board
		if(depth<=0 || board.checkWinner(sign))
		{	
			// evaluateBoard() evaluates board from "sign"'s point of view and returns a positive or negative score.
			return sign*board.evaluateBoard(sign);  
		}
		
		int max = Integer.MIN_VALUE+1; // -VERY SMALL value.
		
		// generate all available possible moves
		ArrayList<board> boardsArray = board.generateNextPossibleBoards(sign);
	
		// loop thru all generated boards
		for(board nextBoard: boardsArray)
		{
			// recurse and store result to "x" .
			int x = -negaMax(nextBoard, depth-1, -beta, -alpha,  -sign); // sign alterantes between +1 & -1 (computer & human)
			
			// got a "better/best" move ?
			if (x>max)
			{
				// save the "best" move so far.
				max = x;
				chosenBoard = nextBoard;
				chosenBoard.showBoard("FOUND BEST MOVE");
			}
			
			// alpha-beta pruning
			if (x>alpha) alpha = x;
			if (alpha>=beta) return alpha;
		}

		// clear boards when done.
		boardsArray.clear();
		
		// return best move so far.
		return max;
	}


allright, and now the checkWinner(sign) method (wich returns true or false if a team is Winning)


public boolean checkWinner(int sign)
{
  board board = this;

  // ---------------------------------------------------------------------------------
  // 0. get current team
  // ---------------------------------------------------------------------------------
  int team = renderer.TEAM_NOTEAM;
  int opponent = renderer.TEAM_NOTEAM;

  if(sign==1)
  {
   // if "computer" turn
   team = renderer.TEAM_OPPONENT;
   opponent = renderer.TEAM_PLAYER;
  }
  else
  {
   // if "human" turn
   team = renderer.TEAM_PLAYER;
   opponent = renderer.TEAM_OPPONENT;
  }


  // ---------------------------------------------------------------------------------
  // 1. check if only 2 tokens (from opponent team!) are left  on current board.
  // ---------------------------------------------------------------------------------
  int counter = 0;

  for(short i=0;i<24;i++)
  {
   if(board.gNode[i].gOccupiedByTeam!=renderer.TEAM_NOTEAM && board.gNode[i].gOccupiedByTeam==opponent) counter++; // count opponent tokens
  }

  switch(team)
  {
   case renderer.TEAM_OPPONENT:
	if(counter<=2 && renderer.gPlayer.gTokensToPlaceOnTable==0)
	{
	 return true;  // opponent has won.
	}
	break;
   case renderer.TEAM_PLAYER:
	if(counter<=2 && renderer.gOpponent.gTokensToPlaceOnTable==0)
	{
	 return true; // player has won.
	}
	break;
  }


  // ---------------------------------------------------------------------------------
  // 2. all opponent tokens are blocked! (no more possible moves, all tokens are blocked)
  // ---------------------------------------------------------------------------------
  for(short i=0;i<24;i++)
  {
   // go thru all tokens in this board, if opponent is not blocked -> return false.
   if(board.gNode[i].gOccupiedByTeam==opponent)
   {
	// check if any empty neighbours for this token
	for(short n=0;n<4;n++)
	{
	 // get neighborur id
	 int id = board.gNode[i].gNeighbourId[n];
	
	 // check if neighbour is empty space.
	 if(id!=-1 && board.gNode[id].gOccupiedByTeam==renderer.TEAM_NOTEAM)
	 {
	  // still having empty spaces to move. (NOT BLOCKED!)
	  return false;
	 }
	}
   }
  }

  // opponent is BLOCKED! so this team is winning -> return true!
  return true;
}



and this is the evaluateBoard(sign) function wich evaluates current board from --> "sign" ("computer" or "human") point of view :


  // evaluate current board.
	public int evaluateBoard(int sign)
	{
		int score 		= 0;
		int formers 	= checkFormers(sign);	// if 2 tokens on same row/column has been found, then a former has been found.
		int blockers 	= checkBlockers(sign);	// if 1 token blocks a token form other team, then we have a blocker.  
		int mills 		= checkMills(sign);		// if a mill has been formed (3 tokens in a row/column), then we have a mill.
		int tkcount 	= checkTokenCount(sign);// count token (team - opponent) difference on this board.
		
		score = score + formers*250;			// multiplier is 10 here for the "formers"
		score = score + blockers*500;			// multiplier is 500 here for the "blockers"
		score = score + mills*1000;				// etc.
		score = score + tkcount*10;

		if(sign==1) // is it "computer" turn?
		{
			return -score; 	// return score for "computer"
		}
		else
		{
			return +score;	// return score for "human"
		}
		
	}



OK, now generating boards in 1st phase (PlacingTokens) is done like so:


public ArrayList<board> generateNextPossibleBoards(int sign)
	{
		// copy current board
		board currentBoard 	= new board(this);
		
		// instantiate a empty array.
		ArrayList<board> boardsArray = new ArrayList<board>();
		
		// current team is unknown.
		int team = -1;
		int opponent = -1;
		int game_status = -1;
		
		// update current team (can be "computer" or "human" player).
		if(sign==1)
		{
			team = renderer.TEAM_OPPONENT;
			opponent = renderer.TEAM_PLAYER;
			game_status = renderer.gOpponent.gGameStatus;
		}
		else
		{
			team = renderer.TEAM_PLAYER;
			opponent = renderer.TEAM_OPPONENT;
			game_status = renderer.gPlayer.gGameStatus;
		}
		
		// according to current player's (computer/human) game-status:
		switch(game_status)
		{	
			case renderer.GAMESTATUS_PLACETOKEN:
				// simulate a single place token (on this board) and save this new board to boardsArray.
				for(short i=0;i<24;i++)
				{
					// go thru all empty spaces on this board , and if not occupied by any token
					if(currentBoard.gNode[i].gOccupiedByTeam==renderer.TEAM_NOTEAM)
					{
						// place (a opponent) token to the empty neighbour found
						currentBoard.makePlaceToken( i , opponent ); // place a opponent token !!!

						boardsArray.add(new board(currentBoard));
						
						// undo previous move
						currentBoard.undoPlaceToken( i , renderer.TEAM_NOTEAM);
					}
				}
				
				break;
...
... return boardsArray; // return all generated boards.

OK , all it's good so far, the "computer" finds best moves and plays good against "human" .
--------------------------------------------------------------------------------------------------------------------------------------------------


The problem is when swithcing to phase2 -> i.e the "PlayGame" phase !
The code doesn't change EXCEPT generating "moves" when in "PlayGame" phase.
Now, generating "moves" is done like so:

public ArrayList<board> generateNextPossibleBoards(int sign)
	{
		// copy current board
		board currentBoard	 = new board(this);
	  
		// instantiate a empty array.
		ArrayList<board> boardsArray = new ArrayList<board>();
	  
		// current team is unknown.
		int team = -1;
		int opponent = -1;
		int game_status = -1;
	  
		// update current team (can be "computer" or "human" player).
		if(sign==1)
		{
			team = renderer.TEAM_OPPONENT;
			opponent = renderer.TEAM_PLAYER;
			game_status = renderer.gOpponent.gGameStatus;
		}
		else
		{
			team = renderer.TEAM_PLAYER;
			opponent = renderer.TEAM_OPPONENT;
			game_status = renderer.gPlayer.gGameStatus;
		}
	  
		// according to current player's (computer/human) game-status:
		switch(game_status)
		{
			 ....
			 ....
case renderer.GAMESTATUS_PLAYNORMAL:
  
	// 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 id
	   int id = currentBoard.gNode[i].gNeighbourId[n];
	  
	   // check if neighbour is empty spot.
	   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 PLAYNORMAL.

....
}   // end function generateNextPossibleBoards()
	

I have done a picture for you to see what happens when depth>1 and why the chosenBoard is not correctly chosen.

http://imageshack.us...0/mistaker.jpg/

step1) As you can see, token from node=3 (depth=3) generates a new "move" to node=4 (depth=2).
step2) After that negaMax() recurses itself again and the token from node=4 generates again a new move to node=7(depth=1).
step3) Similar, from node=7 a token is generated again and set to node=8 (when negaMax() recurses again).

Now token from node=8 is selected as the "chosen" best move --> and return it to main function, right ? (because we have Win or good score)
But...when moving from starting node=3 to node=8 there's a problem (because node=8 token is "far" away from token=3)
This is what i must solve, how do i return best move when depth > 1 ?



Im sorry for the long post.
I hope you accept my appologies !

#5whitenose

Posted 11 October 2012 - 12:31 PM

Hello,

I'm so sorry for the late reply. I had a car accident, all it's ok...
Thanks for all your answers !

As i said first, i'm trying to do a simple 9Men's Morris game (for Android).
This game has 3 phases: PlacingTokens, PlayGame, EndGame as you well know.

I have switched to negaMax() but the problem persists, and i think I know where/when it happens (i will explain) but dont know how to fix it. Posted Image
The problem is returning final "bestMove" to the main calling function .

Had some time today to implemeent negaMax() and i hope didn't made mistakes - and it seems that at "depth=1" when PlacingTokens phase is active -> all it's OK. (meaning that the "computer" plays good enough).
The calling code for this looks like this now for negaMax():



// as you can see "depth=1" (MAX = "computer" turn !)
case renderer.GAMESTATUS_PLACETOKEN:
  
					 //PARAMETERS:   simulationBoard, depth, alpha, beta,  sign (or color wich wil alternate between +1 or -1)
					negaMax(simulationBoard, 1,		Integer.MIN_VALUE+1, Integer.MAX_VALUE-1,   1);

My "negaMax()" function looks like this:

private int negaMax(board board, int depth, int alpha, int beta, int sign)
{
		// if depth reached or we DO have a winner on "this" board
		if(depth<=0 || board.checkWinner(sign))
		{	
			// evaluateBoard() evaluates board from "sign"'s point of view and returns a positive or negative score.
			return sign*board.evaluateBoard(sign);  
		}
		
		int max = Integer.MIN_VALUE+1; // -VERY SMALL value.
		
		// generate all available possible moves
		ArrayList<board> boardsArray = board.generateNextPossibleBoards(sign);
	
		// loop thru all generated boards
		for(board nextBoard: boardsArray)
		{
			// recurse and store result to "x" .
			int x = -negaMax(nextBoard, depth-1, -beta, -alpha,  -sign); // sign alterantes between +1 & -1 (computer & human)
			
			// got a "better/best" move ?
			if (x>max)
			{
				// save the "best" move so far.
				max = x;
				chosenBoard = nextBoard;
				chosenBoard.showBoard("FOUND BEST MOVE");
			}
			
			// alpha-beta pruning
			if (x>alpha) alpha = x;
			if (alpha>=beta) return alpha;
		}

		// clear boards when done.
		boardsArray.clear();
		
		// return best move so far.
		return max;
	}


allright, and now the checkWinner(sign) method (wich returns true or false if a team is Winning)

public boolean checkWinner(int sign)
{
  board board = this;

  // ---------------------------------------------------------------------------------
  // 0. get current team
  // ---------------------------------------------------------------------------------
  int team = renderer.TEAM_NOTEAM;
  int opponent = renderer.TEAM_NOTEAM;

  if(sign==1)
  {
   // if "computer" turn
   team = renderer.TEAM_OPPONENT;
   opponent = renderer.TEAM_PLAYER;
  }
  else
  {
   // if "human" turn
   team = renderer.TEAM_PLAYER;
   opponent = renderer.TEAM_OPPONENT;
  }


  // ---------------------------------------------------------------------------------
  // 1. check if only 2 tokens (from opponent team!) are left  on current board.
  // ---------------------------------------------------------------------------------
  int counter = 0;

  for(short i=0;i<24;i++)
  {
   if(board.gNode[i].gOccupiedByTeam!=renderer.TEAM_NOTEAM && board.gNode[i].gOccupiedByTeam==opponent) counter++; // count opponent tokens
  }

  switch(team)
  {
   case renderer.TEAM_OPPONENT:
	if(counter<=2 && renderer.gPlayer.gTokensToPlaceOnTable==0)
	{
	 return true;  // opponent has won.
	}
	break;
   case renderer.TEAM_PLAYER:
	if(counter<=2 && renderer.gOpponent.gTokensToPlaceOnTable==0)
	{
	 return true; // player has won.
	}
	break;
  }


  // ---------------------------------------------------------------------------------
  // 2. all opponent tokens are blocked! (no more possible moves, all tokens are blocked)
  // ---------------------------------------------------------------------------------
  for(short i=0;i<24;i++)
  {
   // go thru all tokens in this board, if opponent is not blocked -> return false.
   if(board.gNode[i].gOccupiedByTeam==opponent)
   {
	// check if any empty neighbours for this token
	for(short n=0;n<4;n++)
	{
	 // get neighborur id
	 int id = board.gNode[i].gNeighbourId[n];
	
	 // check if neighbour is empty space.
	 if(id!=-1 && board.gNode[id].gOccupiedByTeam==renderer.TEAM_NOTEAM)
	 {
	  // still having empty spaces to move. (NOT BLOCKED!)
	  return false;
	 }
	}
   }
  }

  // opponent is BLOCKED! so this team is winning -> return true!
  return true;
}


and this is the evaluateBoard(sign) function wich evaluates current board from --> "sign" ("computer" or "human") point of view :


  ]// evaluate current board.
	public int evaluateBoard(int sign)
	{
		int score 		= 0;
		int formers 	= checkFormers(sign);	// if 2 tokens on same row/column has been found, then a former has been found.
		int blockers 	= checkBlockers(sign);	// if 1 token blocks a token form other team, then we have a blocker.  
		int mills 		= checkMills(sign);		// if a mill has been formed (3 tokens in a row/column), then we have a mill.
		int tkcount 	= checkTokenCount(sign);// count token (team - opponent) difference on this board.
		
		score = score + formers*250;			// multiplier is 10 here for the "formers"
		score = score + blockers*500;			// multiplier is 500 here for the "blockers"
		score = score + mills*1000;				// etc.
		score = score + tkcount*10;

		if(sign==1) // is it "computer" turn?
		{
			return -score; 	// return score for "computer"
		}
		else
		{
			return +score;	// return score for "human"
		}
		
	}



OK, now generating boards in 1st phase (PlacingTokens) is done like so:

public ArrayList<board> generateNextPossibleBoards(int sign)
	{
		// copy current board
		board currentBoard 	= new board(this);
		
		// instantiate a empty array.
		ArrayList<board> boardsArray = new ArrayList<board>();
		
		// current team is unknown.
		int team = -1;
		int opponent = -1;
		int game_status = -1;
		
		// update current team (can be "computer" or "human" player).
		if(sign==1)
		{
			team = renderer.TEAM_OPPONENT;
			opponent = renderer.TEAM_PLAYER;
			game_status = renderer.gOpponent.gGameStatus;
		}
		else
		{
			team = renderer.TEAM_PLAYER;
			opponent = renderer.TEAM_OPPONENT;
			game_status = renderer.gPlayer.gGameStatus;
		}
		
		// according to current player's (computer/human) game-status:
		switch(game_status)
		{	
			case renderer.GAMESTATUS_PLACETOKEN:
				// simulate a single place token (on this board) and save this new board to boardsArray.
				for(short i=0;i<24;i++)
				{
					// go thru all empty spaces on this board , and if not occupied by any token
					if(currentBoard.gNode[i].gOccupiedByTeam==renderer.TEAM_NOTEAM)
					{
						// place (a opponent) token to the empty neighbour found
						currentBoard.makePlaceToken( i , opponent ); // place a opponent token !!!

						boardsArray.add(new board(currentBoard));
						
						// undo previous move
						currentBoard.undoPlaceToken( i , renderer.TEAM_NOTEAM);
					}
				}
				
				break;
...
...

OK , all it's good so far, the "computer" finds best moves and plays good against "human" .
--------------------------------------------------------------------------------------------------------------------------------------------------


The problem is when swithcing to phase2 -> i.e the "PlayGame" phase !
The code doesn't change EXCEPT generating "moves" when in "PlayGame" phase.
Now, generating "moves" is done like so:

public ArrayList<board> generateNextPossibleBoards(int sign)
	{
		// copy current board
		board currentBoard	 = new board(this);
	  
		// instantiate a empty array.
		ArrayList<board> boardsArray = new ArrayList<board>();
	  
		// current team is unknown.
		int team = -1;
		int opponent = -1;
		int game_status = -1;
	  
		// update current team (can be "computer" or "human" player).
		if(sign==1)
		{
			team = renderer.TEAM_OPPONENT;
			opponent = renderer.TEAM_PLAYER;
			game_status = renderer.gOpponent.gGameStatus;
		}
		else
		{
			team = renderer.TEAM_PLAYER;
			opponent = renderer.TEAM_OPPONENT;
			game_status = renderer.gPlayer.gGameStatus;
		}
	  
		// according to current player's (computer/human) game-status:
		switch(game_status)
		{
			 ....
			 ....
case renderer.GAMESTATUS_PLAYNORMAL:
  
	// 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 id
	   int id = currentBoard.gNode[i].gNeighbourId[n];
	  
	   // check if neighbour is empty spot.
	   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 PLAYNORMAL.

....
}   // end function generateNextPossibleBoards()
	

I have done a picture for you to see what happens when depth>1 and why the chosenBoard is not correctly chosen.

http://imageshack.us...0/mistaker.jpg/

step1) As you can see, token from node=3 (depth=3) generates a new "move" to node=4 (depth=2).
step2) After that negaMax() recurses itself again and the token from node=4 generates again a new move to node=7(depth=1).
step3) Similar, from node=7 a token is generated again and set to node=8 (when negaMax() recurses again).

Now token from node=8 is selected as the "chosen" best move --> and return it to main function, right ? (because we have Win or good score)
But...when moving from starting node=3 to node=8 there's a problem (because node=8 token is "far" away from token=3)
This is what i must solve, how do i return best move when depth > 1 ?



Im sorry for the long post.
I hope you accept my appologies !

#4whitenose

Posted 11 October 2012 - 12:30 PM

Hello,

I'm so sorry for the late reply. I had a car accident, all it's ok...
Thanks for all your answers !

As i said first, i'm trying to do a simple 9Men's Morris game (for Android).
This game has 3 phases: PlacingTokens, PlayGame, EndGame as you well know.

I have switched to negaMax() but the problem persists, and i think I know where/when it happens (i will explain) but dont know how to fix it. Posted Image
The problem is returning final "bestMove" to the main calling function .

Had some time today to implemeent negaMax() and i hope didn't made mistakes - and it seems that at "depth=1" when PlacingTokens phase is active -> all it's OK. (meaning that the "computer" plays good enough).
The calling code for this looks like this now for negaMax():



// as you can see "depth=1" (MAX = "computer" turn !)
case renderer.GAMESTATUS_PLACETOKEN:
  
					 //PARAMETERS:   simulationBoard, depth, alpha, beta,  sign (or color wich wil alternate between +1 or -1)
					negaMax(simulationBoard, 1,		Integer.MIN_VALUE+1, Integer.MAX_VALUE-1,   1);

My "negaMax()" function looks like this:

private int negaMax(board board, int depth, int alpha, int beta, int sign)
{
		// if depth reached or we DO have a winner on "this" board
		if(depth<=0 || board.checkWinner(sign))
		{	
			// evaluateBoard() evaluates board from "sign"'s point of view and returns a positive or negative score.
			return sign*board.evaluateBoard(sign);  
		}
		
		int max = Integer.MIN_VALUE+1; // -VERY SMALL value.
		
		// generate all available possible moves
		ArrayList<board> boardsArray = board.generateNextPossibleBoards(sign);
	
		// loop thru all generated boards
		for(board nextBoard: boardsArray)
		{
			// recurse and store result to "x" .
			int x = -negaMax(nextBoard, depth-1, -beta, -alpha,  -sign); // sign alterantes between +1 & -1 (computer & human)
			
			// got a "better/best" move ?
			if (x>max)
			{
				// save the "best" move so far.
				max = x;
				chosenBoard = nextBoard;
				chosenBoard.showBoard("FOUND BEST MOVE");
			}
			
			// alpha-beta pruning
			if (x>alpha) alpha = x;
			if (alpha>=beta) return alpha;
		}

		// clear boards when done.
		boardsArray.clear();
		
		// return best move so far.
		return max;
	}


allright, and now the checkWinner(sign) method (wich returns true or false if a team is Winning)

public boolean checkWinner(int sign)
{
  board board = this;

  // ---------------------------------------------------------------------------------
  // 0. get current team
  // ---------------------------------------------------------------------------------
  int team = renderer.TEAM_NOTEAM;
  int opponent = renderer.TEAM_NOTEAM;

  if(sign==1)
  {
   // if "computer" turn
   team = renderer.TEAM_OPPONENT;
   opponent = renderer.TEAM_PLAYER;
  }
  else
  {
   // if "human" turn
   team = renderer.TEAM_PLAYER;
   opponent = renderer.TEAM_OPPONENT;
  }


  // ---------------------------------------------------------------------------------
  // 1. check if only 2 tokens (from opponent team!) are left  on current board.
  // ---------------------------------------------------------------------------------
  int counter = 0;

  for(short i=0;i<24;i++)
  {
   if(board.gNode[i].gOccupiedByTeam!=renderer.TEAM_NOTEAM && board.gNode[i].gOccupiedByTeam==opponent) counter++; // count opponent tokens
  }

  switch(team)
  {
   case renderer.TEAM_OPPONENT:
	if(counter<=2 && renderer.gPlayer.gTokensToPlaceOnTable==0)
	{
	 return true;  // opponent has won.
	}
	break;
   case renderer.TEAM_PLAYER:
	if(counter<=2 && renderer.gOpponent.gTokensToPlaceOnTable==0)
	{
	 return true; // player has won.
	}
	break;
  }


  // ---------------------------------------------------------------------------------
  // 2. all opponent tokens are blocked! (no more possible moves, all tokens are blocked)
  // ---------------------------------------------------------------------------------
  for(short i=0;i<24;i++)
  {
   // go thru all tokens in this board, if opponent is not blocked -> return false.
   if(board.gNode[i].gOccupiedByTeam==opponent)
   {
	// check if any empty neighbours for this token
	for(short n=0;n<4;n++)
	{
	 // get neighborur id
	 int id = board.gNode[i].gNeighbourId[n];
	
	 // check if neighbour is empty space.
	 if(id!=-1 && board.gNode[id].gOccupiedByTeam==renderer.TEAM_NOTEAM)
	 {
	  // still having empty spaces to move. (NOT BLOCKED!)
	  return false;
	 }
	}
   }
  }

  // opponent is BLOCKED! so this team is winning -> return true!
  return true;
}


and this is the evaluateBoard(sign) function wich evaluates current board from --> "sign" ("computer" or "human") point of view :


  ]// evaluate current board.
	public int evaluateBoard(int sign)
	{
		int score 		= 0;
		int formers 	= checkFormers(sign);	// if 2 tokens on same row/column has been found, then a former has been found.
		int blockers 	= checkBlockers(sign);	// if 1 token blocks a token form other team, then we have a blocker.  
		int mills 		= checkMills(sign);		// if a mill has been formed (3 tokens in a row/column), then we have a mill.
		int tkcount 	= checkTokenCount(sign);// count token (team - opponent) difference on this board.
		
		score = score + formers*250;			// multiplier is 10 here for the "formers"
		score = score + blockers*500;			// multiplier is 500 here for the "blockers"
		score = score + mills*1000;				// etc.
		score = score + tkcount*10;

		if(sign==1) // is it "computer" turn?
		{
			return -score; 	// return score for "computer"
		}
		else
		{
			return +score;	// return score for "human"
		}
		
	}



OK, now generating boards in 1st phase (PlacingTokens) is done like so:

public ArrayList<board> generateNextPossibleBoards(int sign)
	{
		// copy current board
		board currentBoard 	= new board(this);
		
		// instantiate a empty array.
		ArrayList<board> boardsArray = new ArrayList<board>();
		
		// current team is unknown.
		int team = -1;
		int opponent = -1;
		int game_status = -1;
		
		// update current team (can be "computer" or "human" player).
		if(sign==1)
		{
			team = renderer.TEAM_OPPONENT;
			opponent = renderer.TEAM_PLAYER;
			game_status = renderer.gOpponent.gGameStatus;
		}
		else
		{
			team = renderer.TEAM_PLAYER;
			opponent = renderer.TEAM_OPPONENT;
			game_status = renderer.gPlayer.gGameStatus;
		}
		
		// according to current player's (computer/human) game-status:
		switch(game_status)
		{	
			case renderer.GAMESTATUS_PLACETOKEN:
				// simulate a single place token (on this board) and save this new board to boardsArray.
				for(short i=0;i<24;i++)
				{
					// go thru all empty spaces on this board , and if not occupied by any token
					if(currentBoard.gNode[i].gOccupiedByTeam==renderer.TEAM_NOTEAM)
					{
						// place (a opponent) token to the empty neighbour found
						currentBoard.makePlaceToken( i , opponent ); // place a opponent token !!!

						boardsArray.add(new board(currentBoard));
						
						// undo previous move
						currentBoard.undoPlaceToken( i , renderer.TEAM_NOTEAM);
					}
				}
				
				break;
...
...

OK , all it's good so far, the "computer" finds best moves and plays good against "human" .
--------------------------------------------------------------------------------------------------------------------------------------------------


The problem is when swithcing to phase2 -> i.e the "PlayGame" phase !
So, the code doesn't chagne EXCEPT generating "moves" when in "PlayGame" phase.
Now, generating "moves" is done like so:

public ArrayList<board> generateNextPossibleBoards(int sign)
	{
		// copy current board
		board currentBoard	 = new board(this);
	  
		// instantiate a empty array.
		ArrayList<board> boardsArray = new ArrayList<board>();
	  
		// current team is unknown.
		int team = -1;
		int opponent = -1;
		int game_status = -1;
	  
		// update current team (can be "computer" or "human" player).
		if(sign==1)
		{
			team = renderer.TEAM_OPPONENT;
			opponent = renderer.TEAM_PLAYER;
			game_status = renderer.gOpponent.gGameStatus;
		}
		else
		{
			team = renderer.TEAM_PLAYER;
			opponent = renderer.TEAM_OPPONENT;
			game_status = renderer.gPlayer.gGameStatus;
		}
	  
		// according to current player's (computer/human) game-status:
		switch(game_status)
		{
			 ....
			 ....
case renderer.GAMESTATUS_PLAYNORMAL:
  
	// 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 id
	   int id = currentBoard.gNode[i].gNeighbourId[n];
	  
	   // check if neighbour is empty spot.
	   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 PLAYNORMAL.

....
}   // end function generateNextPossibleBoards()
	

I have done a picture for you to see what happens when depth>1 and why the chosenBoard is not correctly chosen.

http://imageshack.us...0/mistaker.jpg/

step1) As you can see, token from node=3 (depth=3) generates a new "move" to node=4 (depth=2).
step2) After that negaMax() recurses itself again and the token from node=4 generates again a new move to node=7(depth=1).
step3) Similar, from node=7 a token is generated again and set to node=8 (when negaMax() recurses again).

Now token from node=8 is selected as the "chosen" best move --> and return it to main function, right ? (because we have Win or good score)
But...when moving from starting node=3 to node=8 there's a problem (because node=8 token is "far" away from token=3)
This is what i must solve, how do i return best move when depth > 1 ?



Im sorry for the long post.
I hope you accept my appologies !

#3whitenose

Posted 11 October 2012 - 12:28 PM

Hello,

I'm so sorry for the late reply. I had a car accident, all it's ok...
Thanks for all your answers !

As i said first, i'm trying to do a simple 9Men's Morris game (for Android).
This game has 3 phases: PlacingTokens, PlayGame, EndGame as you well know.

I have switched to negaMax() but the problem persists, and i think I know where/when it happens (i will explain) but dont know how to fix it. Posted Image
The problem is returning final "bestMove" to the main calling function .

Had some time today to implemeent negaMax() and i hope didn't made mistakes - and it seems that at "depth=1" when PlacingTokens phase is active -> all it's OK. (meaning that the "computer" plays good enough).
The calling code for this looks like this now for negaMax():



// as you can see "depth=1" (MAX = "computer" turn !)
case renderer.GAMESTATUS_PLACETOKEN:
  
					 //PARAMETERS:   simulationBoard, depth, alpha, beta,  sign (or color wich wil alternate between +1 or -1)
					negaMax(simulationBoard, 1,		Integer.MIN_VALUE+1, Integer.MAX_VALUE-1,   1);

My "negaMax()" function looks like this:

private int negaMax(board board, int depth, int alpha, int beta, int sign)
{
		// if depth reached or we DO have a winner on "this" board
		if(depth<=0 || board.checkWinner(sign))
		{	
			// evaluateBoard() evaluates board from "sign"'s point of view and returns a positive or negative score.
			return sign*board.evaluateBoard(sign);  
		}
		
		int max = Integer.MIN_VALUE+1; // -VERY SMALL value.
		
		// generate all available possible moves
		ArrayList<board> boardsArray = board.generateNextPossibleBoards(sign);
	
		// loop thru all generated boards
		for(board nextBoard: boardsArray)
		{
			// recurse and store result to "x" .
			int x = -negaMax(nextBoard, depth-1, -beta, -alpha,  -sign); // sign alterantes between +1 & -1 (computer & human)
			
			// got a "better/best" move ?
			if (x>max)
			{
				// save the "best" move so far.
				max = x;
				chosenBoard = nextBoard;
				chosenBoard.showBoard("FOUND BEST MOVE");
			}
			
			// alpha-beta pruning
			if (x>alpha) alpha = x;
			if (alpha>=beta) return alpha;
		}

		// clear boards when done.
		boardsArray.clear();
		
		// return best move so far.
		return max;
	}


allright, and now the checkWinner(sign) method (wich returns true or false if a team is Winning)

public boolean checkWinner(int sign)
{
  board board = this;

  // ---------------------------------------------------------------------------------
  // 0. get current team
  // ---------------------------------------------------------------------------------
  int team = renderer.TEAM_NOTEAM;
  int opponent = renderer.TEAM_NOTEAM;

  if(sign==1)
  {
   // if "computer" turn
   team = renderer.TEAM_OPPONENT;
   opponent = renderer.TEAM_PLAYER;
  }
  else
  {
   // if "human" turn
   team = renderer.TEAM_PLAYER;
   opponent = renderer.TEAM_OPPONENT;
  }


  // ---------------------------------------------------------------------------------
  // 1. check if only 2 tokens (from opponent team!) are left  on current board.
  // ---------------------------------------------------------------------------------
  int counter = 0;

  for(short i=0;i<24;i++)
  {
   if(board.gNode[i].gOccupiedByTeam!=renderer.TEAM_NOTEAM && board.gNode[i].gOccupiedByTeam==opponent) counter++; // count opponent tokens
  }

  switch(team)
  {
   case renderer.TEAM_OPPONENT:
	if(counter<=2 && renderer.gPlayer.gTokensToPlaceOnTable==0)
	{
	 return true;  // opponent has won.
	}
	break;
   case renderer.TEAM_PLAYER:
	if(counter<=2 && renderer.gOpponent.gTokensToPlaceOnTable==0)
	{
	 return true; // player has won.
	}
	break;
  }


  // ---------------------------------------------------------------------------------
  // 2. all opponent tokens are blocked! (no more possible moves, all tokens are blocked)
  // ---------------------------------------------------------------------------------
  for(short i=0;i<24;i++)
  {
   // go thru all tokens in this board, if opponent is not blocked -> return false.
   if(board.gNode[i].gOccupiedByTeam==opponent)
   {
	// check if any empty neighbours for this token
	for(short n=0;n<4;n++)
	{
	 // get neighborur id
	 int id = board.gNode[i].gNeighbourId[n];
	
	 // check if neighbour is empty space.
	 if(id!=-1 && board.gNode[id].gOccupiedByTeam==renderer.TEAM_NOTEAM)
	 {
	  // still having empty spaces to move. (NOT BLOCKED!)
	  return false;
	 }
	}
   }
  }

  // opponent is BLOCKED! so this team is winning -> return true!
  return true;
}


and this is the evaluateBoard(sign) function wich evaluates current board from --> "sign" ("computer" or "human") point of view :


  ]// evaluate current board.
	public int evaluateBoard(int sign)
	{
		int score 		= 0;
		int formers 	= checkFormers(sign);	// if 2 tokens on same row/column has been found, then a former has been found.
		int blockers 	= checkBlockers(sign);	// if 1 token blocks a token form other team, then we have a blocker.  
		int mills 		= checkMills(sign);		// if a mill has been formed (3 tokens in a row/column), then we have a mill.
		int tkcount 	= checkTokenCount(sign);// count token (team - opponent) difference on this board.
		
		score = score + formers*250;			// multiplier is 10 here for the "formers"
		score = score + blockers*500;			// multiplier is 500 here for the "blockers"
		score = score + mills*1000;				// etc.
		score = score + tkcount*10;

		if(sign==1) // is it "computer" turn?
		{
			return -score; 	// return score for "computer"
		}
		else
		{
			return +score;	// return score for "human"
		}
		
	}



OK, now generating boards in 1st phase (PlacingTokens) is done like so:

public ArrayList<board> generateNextPossibleBoards(int sign)
	{
		// copy current board
		board currentBoard 	= new board(this);
		
		// instantiate a empty array.
		ArrayList<board> boardsArray = new ArrayList<board>();
		
		// current team is unknown.
		int team = -1;
		int opponent = -1;
		int game_status = -1;
		
		// update current team (can be "computer" or "human" player).
		if(sign==1)
		{
			team = renderer.TEAM_OPPONENT;
			opponent = renderer.TEAM_PLAYER;
			game_status = renderer.gOpponent.gGameStatus;
		}
		else
		{
			team = renderer.TEAM_PLAYER;
			opponent = renderer.TEAM_OPPONENT;
			game_status = renderer.gPlayer.gGameStatus;
		}
		
		// according to current player's (computer/human) game-status:
		switch(game_status)
		{	
			case renderer.GAMESTATUS_PLACETOKEN:
				// simulate a single place token (on this board) and save this new board to boardsArray.
				for(short i=0;i<24;i++)
				{
					// go thru all empty spaces on this board , and if not occupied by any token
					if(currentBoard.gNode[i].gOccupiedByTeam==renderer.TEAM_NOTEAM)
					{
						// place (a opponent) token to the empty neighbour found above
						currentBoard.makePlaceToken( i , opponent ); // place a opponent token !!!

						boardsArray.add(new board(currentBoard));
						
						// undo previous move
						currentBoard.undoPlaceToken( i , renderer.TEAM_NOTEAM);
					}
				}
				
				break;
...
...

OK , all it's good so far, the "computer" finds best moves and plays good against "human" .
--------------------------------------------------------------------------------------------------------------------------------------------------


The problem is when swithcing to phase2 -> i.e the "PlayGame" phase !
So, the code doesn't chagne EXCEPT generating "moves" when in "PlayGame" phase.
Now, generating "moves" is done like so:

public ArrayList<board> generateNextPossibleBoards(int sign)
	{
		// copy current board
		board currentBoard	 = new board(this);
	  
		// instantiate a empty array.
		ArrayList<board> boardsArray = new ArrayList<board>();
	  
		// current team is unknown.
		int team = -1;
		int opponent = -1;
		int game_status = -1;
	  
		// update current team (can be "computer" or "human" player).
		if(sign==1)
		{
			team = renderer.TEAM_OPPONENT;
			opponent = renderer.TEAM_PLAYER;
			game_status = renderer.gOpponent.gGameStatus;
		}
		else
		{
			team = renderer.TEAM_PLAYER;
			opponent = renderer.TEAM_OPPONENT;
			game_status = renderer.gPlayer.gGameStatus;
		}
	  
		// according to current player's (computer/human) game-status:
		switch(game_status)
		{
			 ....
			 ....
case renderer.GAMESTATUS_PLAYNORMAL:
  
	// 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 id
	   int id = currentBoard.gNode[i].gNeighbourId[n];
	  
	   // check if neighbour is empty spot.
	   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 PLAYNORMAL.

....
}   // end function generateNextPossibleBoards()
	

I have done a picture for you to see what happens when depth>1 and why the chosenBoard is not correctly chosen.

http://imageshack.us...0/mistaker.jpg/

step1) As you can see, token from node=3 (depth=3) generates a new "move" to node=4 (depth=2).
step2) After that negaMax() recurses itself again and the token from node=4 generates again a new move to node=7(depth=1).
step3) Similar, from node=7 a token is generated again and set to node=8 (when negaMax() recurses again).

Now token from node=8 is selected as the "chosen" best move --> and return it to main function, right ? (because we have Win or good score)
But...when moving from starting node=3 to node=8 there's a problem (because node=8 token is "far" away from token=3)
This is what i must solve, how do i return best move when depth > 1 ?



Im sorry for the long post.
I hope you accept my appologies !

#2whitenose

Posted 11 October 2012 - 12:26 PM

Hello,

I'm so sorry for the late reply. I had a car accident, all it's ok...
Thanks for all your answers !

As i said first, i'm trying to do a simple 9Men's Morris game (for Android).
This game has 3 phases: PlacingTokens, PlayGame, EndGame as you well know.

I have switched to negaMax() but the problem persists, and i think I know where/when it happens (i will explain) but dont know how to fix it. Posted Image
The problem is returning final "bestMove" to the main calling function .

Had some time today to implemeent negaMax() and i hope didn't made mistakes - and it seems that at "depth=1" when PlacingTokens phase is active -> all it's OK. (meaning that the "computer" plays good enough).
The calling code for this looks like this now for negaMax():



// as you can see "depth=1" (MAX = "computer" turn !)
case renderer.GAMESTATUS_PLACETOKEN:
  
					 //PARAMETERS:   simulationBoard, depth, alpha, beta,  sign (or color wich wil alternate between +1 or -1)
					negaMax(simulationBoard, 1,		Integer.MIN_VALUE+1, Integer.MAX_VALUE-1,   1);

My "negaMax()" function looks like this:

private int negaMax(board board, int depth, int alpha, int beta, int sign)
{
		// if depth reached or we DO have a winner on "this" board
		if(depth<=0 || board.checkWinner(sign))
		{	
			// evaluateBoard() evaluates board from "sign"'s point of view and returns a positive or negative score.
			return sign*board.evaluateBoard(sign);  
		}
		
		int max = Integer.MIN_VALUE+1; // -VERY SMALL value.
		
		// generate all available possible moves
		ArrayList<board> boardsArray = board.generateNextPossibleBoards(sign);
	
		// loop thru all generated boards
		for(board nextBoard: boardsArray)
		{
			// recurse and store result to "x" .
			int x = -negaMax(nextBoard, depth-1, -beta, -alpha,  -sign); // sign alterantes between -1 & +1 (computer & human)
			
			// got a "better/best" move ?
			if (x>max)
			{
				// save the "best" move so far.
				max = x;
				chosenBoard = nextBoard;
				chosenBoard.showBoard("FOUND BEST MOVE");
			}
			
			// alpha-beta pruning
			if (x>alpha) alpha = x;
			if (alpha>=beta) return alpha;
		}

		// clear boards when done.
		boardsArray.clear();
		
		// return best move so far.
		return max;
	}


allright, and now the checkWinner(sign) method (wich returns true or false if a team is Winning)

public boolean checkWinner(int sign)
{
  board board = this;

  // ---------------------------------------------------------------------------------
  // 0. get current team
  // ---------------------------------------------------------------------------------
  int team = renderer.TEAM_NOTEAM;
  int opponent = renderer.TEAM_NOTEAM;

  if(sign==1)
  {
   // if "computer" turn
   team = renderer.TEAM_OPPONENT;
   opponent = renderer.TEAM_PLAYER;
  }
  else
  {
   // if "human" turn
   team = renderer.TEAM_PLAYER;
   opponent = renderer.TEAM_OPPONENT;
  }


  // ---------------------------------------------------------------------------------
  // 1. check if only 2 tokens (from opponent team!) are left  on current board.
  // ---------------------------------------------------------------------------------
  int counter = 0;

  for(short i=0;i<24;i++)
  {
   if(board.gNode[i].gOccupiedByTeam!=renderer.TEAM_NOTEAM && board.gNode[i].gOccupiedByTeam==opponent) counter++; // count opponent tokens
  }

  switch(team)
  {
   case renderer.TEAM_OPPONENT:
	if(counter<=2 && renderer.gPlayer.gTokensToPlaceOnTable==0)
	{
	 return true;  // opponent has won.
	}
	break;
   case renderer.TEAM_PLAYER:
	if(counter<=2 && renderer.gOpponent.gTokensToPlaceOnTable==0)
	{
	 return true; // player has won.
	}
	break;
  }


  // ---------------------------------------------------------------------------------
  // 2. all opponent tokens are blocked! (no more possible moves, all tokens are blocked)
  // ---------------------------------------------------------------------------------
  for(short i=0;i<24;i++)
  {
   // go thru all tokens in this board, if opponent is not blocked -> return false.
   if(board.gNode[i].gOccupiedByTeam==opponent)
   {
	// check if any empty neighbours for this token
	for(short n=0;n<4;n++)
	{
	 // get neighborur id
	 int id = board.gNode[i].gNeighbourId[n];
	
	 // check if neighbour is empty space.
	 if(id!=-1 && board.gNode[id].gOccupiedByTeam==renderer.TEAM_NOTEAM)
	 {
	  // still having empty spaces to move. (NOT BLOCKED!)
	  return false;
	 }
	}
   }
  }

  // opponent is BLOCKED! so this team is winning -> return true!
  return true;
}


and this is the evaluateBoard(sign) function wich evaluates current board from --> "sign" ("computer" or "human") point of view :


  ]// evaluate current board.
	public int evaluateBoard(int sign)
	{
		int score 		= 0;
		int formers 	= checkFormers(sign);	// if 2 tokens on same row/column has been found, then a former has been found.
		int blockers 	= checkBlockers(sign);	// if 1 token blocks a token form other team, then we have a blocker.  
		int mills 		= checkMills(sign);		// if a mill has been formed (3 tokens in a row/column), then we have a mill.
		int tkcount 	= checkTokenCount(sign);// count token (team - opponent) difference on this board.
		
		score = score + formers*250;			// multiplier is 10 here for the "formers"
		score = score + blockers*500;			// multiplier is 500 here for the "blockers"
		score = score + mills*1000;				// etc.
		score = score + tkcount*10;

		if(sign==1) // is it "computer" turn?
		{
			return -score; 	// return score for "computer"
		}
		else
		{
			return +score;	// return score for "human"
		}
		
	}



OK, now generating boards in 1st phase (PlacingTokens) is done like so:

public ArrayList<board> generateNextPossibleBoards(int sign)
	{
		// copy current board
		board currentBoard 	= new board(this);
		
		// instantiate a empty array.
		ArrayList<board> boardsArray = new ArrayList<board>();
		
		// current team is unknown.
		int team = -1;
		int opponent = -1;
		int game_status = -1;
		
		// update current team (can be "computer" or "human" player).
		if(sign==1)
		{
			team = renderer.TEAM_OPPONENT;
			opponent = renderer.TEAM_PLAYER;
			game_status = renderer.gOpponent.gGameStatus;
		}
		else
		{
			team = renderer.TEAM_PLAYER;
			opponent = renderer.TEAM_OPPONENT;
			game_status = renderer.gPlayer.gGameStatus;
		}
		
		// according to current player's (computer/human) game-status:
		switch(game_status)
		{	
			case renderer.GAMESTATUS_PLACETOKEN:
				// simulate a single place token (on this board) and save this new board to boardsArray.
				for(short i=0;i<24;i++)
				{
					// go thru all empty spaces on this board , and if not occupied by any token
					if(currentBoard.gNode[i].gOccupiedByTeam==renderer.TEAM_NOTEAM)
					{
						// place (a opponent) token to the empty neighbour found above
						currentBoard.makePlaceToken( i , opponent ); // place a opponent token !!!

						boardsArray.add(new board(currentBoard));
						
						// undo previous move
						currentBoard.undoPlaceToken( i , renderer.TEAM_NOTEAM);
					}
				}
				
				break;
...
...

OK , all it's good so far, the "computer" finds best moves and plays good against "human" .
--------------------------------------------------------------------------------------------------------------------------------------------------


The problem is when swithcing to phase2 -> i.e the "PlayGame" phase !
So, the code doesn't chagne EXCEPT generating "moves" when in "PlayGame" phase.
Now, generating "moves" is done like so:

public ArrayList<board> generateNextPossibleBoards(int sign)
	{
		// copy current board
		board currentBoard	 = new board(this);
	  
		// instantiate a empty array.
		ArrayList<board> boardsArray = new ArrayList<board>();
	  
		// current team is unknown.
		int team = -1;
		int opponent = -1;
		int game_status = -1;
	  
		// update current team (can be "computer" or "human" player).
		if(sign==1)
		{
			team = renderer.TEAM_OPPONENT;
			opponent = renderer.TEAM_PLAYER;
			game_status = renderer.gOpponent.gGameStatus;
		}
		else
		{
			team = renderer.TEAM_PLAYER;
			opponent = renderer.TEAM_OPPONENT;
			game_status = renderer.gPlayer.gGameStatus;
		}
	  
		// according to current player's (computer/human) game-status:
		switch(game_status)
		{
			 ....
			 ....
case renderer.GAMESTATUS_PLAYNORMAL:
  
	// 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 id
	   int id = currentBoard.gNode[i].gNeighbourId[n];
	  
	   // check if neighbour is empty spot.
	   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 PLAYNORMAL.

....
}   // end function generateNextPossibleBoards()
	

I have done a picture for you to see what happens when depth>1 and why the chosenBoard is not correctly chosen.

http://imageshack.us...0/mistaker.jpg/

step1) As you can see, token from node=3 (depth=3) generates a new "move" to node=4 (depth=2).
step2) After that negaMax() recurses itself again and the token from node=4 generates again a new move to node=7(depth=1).
step3) Similar, from node=7 a token is generated again and set to node=8 (when negaMax() recurses again).

Now token from node=8 is selected as the "chosen" best move --> and return it to main function, right ? (because we have Win or good score)
But...when moving from starting node=3 to node=8 there's a problem (because node=8 token is "far" away from token=3)
This is what i must solve, how do i return best move when depth > 1 ?



Im sorry for the long post.
I hope you accept my appologies !

PARTNERS