Author: Dan Newman
Date: 09:14:24 01/04/02
Go up one level in this thread
On January 04, 2002 at 10:33:27, John Coffey wrote:
>On January 04, 2002 at 10:14:17, Severi Salminen 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?
>>
>>The optimal solution is a movegenerator that allways generated the best move.
>>But since that is quite impossible it is best to try to generate only those
>>moves that are likely needed and get a cutoff as fast as possible. 1. try the
>>hash move and don't generate others. 2. generate captures and try the good
>>ones. 3. try killers. 4. generate the rest and order them by history values. 5.
>>try the bad captures. In each step try to do as little as possible, generate
>>only the moves you need and do it fast. So if you get a cutoff with a hash move,
>>you really don't need to know _anything_ about the rest of the possible moves.
>>
>>Severi
>
>How many programs actually do this and how many generate the entire move list?
>
>John Coffey
I generated the entire list in my first program, under the misapprehension
that I was saving some work this way. Currently, I do this:
1) Probe the transposition table and hope for an immediate return.
2) Try the null move and hope for a cutoff.
3) Try the hash table move, if any. If there isn't one and I'm on
the PV, do an "internal iterative deepening" search for a good move
and try that.
4) Generate the captures and promotions only and sort them with a SEE.
5) Try only the winning captures as determined by the SEE.
6) Try the killer moves.
7) Try the losing captures. (I think this might be better placed lower
down in this list, but the structure of my program at one time
required that I do this here.)
8) Generate the non-capture/non-promotion moves.
9) Try a few of these moves selected by the history heuristic. Do this
by repeated scans (say three to five) through the list of moves as
that is probably cheaper than sorting the whole list.
10) Try the remaining in the order they are found. The idea here is that
if, after all that move ordering, we haven't yet gotten a cutoff, we
are probably in an "all" node where we have to try all the moves
anyway.
By generating the captures and non-captures separately, I avoid some
work whenever a capture gives a cutoff. Doing things in a lazy fashion
quite frequently saves cpu cycles in a chess program.
-Dan.
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.