Author: Uri Blass
Date: 03:42:29 03/30/04
Go up one level in this thread
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
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.