Author: Uri Blass
Date: 04:23:46 10/14/03
Go up one level in this thread
On October 14, 2003 at 07:17:27, Omid David Tabibi wrote: >On October 14, 2003 at 04:46:19, Omid David Tabibi wrote: > >>On October 14, 2003 at 04:22:48, Christophe Theron wrote: >> >>>On October 14, 2003 at 02:53:04, Tony Werten wrote: >>> >>>>On October 13, 2003 at 18:19:06, Omid David Tabibi wrote: >>>> >>>>>On October 13, 2003 at 08:08:15, Omid David Tabibi wrote: >>>>> >>>>>>On October 13, 2003 at 07:51:47, Tony Werten wrote: >>>>>> >>>>>>>On October 13, 2003 at 04:47:28, Omid David Tabibi wrote: >>>>>>> >>>>>>>>On October 13, 2003 at 02:28:46, Tony Werten 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). >>>>>>>>>>And considering that more than 75% of the nodes in a normal search are in >>>>>>>>>>quiescence, and most of those nodes are at depth = 0 (i.e., the first ply of >>>>>>>>>>quiescence), no wonder that the slowdown is so steep. >>>>>>>>>> >>>>>>>>>>I can optimize this a little by using a gen_checking_moves() function, instead >>>>>>>>>>of generating all moves, but the slowdown will remain significant even in that >>>>>>>>>>case. >>>>>>>>> >>>>>>>>>Nope, not if you do it right. >>>>>>>>> >>>>>>>>>You already have done the hard work, why not use it ? >>>>>>>>> >>>>>>>>>Take the position of the opponent king, generate all knight moves from that >>>>>>>>>square, look in your attacktables if you attack these squares with a knight. >>>>>>>>> >>>>>>>>>If yes, you have a knight checkmove. >>>>>>>>> >>>>>>>> >>>>>>>>I was thinking about this overnight, and this seems to be a good way of doing >>>>>>>>it. Starting from the king's square I should scan all diagonals, columns and >>>>>>>>ranks, until reaching a blocking piece. >>>>>>> >>>>>>>Yes, except that if the piece is of color "side to move", you should continue >>>>>>>the scan. >>>>>> >>>>>>Ah yes, discovered checks! >>>>> >>>>>And also weird cases involving ep: >>>>> >>>>>[D]8/8/8/1k1pP1R1/8/8/8/4K3 w - d6 0 2 >>>>> >>>>>The move exd6 is a checking move. sigh... >>>> >>>>Skip it. >>>> >>>>Tony >>> >>> >>> >>>Yes. Do yourself a favor and ignore this case. You will *NEVER* notice the >>>difference. >>> >> >>Ah yes, ep checking captures can be totally ignored in quiescence, since they >>will be generated anyway as part of non-losing captures... > >Actually it seems that it is safe to ignore all capturing checks altogether in >gen_checks(). If the capture is non-losing, it will already be generated, and if >it is a losing capture, the odds that it turns out to be a good move aren't that >high (assuming that SEE hasn't mistakenly deemed the move as losing capture, >while in fact it is a winning capture since one of the defenders is pinned...) There are more possible reasons(for example the defender stop defending another piece). Uri
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.