Author: Mridul Muralidharan
Date: 14:16:45 03/17/04
Go up one level in this thread
On March 17, 2004 at 16:53:00, Vasik Rajlich wrote: >On March 17, 2004 at 13:05:56, Mridul Muralidharan wrote: > >>Hi, >> Will post them in a day or two - wont make it to home early enough from work >>to do this tonight ... >> >>If you want to try this yourself , you could do this with crafty : >> >>1) Comment out the history updation code. (I think in history.c) >>2) Generate pcsq tables - these can be picked up from the evaluation logic >>itself and tuned. (static one time operation). >>Note - you might need to add additional info for rook - crafty pcsq for rooks >>are not sufficient - add something related to file_distance from enemy king or >>just plain distance from enemy king. >> >>3) In next.c , currently whereever crafty picks up the move score from the >>history (history_w , history_b) arrays , just use the pcsq tables to do the >>same. (pcsq[piece][to] - pcsq[piece][from]) >>(If your board design is non-bitboard based - then identification of the piece >>that moves becomes very cheap indeed ! - not that it will be very expensive in >>bitboarders) >> >>Now you are done ! >> >>My expiriments with my programs have given a definite plus towards handcrafted >>pcsq values. While history had a random + or - 5% tree size change which I >>attributed to noise. >>Note - there are indeed positions where every move ordering heurestic will be >>effective. >>In the case of history , if a few set of moves to a few set of positions (like a >>massive attack towards the king) lead to higher number of cutoffs and the best >>solution pv lines lie in such a direction , then the values for moves towards >>these squares will start getting a higher value resulting in better move >>ordering. >>But for quieter or more subtle tactical positions (where it is not a attack >>massively at king , etc theme) - history is almost same as random move >>ordering. >>Ofcourse , there will be very short term local effects that can be benificial >>when using history - which is what Sune Fischer and Gerd Isenberg are trying to >>capitalise on which can be good - but on a more general case , not much use. >> >>You can always add bonuses to various types of moves by doing a lowlevel pseudo >>analyis of the moves depending on how slow you want your mode ordering to be :) >> >>My take is, history table is just too generic data collected over a large set of >>unrelated positions. Trying to use this in a particular set of moves for a given >>position is almost futile. >> >>I have not tried what Sune Fischer suggested , though I have tried some of the >>ideas mentioned by Gerd Isenberg (not all). >> >>As you will be knowing much better than me , each piece tends to be more >>effective in a few squares - for non capture moves , makes sense to try to put >>these pieces there first ! >> >>Asuming that tactically better moves could be found eariler from such a generic >>table _after_ you have tried - >>a) hash move >>b) all possible winning captures , and >>c) killers >>(by the way , please try the advantages of using 2(or more) killers each from >>current_ply and current_ply - 2 : even Ed Schroeder mentions this in his site) >> >>seems a bit farfetched to me. More like trying to take a guess at what is the >>hidden number out of 1000 choices ;) >> >>Move ordering in an interesting problem in itself - very small improvements here >>could lead to exponential improvement in search since your search tree may get >>reduced dramatically. >>Hence I spent quiet sometime on this - which now I think I should have spent on >>tweaking my eval ;) >> > >Hi Mridul, > >Yes, move ordering is an intesting problem. I need to do quite a few tests, to >see if my intuitions are right. > >Generally, as I see it, there is some balance between ordering moves cheaply and >ordering them well. You can always order moves better by doing more work. The >question is, what do you gain? In an MTD (f) search, the answer usually is: >nothing. (I also think this applies to PVS search.) > >If you're at a fail-low node, move ordering doesn't matter at all. If you're at >a fail-high node, you'll mostly fail high on the hash move. If the hash move >fails low, you're probably failing low. If you're failing high and there is no >hash move, you will often fail high with multiple moves (for example, near the >leaves, up material). If you have no hash move and there is only one fail-high >move, then it is usually either a winning capture or a killer move. In all of >these above scenarios, which cover the vast majority of interior nodes, your >move ordering doesn't matter past good captures and killers. > >So, there are only a few nodes where you will profit at all from a better move >ordering of the big mass of positional moves. Intuitively, I'd expect that the >best approach is something simple and cheap - and history tables fit the bill. > >There may also be some relationship between the speed of your engine and the >quality of move ordering. The lower your NPS count, the more it makes sense to >order your moves well. (In fact, to do everything well.) > >Anyway this is one of about 250 things which needs revamping & testing in my >engine. I'll let you know if I find anything interesting ... > >Cheers, >Vas > >> >>Mridul Hi Vas, Good summary - I was reading a paper about belle recently , maybe you could give that a try too - i googled for it and got it ... (url is at home - it is bloody 2 at night and still in office :( ) Also , in case you want to expiriment with search and move ordering and if you do have a good evaluation (I expect you to have this soon if you dont have this already ! , considering you are a master player and would very soon try to incorporate some of your positional and tactical understanding of a position into the eval of your engine) you could try the following : Dont use pvs or negascout of mtd(f) or other such null window approaches. Just use plain alphabeta with a bit expensive move ordering. This not only can be useful in allowing you to "waste" time in attempting better move ordering , but now you can also try out all sort of more complicated (and so more code to be executed) pruning techniques since it does not become as costly to do so now. You will not be keeping on re-searching the same position/node with different windows quiet as frequently as before. This would also "reduce" the cost of some extensions like singular extensions. If you do look more closely , rebel does something like this according to the published page by Ed Schroeder - he says that he does not use "null window tricks". This technique did not work well for me in mess and in current version - but it is a very very interesting technique and I will keep revisiting this in the future (as I have been doing in the past 2 years !) in case I can think something more or improve it more ... Another area of interest for me is QSearch - this is a veritable gold mine when it comes to improving a chess program and to play around and research in. Lots of ideas can be tried here .... Ofcourse , when it comes to search base extensions , reductions , etc - lot of it gets discussed at CCC - Tord , etc will be help you more on this. I practice selective extensions though , which does not seem to be very common other than in some commercials and some private engines ... Search , Qsearch , eval , move ordering and MP - these are my interests in chess (did I miss out any other aspect in chess programming ? ;) ) Best Regards 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.