A MiniMax tree is an arborescent structure generated by an AI role-playing game (e.g., tic tac toe) to simulate the player and its opponent turns, giving scores to each these turns.

enter image description here

In the image above, $A$ is the player, $B$ is the opponent, $C4$ is the best tack chosen, using MiniMax.

When choosing $B1=3$ and $B2=5$, is it necessary to visit all child nodes of $B3$?

It apparently stops at $C8$, then stops 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 won't search any lower value than $2$, when it considers the maximum for $A$, which must be forcibly bigger than $5$.

The complete "Alpha-Beta Pruning" process is illustrated below.

enter image description here

After thinking for a while, I have deduced the presence of a system of mathematical inequalities that allows finding a structure of positive number labelled 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, 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 follows:

       --------------         ---------------
  ----------  ----------  ----------    ------------
  |        |  |        |  |        |    |          |
 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)+ \dots$ for binary trees defined in an infinite range of positive integers $]0,\infty[$ (with duplication).

The problem is wider than that. 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?

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)

I will conceive an example with non-empty set to reinforce my point of view ...


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.