Author: Ricardo Gibert
Date: 10:22:20 06/01/00
Go up one level in this thread
On June 01, 2000 at 01:33:38, Ed Schröder wrote: >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%. Is this with futility pruning, extended futility pruning & Null move pruning disabled? > >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.