Author: Tim Foden
Date: 02:37:17 03/30/04
Go up one level in this thread
On March 30, 2004 at 04:52:39, Uri Blass wrote: >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 Obviously true... but we are not talking about *every* order of moves... we are looking for a *single* order of moves which would reduce the alpha-beta search to a minimax search. Thus your example would not be correct, as we would in this case search Qxh2+ *before* either Qh5 or Qh4 (as Qxh2+ is worse than either). 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.