MultiSource/Benchmarks/Fhourstones/c4.c

/* 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 <stdlib.h>
#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;

extern int trans_init();
extern int wins();
extern int makemove();
extern int backmove();
extern int transpose();
extern int transrestore();
extern int transtore();
extern int printMoves();
extern int reset();
extern int emptyTT();
extern int htstat();

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;
}