Author: Uri Blass
Date: 01:52:39 03/30/04
Go up one level in this thread
On March 30, 2004 at 03:50:26, Tim Foden wrote: >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. ok suppose this position is not the root of the search This is the root and you search to depth 4. [D]7k/7p/7q/8/8/8/7P/2Q4K b - - 0 1 You are going to search Qxc1 last but you need to search both Qh5 Qd1 Qh4... and Qh4 Qe1 Qh5... if you want your search to be as worse as minimax. 1)suppose that you search Qh5 first After searching Qh5 you already have alpha near 0. Now at some point you search Qh4 Qg1 Qxh2+ and you know that black has at least a score near draw based on searching Qh5 so Qxh2+ cannot fail high and it is white who will fail high after it. 2)The second case is completely symmetric. Suppose that you search Qh4 first After searching Qh4 you already have alpha near 0. Now at some point you search Qh5 Qg1 Qxh2+ and you know that black has at least a draw so Qxh2+ cannot fail high and it is white who wil fail high after it. I proved that even without the assumption of equal score alphabeta cannot behave as worse as minimax for every order of moves. 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.