Author: Vasik Rajlich
Date: 13:53:00 03/17/04
Go up one level in this thread
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
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.