Author: Ed Schröder
Date: 10:59:41 06/01/00
Go up one level in this thread
On June 01, 2000 at 13:22:20, Ricardo Gibert wrote: >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? The answer to your question it is yes, yes and no. The AB_FOOL algorithm just uses the standard engine without any exception. Ed >>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.