Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: QNodes, Lead Nodes and Best Practice?

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.