Author: Heiner Marxen
Date: 18:49:46 06/01/00
Go up one level in this thread
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
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.