Author: Robert Hyatt
Date: 12:31:21 10/15/99
Go up one level in this thread
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?
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.