Author: Gerd Isenberg
Date: 14:19:24 07/24/04
Go up one level in this thread
On July 24, 2004 at 15:59:19, Dieter Buerssner wrote: >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. That's what i ment. Getting all N moves. For one move a constant O(1). 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. Yes. Therefore my current finite state generator which i feel is too complicated and needs some extra ply indexed data as node members as well. >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()). Never heard about that algorithm. Anyway moving moves arround seems to much wasted work if you fail high early. >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. Keeping things simple is one idea with the max64-getter. Don't matter how much effort for scoring. During movegen i consider at least history and pieces obviously moving en prise. Cheers, Gerd > >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.