Author: Andrew Williams
Date: 05:25:27 10/12/03
Go up one level in this thread
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? 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. Andrew >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. > > >> >>My experience when I first tried was better result in test suites when there was >>not significant change in the level in games. >> >>I decided to keep it because I knew that my implementation is not optimal and I >>may earn later by pruning some of the checks. >> >>I later discovered bugs in my implementation that I fixed(for example returning >>wrong mate scores from the quiescence) >> >>I also decided later to prune part of the checks in the qsearch when the >>attacker can be captured and is not defended. >> >>I did not compare last version with no checks in the quiescence. >> >>Uri
This page took 0.01 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.