Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: move ordering and node count

Author: Dieter Buerssner

Date: 11:30:17 03/29/04

Go up one level in this thread


On March 29, 2004 at 10:17:18, martin fierz wrote:

>aloha!
>
>i was discussing this somewhere in a thread, but thought i'd like to make this
>question more visible in the hope of getting a good answer:
>
>everybody knows that with plain alpha-beta, a fixed number of moves N per node,
>and perfect move ordering a search to depth D needs
>
>nodes(depth) = sqrt(N)^(D/2) nodes.
>
>with absolutely imperfect move ordering it needs
>
>nodes(depth) = N^(D) nodes.

This has not so much to do with your question, but I doubt the last part of your
sentence. I believe, it will be impossible to become as bad as the minimax tree,
even when by purporse ordering the moves "perfectly wrong". You will still have
plenty of situations, where many different moves give a cutoff. In a previous
experiment, I got 50% beta cutoffs for the first move, when randomizing the move
order. Note that this is far away, from a minimax tree (where you would need
100% beta cutoffs in the last tried moves - there are in general many more move,
you try before).

Regards,
Dieter




This page took 0.01 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.