Author: Dann Corbit
Date: 15:33:33 10/15/99
Go up one level in this thread
On October 15, 1999 at 15:31:21, Robert Hyatt wrote: >On October 15, 1999 at 15:12:36, Dann Corbit wrote: >>On October 15, 1999 at 15:02:05, Robert Hyatt wrote: >>[snip] >>>No.. he makes a pass over the entire move list to pick the move with the >>>highest 'priority'. Then the next time he wants a move, he does this again. >>>One pass per move is the only way I can see to do it unless they are actually >>>sorted by priority first, which is a waste of cpu cycles... >> >>Sounds like a priority queue to me. >> >>There are priority queues with worst case behavior for all operations that is >>O(1) except for delete_min() which is O(log(n)). However, I find that the most >>efficient in real life is a binomial queue[1] which is O(log(n)) for insert() >>and also for delete_min(). >> >>[1] "Algorithms in C" by Robert Sedgewick, 3rd edition. Pages 395-401. > > >Just remember that this is right in the heart of the 'chess loop'. Anything >you do here, you do once for every node in the tree, which means _often_. > >you could set up 7 linked lists and add moves to the end of the right list. >but when you analyze chess trees, you see why it doesn't work... because _so_ >many positions in the tree only search one move and exit. Why do all that >work? when 1/2 of the time it is absolutely wasted? You don't have to use that sort of a structure. You can use an ordinary heap that is held in an array. Mark Allen Weiss does it that way in his C data structures book. That would assume you know the biggest that the array will get, though. On the other hand, it is quite likely that I simply do not understand the problem at hand. But when someone says they want to iterate, finding the top (or bottom) value each time, it seems that a priority queue is in order. Is the size of the structure itself dynamic? Where in the code does this search occur? I would like to take a peek at it.
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.