Author: Dieter Buerssner
Date: 12:59:19 07/24/04
Go up one level in this thread
On July 23, 2004 at 18:33:36, Gerd Isenberg wrote: >Is your getNextMove O(N**2)? O(N**2)?? You must mean sorting all moves. Getting one move should always be O(N) (n=number of available/remaining) moves at worst. Getting N moves could of course need time proportional to N**2. As you know, often we only need to pick one move, that fails high then. One can of course also sort all moves in O(N log N) time. Or using radix sort (if i remember the name correctly) in linear time (radix sort is a bit like firstone/lastone. You could sort say 10 different numbers, by adding them to an empty bitboard. Then pick them ordered out again by Firstone()). One could also not store the moves in an array, but in some tree (a heap). I tried some things, but did not see a difference, besides more complicated code :-) I only did the more sophisticated things, when the engine guessed, that this node will not fail high. Such a guess is of course not reliable. Otherwise one would not need to sort at all. Cheers, Dieter
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.