[chess engine programming] minimax and alpha-beta. 3-4 plies. Normal?

Hi,
I have being writing a chess engine and has just began the AI part (finished move generation and implemented all the rules). What I have implemented so far is a simple minimax with alpha-beta prunning (random ordering). The evaluation function only takes material balance into account. Boards are implemented using bitboards (simple ray-through for sliding pieces, no rotated bitboards). Currently, on ~10 seconds per move, I get 5 plies at the beginning, 3-4 in middlegame and endgame (without opening book and endgame database). Does that seem normal? To me the numbers seem pretty low, but I have no prior experience in chess programming.

Thank you very much

Originally Posted by cyberfish

Hi,
I have being writing a chess engine and has just began the AI part (finished move generation and implemented all the rules). What I have implemented so far is a simple minimax with alpha-beta prunning (random ordering). The evaluation function only takes material balance into account. Boards are implemented using bitboards (simple ray-through for sliding pieces, no rotated bitboards). Currently, on ~10 seconds per move, I get 5 plies at the beginning, 3-4 in middlegame and endgame (without opening book and endgame database). Does that seem normal? To me the numbers seem pretty low, but I have no prior experience in chess programming.

How good or bad that depth is depends on your game playing performance. If you're only looking to 5 ply but you're kicking butt, it doesn't really matter much.

There's a complex interaction going on here. If your evaluation function is complex, then evaluating each move takes longer. But if the values are BETTER, this leads to better play, because you maximize the benefits of move ordering for alpha-beta, and you don't have to search as deep to get a reasonable estimate of the board evaluation. If your evaluation function is braindead, you should be able to search a few ply deeper -- if you're not, there's something wrong with logic elsewhere in the program.

Even a poor evaluation function can perform well, if you are able to search deep enough.

Can you give any more details about your evaluation function? Are you using a transposition table? Are you using incremental move ordering? Are you using iterative deepening?

Thank you for your reply.

How good or bad that depth is depends on your game playing performance. If you're only looking to 5 ply but you're kicking butt, it doesn't really matter much.

Doesn't seems like that is the case. I can beat it very easily and I have a rating of ~1000 on FICS =)

If your evaluation function is braindead, you should be able to search a few ply deeper -- if you're not, there's something wrong with logic elsewhere in the program.

That is what I thought, too, but I don't see what is wrong. The evaluation is braindead.

Can you give any more details about your evaluation function? Are you using a transposition table? Are you using incremental move ordering? Are you using iterative deepening?

I am using iterative deepening, but results from previous depths are discarded (for now). There is currently no transposition table, or incremental move order (except I search the captures first).

here is my evaluation function -

Code:

int staticEvaluate(Board &board) {
	
	int result = 0;
	
	//BEGIN: material balance
	
	int sum = 0;
	
	for (int i = 0; i != 64; ++i) {
		PieceType at_type = board.getType(i);
		if (at_type != EMPTY) {
			sum += BaseValues[at_type];
		}
	}
	
	result += sum;
	
	//END: material balance
		
	return result;
	
}

Thank you

based on the result of gprof, it appears that my engine evaluates about 1.2 million moves per second. I guess I will just move on to implement other algorithms and optimizations.

Originally Posted by cyberfish

based on the result of gprof, it appears that my engine evaluates about 1.2 million moves per second. I guess I will just move on to implement other algorithms and optimizations.

Move ordering, move ordering, move ordering! Start taking advantage of your iterative deepening. Usually this is implemented with a transposition table, but you can do it without one as well.

Move ordering, move ordering, move ordering! Start taking advantage of your iterative deepening. Usually this is implemented with a transposition table, but you can do it without one as well.

Thank you for your suggestion =). I understand the importance of move ordering, but I just wanted to make sure that my basic implementations of minimax and alpha-beta are fine before I move on to things like transposition table. The depth it currently reaches scares me a bit though (3-4 plies in midgame with an extremely simple evaluation function).

Thank you

about 1.2 million moves per second

hmm I think I made a mistake in interpreting gprof result. My engine is actually only searching ~30000 positions per second. I guess something is seriously wrong...

Originally Posted by cyberfish

hmm I think I made a mistake in interpreting gprof result. My engine is actually only searching ~30000 positions per second. I guess something is seriously wrong...

Can you post the function coverage profile -- not the entire thing, just the first level table?

Can you post the function coverage profile -- not the entire thing, just the first level table?

Thank you for your help, it's much appreciated. I am not sure what is the function coverage profile. Is it the same as the "flat profile"? Here is the flat profile section:

