Author: Robert Hyatt
Date: 06:28:13 10/16/03
Go up one level in this thread
On October 15, 2003 at 02:46:18, José Carlos wrote: >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. If you look at Crafty's "GenerateCheckEvasions()" this is handled as a special case. IE if more than one piece checks the king, then only king moves are even considered. > > > >>> >>>>> >>>>>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.