alpha-beta performance

[sebj]

Hi everybody,

I have just finished my first chess engine. He plays legal moves and recognize when he is checkmated, which already makes me happy ( I am sure you know this !).

I am worried about the performance now. I am using a very simple alpha-beta search algorithm (basicly, the algorithm you can find on wikipedia), but the perf are very poor. From the initial position, I reach a depth of 4 ply in +- 5 minutes.

Can you please tell me what can I expect from this basic version of alpha-beta (lets say, how much time does it takes normally to reach a depth of 4) ? It will help me to identify if I have to work on my search algorithm or on something else.

Thanks for your comments,

[pedrox]

For that the alpha-beta algorithm work you have to sort the possible moves to a position from best to worst, so avoid check many moves to produce a beta cutoff.

I imagine your engine does not have hash tables, I guess you're using iterative depth, then orders first the best move of previous depth, then order winning captures of material, then equal captures, then the losers. Moves without captures should sort by killers, history or by some kind of pieces squares tables with information for pieces centralized on the board.

Move Ordering --> http://chessprogramming.wikispaces.com/Move+Ordering

[hyatt]

If you order moves reasonably (reasonable means 90% of time you search the best move first, a normal quality for current programs) then the basic idea is that alpha/beta will DOUBLE the normal minimax search depth. 4 plies sounds way wrong, even for worst-first move ordering...

Maybe your q-search is running amok or something.