Author: martin fierz
Date: 00:50:33 03/30/04
Go up one level in this thread
On March 29, 2004 at 18:18:48, Uri Blass wrote: >On March 29, 2004 at 18:10:50, martin fierz wrote: > >>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 > >I already posted a counter example in the reply to my post > >You do not need dieter's example when evaluations are the same in order to have >situation when all moves fail high > >see http://www.talkchess.com/forums/1/message.html?357267 > >Uri that is not a counter example. a counter example has a real minimax tree which shows me where you fail high. obviously, you cannot fail high if beta is infinite. so the whole idea of searching the tree the wrong way round is that you start with beta = inf, then you look at stupid moves like Qxh2, but because beta is infinite, you don't fail high. instead, you reduce beta to something like +9 in your example, and continue the search, and still don't fail high in other nodes, because you searched the stupid move Qxh2+ first, which gave you the highest possible beta to start out with.... 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.