Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: move ordering and node count

Author: Uri Blass

Date: 12:43:38 03/29/04

Go up one level in this thread


On March 29, 2004 at 15:22:50, martin fierz wrote:

>On March 29, 2004 at 14:30:17, Dieter Buerssner wrote:
>
>>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
>
>hi dieter,
>
>hmm, everybody writes this that making A/B MO as bad as possible you return to
>minimax. somewhere below gerd just made the same point as you did here. and if
>two experienced programmers like you say so, i am of course afraid to contradict
>you :-)
>but i have to contradict you all the same. in a perfectly misordered tree you
>will *never* fail high. which also means that the case that you and gerd were
>thinking of never happens.
>
>cheers
>  martin

I think that it is impossible never to fail high.
What do you do when all legal moves cause a fail high?

Uri



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.