Author: John Lowe
Date: 09:03:27 12/24/02
Go up one level in this thread
On December 24, 2002 at 11:12:48, Uri Blass wrote: >On December 24, 2002 at 11:04:06, John Lowe wrote: > >>On December 24, 2002 at 10:21:32, José Carlos wrote: >> >>>On December 24, 2002 at 10:04:00, John Lowe wrote: >>> >>>>On December 24, 2002 at 05:46:02, Dave Gomboc wrote: >>>> >>>>>On December 24, 2002 at 05:41:50, John Lowe wrote: >>>>> >>>>>>On December 24, 2002 at 05:32:06, Uri Blass wrote: >>>>>> >>>>>>>On December 24, 2002 at 04:16:11, John Lowe wrote: >>>>>>> >>>>>>>>On December 23, 2002 at 20:23:04, Robert Hyatt wrote: >>>>>>>> >>>>>>>>>On December 23, 2002 at 19:21:57, Uri Blass wrote: >>>>>>>>> >>>>>>>>>>On December 23, 2002 at 18:31:03, Dieter Buerssner wrote: >>>>>>>>>> >>>>>>>>>>>On December 23, 2002 at 18:08:15, Martin Bauer wrote: >>>>>>>>>>> >>>>>>>>>>>>Hello, >>>>>>>>>>>> >>>>>>>>>>>>i have a queastion about move ordering. There are many sources with move >>>>>>>>>>>>ordering heuristics like killer heuristic, history and so on... >>>>>>>>>>>> >>>>>>>>>>>>But I found no description _how_ to program the move ordering in an _efficient_ >>>>>>>>>>>>way. In my own enginge I use an integer value together with the move and put it >>>>>>>>>>>>on the move stack. Moves that should be searched first, become a high value and >>>>>>>>>>>>the less important moves a low one. Then there is a function named >>>>>>>>>>>>"NextBestMove" that that looks for the highest value at the actual searchdepth >>>>>>>>>>>>on the movestack. Therefore it must look at all possible moves in the actual >>>>>>>>>>>>position. When the best move is found, the value is set to -Matescore, so it can >>>>>>>>>>>>not get the best move the next time the function is called. >>>>>>>>>>> >>>>>>>>>>>This is the normal way to do it, I think. Instead of giving a "marker score", to >>>>>>>>>>>not search the move again, you could shift the move to the start or to the end >>>>>>>>>>>of the array, and remember the new bounds (incrementing a pointer may be enough >>>>>>>>>>>for this). This will save a few CPU cycles. It is essentially the inner loop of >>>>>>>>>>>a normal selection sort. >>>>>>>>>>> >>>>>>>>>>>>This algorithm must have a look at all possible moves in the position at the >>>>>>>>>>>>actual depth, even if the frist 10 best moves are searched. This look not >>>>>>>>>>>>efficient to me, because it is an O(n) algorithm in reading the best move and >>>>>>>>>>>>O(1) in storing the best move. >>>>>>>>>>> >>>>>>>>>>>I think, there is no practical better way. Sorting the whole move list can >>>>>>>>>>>easily be done faster (especially, when it has some considerable length, so not >>>>>>>>>>>just relpy to check). But often, the work will be done for nothing, because one >>>>>>>>>>>move will be enough for a cutoff. I experimented a bit with the following idea: >>>>>>>>>>>Try to guess, when we expect a fail high node: use the selection sort method >>>>>>>>>>>above. Whe expecting a fail low node, do a qsort (the Standard C-language qsort >>>>>>>>>>>would probably be a bit slow for this, because of all the calls to the compare >>>>>>>>>>>function, I had written my own). But, I really could not measure any performance >>>>>>>>>>>increase, so I gave up on the idea. It just made the code bigger ... >>>>>>>>>> >>>>>>>>>>If you expect a fail low move you can simply not care about order of moves. >>>>>>>>>>Latest movei does not continue to sort the moves if the first 10 moves did not >>>>>>>>>>give a fail high(I do not know if 10 is the best number but the gain that I may >>>>>>>>>>get from changing it is small because movei is not a fast searcher). >>>>>>>>>> >>>>>>>>>>Uri >>>>>>>>> >>>>>>>>>I've done this in crafty for many years. I try the hash move, the good capture >>>>>>>>>moves, the killer moves (2), and then if the first 4 history moves don't produce >>>>>>>>>a fail high, I just take the remaining moves in the order they were generated. >>>>>>>>> >>>>>>>>>saves time. >>>>>>>> >>>>>>>>I have understood good capture, killer and history but could you expand "hash >>>>>>>>move" a little. (Terra incognita for me) >>>>>>> >>>>>>>hash move is a move that you remember from the hash tables and caused a fail >>>>>>>high in the same position in previous search. >>>>>>> >>>>>>>Uri >>>>>> >>>>>>That's what I thought but why "try" again - have some parameters changed? >>>>> >>>>>Yes, you're searching one ply deeper this time. :-) >>>>> >>>>>Dave >>>> >>>>So the hash move is just a term for the best-so-far and nothing to do with >>>>duplication of positions? >>> >>> No. It's supposed you're doing iterative deepening. At iteration 10, you >>>search every root position with depth = 10. When finished, if you have enough >>>time, you start iteration 11. Then you have the exact same positions as before, >>>but you want to analyze them one ply deeper. So, for each one, you try first the >>>move you find in the hash table for that exact position, because it proved best >>>the last time you searched it. You usually get a cutoff there (if you got in the >>>previous search, of course) because adding a ply doesn't make a dramatic >>>difference in most positions (most positions in the tree are irrelevant). >>> >>> José C. >> >>Hi Jose, >> >>One more try! >> >>We're looking at a root position which may or may not be the best-so-far. We've >>finished looking at ply 10 - some positions were duplicates of analysed >>positions and were not analysed again because their "value" was in the hash >>table, some were never analysed but pruned by the cutoff. >> >>We begin ply eleven for that root position by generating a movelist from the >>most likely candidate (ply 10) to give a cutoff. >> >>I thought we were talking about move order in this (ply eleven) movelist. The >>only move in this list that can be called a "hash move" will be one that has >>been seen before at ply eleven, evaluated and stored in the hash table....... > >Suppose you have no book and analyze the opening position > >You searched to depth 10 and found that 1.d3 is not good because 1...d5 gave a >cutoff. > >Now you search to depth 11. >What is the first move that you search in reply to 1.d3? >You start with 1...d5 because that move is in the hash tables. > >Uri I've no problem with that Uri, but these are moves from the root position. (Plies one and two) There's no reason why a move that was weak at ply one should be weak at ply eleven or refuted by the same cutoff move. It will be whites sixth move! Will someone tell me that "Hash move" has nothing to do with ordering the movelist generated for white at depth eleven or that it has and I can't see the wood for the trees or something. My brain hurts........
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.