/* alpha-beta.c - Discussion at
       http://www.cis.temple.edu/~ingargio/cis587/readings/alpha-beta.html
 */

#include <stdio.h>
#include <stdlib.h>

enum kind {Min, Max};

/* A node can have any number of successors.
   We represent the tree using a binary tree. The link child goes
   to one of the successors, and from there the link sibling will
   take to all other successors.
 */
struct node {
   char * name;    /* used only for convenience in displaying information */
   enum kind knd;  /* if the node is a Max node or a Min node */
   int value;      /* relevant only for leaves */
   int alpha;        
   int beta;
   struct node *child;
   struct node *sibling;
};

/* preorder traversal of the tree */
void printNode(const struct node * const p)
{
  const struct node * r;

  for (r = p; r != NULL; r = r->sibling) {
    printf ("name = %s\t kind = %d\t value = %d\t alpha = %d\t beta = %d\n", r->name, (int)(r->knd), 
	    r->value, r->alpha, r->beta);
    printNode(r->child);
  }
}

#define min(x,y) ((x)<(y))?x:y
#define max(x,y) ((x)>(y))?x:y

/* The Minimax algorithm with Alpha-Beta cutoff */
int minimaxAB (struct node * n, int a, int b) /* Here A is always less than B */
{
  if (n->child == NULL)
    return n->value;
  n->alpha = INT_MIN;
  n->beta = INT_MAX;
  if (n->knd == Min) {
    struct node *r;
    for (r = n->child; r != NULL; r = r->sibling) {
      int newb = min(b, n->beta); 
      int val = minimaxAB(r, a, newb);
printf("minimax at %s, with a = %d, b = %d is %d\n", r->name, a, newb, val);
      n->beta = min(n->beta, val);
      if (a >= n->beta)
	break;
    }
    return n->beta;
  } else {
    struct node *r;
    for (r = n->child; r != NULL; r = r->sibling) {
      int newa = max(a, n->alpha);
      int val = minimaxAB(r, newa, b);
printf("minimax at %s, with a = %d, b = %d is %d\n", r->name, newa, b, val);
      n->alpha = max(n->alpha, val);
      if (n->alpha >= b)
	break;
    }
    return n->alpha;
  }
}

