Author: Vasik Rajlich
Date: 01:43:20 03/18/04
Go up one level in this thread
On March 17, 2004 at 17:16:45, Mridul Muralidharan wrote: >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 ... > This is one of the few things I don't plan to test. I remember reading that PVS performs 10-20% better than pure alpha-beta, with MTD (f) about equal to PVS. >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 .... > Yeah, true, this is a big area. Actually secretly I hope to get rid of q-search completely and replace it with a static exchange evaluator. I don't trust a cheap q-search, and don't want an expensive one. This way, the search could concentrate on finding good positional moves. I made so far one experiment with this, and it killed my engine. (The loss in strength was >100 points) However the static evaluator was not very good. There are also issues with move ordering. With a good q-search, the easy tactics get sorted out more quickly, and you have better move ordering after the first few iterations. >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 ... > Perhaps you means "singular extensions" (yes I know it was 2:00 am :-)). Rybka also has a number of "selective extensions", it's the non-selective ones that I can't get to work :-) Cheers, Vas >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 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.