Author: Robert Hyatt
Date: 05:03:35 01/22/98
Go up one level in this thread
On January 21, 1998 at 22:27:42, Andrew Walker wrote: > 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. this has two serious problems: 1. based on past results, changing its mind from one iteration to the next happens less often than not changing. 2. your idea would slow the program by a factor of two most of the time, because you will have to find a PV from the N-1 set of moves, and then most of the time you will fail high and have to research the real best move, making the tree much larger. Also, a factor of two won't really be enough... Because after you get the PV move from the depth=N search, you use those moves to order the depth N+1 search. You would start off, using your idea, with nothing to help but the transposition table and history counts. But at deeper searches it is likely that searching the PV move at the end of the last search would overwrite most of the useful transposition table stuff. I don't see how this would work at all, from an efficiency point of view. But it would be easy to test... > 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 >difference. > 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 > ajw01@uow.edu.au
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.