/* Just an example of a game */
struct node game[31] = {
/* 0 */   {"A",  Max, 0, INT_MIN, INT_MAX, (struct node *)(game+1),  (struct node *)NULL},
/* 1 */   {"B",  Min, 0, INT_MIN, INT_MAX, (struct node *)(game+3),  (struct node *)(game+2)},
/* 2 */   {"Q",  Min, 0, INT_MIN, INT_MAX, (struct node *)(game+5),  (struct node *)NULL},
/* 3 */   {"C",  Max, 0, INT_MIN, INT_MAX, (struct node *)(game+7),  (struct node *)(game+4)},
/* 4 */   {"J",  Max, 0, INT_MIN, INT_MAX, (struct node *)(game+9),  (struct node *)NULL},
/* 5 */   {"R",  Max, 0, INT_MIN, INT_MAX, (struct node *)(game+11), (struct node *)(game+6)},
/* 6 */   {"Y",  Max, 0, INT_MIN, INT_MAX, (struct node *)(game+13), (struct node *)NULL},
/* 7 */   {"D",  Min, 0, INT_MIN, INT_MAX, (struct node *)(game+15), (struct node *)(game+8)},
/* 8 */   {"G",  Min, 0, INT_MIN, INT_MAX, (struct node *)(game+17), (struct node *)NULL},
/* 9 */   {"K",  Min, 0, INT_MIN, INT_MAX, (struct node *)(game+19), (struct node *)(game+10)},
/*10 */   {"N",  Min, 0, INT_MIN, INT_MAX, (struct node *)(game+21), (struct node *)NULL},
/*11 */   {"S",  Min, 0, INT_MIN, INT_MAX, (struct node *)(game+23), (struct node *)(game+12)},
/*12 */   {"V",  Min, 0, INT_MIN, INT_MAX, (struct node *)(game+25), (struct node *)NULL},
/*13 */   {"Z",  Min, 0, INT_MIN, INT_MAX, (struct node *)(game+27), (struct node *)(game+14)},
/*14 */   {"Z3", Min, 0, INT_MIN, INT_MAX, (struct node *)(game+29), (struct node *)NULL},
/*15 */   {"E",  Max, 10, INT_MIN, INT_MAX, (struct node *)NULL,      (struct node *)(game+16)},
/*16 */   {"F",  Max, 11, INT_MIN, INT_MAX, (struct node *)NULL,      (struct node *)NULL},
/*17 */   {"H",  Max,  9, INT_MIN, INT_MAX, (struct node *)NULL,      (struct node *)(game+18)},
/*18 */   {"I",  Max, 12, INT_MIN, INT_MAX, (struct node *)NULL,      (struct node *)NULL},
/*19 */   {"L",  Max, 14, INT_MIN, INT_MAX, (struct node *)NULL,      (struct node *)(game+20)},
/*20 */   {"M",  Max, 15, INT_MIN, INT_MAX, (struct node *)NULL,      (struct node *)NULL},
/*21 */   {"O",  Max, 13, INT_MIN, INT_MAX, (struct node *)NULL,      (struct node *)(game+22)},
/*22 */   {"P",  Max, 14, INT_MIN, INT_MAX, (struct node *)NULL,      (struct node *)NULL},
/*23 */   {"T",  Max, 15, INT_MIN, INT_MAX, (struct node *)NULL,      (struct node *)(game+24)},
/*24 */   {"U",  Max,  2, INT_MIN, INT_MAX, NULL, NULL},
/*25 */   {"W",  Max,  4, INT_MIN, INT_MAX, NULL, game+26},
/*26 */   {"X",  Max,  1, INT_MIN, INT_MAX, NULL, NULL},
/*27 */   {"Z1", Max,  3, INT_MIN, INT_MAX, NULL, game+28},
/*28 */   {"Z2", Max, 22, INT_MIN, INT_MAX, NULL, NULL},
/*29 */   {"Z4", Max, 24, INT_MIN, INT_MAX, NULL, game+30},
/*30 */   {"Z5", Max, 25, INT_MIN, INT_MAX, NULL, NULL}
		       };

/* Game in Nillson, 1980 pg 124 */
struct node game1[99] = {
  {"0",  Max, 0, INT_MIN, INT_MAX, game1+1, NULL},

  {"1",  Min, 0, INT_MIN, INT_MAX, game1+4, game1+2},
  {"2",  Min, 0, INT_MIN, INT_MAX, game1+6, game1+3},
  {"3",  Min, 0, INT_MIN, INT_MAX, game1+8, NULL},

  {"4",  Max, 0, INT_MIN, INT_MAX, game1+11, game1+5},
  {"5",  Max, 0, INT_MIN, INT_MAX, game1+12, NULL},
  {"6",  Max, 0, INT_MIN, INT_MAX, game1+14, game1+7},
  {"7",  Max, 0, INT_MIN, INT_MAX, game1+16, NULL},
  {"8",  Max, 0, INT_MIN, INT_MAX, game1+17, game1+9},
  {"9",  Max, 0, INT_MIN, INT_MAX, game1+19, game1+10},
  {"10", Max, 0, INT_MIN, INT_MAX, game1+21, NULL},

