Author: martin fierz
Date: 04:37:28 03/30/04
Go up one level in this thread
On March 30, 2004 at 06:42:29, Uri Blass wrote: >On March 30, 2004 at 05:37:17, Tim Foden wrote: > >>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. > >My example is correct. > >I am not talking about 1...Qxh2+ but about 2...Qxh2+ > >look at the following 2 lines: > >Qh5 Qg1 Qxh2+ >Qh4 Qg1 Qxh2+ > >I claim that at least one of the Qxh2+ in these lines is not going to fail high > >Let assume without loss of generality that Qh5 is searched before Qh4 >I claim that when we search Qh4 Qg1 Qxh2+ we already know that black is not >losing based on searching the Qh5 line so Qxh2+ is going to fail low against the >first move of white. > >The point is that after Qh4 Qg1 Qxh2+ first move of white fail high when white >has 2 legal moves and we always avoid searcing the second move. > >Uri hi uri, point taken - i now understand your example and agree that you are right. i now think that if you want to degenerate your A/B-search into a minimax search, you need not only a totally wrong-ordered search tree, but also certain properties of the value in the search tree to hold. for example, if you draw a minimax tree up to an odd depth D which you search from left to right, and assign the N leaves values 0.....N-1 from left to right, then you can never fail high anywhere. obviously this case is totally unrealistic, and even impossible for large N as dieter has pointed out - the eval function can typically only reach a finite number of values, so that for large N you cannot construct such a tree. but even if you produce a random tree (in the sense that you assign the leaves values from 0...N-1 randomly), and then proceed to search it in the worst way possible, you will be much more efficient than minimax, as you have pointed out. cheers martin - who has just learned something :-)
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.