Author: Omid David Tabibi
Date: 07:45:36 10/12/03
Go up one level in this thread
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... > >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. > >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 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.