Author: Mridul Muralidharan
Date: 12:31:29 03/18/04
Go up one level in this thread
Hi Vas, My comments inline Thanks Mridul On March 18, 2004 at 04:43:20, Vasik Rajlich wrote: >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. I was not sucessful in getting rid of QSearch with a Static Exchange Evaluator. But I really dont know whether I would like to go in that direction. Tactics - as in capture/promotions are not the only non-quiescent moves that are possible in a position. Forks , attacking a higher valued piece which has no escape , checks , etc are all quiet dangerous and make the position unstable enough to make the evaluation of that position unreliable (unless you manage to include all this in the eval that is :) ) Getting all these into QSaerch without blowing it out of propotion is not exactly as tough as it sounds ..... and not as costly ! (If you compare the complete picture that is : with all this and without all this : strength improves for me). > >>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 :-)). Actually I meant selective extensions. I had already posted this idea sometime back , but most people rejected it here - though some found it interesting and did try it :) Some day in the future , I will publish this on my website with all the patterns and possibly the code , but for now , it remains with me and very few of my close friends. Let us take checks for example - if you just list the moves for which you are going to extend , you will see that most of them are really crap moves. (This is how I came about developing this). Next I wanted to eliminate extending these obviously useless checking moves - this lead to a bunch of patterns. When I implemented these , my engine strength went down ! When I analysed why, I found out a set of pretty valuable patterns which have to be excluded which I was not taking care of - added them , improved a strength bit. Repeat the cycle. In the end after naerly 4 months of this sort of gruelling work , I succeeded in eliminating extending almost all useless checks. (Almost - since there were some positions which were just too tough to identify and which I just extend - but this is < 1% of all extended checking moves). Note - my idea in doing all this was not to make the strongest possible engine , etc , etc. I dont know how much all this was justified - the strength was better , and at deeper ply depths , it had a smaller tree due to better branching factor. (This is one reason why I always maintain that you cannot compare blitz with standard games - contrary to what most people preach here at CCC). Something interesting , something different and something that made me think analyse and improve my program. Thats all this excerise was for :) Ofcourse , you can kick out all this out , use cheap move ordering , use cheap eval , use brute extensions , use cheap move generation like what vincent described and come up with a program that resides in L1 cache that does 1.5 mln nps on a 1 gig machine - but will I be satisfied with it ? NO!! :) I have not achieved anything other than an optimisation excerise ! By the way , I use singular extensions too - and in my latest program , which I will be releasing pretty soon - they work like a charm ! They give me tremendous tactical strength. Best Regards Mridul PS : I doubt I can make those pcsq values today too ... sorry about it - but I see some related posts so maybe one of them might have answered your questions. Only suggestion that I can give is - Dont believe any of that data ! Try it out for yourself in your engine and then believe it :) Most , if not all, heurestics and techniques are quiet heavily influenced by the engine on which you are trying it. > >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.02 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.