Does the object you pass to recursive functions have its own container of moves? Because you may be continually adding moves to the same object rather than making a copy of the object which would break the recusrion. You need to pass copies of objects to recursive functions, not references. I'd check that first... in the debugger, as Al says.

Does the object you pass to recursive functions have its own container of moves? Because you may be continually adding moves to the same object rather than making a copy of the object which would break the recusrion. You need to pass copies of objects to recursive functions, not references. I'd check that first... in the debugger, as Al says.

Passing the board by reference and making and undoing moves the way his code does is very common. You can also extend the board to keep some precomputed information that is easy to update incrementally with each move. For instance, my chess engine has this:

void Board::place_piece(int square, int piece) {
  a[square] = piece;
  bb[piece] |= 1ul << square;
  zobrist_key ^= zobrist_table[piece][square];
  material_zobrist_key += zobrist_table[piece][0];
  opening_material_score += opening_square_piece_table[piece][square];
  endgame_material_score += endgame_square_piece_table[piece][square];
  total_material += naive_material_value[piece];
}

void Board::remove_piece(int square, int piece) {
  a[square] = Empty;
  bb[piece] &= ~(1ul << square);
  zobrist_key ^= zobrist_table[piece][square];
  material_zobrist_key -= zobrist_table[piece][0];
  opening_material_score -= opening_square_piece_table[piece][square];
  endgame_material_score -= endgame_square_piece_table[piece][square];
  total_material -= naive_material_value[piece];
}

`a' is an array with the content of each square on the board, and `bb' is a bitboard (a 64-bit number indicating where a piece type appears). The other five things are of the nature that we are discussing: They are kept incrementally as you make and undo moves. The code that makes and undoes moves uses the two functions above.

Yeah, I get that... obviously you need to check that the undo stuff is correctly undoing the state though or else the container size explosion described is likely to be the result. Debugger-me-do...

That's similar to what I'm doing:

	private void placePiece(int cell)
	{
		this.board.getCells()[cell] = playerType;
		this.board.getActivePieces()[playerType]++;
	}
	
	private void undoPlacePiece(int cell)
	{
		this.board.getCells()[cell] = CellState.Empty;
		this.board.getActivePieces()[playerType]--;
	}

But the activepieces still increase out of proportion.

How did it go with the debugger?

You can also write a simple test program that makes and undoes some moves, so you can see what's going on independently of the complicated alpha-beta search.

Hmm... although I could see the variables increasing and sometimes decreasing I couldn't fully follow. I'm suspecting that the variable goes out of sync because after every move and every undo I'm swapping the players (the current player on turn).

A good test for ensuring that your move/undo is working properly is to temporarily save (clone) the state before each application of the move function and then after the undo move function testing that the state is the same as your saved state. Obviously this is a huge performance hit so enable it, do a test to a reasonable depth of search (so that this clone and test is executed on all searched nodes) and once satisfied disable it. If there is a problem the comparison will pinpoint which part of the move/undo move is not performing correctly.

I decided to copy the board anyways instead of undoing moves for now. If I have perfomance issues with copying I'll have to revert to undoing moves.

It comes down to what your objective is for this implementation. If you are trying to make a strong AI try to tackle the move/undo problem before delving into any of the enhanced search features (PVS, History heuristics, killer moves, null move) as it will become much harder to make the change later. Also your search depth will suffer greatly as copying is going to be your main bottleneck for the AI so you won't be generating nearly as many nodes compared to move/undo.

Yes I noticed that copying is a bottleneck. I'm currently searching at 5 ply but when I increase it to 7 it starts taking its time search. Maybe I should go back to make/undo.