Daily Archives: 2010-06-18

Tales of a chess engine developer 1

Chess engine development is one of the most brain-crushing activities I’ve been involved on the last years. Last nigths I was working again on my Carballo Chess Engine with some advances.

First of all I decided to leave Negamax and go with Principal Variation Search (PVS). Also decided to implement separate methods for root nodes, PV nodes and null window searches. On previous experiments PVS was performing worse than Negamax, but I discovered the reason: the aspiration window has some implementation issues with PVS: when the search for a move fails low at the root node the move must be researched enlarging the window.

I was very stranged of why Futiliy Pruning was not working for me, but finally discovered the reason: a simple sign change after evaluation was the reason! Also implemented to store the evaluation values on the Transposition Table (TT).

The next step: why Carballo searched much less depths than other engines, it was due to quiescence search. I was generating checks for the first 4 PLY’s of quiescence, but some other engines not, so this was the reason. I decide to generate only checks on the first PLY of quiescence and only for PV nodes. Also modified a bit the move generation to optimize for quiescence.

During this time also found many interesting bugs, I was storing on the TT the bound and not the score when failing high/low, also on PV nodes is better to use only the TT for ordering and not to return scores from it, this helps avoiding draws. Also found a serious bugs involving time management (was taking as reference opponent’s time) and with contempt factor on IID searches corrupting TT entries. Finally added a Pawn Push Extension and removed the Recapture Extension and now some extensions now depend of the node type.

Running some test tournaments, I hope to get some good results soon and add the improved engine to my Mobialia Chess.