/* baumsuche.c
 * Testrahmen fuer Baumsuche Routinen
 * Bewertungsfunktion wird durch Zufallszahlen simuliert
 * Autor: Andre Adrian
 * Version 2jan2009
 */
 
#include <stdio.h> 
#include <stdlib.h> 
#include <time.h>

#define N   20            // Verzweigungsfaktor
#define D   6             // Tiefe
int R = 16;               // Anzahl Werte von value()

#define INF 1000          // Unendlich
#define T   N*N*N*N*N*N   // N ^ D

#define max(a,b) ((a)>(b)?(a):(b))

int ii[D];
int v[T];
int nodeNS, nodeNM, nodeNM0, nodeNS1;


// Bewertungsfunktion
int value()
{
  int ndx = 0, i;
  
//  printf("  Terminal ");
  for (i = 0; i < D; ++i) {
    // Hohner Schema
    ndx = N * ndx + ii[i];
//    printf("%2d ", ii[i]);
  }
//  printf("v=%d\n", v[ndx]);
  return v[ndx];
}

// NegaMax Baumsuche
int negamax(int depth, int al, int be)
{
  // Reinefeld S. 24
//  printf("Negamax d=%d, al=%d be=%d\n", depth, al, be);
  int v, t;
  int i;
  if (0 == depth) {
    ++nodeNM;
    return value();
  } 
  v = al;
  for (i = 0; i < N; ++i) {
    ii[depth] = i;
    t = -negamax(depth-1, -be, -v);
    v = max(v, t);
    if (v >= be)
      return v;
  }
  return v;
}

// NegaScout (PV) - Reinefeld Version
int negascout(int depth, int al, int be)
{
  // Reinefeld S. 41
//  printf("Negascout d=%d, al=%d be=%d\n", depth, al, be);
  int lo, hi, t;
  int i;
  if (0 == depth) {
    ++nodeNS;  
    return value();
  }
  lo = -INF;
  hi = be;
  for (i = 0; i < N; ++i) {
    ii[depth] = i;
    t = -negascout(depth-1, -hi, -max(lo,al));
    if (t > max(lo,al) && t < be && i > 0 && depth > 2)
//    if (t > max(lo,al) && t < be && i > 0)
      t = -negascout(depth-1, -be, -t);
    lo = max(lo,t);
    if (lo >= be)
      return lo;
    hi = max(lo,al)+1;
  }
  return lo;
}

// NegaScout (PV) - Wikipedia Version
int negascout1(int depth, int al, int be)
{
//  printf("Negascout d=%d, al=%d be=%d\n", depth, al, be);
  int b, a;
  int i;
  if (0 == depth) {
    ++nodeNS1;  
    return value();
  } 
  b = be;
  for (i = 0; i < N; ++i) {
    ii[depth] = i;
    a = -negascout1(depth-1, -b, -al);
    if (a > al)
      al = a;
    if (al >= be)
      return al;
    if (al >= b) {
//      printf("full ");
      al = -negascout1(depth-1, -be, -al);
      if (al >= be)
        return al;
    }
    b = al+1;
  }
  return al;
}

// MTD(f)
int mtdf(int f, int d)
{
  int g, up, lo, be;
  
  nodeNM = 0;
  g = f;
  up = INF;
  lo = -INF;
  do {
    if (g == lo) be = g+1; else be = g;
    g = negamax(d, be-1, be);
    if (g < be) up = g; else lo = g;
  } while (lo < up);
  return g;
}

int main(int argc, char *argv[])
{
  int i, es, es1, em, et;
  
  if (argc > 1) {
    R = atoi(argv[1]);
  }
  printf("Baumsuche Verzweigung=%d Tiefe=%d Anzahl Werte=%d\n",
   N, D, R);
  
  srandom(time(NULL));                      /* make rand() calls random */  
  for (i = 0; i < T; ++i) {
    v[i] = ((random()>>8) % R) -R/2;
  }
  em = negamax(D-1, -INF, INF);
  nodeNM0 = nodeNM;
  es = negascout(D-1, -INF, INF);
  es1 = negascout1(D-1, -INF, INF);
  et = mtdf(0, D-1);
  printf("em=%d es=%d es1=%d et=%d\n", em, es, es1, et);
  printf("Nodes NM=%d NS=%d NS1=%d NT=%d\n", nodeNM0, nodeNS, nodeNS1, nodeNM);
  return 0;
}