Author: Vasik Rajlich
Date: 14:58:32 03/18/04
Go up one level in this thread
On March 18, 2004 at 15:31:29, Mridul Muralidharan wrote: >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). > I'm curious, what would be an example of a "pattern"? How many are there? I would guess that most "bad" check extensions are very shortly going to be followed by a successful null-move. >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 ! True, but that might well be better than a huge bloated program with rules everywhere tripping all over each other. I'm actually doing a huge simplification of my eval function at the moment ... > >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. Yes, it's amazing how often that's true. > > > >> >>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.