Author: martin fierz
Date: 15:10:50 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 hi uri, they won't. simply because you are looking at them in the wrong order. you can draw up a minimax tree which is perfectly ill-ordered and see what happens. you can only fail high if you already have a limit to fail high against. because the tree is ordered the wrong way, you don't get that limit. at least that's what i think is the case here - but i might well be wrong :-) in my attempts to draw trees and understand this, i could not find fail highs in trees ordered the wrong way round. if you find a counter-example, you can prove me wrong... cheers martin
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.