Author: Anthony Cozzie
Date: 06:49:11 06/14/04
Go up one level in this thread
On June 14, 2004 at 09:08:14, Steve Maughan wrote:
>I've been tinkering with Monarch's qsearch and wondered if I could get some
>input from other engine authors as to best practice for the quiescent search.
>
>Take for example this random (TWIC500) middlegame position:
>
>[D]2r2rk1/1p1b1p2/1p4pp/3pPnQ1/3P4/5P1P/PPB2BP1/R3R1K1 b - -
>
>There's nothing special going on and here's Monarch's analysis:
>
>Engine: Monarch 1.1 (64 MB)
>by Steve Maughan
> 3/04 0:00 -3.78++ 24...hxg5 (729)
> 3/04 0:00 -1.52 24...hxg5 25.Bd3 Ne7 (861)
> 4/07 0:00 -1.48 24...hxg5 25.Bd3 Rfd8 26.g4 (2.388)
> 5/09 0:00 -1.51 24...hxg5 25.Bd3 Ne7 26.Be3 Nc6 (8.013)
> 6/11 0:00 -1.57 24...hxg5 25.Bd3 Ne7 26.g4 Nc6 27.Rad1 (18.410)
> 7/13 0:00 -1.51 24...hxg5 25.Bd3 Ne7 26.a3 Rfe8 27.Be3 Nc6 (64.452)
> 8/15 0:00 -1.49 24...hxg5 25.Bd3 Ng7 26.h4 gxh4 27.Bxh4 Ne6 28.Be7
>(218.401)
> 9/19 0:00 -1.49 24...hxg5 25.Bb3 Be6 26.g4 Nh4 27.Bd1 f6 28.f4 fxe5
>(629.445) 750
> 10/20 0:01 -1.48 24...hxg5 25.Bb3 Be6 26.g4 Nh4 27.Re3 f6 28.exf6 Rxf6 29.f4
>(1.060.099) 858
> 11/23 0:07 -1.47 24...hxg5 25.Bd3 Ng7 26.Be3 Ne6 27.g3 f5 28.f4 gxf4 29.gxf4
>Rfe8 (7.291.429) 895
> 12/24 0:12 -1.48 24...hxg5 25.Bb3 Bc6 26.Rad1 f6 27.Rd3 Rc7 28.g4 Ne7 29.e6
>f5 30.Bc2 (12.437.456) 945
> 13/28 0:19 -1.47 24...hxg5 25.Bb3 Bc6 26.Rad1 f6 27.Rd3 Rc7 28.a4 Rg7 29.g4
>Ne7 30.e6 f5 (18.894.237) 957
> 14/29 0:58 -1.47 24...hxg5 25.Bb3 Bc6 26.Rad1 f6 27.Rd3 Ng7 28.exf6 Rxf6
>29.Re5 Rf5 30.Re7 Re8 31.Rde3 (57.553.890) 964
> 15/16 1:22 -1.47 24...hxg5 25.Bb3 Bc6 26.Rad1 f6 27.Rd3 Ng7 28.exf6 Rxf6
>29.Re5 Rf5 30.Re7 Re8 31.Rde3 (79.374.564) 978
>best move: h6xg5 time: 1:22.929 min n/s: 957.369 nodes: 79.374.564
>Total Nodes : 79374564
>Quiescent Nodes : 26210648 (33.0%)
>Leaf Nodes : 38072779 (48.0%)
>Hash Probe Effectiveness: 28.2%
>Move Order Effectiveness: 93.1%
>
>I define leaf nodes as positions that return a score without calling any move
>generation routine; quiescent nodes are those that call a move generation from
>within the qsearch and the others are those that call a move generation routine
>from within the main search (alpha_beta) includung null moves.
>
>So you can see that of the 79 million nodes searched 26 million (33%) were in
>the qsearch. This seams a bit high to me considering that 38 million (48%) were
>leaf nodes. Currently I'm doing check in the first ply of the qsearch and SEE
>based pruning. The pseudo code looks like the following:
>
>if in_check
> generate all moves and handle as a normal node
>else
> e = evaluate();
> if (e>=a){
> if (e>=b){
> leaf_nodes++;
> return e;
> }
> a = e;
> }
>
> if (max_check_ply >= current_ply){
> move_count = generate_check_captures(); //GENERATE ALL GOOD CAPTURES &
>CHECKS (ONLY DONE ON THE FIRST PLY OF THE QSEARCH)
> }
> else if (e+90>a){
> move_count = generate_all_good_captures(); // GENERATE ALL GOOD CAPTURES
> }
> else
> //GENERATE ONLY THE GOOD CAPTURES THAT WILL GET THE SCORE CLOSE TO ALPHA
> move_count = generate_captures_with_threshold(p,a-e-90);
>
> Loop though all the moves as normal...
>
>Of course the '90' in the above pseudo code is somewhat arbitrary.
>
>So two questions:
>1. Are Monarch's ratios of qnodes and lead nodes to total nodes reasonable?
>2. What else can I do improve my QSearch?
>
>Thanks,
>
>Steve
Zappa searches about 80% q-nodes usually. I do checks on depths 1 & 2 of
q-search. I would like to eventually do checks at all depths in q-search, but
that requires some serious work on restricting the checks.
anthony
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.