  {"11", Min, 0, INT_MIN, INT_MAX, game1+22, NULL},
  {"12", Min, 0, INT_MIN, INT_MAX, game1+24, game1+13},
  {"13", Min, 0, INT_MIN, INT_MAX, game1+25, NULL},
  {"14", Min, 0, INT_MIN, INT_MAX, game1+26, game1+15},
  {"15", Min, 0, INT_MIN, INT_MAX, game1+27, NULL},
  {"16", Min, 0, INT_MIN, INT_MAX, game1+29, NULL},
  {"17", Min, 0, INT_MIN, INT_MAX, game1+30, game1+18},
  {"18", Min, 0, INT_MIN, INT_MAX, game1+31, NULL},
  {"19", Min, 0, INT_MIN, INT_MAX, game1+32, game1+20},
  {"20", Min, 0, INT_MIN, INT_MAX, game1+33, NULL},
  {"21", Min, 0, INT_MIN, INT_MAX, game1+34, NULL},

  {"22", Max, 0, INT_MIN, INT_MAX, game1+36, game1+23},
  {"23", Max, 0, INT_MIN, INT_MAX, game1+38, NULL},
  {"24", Max, 0, INT_MIN, INT_MAX, game1+41, NULL},
  {"25", Max, 0, INT_MIN, INT_MAX, game1+43, NULL},
  {"26", Max, 0, INT_MIN, INT_MAX, game1+44, NULL},
  {"27", Max, 0, INT_MIN, INT_MAX, game1+46, game1+28},
  {"28", Max, 0, INT_MIN, INT_MAX, game1+47, NULL},
  {"29", Max, 0, INT_MIN, INT_MAX, game1+48, NULL},
  {"30", Max, 0, INT_MIN, INT_MAX, game1+49, NULL},
  {"31", Max, 0, INT_MIN, INT_MAX, game1+51, NULL},
  {"32", Max, 0, INT_MIN, INT_MAX, game1+53, NULL},
  {"33", Max, 0, INT_MIN, INT_MAX, game1+54, NULL},
  {"34", Max, 0, INT_MIN, INT_MAX, game1+55, game1+35},
  {"35", Max, 0, INT_MIN, INT_MAX, game1+56, NULL},

  {"36", Min, 0, INT_MIN, INT_MAX, game1+58, game1+37},
  {"37", Min, 0, INT_MIN, INT_MAX, game1+60, NULL},
  {"38", Min, 0, INT_MIN, INT_MAX, game1+62, game1+39},
  {"39", Min, 0, INT_MIN, INT_MAX, game1+63, game1+40},
  {"40", Min, 0, INT_MIN, INT_MAX, game1+66, NULL},
  {"41", Min, 0, INT_MIN, INT_MAX, game1+68, game1+42},
  {"42", Min, 0, INT_MIN, INT_MAX, game1+70, NULL},
  {"43", Min, 0, INT_MIN, INT_MAX, game1+72, NULL},
  {"44", Min, 0, INT_MIN, INT_MAX, game1+74, game1+45},
  {"45", Min, 0, INT_MIN, INT_MAX, game1+76, NULL},
  {"46", Min, 0, INT_MIN, INT_MAX, game1+78, NULL},
  {"47", Min, 0, INT_MIN, INT_MAX, game1+80, NULL},
  {"48", Min, 0, INT_MIN, INT_MAX, game1+82, NULL},
  {"49", Min, 0, INT_MIN, INT_MAX, game1+83, game1+50},
  {"50", Min, 0, INT_MIN, INT_MAX, game1+84, NULL},
  {"51", Min, 0, INT_MIN, INT_MAX, game1+86, game1+52},
  {"52", Min, 0, INT_MIN, INT_MAX, game1+88, NULL},
  {"53", Min, 0, INT_MIN, INT_MAX, game1+90, NULL},
  {"54", Min, 0, INT_MIN, INT_MAX, game1+92, NULL},
  {"55", Min, 0, INT_MIN, INT_MAX, game1+94, NULL},
  {"56", Min, 0, INT_MIN, INT_MAX, game1+96, game1+57},
  {"57", Min, 0, INT_MIN, INT_MAX, game1+98, NULL},

