AI search and Java

Newbie & Debugging Questions
#1

Hi all,

I’m writing a board game and currently implementing the AI using the standard Negamax. This algorithm calls itself recursively.

To speed up things I implemented a makemove/undomove within the function and I don’t pass the board object as a parameter to itself. However, due to the nature of Java not passing objects by reference, the changes to the board state when going deeper into the recursion are also reflected into the upper levels.

When I just copy the board state every time, the function works fine because each recursion works on a new copy based on a copy of one level above it. In this case I do have to pass the board state copy as a parameter and this copy copied immediately.

This has serious issues because as I hit a depth of 6 the search slows down considerably. So I’d rather have the move/undo functionality to speed up things.

So my question is: Is it possible in Java, and if yes, how? Or am I restricted to copying the board each and every time with serious performance issues?

Thanks,
C

#2

[quote]To speed up things I implemented a makemove/undomove within the function
[/quote]
This will work fine, so long as you are doing depth-first search (which you are, because of the recursive calls).

[quote]due to the nature of Java not passing objects by reference
[/quote]
Typo? You mean Java always passes by reference. So no new copy of an object is made by default.

[quote]and I don’t pass the board object as a parameter to itself
[/quote]
This is a little confusing. Does it mean that the search function is within the board class itself? Or that a single static board object exists?

Regardless, I’d have player objects decide their own moves and have any search functions in their classes. These methods should pass a board around as a parameter.

All you need to do is put your move and undo-move before and after each recursive call, as in (pseudocode):


double search(Board board, int depth)
  if( depth=0 )
    return heuristic(board)
  else
     maxValue = 0
     for each move in children(board)
       move.makemove(board)
       maxValue = max(maxValue,search(board,depth-1)
       move.undomove(board)
     return maxValue
#3

Your pseudocode snippet is similar to my function. I’m passing the board as one of the parameters and make/unmake the same way.

My make function does:

  1. place new piece on the board
  2. increment new pieces for current player
  3. switch players (opponent is now the current player)

My unmake function does:

  1. remove new piece from the board
  2. decrement new pieces for current player
  3. switch players

However, after a few plies into the search the number of new pieces for each player are way off (eg. 22, -18, etc)

So what could be wrong?

#4

What you’re doing sounds right to me so it’s probably just a bug.

Are there any other side effects on the board from adding a piece, like removing opponents pieces, that the undo might get wrong? Is the move being used for move/undo being modified at all during the search?

#5

It’s only the piece counters that aren’t updated property because the same board is used in the recursion. Placing/undoing a cell position works because it gets the information from the move itself, which btw… doesn’t change between and make/unmake.