Author: Robert Hyatt
Date: 23:06:01 06/01/00
Go up one level in this thread
On June 01, 2000 at 21:49:46, Heiner Marxen wrote: >On May 31, 2000 at 21:58:00, Robert Hyatt 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. >> >>The problem is that the number of moves for a particular node is not constant >>from iteration to iteration. This is caused by the odd/even effect of alpha/ >>beta trees. And if you change either alpha or beta, you can drastically change >>the shape of the tree you search with those bounds. >> >>I don't see how to determine node expectancies without simply searching them to >>see what they are. > >That is (sort of) bad news. > >>It would be possible to test this of course, just for fun, by actually checking >>all the moves for node counts and then using other 'guestimate' algorithms to >>approximate these numbers without requiring the actual search. >> >> >> >> >> >>> >>>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 sort _at the root_ like this. And it works. But only at the root... > >Yes, that is what I remembered. I could not find comments about this >in crafty's main.c... do you remember the version you introduced this >sorting at the root, and how much speed up were gained? > >Heiner I did it for a long time, mainly because I also did the same thing in Cray Blitz. The reason I did it was mainly for those "change your mind" cases... You search and get a score for move 1. You search moves 2 thru M-1 very quickly. You search move M and it takes a long time because it is close to becoming good enough to replace the best move (move 1) but not quite yet. You search moves M+1 thru N very quickly. Sorting by node counts moves move M to slot 2 in the move list, so that you search it right after searching the current best move. If you are going to change your mind, you do it a bit quicker. But it isn't any huge savings, just something "useful" overall.
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.