Author: José Carlos
Date: 23:46:18 10/14/03
Go up one level in this thread
On October 12, 2003 at 11:49:49, Omid David Tabibi wrote: >On October 12, 2003 at 11:13:22, Andrew Williams wrote: > >>On October 12, 2003 at 10:45:36, Omid David Tabibi wrote: >> >>>On October 12, 2003 at 08:25:27, Andrew Williams wrote: >>> >>>>On October 12, 2003 at 07:35:57, Omid David Tabibi wrote: >>>> >>>>>On October 12, 2003 at 07:24:51, Uri Blass wrote: >>>>> >>>>>>On October 12, 2003 at 06:32:25, Omid David Tabibi wrote: >>>>>> >>>>>>>Recently I conducted some extensive experiments with two versions of Falcon, one >>>>>>>with checks in quiescence and one without. Falcon already has lots of >>>>>>>extensions, but adding checks in quiescence resulted in a significant boost for >>>>>>>tactical strength. >>>>>>> >>>>>>>I tested the following options: >>>>>>> >>>>>>>a) checks everywhere in quiescence >>>>>>>b) checks only in the first ply of quiescence >>>>>>>c) no checks in quiescence >>>>>>> >>>>>>>Option 'a' was ruled out after some testing, as it resulted in a total explosion >>>>>>>of quiescence search. I tried controlling it in some ways, but still the >>>>>>>overhead was considerably more than the benefit. It seems that The King and >>>>>>>HIARCS are the only engines using this method. >>>>>>> >>>>>>>Option 'b' produces almost the same tactical strength as option 'a', with a >>>>>>>considerably lower overhead. The most significant contribution of checks in the >>>>>>>first ply of quiescence seems to be in conjuction with null-move pruning near >>>>>>>leaf nodes: >>>>>>> >>>>>>>For example at depth = 3, using R = 2, the null-move search will be called with >>>>>>>a depth of 0, i.e., direct call to quiescence search. Here the presence of >>>>>>>checks in the first ply can return a checkmate value which will result in an >>>>>>>extension to main search (mate threat extension). >>>>>>> >>>>>>>Only using checks in the first ply of quiescence, Falcon managed to solve almost >>>>>>>all tactical positions of LCTII in less than 1 second, outperforming the normal >>>>>>>version (no checks in quiescence). But adding checks in quiescence (although >>>>>>>only at its first ply) significantly slowed down the engine (from average of >>>>>>>350kNPS to 150kNPS on my PIII/733MHz) and resulted in a worse branching factor. >>>>>>> >>>>>>>Next I conducted some self-play matches between the two versions, and also some >>>>>>>matches versus other engines. >>>>>>> >>>>>>>The results of the matches were quite interesting. The version with checks in >>>>>>>quiescence not only didn't outperform the normal version in actual games, but >>>>>>>produced slightly inferior games in general. I especially conducted a few tens >>>>>>>of matches for each version against Crafty. The normal version beat Crafty by >>>>>>>something like 60%-40%. The version with checks in quiescence scored 50%. >>>>>>>Whenever the game turned tactical it literally butchered Crafty, but on normal >>>>>>>quiet positions Crafty once and again made a mincemeat of it by simply searching >>>>>>>deeper, which resulted in a better positional play. >>>>>>> >>>>>>>So, it seems that adding checks in quiescence is great for solving tactical test >>>>>>>suites, but not so for actual game play. The same goes for some of the >>>>>>>aggressive extensions I tried; great for tactics, poor in games. >>>>>>> >>>>>>>I'd be interested to hear others' thoughts on this issue. >>>>>>> >>>>>>>I also considered using some form of static mate threat detection, independent >>>>>>>of null-move search, but haven't found any interesting way to do so yet. Also, >>>>>>>Falcon does not detect checkmates statically in eval(), but only when one side >>>>>>>doesn't have any legal moves, i.e., it needs an additional ply to see the >>>>>>>checkmate. But I don't think the latter is any important, since when the other >>>>>>>side is checked, a check extension is already done, which will result in the >>>>>>>detection of the checkmate. >>>>>> >>>>>>How can checks only in the first ply of the quiescence >>>>>>do your program more than twice slower in nodes per second? >>>>>> >>>>>>Did you profile your program to see what parts it waste more time on them? >>>>> >>>>>Falcon's quiescence uses SEE to prune losing captures. Also its gen_captures() >>>>>function is very fast because of the attack tables. But adding checks requires >>>>>generation of all moves (a costly operation), and doing a makemove() for each of >>>>>them to see whether they check the opponent (makemove is the most expensive >>>>>function in the program, since the attack tables are dynamically updated there). >>>> >>>>Hi Omid, >>>> >>>>I have a move_gives_check_or_promotes(move mv) function which I use in certain >>>>places (there's an associated gives_discovered_check(..)). At the time >>>>implemented it, this was a lot faster than doing the make_move(..), for the same >>>>reasons that you give. However, I'm afraid I can't remember exactly how much >>>>faster. Do you have a get_me_out_of_check() move generator, for the case when >>>>the King is in check? Or do you just generate (and make) all moves again if the >>>>King is in check in the Qsearch? >>> >>>Generate all moves and do makemove() in an inefficient way... >>> >> >>My get_me_out_of_check() function generates captures of the attacking piece, >>then if it's a sweeper it walks between king and attacker generating blocking >>moves. Finally it looks at the King's escape squares to see if they are >>clear/attacked. The nice thing about this is that you can use your attackboards >>to do lots of this work. The nasty thing is that if you use it in the normal >>search, you run the risk of appalling losses until you iron out all the bugs. >>Caveat emptor (I don't know what "user of a technique" is in Latin). > >Good idea. Will try to implement it tonight, but it would be hard to debug since >I cannot compare the new nodes count to the old one as the order of moves will >change using the new check evasion move generator. Using this move generator >also helps in knowing the exact number of legal moves, which can be used for one >reply extension. > >I believe this will result in some speedup in normal search, but the big issue >in doing checks in quiescence will still remain generating checking moves not >check evasions. I haven't found a good way for doing so using the 32 bit attack >tables. Don't forget double checks. If two pieces attack your king then only king moves can get out of check. Capturing one of the checking pieces is not enough (unless it's the king that captures and the piece is undefended). José C. >> >>>> >>>>I found your post interesting, as I have experimented many times with generating >>>>checks in the first ply of quiesce(); each time I have had promising results, >>>>but never quite good enough to justify the extra complexity. >>> >>>That was what I thought, as I use an attack table scheme very similar to yours >>>(32 bit). It is very slow and painful to update it dynamically in makemove() but >>>it pays off in the evaluation function (mainly for king attack evaluation), and >>>in a very efficient capture moves generations. It also works great in SEE. >>> >> >>Yes. I can't help feeling that it *should* be possible to make it work. The idea >>of an intermediate search which does more than the qsearch but less than the >>main search is something I return to every now and again. >> >>Andrew
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.