Author: Vasik Rajlich
Date: 03:33:56 03/17/04
Go up one level in this thread
On March 16, 2004 at 17:50:02, Mridul Muralidharan wrote: > One additional comment which I forgot to mention : > pcsq values based move ordering can and does perform worse than history for >some class of positions where there are lot of "history favourable" cutoffs >happening and for some other types of positions too. > But in most of these cases , using ply - 2 killers and bumping number of >killers from 2 to 3 or say 4 was also sufficient compensation for removing >history even these sort of positions ! > > Take a set of quiet positions and it will be possible to see history being >totally equal or slightly worse or slightly better than random (or no) move >ordering. > Eliminating all these and making move ordering as good as possible made >messchess a very slow engine that it is now. (This and a lot of other search and >eval related stuff :) ). > >Mridul > Hello Mridul, your comments are interesting, but not (for me) intuitive. Can you post some numbers & results? In particular I would be curious to see the results which show that replacing history tables with piece-square calculations improves move ordering. Cheers, Vas > >On March 16, 2004 at 17:17:11, Mridul Muralidharan wrote: > >>On March 16, 2004 at 14:48:14, Robert Hyatt wrote: >> >>>On March 16, 2004 at 13:52:21, Mridul Muralidharan wrote: >>> >>>>On March 16, 2004 at 13:06:34, Robert Hyatt wrote: >>>> >>>>>On March 16, 2004 at 12:41:55, Sune Fischer wrote: >>>>> >>>>>>On March 16, 2004 at 12:30:42, Robert Hyatt wrote: >>>>>> >>>>>>>On March 16, 2004 at 12:04:22, Sune Fischer wrote: >>>>>>> >>>>>>>>On March 16, 2004 at 11:25:55, Vincent Diepeveen wrote: >>>>>>>> >>>>>>>>>On March 16, 2004 at 11:19:17, Renze Steenhuisen wrote: >>>>>>>>> >>>>>>>>>I principally agree with GCP here. I do not understand how in certain software >>>>>>>>>HH can work. Must be a bug in their move ordering IMHO. >>>>>>>> >>>>>>>>If you can't make them work, why do you reply to his post? >>>>>>>> >>>>>>>>-S. >>>>>>> >>>>>>> >>>>>>>Ignorance. Unabashed ignorance... >>>>>>> >>>>>>>What else? >>>>>>> >>>>>>>HH works just fine. Of course if Vincent can't get them to work, then it is >>>>>>>impossible that they will work for anybody. "proof" enough?? >>>>>> >>>>>>Yes, and this time the poster even gets to contact him personally for more >>>>>>information on how NOT to make them work! >>>>>> >>>>>>I admit I can see his point, precious secrets _like that_ are not to be posted >>>>>>in a public forum :) >>>>>> >>>>>>-S. >>>>> >>>>> >>>>>none of his "precious secrets" should be posted... >>>>> >>>>>:) >>>> >>>>Just try this - after the end of a 3 min search from a fairly complicated middle >>>>game position (like for example - Nxh6 nolot position) , print out the history >>>>values. >>>> >>>>You will see the junk that is contained in the table. >>> >>>Do you understand what this "junk" means??? >> >>Please print out the 64 * 64 values - and try to analyse them : you will get a >>better idea of what I am trying to convey. >>Assuming that you are searching for 3 mins at 500 knps (on my box crafty gives >>this much for a typical middle game pos)- that is around : 90 mln nodes. >>It is indeed very interesting to see these values after so many operations to >>the history table :) >> >>> >>>I don't see how it can be called "junk". The data simply reflects how useful >>>each move was in the search done. >>> >>>> >>>>If you seriously expect much of information to be obtained from this for move >>>>ordering - I dont know what to say. >>> >>>I feel the same, except in an inverse way. >>> >>>History works for me. Turn it off and the tree gets bigger. A couple of >>>samples: >>> >>> nodes w history nodes wo history >>>pos1 38,151,984 42,728,175 >>>pos2 167,685,660 184,874,107 >>>pos3 81,663,363 124,704,814 >> >>Can you give me the logs for this ? Especially the last data - I remember >>running some tests on crafty and having minimal effect on removing history >>tables from it. >>Also - for my initial expiriments before I wrote messchess , crafty with >>handtuned pcsq tables was performing better due to a more reduced tree. >> >>> >>>Now if you believe those three randomly chosen positions are worse because of >>>"random junk" feel free. The tree size is _remarkably+ smaller on pos 3, and >>>significantly smaller on the other two... >> >>As an example : static pcsq values gives much better numbers. >>I tried the pcsq values from your eval scaled by appropriate factor (*5 for >>knight , etc). >> >> >>> >>> >>> >>> >>>> >>>>I like some other mentioned here though - clear it x number of ply or y number >>>>of seconds - helps to reduce the randomness. >>> >>>Why would I want to do that? This data is useful all over the tree. This is >>>the very idea behind it. Killers are local. History is global. Use both. >> >> >>64 * 64 table is supposed to be representative in any way for 10 mln nodes ??? >> >>And considering that you do remaining_depth * remaining_depth as the increment >>for history table for a given move - i have noticed that lot of cases the >>history values just come back to zero due to overflow (in crafty - i dont use >>history) ! >> >>> >>> >>> >>>>Also Ed's idea is also somewhat better. >>>> >>>>I have not tried these , so cant comment - but helps in localising the effects >>>>to a smaller subtree where the tables could be potentially more relevent. >>>> >>>>But essentially , history tables in the general sense will detreriorate into >>>>random move ordering quiet soon for higher depth when number of nodes increases. >>> >>>Then explain how my "random move ordering" is way more efficient. You are not >>>understanding what goes on in the history heuristic within the tree... >> >> >>Suppose I take the approach of sorting moves as pawn moves first , knight moves >>next , then bishop , then rook , then queen then king - is there any logic >>behind this ? >>(Actually this is not as random or bad an idea as you might think it is) - do >>you know the effect on the game tree for this approach ? >>For some positions - this is way too good scheme actually ! >> >>Your data : >>pos1 38,151,984 42,728,175 -> 9.5% >>pos2 167,685,660 184,874,107 -> 9.2 % >>pos3 81,663,363 124,704,814 -> 34 % >> >>Isn't this itself not giving us some clue ? >>The move ordering is essentially random - just 'cos it affect some positions >>better than others does not mean anything. Same way , there are positions where >>history gives a negetive advantage (i mean - disadvantage) between history on >>and off. >>In the update formula history[from * 64 + to] += increment; >>If you try 2 * remaining_depth - you will get another set of values. >>If you try remaining_depth - another set , remaining_depth ^ 3 - another set , >>etc , etc , etc. >>Essentially you are not proving anything. >> >>The probability (since this is for all moves at current position from sqi to >>sqj) that a move from sq1 to sq2 caused a higher number of cutoff in the search >>tree in some arbitrary subtree is no way indicative of the goodness of a move in >>the current position under consideration. >>It is more like a vain hope that it worked better earlier , hoping it will >>continue to work now ! >> >>Also , please do note - crafty (afaik) has only a very primitive set of move >>ordering logic. >>I think the move-ordering order from my recollection is - >>1) hash move (could be iid move also ?). >>2) captures for which victim_see >= capturing_piece_see with MVVLA. >>3) 2 killers. >>4) 4 history moves. >>5) rest of moves. >> >>(Hope I did not get this wrong). >>That is - almost no move ordering logic. >> >>Even a pcsq logic here wold can only be an improvement ! >> >>> >>> >>>> >>>>Is that one of the reasons why you sort and try history scores for only first n >>>>(i think 4) number of history moves in crafty ? >>> >>>Nope. It is for efficiency. at ALL nodes ordering is irrelevant. If, after >>>the hash move, good captures, two killers, I can't get a cutoff on one of the >>>first four history moves, I give up as I probably won't get a cutoff at all. >>> >>> >>> >>> >>>> >>>>Maybe this could be an optimisation reason also - i dont know. >>> >>>It isn't anything but performance based... >>> >>> >>>> >>>>But if there is a possibility of hitting a better move earlier on using history >>>>tables , then shouldn't crafty not be trying it for all the moves ? - the gain >>>>could be potentially exponential in case of earlier cutoff ! >>> >>>I _do_ try it _everywhere_.... >> >>What I meant here (this is explaination for what I mention a few lines above >>also) is - >>If history is good - >>then you will get the next best move for all moves at current position based on >>the history table information - not only for first 4. >>Out of say 60 pseudo legal moves , at say depth 2 in a depth 10 search - if >>history really does work - wont such an approach have a much better tree >>shrinkage ? >>We are talking about theoretical efficiency of history tables here. >>Hope I am clear in what I am trying to convey here ... sleep does strange things >>to your mind ! >> >>Mridul >> >>> >>> >>>> >>>>Mridul
This page took 0.01 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.