Author: scott farrell
Date: 07:46:29 09/22/02
Go up one level in this thread
On September 22, 2002 at 10:14:27, Tom Likens wrote:
Tom,
I dont have an incremental move generator, so I have all moves generated ahead
of time. So sorting them all is as fast as sorting a few (with a quicksort
routine).
Scott
>On September 22, 2002 at 01:10:10, scott farrell wrote:
>
>Scott,
>
>When you get to number 6 below you probably only need to sort the first few
>moves
>using the history heuristic. If you don't see a cut-off after the first few
>moves, then you
>are more than likely at a type-3 node where all the positions need to be
>searched.
>Therefore wasting a lot of time sorting them is just that -wasting- time ;)
>
>I currently sort the first 5 "unwashed" moves, as you so colorfully call them,
>the rest
>are simply searched in the order returned by the move generator.
>
>regards,
>--tom
>
>>On September 21, 2002 at 12:20:24, scott farrell wrote:
>>
>>1. hash move first
>>2. winning captures as per MVVLVA or en pris (I guess that's part way to SEE)
>>3. even captures
>>4. killer moves
>>5. losing captures
>>6. the great unwashed !!! sort by historyFromTo, and historyFrom
>>
>>It got my move order from around an average of around 90% to around 92-93%, and
>>now peaks at 95% (as measured by a beta cutoff on the first move tried).
>>
>>I found sorting everything by the history table helped also, so if there are a
>>few ways to capture a queen, use both the LVA, the history table, and killers to
>>work out which is better. Same with even captures and losing captures. Generally
>>if there seems to be more than one move in a given category, using something
>>external to the current board seems to be a better way of breaking a tie (or a
>>close tie).
>>
>>Thanks again
>>Scott
>>
>>>I was just fiddling with my move ordering (as we all do from time to time).
>>>
>>>I found that my MVVLVA code worsened (is that a word?) my move ordering, and
>>>slow my searches significantly.
>>>
>>>I altered it to just simply ordering the capture by the size of the material it
>>>is to take, disregarding the size of the piece to perform the capture.
>>>
>>>As far as I know current wisdom for move ordering is something like this:
>>>1. from hastable first
>>>2. killers next
>>>3. winning captures ordered by MVVLVA
>>>4. other moves
>>>5. losing captures
>>>
>>>My updated move ordering is:
>>>1. from hastable first
>>>2. killers next
>>>3. all captures, ordered by the size of the captured piece (largest first), and
>>>ties broken by size of attacker only
>>>4. other moves
>>>5. losing captures
>>>
>>>I havent looked into to hard just yet, but I am pretty sure its got something to
>>>do with search extensions, and recapture extensions. Running all the captures
>>>first allows the extensions to kick in quickly and cause lots of nice cutoffs.
>>>
>>>The other thing it might be is a bug in my code - and turning off the MVVLVA
>>>ordering of capture bypassed the bug, but its only a few lines, and I dont think
>>>there is any bugs.
>>>
>>>What do you all think? am I crazy, do I have a bug, or are some programs already
>>>doing this?
>>>
>>>Scott
>>>
>>>Here is my old code:
>>>
>>> if (moves[depthTree][i].capture > 0)
>>> {
>>> //black is capturing a white piece
>>> if (b.isAttacked(moves[depthTree][i].s2, Board.WHITE))
>>> moves[depthTree][i].searchOrder
>>> += (Board.pieceValues[moves[depthTree][i].capture]
>>> - Board.pieceValues[
>>> - moves[depthTree][i].piece])
>>> * 100000 ;
>>> else
>>> //enpris
>>> moves[depthTree][i].searchOrder
>>> += Board.pieceValues[moves[depthTree][i].capture]
>>> * 100000 ;
>>> } else if (moves[depthTree][i].capture < 0)
>>> {
>>> //white is capturing a black
>>> if (b.isAttacked(moves[depthTree][i].s2, Board.BLACK))
>>> moves[depthTree][i].searchOrder
>>> += (Board.pieceValues[-moves[depthTree][i].capture]
>>> - Board.pieceValues[moves[depthTree][i].piece])
>>> * 100000 ;
>>> else
>>> //enpris
>>> moves[depthTree][i].searchOrder
>>> += Board.pieceValues[-moves[depthTree][i].capture]
>>> * 100000 ;
>>> }
>>>
>>>
>>>and my new code that is much much better at ordering:
>>>
>>> if (moves[depthTree][i].capture > 0)
>>> {
>>> moves[depthTree][i].searchOrder
>>> += (Board.pieceValues[moves[depthTree][i].capture] +
>>>moves[depthTree][i].piece)
>>> * 1000;
>>> } else
>>> {
>>> moves[depthTree][i].searchOrder
>>> += (Board.pieceValues[-moves[depthTree][i].capture] -
>>>moves[depthTree][i].piece)
>>> * 1000;
>>> }
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.