Author: Peter Kappler
Date: 16:34:04 06/07/99
Go up one level in this thread
On June 07, 1999 at 18:53:36, Heiko Mikala wrote: >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. > Heiko, What you are describing is very similar to "Enhanced Transposition Cutoffs", where you test to see if any of the moves in your movelist leads to a position which has a score in the hashtable that can cause a cutoff. I think that ETC can speed up your search by anywhere from 10-25%. --Peter
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.