Maximizing pruned branches in an alpha-beta tree
Preliminary
After doing some searches of similar questions posted here and elsewhere, i feel like this is the right place to inquire about, now let's get through some boring main notations...
* A MiniMax tree is an arborescence structure generated by an AI role-playing game to simulate the opponent turns giving notes/scores to each of, and so each turn taken by the player itself, in order that a maximal value is chosen as the actual perfect step against the minimum value which represents the best step taken by the opponent.
in the image above A is the player, B is the opponent, C4 is the best tack chosen using MiniMax.
* First thing which would cross your mind, when chosing B1=3, B2=5, is it necessay to visit all child-nodes of B3?, of course the computer wouldnt act stupid if you code it to not be stupid, then it will stop at C8 then breaks the process, why? well that is called Alpha-Beta pruning, it cuts the C9 subtree and all its successors within the subtree B3 because it wont searcg any lower value than 2 when it does consider the maximum for A which must be forcibly bigger than 5. The all process is illustrated below for wiki-joint model.
After thinking a while, I have deduced the presence of a system of mathematical inequalities that allows finding a structure of positive number labeled tree-leafs forming a tree that generates a maximal number of branch-pruning.
Look here in this example in french, let us assign this data-configuration to terminal leafs ${6,7,1000,4,2000,3000}$ , 4 nodes (3 leafs in two subtrees) of this tree arent visited because:
$\begin{eqnarray} \left{ \begin{aligned} 7\;>\;6\ \ (1\ branch\ =\ 1\ leaf)\ 4\;<\;6\ (1\ node\ =\ 2\ leafs)\ \end{aligned} \right. \end{eqnarray}$
So as remarked that the inequality changes direction as long as we mount to higher levels of the tree.
from that base, maximizing branch pruning can be achieved by assigning alternatively bigger than smaller values for specific ranges of leafs, regarding a symbolic binary tree as follow :
|
----------------------
-------------- ---------------
---------- ---------- ---------- ------------
| | | | | | | |
x0 x1 x2 x3 x4 x5 x7 x8
As a beginning rule, opting for the maximum from the tree summit underlies the nature of values selected from the base, which is the maximum in this case, this gives a system of inequalities helping us to exclude maximum number of leafs from being visited.
$\begin{eqnarray} \left{ \begin{aligned} x_2\;>\;max(x_0,x_1)\ \ (1\ branch\ =\ 1\ leaf)\ max(x_4,x_5)\;<\;max(x_0,x_1)\ (1\ node\ =\ 2\ leafs)\ ...\end{aligned} \right. \end{eqnarray}$
Number of leafs we excluded is $1+2$ , generalized to $(1+2^1)+(1+2^2)+....$ for binary trees defined in an infinite range of positive integers ]0,$\infty$[ (with duplication).
The Question
Consider that tree is also parsed counter-clockwise, and we want to maximize the unvisited leafs when we parse a n-ary tree both directions as an intersection of two unvisited sets , is there a way to figure out a general system of inequalities for that ? a closed form for the maximum in terms of $n$ the level of this tree ? a O(N) algorithm working along this ground to output a data-set of corresponding leafs? 835