Author: Ed Schröder
Date: 22:33:38 05/31/00
Go up one level in this thread
On May 31, 2000 at 18:54:42, Heiner Marxen wrote: >On May 31, 2000 at 17:38:52, Robert Hyatt wrote: > >>On May 31, 2000 at 17:25:22, blass uri wrote: >> >>>On May 31, 2000 at 17:21:05, blass uri wrote: >>><snipped> >>>>If people want to get an estimate how much better they can improve the move >>>>ordering then I suggest to develop 2 programs. >>>> >>>>1)Program A searches with the same extensions of the original program when only >>>>the order of moves may be different because it gets it from program B >>>> >>>>2)program B searches for the best move ordering and gives program A only the >>>>knowledge about the order of moves to search. >>>> >>>>When you count nodes count only nodes of program A to get a fixed depth and >>>>compare it with the number of nodes of the original program to get the same >>>>depth. >>>> >>> >>>I can add that I think that this is not a simple task to write the programs A >>>and B(when the main problem should be writing program B that searches for the >>>smallest tree to produce a cutoff). >>> >>>Uri >> >> >>There are two issues: >> >>(1) you can write code to prove that one move is better than another, simply >>by searching both moves. >> >>(2) you can _not_ write code to choose a move that leads to the smallest sub- >>tree, without first searching the moves. Otherwise there is no way to compare >>them. And once you have searched them, there would be no benefit to then >>searching the move with the smallest tree _again_. >> >>This is one of those "you can't answer the question until you do the search, and >>once you have done the search, it is too late to ask the question." > >It can be done where iterative deepening is done: you measure the number >of nodes searched for the moves, and when searching with increased depth, >after the first move you order the others in increasing node number from >the last depth. > >I vaguely remember that this has been discussed here and is already done. >If so, has anyone ever measured the effect (speed up) of such sorting? > >Heiner I am working on such a technique but so far I am not able to get a clear speed-up although I feel the potential somehow is there. I will explain in the hope to get some feedback here or by email. Whenever a move is "good enough" for an A/B cutoff it is likely there are (say) 3 other moves that will also produce a cutoff. So in total you have 4 (good) moves sufficient for a cutoff. But since you only search the first one you will never know if move 2-4 will a) be better in score and/or b) will produce a shorter sub-tree (lesser nodes) and therefore moves 2-4 are candidates to improve move-ordering, -> faster search. The idea is to fool (ignore) A/B so that the engine is forced to look at more alternatives (in our example 3), thus is total 4 moves are searched. You then decide which one of the 4 will be used for move-ordering (store in hash table). Criteria: a) the one with the best score is used b) the one with the smallest nodes is used How to fool A/B: Totally ignoring A/B is a bad idea since you still can get stuck in a 4-5 ply search after 1 minute. But when you set a small fixed "A/B fool window" on beta you will notice the "A/B fool" search becomes reasonable fast. When I set the value of the "fool window" to 0.25 I am still able to get 5-7 plies in the mid- game within the first 10 seconds of the search. And that is exactly the idea: let the engine search for 10 seconds with "A/B fool" in the hope of better move-ordering in order to get back the invested 10 seconds and hopefully a lot more. The idea really works as in 80% of the cases the algorithm is at least able to get back the invested 10 seconds. But overall after testing about 200 positions the gain is only a disappointing 1%. On the other hand it proves the idea has potential. Maybe using 5 seconds instead of 10 will have the same effect on move ordering and then the gain is automatically more. Maybe one should increase or decrease the "fool window". I haven't tested these options yet. Of course the idea is only valid on longer time controls. A formula to control the "A/B fool search" could be: seconds=average time/16 (or so). Ed
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.