Author: Heiko Mikala
Date: 15:53:36 06/07/99
Hi everybody! Recently I had an idea to speed up the search in my chess engine, which I would like to discuss with you: Imagine you are in the middle of a search at ply n and you have already done everything you normally do at the start of a new ply to avoid searching new moves. That is, you have tested for draw, tested for a mate, checked your transposition table, maybe executed a null move and so on. Now you are at the point where you have to search all the moves at ply n. Let's say there are m possible moves, you search m-1 of these moves without finding anything of interest. Now you search the last possible move - and find that it leads to a draw, and that the draw score is higher than your current best score or even higher than beta (which would mean a beta-cutoff and much time wasted searching the first m-1 moves). Here comes the idea: If, before searching all the moves, beta is below zero, how about first executing all the possible moves (without searching them further), see if one leads to draw and if so return with a beta cut-off? Simply executing the moves and testing for draw is obviously much faster, than searching whole sub-trees. Another possible (?) enhancement: If you find a draw score, and your current best score and alpha are < 0, set current best score to 0. If 0>alpha, set alpha=0. Which would at least narrow the alpha-beta window. This should be possible without any danger, because the draw score is a true score, not a result of a more or less insecure evaluation function. Well, I thought this was a good idea, and after carrying it around with me for a few months, today I finally implemented and tested it - with disappointing results. Now, my question to you is, what do you think of this idea? Am I overseeing something? Is this idea really a bad idea, or did I only make a mistake in my implementation? I didn't have much time yet to test this, but here are the first results. I ran three different versions of my chess engine against a few positions of the BT2630 test, one version without the draw-test, one with only testing for a beta-cutoff and one with testing for beta-cutoffs and the alpha-enhancement: The numbers are times in seconds to find the correct move. BT-Nr. Normal beta-only alpha & beta --------------------------------------------------------- 1 150 116 116 2 36 38 39 3 145 251 253 5 31 19 7 (*) 6 5 5 5 7 1 1 1 8 5 5 5 10 5 5 5 11 2 2 2 12 21 197 198 14 1 2 2 17 226 240 241 18 32 13 13 20 8 9 9 22 1 1 1 26 0 0 0 27 124 148 148 [ (*) Here (Pos. 5) the correct move was found one ply earlier than without the draw test, but only "by accident". Which means, the draw test does not really have a positive effect in this position. ] All the solutions were found at the same depths, except for (*), so the time in seconds is a valid measure for comparison. The search was not significantly slowed down by the extra tests. In position No. 12 the search tree exploded, instead of becoming smaller. My feeling is, that the differences in search times are mainly due to slightly different sort orders of the move lists not really a result of the draw test. And instead of an enhancement it looks more like a worsening... What do you think? Is anyone in the mood to test this idea in his own engine? Greetings, Heiko.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.