Computer Chess Club Archives




Subject: New(?) search idea.

Author: Andrew Walker

Date: 19:27:42 01/21/98

	Here's an idea I came up with recently, it may be old news
but I've never heard of it being used so here goes:

	One thing I've noticed with chess programs (mainly at a fixed time per
move) is that often the search will stop when they have spent ages
considering the main move, or when several replys to a none best
move have been examined and it looks like it may become the new best
move. Generally the best thing that can happen in a search is when a new
move becomes the main move and with a reasonably higher evaluation.
So we would like this to happen sooner if at all possible.
	The way searches normally work is that when the depth is increased, the
best move will be searched first. My idea is to search
all of the other moves first.
	Lets say a depth 6 search has been done for white and the best move is
e2-e4 with a score of +0.1. What we could do is start the depth 7 search
looking at all moves except e2-e4, and make them try to beat a score of
0.1+c, where c is a small positive constant such as 0.2.
Two cases are possible a) A new best move is found
		       b) No best new move is found
Now we search the old best move, e2-e4, at a depth of 7. In case b)
it is searched fully, and in case a) it is searched to see if it can
beat the new best move.
	In case a), after this the depth 7 search is complete.
	In case b) it becomes slightly more involved. e2-e4
now has a new evaluation which may be better or worse than the old +0.1
score. If it is better than 0.1+c then the depth 7 search is complete.
Otherwise the other possible moves need to be re-searched with a new
evaluation to beat. This may be fairly quick if the black replys
searched earlier and their scores have been stored, as the black reply
may still have a low enough evaluation to refute the white move.
	Why do this? In case a) above you can see that we may end up with the
new best move being searched fully, but e2-e4 being discarded
early. This may represent a saving in time as the old method will have
searched e2-e4 fully and the new best move fully.
	The idea of the small positive c is to increase the chances that
the new best move found in case a) will defeat e2-e4 when e2-e4 is
searched at depth 7, and so provide a saving in time. A comprimise needs
to be reached as too high a value lowers the chance of the new move
being found early.
	Lets say at depth 7 e2-e4 has a score of +0.15, d2-d4 is +0.18
and c is 0.2. Here d2-d4 won't be found early as in case a. Both will be
searched fully by this and the old method so there should be little
	Another possibility is if d2-d4 has a score such as 0.31 which
makes it get picked up earlier. If the search is stopped before e2-e4
is searched fully then we are risking the chance it may have a higher
score such as 0.35. Hence d2-d4 will be played, but in the old method
e2-e4 would have been played. So the value of c really is a trade off,
it needs to be high enough so that this is a smaller risk, but low
enough that a better move is likely to be found early.
	I hope this all made sense, and I would like to know if this is
is a waste of time or may be of interest.
	Andrew Walker

This page took 0.02 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.