Author: Dan Andersson

Date: 17:49:28 06/18/03

Go up one level in this thread

Doing some leafing through Knuth and some slight reasoning I came to derive the following formula. It is approximate. A more exact depends on depth being odd or even. A more exact one would also double the nodes approximately. b^l*n^l b is the branching factor of the tree l is depth/2 and n is P+(1-P)(b-1). P is the probability of choosing a cutoff in the first move. The 'constant' n is the number of nodes searched in the mean when move ordering fails to find the cutoff. Calcualting n is a bother but some tries are possible I chose the worst case here. That when cutoff fails I wont find it until the last move. Not because it is the only possibility. But to err on the side of caution. This gives an overhead of about 4.5 per two plies when P is 0.9 in chess. Not a reasonable number. Maybe n=P+(1-P)(b/2) is more reasonable giving the cutoff a flat distribution in the remaining moves. That gives an overhead of about 2.5 per two plies. The main point is that when P goes to 1 n also closes in on 1. And the size goes Hope I haven't made a mess when figuring this. MvH Dan Andersson

- Re: PVS and MTD(f) branching factor
**Dieter Buerssner***14:46:50 06/19/03*- Re: PVS and MTD(f) branching factor
**Dan Andersson***16:09:32 06/19/03*- A new look.
**Dan Andersson***02:41:04 06/20/03*- Re: A new look.
**Dan Andersson***03:05:38 06/20/03*- Re: A new look.
**Dan Andersson***03:32:48 06/20/03*- Re: A new look.
**Dan Andersson***06:52:49 06/20/03*

- Re: A new look.

- Re: A new look.

- Re: A new look.
- A Visualization link.
**Dan Andersson***16:15:28 06/19/03*

- A new look.

- Re: PVS and MTD(f) branching factor

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.