text: /* Fhourstones 2.0 connect-4 solver
  // (http://www.cwi.nl/~tromp/c4/fhour.html)
  //
  // implementation of the well-known game
  // played on a vertical board of 7 columns by 6 rows,
  // where 2 players take turns in dropping counters in a column.
  // the first player to get four of his counters
  // in a horizontal, vertical or diagonal row, wins the game.
  // if neither player has won after 42 moves, then the game is drawn.
  //
  // This software is copyright (c) 1996 by
  //      John Tromp
  //      Lindenlaan 33
  //      1701 GT Heerhugowaard
  //      Netherlands
  // E-mail: tromp@cwi.nl
  //
  // This notice must not be removed.
  // This software must not be sold for profit.
  // You may redistribute if your distributees have the
  // same rights and restrictions.
  */
  
  #include "types.h"
  #include "c4.h"
  
  #define HISTINIT	{-1,-1,-1,-1,-1,-1,-1,-1,\
  			-1, 0, 1, 2, 4, 2, 1, 0,\
  			-1, 1, 3, 5, 7, 5, 3, 1,\
  			-1, 2, 5, 8,10, 8, 5, 2,\
  			-1, 2, 5, 8,10, 8, 5, 2,\
  			-1, 1, 3, 5, 7, 5, 3, 1,\
  			-1, 0, 1, 2, 4, 2, 1, 0}
  
  int history[2][56] = {HISTINIT, HISTINIT};
  int64 nodes, msecs;
  
  extern int colthr[];
  extern boolean colwon[];
  extern int plycnt;
  extern int columns[], height[];
  
  extern int64 posed;
  
  void c4_init()
  {
    trans_init();
  }
  
  int ab(int alpha, int beta)
  {
    int besti,i,j,h,k,l,val,score;
    int x,v,work;
    int nav, av[8];
    int64 poscnt;
    int side, otherside;
  
    nodes++;
    if (plycnt == 41)
      return DRAW;
    side = (otherside = plycnt & 1) ^ 1;
    for (i = nav = 0; ++i <= 7; ) {
      if ((h = height[i]) <= 6) {
        if (wins(i,h,3) || colthr[columns[i]] != 0) {
          if (h+1 <= 6 && wins(i,h+1,1<<otherside))
            return LOSE;
          av[0] = i;		/* forget other moves */
          while (++i <= 7)
            if ((h = height[i]) <= 6 &&
                (wins(i,h,3) || colthr[columns[i]] != 0))
              return LOSE;
          nav = 1;
          break;
        }
        if (!(h+1 <= 6 && wins(i,h+1,1<<otherside)))
          av[nav++] = i;
      }
    }
    if (nav == 0)
      return LOSE;
    if (nav == 1) {
      makemove(av[0]);
      score = -ab(-beta,-alpha);
      backmove();
      return score;
    }
    if ((x = transpose()) != ABSENT) {
      score = x >> 5;
      if (score == DRAWLOSE) {
        if ((beta = DRAW) <= alpha)
          return score;
      } else if (score == DRAWWIN) {
        if ((alpha = DRAW) >= beta)
          return score;
      } else return score; /* exact score */
    }
    poscnt = posed;
    l = besti = 0;
    score = -999999;	/* try to get the best bound if score > beta */
    for (i = 0; i < nav; i++) {
      for (j = i, val = -999999; j < nav; j++) {
        k = av[j];
        v = history[side][height[k]<<3|k];
        if (v > val) {
          val = v; l = j;
        }
      }
      j = av[l];
      if (i != l) {
        av[l] = av[i]; av[i] = j;
      }
      makemove(j);
      val = -ab(-beta,-alpha);
      backmove();
      if (val > score) {
        besti = i;
        if ((score = val) > alpha && (alpha = val) >= beta) {
          if (score == DRAW && i < nav-1)
            score = DRAWWIN;
          break;
        }
      }
    }
    if (besti > 0) {
      for (i = 0; i < besti; i++) {
        history[side][height[av[i]]<<3|av[i]]--;	/* punish bad historiess */
      }
      history[side][height[av[besti]]<<3|av[besti]] += besti;
    }
    poscnt = posed - poscnt;
    for (work=1; (poscnt>>=1) != 0; work++) ;	/* work=log #positions stored */
    if (x != ABSENT) {
      if (score == -(x>>5))	/* combine < and > */
        score = DRAW;
      transrestore(score, work);
    } else transtore(score, work);
    if (plycnt == REPORTPLY) {
      printMoves();
      printf("%c%d\n", "##-<=>+#"[4+score], work);
    }
    return score;
  }
  
  int solve()
  {
    int i,side;
    int x,work,score;
    int64 poscnt;
    extern int64 millisecs();
  
    nodes = 0;
    msecs = 1;
    side = (plycnt+1) & 1;
    for (i = 0; ++i <= 7 ;)
      if (height[i] <= 6) {
        if (wins(i, height[i], 1<<side) || colthr[columns[i]] == (1<<side))
          return (side!=0 ? WIN : LOSE) << 5;	/* all score & no work:) */
      }
    if ((x = transpose()) != ABSENT) {
      if ((x & 32) == 0)   /* exact score */
        return x;
    }
    msecs = millisecs() - 1L;
    score = ab(LOSE,WIN);
    poscnt = posed;
    for (work=1; (poscnt>>=1) != 0; work++) ; /*work = log of #positions stored*/
    msecs = millisecs() - msecs;
    return score << 5 | work;
  }
  
  int main()
  {
    int c, i, result;
  
    if (sizeof(int64) != 8) {
      printf("sizeof(int64) == %d; please redefine.\n", sizeof(int64));
      exit(0);
    }
    c4_init();
    puts("Fhourstones 2.0");
    printf("Using %d transposition table entries with %d probes.\n",
            TRANSIZE, PROBES);
    for (;;) {
      reset();
      while ((c = getchar()) != -1) {
        if (c >= '1' && c <= '7')
          makemove(c - '0');
        else if (c >= 'A' && c <= 'G')
          makemove(c - 'A' + 1);
        else if (c >= 'a' && c <= 'g')
          makemove(c - 'a' + 1);
        else if (c == '\n')
          break;
      }
      if (c == -1)
        break;
      printf("Solving %d-ply position after ", plycnt);
      printMoves();
      puts(" . . .");
  
      emptyTT();
      result = solve();		/* expect score << 5 | work */
      printf("score = %d (%c)  work = %d\n",
        (result>>5), "##-<=>+#"[4+(result>>5)], result&31);
      printf("%lu pos / %lu msec = %.1f Kpos/sec\n",
        (long)nodes, (long)msecs, (double)nodes/msecs);
      htstat();
    }
    return 0;
  }
  