Author: Christophe Theron
Date: 01:22:48 10/14/03
Go up one level in this thread
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.
Christophe
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.