example minimax implementation

minimax.c

/*---------------------------------
 minimax example

     /        |            \
   /  \      / \       /   |   \
  /\  /\    /\ /\     /\  /\   /\
 2 7 8  1  4 5 9 0   3 6 5 1  2  1

becomes
               7
      /        |            \
      7        5            2
    /  \      / \       /   |   \
   7   8     5  9       6   5    2
  /\  /\    /\ /\     /\  /\   /\
 2 7 8  1  4 5 9 0   3 6 5 1  2  1

aka player 1 will take the left branch to 7,
player two will take the left branch to 7,
player 1 will take the right branch to 7.
-----------------------------------------*/

#include <iostream>
#include <search.h>

#define MAXNUMCHILDREN 7
#define MAXDEPTH 8

struct node {
    size_t nchildren;
    struct node *children[MAXNUMCHILDREN];
    int value;
    int* path;
};

struct node* nodealloc(int value) {
    struct node* nd = (struct node *) malloc(sizeof(struct node));
    nd->path = (int *) malloc(sizeof(int) * MAXDEPTH);
    nd->value = value;
    nd-> nchildren = 0;
    return nd;
}

struct node* defaultnode() {
    return nodealloc(-1);
}


// add children left to right
struct node* add(struct node* nd, int value) {
    struct node* child = nodealloc(value);
    nd->children[nd->nchildren] = child;
    nd->nchildren++;
    return nd;
}

struct node* adddefaultchildren(struct node* nd, int nchildren) {
    for (int i = 0; i < nchildren; i++) {
        nd = add(nd, -1);
    }
    return nd;
}

struct node* getchild(struct node* nd, int childindex) {
    return nd->children[childindex];
}

// preorder print
void printtree(struct node* nd) {
    if (nd != nullptr) {
        printf("%d ", nd->value);
        for (int i = 0; i  < nd->nchildren; i++) {
            printtree(nd->children[i]);
        }
    }
}

struct result {
    int value;
    struct node* nd;
    int path[MAXDEPTH];
    int pathdepth;
};

void printgamepath(struct result *r) {
    printf("game path:\t");
    for (int i = 0; i < r->pathdepth; i++) {
        printf("%d ", r->path[r->pathdepth - i - 1]);
    }
    printf("\n");
}

struct result* resultalloc() {
    struct result* r = (struct result*) malloc(sizeof(result));
    r->pathdepth = 0;
    return r;
}

struct result* minimax(struct node* nd, int player) {
    struct result* r = resultalloc();
    r->nd = nd;
    if (nd->value == -1) {
        struct result *c;
        int branchindex;
        if (player == 0) {
            int maxvalue = -1;
            for (int i = 0; i < nd->nchildren; i++) {
                c = minimax(nd->children[i], 1);
                r->pathdepth = c->pathdepth + 1;
                if (c->value > maxvalue) {
                    maxvalue = c->value;
                    branchindex = i;
                    memcpy(r->path, c->path, sizeof(r->path));
                    r->path[r->pathdepth-1] = branchindex;
                }
            }
            r->value = maxvalue;
        } else {
            int minvalue = 123123213;
            for (int i = 0; i < nd->nchildren; i++) {
                c = minimax(nd->children[i], 0);
                r->pathdepth = c->pathdepth + 1;
                if (c->value < minvalue) {
                    minvalue = c->value;
                    branchindex = i;
                    memcpy(r->path, c->path, sizeof(r->path));
                    r->path[r->pathdepth-1] = branchindex;
                }
            }
            r->value = minvalue;
        }
    } else {
        // leaf node case
        r->value = nd->value;
        r->pathdepth = 0;
    }
    nd->value = r->value;
    return r;
};


int main() {

    printf("-1 placeholder for empty nodes\n");
    struct node* tree = defaultnode();

    // build tree with leaf values
    adddefaultchildren(tree, 3);
    adddefaultchildren(getchild(tree, 0), 2);
    adddefaultchildren(getchild(tree, 1), 2);
    adddefaultchildren(getchild(tree, 2), 3);

    add(getchild(getchild(tree, 0), 0), 2);
    add(getchild(getchild(tree, 0), 0), 7);

    add(getchild(getchild(tree, 0), 1), 8);
    add(getchild(getchild(tree, 0), 1), 1);

    add(getchild(getchild(tree, 1), 0), 4);
    add(getchild(getchild(tree, 1), 0), 5);

    add(getchild(getchild(tree, 1), 1), 9);
    add(getchild(getchild(tree, 1), 1), 0);

    add(getchild(getchild(tree, 2), 0), 3);
    add(getchild(getchild(tree, 2), 0), 6);
    add(getchild(getchild(tree, 2), 1), 5);
    add(getchild(getchild(tree, 2), 1), 1);
    add(getchild(getchild(tree, 2), 2), 2);
    add(getchild(getchild(tree, 2), 2), 1);

    printf("original tree pre-order\t");
    printtree(tree);
    printf("\n");

    struct result* r = minimax(tree, 0);

    printf("minimax tree pre-order:\t");
    printtree(tree);
    printf("\n");

    printgamepath(r);

}