Author: Tim Foden
Date: 00:50:26 03/30/04
Go up one level in this thread
On March 29, 2004 at 15:50:41, Uri Blass wrote: >On March 29, 2004 at 15:49:40, Uri Blass 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 >> >>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 > >I mean clearly smaller. As we are comparing plain minimax with alpha-beta, we should be starting alpha-beta with -infintiy...+infinity as the limits, for a theoretical comparison. Obviously if you start the search with reduced limits due to Aspiration search, then your example would fail high, but if the limits were -inf...+inf then it is not true that qxh2+ would necessarily fail high. Cheers, Tim.
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.