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