Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: move ordering and node count

Author: Uri Blass

Date: 12:49:40 03/29/04

Go up one level in this thread


On March 29, 2004 at 15:43:38, Uri Blass wrote:

>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

Let take for example the following position

[D]7k/7p/8/8/7q/8/7P/6QK b - - 0 1

When you search Qxh2+ what do you search for white in order not to fail high.
The answer is that there is no move for white that does not fail high so your
tree is clearly bigger than the tree when you use minimax.

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.