Author: Mridul Muralidharan
Date: 14:50:02 03/16/04
Go up one level in this thread
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 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.