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.