Author: Leen Ammeraal
Date: 23:29:05 01/03/02
Go up one level in this thread
In discussions about O(n^2) algorithms, it should be kept in mind that these algorithms are bad only for large values of n. Here n is relatively small. Nevertheless, you can do better than sorting the whole list of moves. Look for the best and swap it with the first, so that the first is on top. Use the first move, and look for the best move in the remaining list. Then again, swap this best move with the first one in the remaining list and use it. (Actually, you need not store the best move in the first position each time, just before using it.) The advantage of this method is related to the fact that possibly not all moves will be used because of beta cutoffs. Leen On January 04, 2002 at 01:39:47, John Coffey wrote: >There has been some confusion in my mind for years >about move ordering. I know that good move ordering will reduce the size of >the tree. How important is it to get all the moves in the best order as >oppose to just starting with the best candidate? > >For example, I read that some programs generate the entire move list, and >then scan through the list to find the move with the best score (by some >criteria such as the value of captures) and then rescan the list when it is >time to try the next move. Both this scheme and sorting seem very time >consuming to me because we could be talking about N^2 compares. Cutoffs >will reduce the time a great deal. > >If you start with a move from the hash table/transposition table, then how >important is it to >order the remaining moves? If it weren't important, then you wouldn't have >to generate the entire move list, but as I understand it, most programs >generate the entire move list anyway? I think that Crafty does. > >John Coffey
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.