Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: PVS and MTD(f) branching factor

Author: Bo Persson

Date: 03:25:20 06/19/03

Go up one level in this thread


On June 18, 2003 at 12:56:36, Russell Reagan wrote:

>On June 18, 2003 at 04:24:00, martin fierz wrote:
>
>>better move ordering reduces the branching factor! you can easily see that from
>>best/worst case which is sqrt(N)(best) and N(worst) as branching factor for
>>alpha beta. that's not a constant speed improvement then...
>
>Hi Martin,
>
>Sorry if I wasn't very clear.
>
>I was wondering if pvs/mtd(f) with perfect move ordering led to a decrease in
>the branching factor over alpha-beta with perfect move ordering, or only a
>constant speedup. Better move ordering does lead to a reduced branching factor,
>but I was wondering about the situation where all 3 algorithms had perfect move
>ordering already.
>
>So, I am not talking about the improvement where you go from an N branching
>factor to a sqrt(N) branching factor, but when you go from alpha-beta with
>perfect move ordering, to pvs/mtd(f) with perfect move ordering.

But you don't have perfect move ordering. If you had, you could just generate
the PV and be done with it. :-)

When you have a perfect move ordering in finite time, you can solve the game of
chess in one run of the program. Maybe that is the problem with your question?


>
>Does this make it more clear?
>
>Thanks,
>Russell



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.