4
$\begingroup$

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.

enter image description here

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.

enter image description here


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?

Right firstmost example of a trenary tree there was 3 cuts (1 of them is potential) at C5, C9 which results in 3 unvisited leafs (C5,C6,C9)

Parsing same tree right-to-left results in 1 cut (C2) which means 2 unvisited leafs, the overall (intersection) is 0 (all nodes are visited)


My progress:

  • After diving quite deep into this tree, I could calculate the minimal number of survivng leafs from one of either both directions as:

$U(0) = n $

$U(1) = n+n-1$

$U(k) = U(k-1)+(n-1)U(k-2)$

Where : n is the degree of this complete and balanced graph, k is the depth.

an illustration with a trenary graph, and system of inequality where the formula is bounded by:

enter image description here

Number of visited leafs here:

$U(0) = 3 $

$U(1) = 3+1+1$

$U(k) = U(k-1)+(2)U(k-2)$

Considering both directions now, for graph degrees > 2, the minimal of surviving leafs are $2U(k)$ where they cant be intersected for trenary graphs or bigger, that means the unvisited leafs are $n^k-2U(k)$, I am still wondering what is the overall system of inequalities which generates these special configurations of integer leaf-labels.


$\endgroup$
  • 1
    $\begingroup$ Please clarify what exactly your question is, and formulate a fitting title. $\endgroup$ – Raphael Jun 21 '16 at 8:57
  • $\begingroup$ @Raphael a closed form + system of inequalities $\endgroup$ – Abr001am Jun 21 '16 at 9:19
  • 1
    $\begingroup$ Those are words, not a question. Anyway, I see that you put your question under "the problem" and not "the question"; that's potentially confusing. $\endgroup$ – Raphael Jun 21 '16 at 9:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.