Alpha–beta pruning in non-binary-tree

Question

Is the classical Alpha–beta pruning code on c++ works with Non-binary-tree(3 or more children for node), because all examples of this code are used with binary trees, and when I run this code on VS, the real answer(on paper) and the result of the code are different.Is it normal? Here is the code from the internet:

#include <iostream>
#include <algorithm>
#include <cmath>
#include <climits>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int getHeight(int n) {
   return (n == 1) ? 0 : 1 + log2(n / 2);
}
int minmax(int height, int depth, int nodeIndex,
bool maxPayer, int values[], int alpha,
int beta) {
   if (depth == height) {
      return values[nodeIndex];
   }
   if (maxPayer) {
      int bestValue = INT_MIN;
      for (int i = 0; i < height - 1; i++) {  //MAYBE THE PROBLEM IS HERE??????
         int val = minmax(height, depth + 1, nodeIndex * 2 + i, false, values, alpha, beta);
         bestValue = max(bestValue, val);
         alpha = max(alpha, bestValue);
         if (beta <= alpha)
            break;
      }
      return bestValue;
   } else {
      int bestValue = INT_MAX;
      for (int i = 0; i < height - 1; i++) {
         int val = minmax(height, depth + 1, nodeIndex * 2 + i, true, values, alpha, beta);
         bestValue = min(bestValue, val);
         beta = min(beta, bestValue);
         if (beta <= alpha)
            break;
      }
      return bestValue;
   }
}
int main() {
   int values[] ={9,3,10,20,1,15,2,27,35,4,7,14,2,1,55,0,8,6,0,2,80,47,33,42,14,25,1 }; ////for example, 9,3 and 10 are the children of the same node
   int height = getHeight(SIZE(values));
   int result = minmax(height, 0, 0, true, values, INT_MIN, INT_MAX);
   cout <<"Result : " << result << "\n";
   return 0;
}

Answer 1

It looks like you have a tree defined in a heap structure.

You cannot really use this array structure for representing a tree if the number of children of a node is variable ("3 or more"). It is intended for trees that are complete:

• Each node has either k children or none, with the exception of one node, which may have any number of children between 1 and k (which are leaves).
• All the levels of the tree are completely filled
• Except maybe the last level which may be incomplete, but all the leaf nodes in that level should be at the left side of that level. The rightmost leaf of this bottom level is a child of the exceptional node mentioned in the first bullet point.

So if your tree follows those rules, then you still need to make some adaptations to your code, as it still refers to the case where k is 2 (binary tree).

From a comment in your code it seems that you don't store a value for the root of the tree (as you call 9 a child), so that the value at index 0 is a child of the root, not the root itself.

• The formula to know the height of the tree is: 1 + _⌊log_k(n+1)_⌋. The addition of 1 to n is to account for the missing root value.
• The number of children of a node is not dependent on height, but on k (which you should define, possibly as a constant). So your for loop should run k times.
• The index of the child is not nodeIndex * 2 + i, but nodeIndex * k + i