Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.javascript > #28532

Re: Time complexity and division

Show all headers | View raw

On 6/21/15 4:01 PM, Evertjan. wrote:
> Ah yes, here it is:
>
> "Alpha–beta pruning is a search algorithm that seeks to decrease the number
> of nodes that are evaluated by the minimax algorithm in its search tree."
> [Allen Newell and Herbert A. Simon, 1958].
> <https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning>
>
> "A minimax approximation algorithm [..] is a method to find an approximation
> of a mathematical function that minimizes maximum error."
> <https://en.wikipedia.org/wiki/Minimax_approximation_algorithm>
>
> Deep Alpha-Beta Pruning: An alpha or beta cut-off value may be used to prune
> trees at any node which is an even number of levels below it
> [Alpha-beta Pruning Algorithm, Fuller, Gaschnig and Gillogly, 1973]
>
> ========================
>
> Odd that an odd number of levels was even disregarded,
> perhaps as it would give a unacceptable bias?
>
> Indeed this may have been decisive in combatting the time complexity
> of the primitive calculating machines used during that computer stone-age.
>
> Perhaps Jonas was still inside the whale at that time?
>

I think the even number of layers is due to the fact that even layers 
and odd layers are acting different. For example, even layers may be 
maximizing, while the odd layers are minimizing, or even layers are my 
choices, odd layers are my opponents.

If I currently have a value of X and I am the maximizer, then if some 
odd layer below currently can say no higher than Y, less than X, then I 
can prune all the unevaluated even nodes just below that layer, as I 
know that I will chose a path that avoids this node, since I know I can 
do better. (I can't 'prune' the node that said Y, as I have already 
started to evaluate it, the best I can do is prune everything 
unevaluated just below it and thus finish the evaluation of that node. I 
don't get the real answer for that node, but I know that the even node 
above it either has a better option to take, or some higher even node 
has a better option and I won't get to here).

An alternative description would be that we can prune off (and abort the 
calculation of) any odd branch that we know we won't enter as we have 
better choices. In that model WE can't prune even branches as those are 
based on our opponents move, those will get pruned when we flip our 
brain and start to think of what they should do for each of the 
positions we are thinking of giving them. THEY will prune off the even 
branches. Mathematically, it seems preferred to described the nodes 
pruned as those never evaluated, as opposed to those whose evaluations 
are not completed.

Similar logic to prune out an odd layer would look at the value of the 
even layer above it and compare that to some odd layer above it. But, we 
do the pruning based on a node, and that node it the base, which is 
called level 0 (or even), so an pruning can't occur there (it might 
happen when we recurse, and effectively swap the definition of even and 
odd layers are reverse the value function).

Back to comp.lang.javascript | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

Time complexity and division jonas.thornvall@gmail.com - 2015-06-20 04:21 -0700
  Re: Time complexity and division Scott Sauyet <scott.sauyet@gmail.com> - 2015-06-20 18:08 -0700
    Re: Time complexity and division jonas.thornvall@gmail.com - 2015-06-21 00:23 -0700
    Re: Time complexity and division jonas.thornvall@gmail.com - 2015-06-21 01:01 -0700
      Re: Time complexity and division "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2015-06-21 10:09 +0200
        Re: Time complexity and division jonas.thornvall@gmail.com - 2015-06-21 02:48 -0700
          Re: Time complexity and division jonas.thornvall@gmail.com - 2015-06-21 03:02 -0700
          Re: Time complexity and division "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2015-06-21 21:43 +0200
  Re: Time complexity and division Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-06-21 12:35 +0100
    Re: Time complexity and division "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2015-06-21 22:01 +0200
      Re: Time complexity and division Richard Damon <Richard@Damon-Family.org> - 2015-08-15 11:02 -0400

csiph-web