  {"58", Max,  0, INT_MIN, INT_MAX, NULL, game1+59},
  {"59", Max,  5, INT_MIN, INT_MAX, NULL, NULL},
  {"60", Max, -3, INT_MIN, INT_MAX, NULL, game1+61},
  {"61", Max,  3, INT_MIN, INT_MAX, NULL, NULL},
  {"62", Max,  3, INT_MIN, INT_MAX, NULL, NULL},
  {"63", Max, -3, INT_MIN, INT_MAX, NULL, game1+64},
  {"64", Max,  0, INT_MIN, INT_MAX, NULL, game1+65},
  {"65", Max,  2, INT_MIN, INT_MAX, NULL, NULL},
  {"66", Max, -2, INT_MIN, INT_MAX, NULL, game1+67},
  {"67", Max,  3, INT_MIN, INT_MAX, NULL, NULL},
  {"68", Max,  5, INT_MIN, INT_MAX, NULL, game1+69},
  {"69", Max,  2, INT_MIN, INT_MAX, NULL, NULL},
  {"70", Max,  5, INT_MIN, INT_MAX, NULL, game1+71},
  {"71", Max, -5, INT_MIN, INT_MAX, NULL, NULL},
  {"72", Max,  0, INT_MIN, INT_MAX, NULL, game1+73},
  {"73", Max,  1, INT_MIN, INT_MAX, NULL, NULL},
  {"74", Max,  5, INT_MIN, INT_MAX, NULL, game1+75},
  {"75", Max,  1, INT_MIN, INT_MAX, NULL, NULL},
  {"76", Max, -3, INT_MIN, INT_MAX, NULL, game1+77},
  {"77", Max,  0, INT_MIN, INT_MAX, NULL, NULL},
  {"78", Max, -5, INT_MIN, INT_MAX, NULL, game1+79},
  {"79", Max,  5, INT_MIN, INT_MAX, NULL, NULL},
  {"80", Max, -3, INT_MIN, INT_MAX, NULL, game1+81},
  {"81", Max,  3, INT_MIN, INT_MAX, NULL, NULL},
  {"82", Max,  2, INT_MIN, INT_MAX, NULL, NULL},
  {"83", Max,  3, INT_MIN, INT_MAX, NULL, NULL},
  {"84", Max, -3, INT_MIN, INT_MAX, NULL, game1+85},
  {"85", Max,  0, INT_MIN, INT_MAX, NULL, NULL},
  {"86", Max, -1, INT_MIN, INT_MAX, NULL, game1+87},
  {"87", Max, -2, INT_MIN, INT_MAX, NULL, NULL},
  {"88", Max,  0, INT_MIN, INT_MAX, NULL, game1+89},
  {"89", Max,  1, INT_MIN, INT_MAX, NULL, NULL},
  {"90", Max,  4, INT_MIN, INT_MAX, NULL, game1+91},
  {"91", Max,  5, INT_MIN, INT_MAX, NULL, NULL},
  {"92", Max,  1, INT_MIN, INT_MAX, NULL, game1+93},
  {"93", Max, -1, INT_MIN, INT_MAX, NULL, NULL},
  {"94", Max, -1, INT_MIN, INT_MAX, NULL, game1+95},
  {"95", Max,  3, INT_MIN, INT_MAX, NULL, NULL},
  {"96", Max, -3, INT_MIN, INT_MAX, NULL, game1+97},
  {"97", Max,  2, INT_MIN, INT_MAX, NULL, NULL},
  {"98", Max, -2, INT_MIN, INT_MAX, NULL, NULL}

};

int main()
{
  int val;

/* Example from http://www.cis.temple.edu/~ingargio/cis587/readings/alpha-beta-example.html  
  printNode(game); 
  val = minimaxAB(game, INT_MIN, INT_MAX);
  printf("\nValue is: %d\n", val);
 */

/* Example from Nillson: Principles of AI, 1980, page 124 */
  printNode(game1); 
  val = minimaxAB(game1, INT_MIN, INT_MAX);
  printf("\nValue is: %d\n", val);

  return 0;
}