Author: Ross Boyd
Date: 18:20:35 09/23/04
Go up one level in this thread
On September 23, 2004 at 12:25:41, Stuart Cracraft wrote:
>On September 22, 2004 at 22:17:10, Stuart Cracraft wrote:
>
>>On September 22, 2004 at 21:09:33, Robert Hyatt wrote:
>>
>>>On September 22, 2004 at 20:55:37, Stuart Cracraft wrote:
>>>
>>>>On September 22, 2004 at 19:38:53, Robert Hyatt wrote:
>>>>
>>>>>On September 22, 2004 at 18:53:51, Stuart Cracraft wrote:
>>>>>
>>>>>>Are you saying I should consider marking each move after its search, then
>>>>>>back up the score value, node count, etc., then resort based on that?
>>>>>>
>>>>>>I could see that various parts of the subtree have generated new history
>>>>>>heuristic scores for from/to move coordinate pairs and that a resort could
>>>>>>affect the remaining move order.
>>>>>>
>>>>>>I don't currently resort at any level after the movegen at that level.
>>>>>>I just search all the moves in the original post-movegen-sort-order.
>>>>>>
>>>>>>I am fine with considering doing continual resorts but worry about the
>>>>>>overhead and the return. But with it being the all important move-ordering,
>>>>>>what have you seen in doing these resorts in terms of improvement
>>>>>>
>>>>>>Stuart
>>>>>
>>>>>There is _no_ overhead. It is done only at the root, once per iteration. For a
>>>>>12 ply search, a total of 12 times. That won't use measurable CPU time. The
>>>>>point is that root move ordering is critical for efficiency..
>>>>
>>>>That's a new one on me. I always thought it was throughout the tree. I'll
>>>>have to chew up some code on this one.
>>>
>>>
>>>Ordering is important everywhere. But this thread was about ordering at the
>>>_root_ of the tree...
>>
>>I will try it.
>
>Please see earlier post -- result for ply == 0 reordering based on
>history heuristic is +2 on problems and -2% on search tree. This is
>not a bad result and certainly better than most things I try.
>
>I don't quite follow how total nodes searched can be used to resort
>the movelist -- you've already searched those moves. What use are they
>for a resort? There's no flow-over effect to the unsearched moves.
>
>Stuart
Stuart, I think you're missing something here.
Like 99% of us you're using iterative deepening, right?
That is, you search all root moves progressively deeper starting at depth 1.
After searching ALL the root moves, you can reorder the root moves based on how
many nodes they chewed up during their search. Moves that produce high node
counts are ordered ahead of low counts.... a high node count indicates that the
move has some merit and was hard to refute. (The exception of course is the
bestmove which should always be searched first at each iteration).
Then you zero each move's nodecount and start the root search again with depth =
depth + 1...
If you haven't done so already its probably simplest to write a dedicated
root_search module that handles all the above.
BTW, I started with WAC as a debugging benchmark for TRACE. At first she
struggled but gradually she solved all but 2 of them. On a P3-450 she solves
~280/300 @ 2 secs and 297/300 @ 27 secs. Now I don't pay attention to WAC - the
real problem is not in finding 'winning' moves - but avoiding losing moves.
There are so many ways to lose a game of chess...
Things which helped me the most...
* making sure the move generator is fully debugged (write a perft routine)
* making sure the hash table is working correctly
* making sure the search is working correctly
* adding nullmove search
* evaluating mobility
* SEE pruning in qsearch to cull losing captures
* in qsearch, gen all moves when in check...
* in qsearch, if not in check and no captures produced a beta cut and this is
first ply of qsearch then generate and qsearch non-captures that give check.
* use Bruce Moreland's nullmove threat detection idea in main search.
ie.
if (nullmove_score==-CHECKMATE+ply+2)
extend the search
Hope this helps.
Ross
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.