Code:

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 42.55      1.29     1.29  7837472     0.00     0.00  Board::canCapture(unsigned long long)
 17.88      1.83     0.54   277323     0.00     0.00  Board::generateLazyMoves()
 16.72      2.33     0.51  7837494     0.00     0.00  Board::Board(Board&, Move)
 11.26      2.67     0.34       80     0.00     0.04  MiniMax(Board&, int, int, int, int&)
  4.64      2.81     0.14  1723099     0.00     0.00  std::vector<Move, std::allocator<Move> >::_M_insert_aux(__gnu_cxx::__normal_iterator<Move*, std::vector<Move, std::allocator<Move> > >, Move const&)
  3.31      2.91     0.10   277204     0.00     0.00  Board::validateMoves_rtnBoard(std::vector<Move, std::allocator<Move> >*)
  2.98      3.00     0.09  1672405     0.00     0.00  std::vector<Board, std::allocator<Board> >::_M_insert_aux(__gnu_cxx::__normal_iterator<Board*, std::vector<Board, std::allocator<Board> > >, Board const&)
  0.50      3.02     0.02    17786     0.00     0.00  Board::underAtk(unsigned long long)
  0.17      3.02     0.01                             Board::getTypeAsArray(int*) const
  0.00      3.02     0.00      131     0.00     0.00  beginsWith(char*, std::string&)
  0.00      3.02     0.00      119     0.00     0.00  Board::generateMoves()
  0.00      3.02     0.00      119     0.00     0.00  Board::validateMoves(std::vector<Move, std::allocator<Move> >*)
  0.00      3.02     0.00      117     0.00     0.00  Board::getGameState()
  0.00      3.02     0.00        8     0.00     0.00  std::vector<int, std::allocator<int> >::_M_insert_aux(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, int const&)
  0.00      3.02     0.00        2     0.00     0.00  checkClaimDraw(std::vector<Board, std::allocator<Board> >&, Move&, bool)
  0.00      3.02     0.00        1     0.00     0.00  global constructors keyed to kingAtk
  0.00      3.02     0.00        1     0.00     0.00  algeToMove(std::string, Board*, signed char)
  0.00      3.02     0.00        1     0.00     0.00  moveToAlge(Move)
  0.00      3.02     0.00        1     0.00     0.00  computeConst()
  0.00      3.02     0.00        1     0.00     3.02  findBestMove(Board, int&, unsigned long, int, bool)
  0.00      3.02     0.00        1     0.00     0.00  __static_initialization_and_destruction_0(int, int)
  0.00      3.02     0.00        1     0.00     0.00  char* std::string::_S_construct<char*>(char*, char*, std::allocator<char> const&, std::forward_iterator_tag)

and in case it is of any use, here is the full output -
http://cyberfish.wecheer.com/gprof_out.txt

the Board::canCapture() function is a function used to determine whether the moving side can capture a particular piece. Currently, the only use of this function is in move validation (making moving into check or leaving the king in check impossible).

the Board::generateLazyMoves() function generates all legal moves but does not check whether the moves will leave the king in check.

the Board::Board(Board&, Move) constructor constructs a new board by copying an old board and applying a move.

in the profiled run, I started a new game and set the engine to play black with a time control of 5 minutes per move, and I typed in the move "e2e4", and then quit.

or, in xboard protocol:

Code:

xboard
protover 2
level 40 5 0
new
random
usermove e2e4
quit

Thank you very much

I'm a little surprised that your board constructor(copying) takes so much time - yes it's called 8 million times, and that's certainly a lot. Are you using a loop to copy the content of the board or something like memcpy()?

--
Mats

I'm a little surprised that your board constructor(copying) takes so much time - yes it's called 8 million times, and that's certainly a lot. Are you using a loop to copy the content of the board or something like memcpy()?

thank you for your help. I am using memcpy to copy the board (~180 bytes). My wild guess would be because the constructor is full of branching (checking for castling, en passant, promotion, see if castling availability changed etc).

[edit]
Just had a look at the constructor code, it looks pretty ugly with all the if's. I will try rewriting it and see what happens.
[/edit]

Branches are bad for modern processors, so if you can make them go away (or make them more predictable) then that's a good thing.

Copying 180 bytes * 8 million times = 1.4GB, so it will take a little bit of time... Of course, it's presumably not copying to a new location every time, so hopefully the processor cache will help some of the time at least - I take it you're not building and keeping 8 million boards, but rather creating one, checking the move and then destroying the board after evaluating the result of the move, yes?

--
Mats

Thank you for your reply.

I am currently rewriting this constructor to minimize branches, but can you please explain what do you mean by "making them more predictable"?

And I am destroying boards once they are done with. There are no more than 500 boards in memory at any time.

Well, if branches are "predictable", in other words, the branch is taken in one direction every time (or nearly all the time) then the processor will be able to "predict" the correct path to take. Unpredictable would be something like this:

Code:

char str[] = "aAbDeEcDDeCaarE";

int i, uc = 0, lc = 0;
int len = strlen(str)
for(i = 0; i < len; i++) 
{
    if (isupper(str[i]) uc++; else lc++;
}

Since the upper/lower case letters are all scrambled in different order, the processor wouldn't be able to predict one from the other. If you sorted the string, it would have all the lower-case at one end and the upper case at the other, and thus prediction would work except for the first and the "split-point".

Not sure if you can do anything about that, tho'.

By the way, if the compiler is clever, it can do the above code without branches at all, and when I tested it, it was about 4x faster with branches eliminated compared to branches - I sent the suggestion to someone in the GCC group about 4 years back, and I has pleasantly surprised when I saw some of the suggested code when looking at the output of a gcc compiled code-snippet. I also think MS compilers do the same thing if it's feasible.

--
Mats

I see, thank you for the explanation, but I don't think I can do anything about that in my code =)

by the way, I am using gcc 4.1.3 on Linux, so I guess I am benefited by your suggestion.