/* Connect 4 copyright C. Michael 1990  */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define LINE     4             /* care alter weights wt[] if > 5  */
#define WT1      1             /* choose weights increasing eg 1,3,9,27,. */
#define WT2      3             /* choose weight for LINE  as 999          */
#define WT3      9
#define WT4    999
#define WT5    999
#define NOCOLS 7               /* care LINE <= NOCOLS and NOROWS      */
#define NOROWS 6
#define BALLS  42              /* see test later that <= NOCOLS*NOROWS */
#define LEVWC 8              /* Comp: win/loose lookahead level */
#define LEVHC 3              /* Comp: heuristic lookahead level */
#define LEVWY 8              /* You: win/loose lookahead level */
#define LEVHY 3              /* You: heuristic lookahead level */
#define CROSS  -1     /*   char values used    */
#define NOUGHT   1    /* needs CROSS as - NOUGHT */
#define EMPTY   0     /* must be zero to speed up code */
#define LINEP   5     /* (LINE + 1)            */
#define LINEM   3     /* (LINE - 1)            */
#define DIMCOLS 9     /* (NOCOLS + 2)          */
#define DIMROWS 8     /* (NOROWS + 2)          */
#define DIMROWM 7     /* (DIMROWS - 1)         */
#define DIMROWP 9     /* (DIMROWS + 1)         */
#define DIMCR   72    /* (DIMROWS*DIMCOLS)     */
#define DIMCMBYR 64   /* (DIMROWS*(NOCOLS+1))  */
#define RAND_MAX 2147483700  
#define RANDBY2  1073741700
#define min(A,B)  ((A) < (B) ? (A) : (B) )
#define min3(C,D,E)  min( (C) ,min( (D), (E) ) )
#define max(A,B)  ((A) > (B) ? (A) : (B) )
#define NOBALLS 42    /* min(BALLS, NOCOLS*NOROWS) */

int slevc, slevh;            /* C: win/loose, heuristic */
int dc[DIMCOLS];
int perm[DIMCOLS]={0,4,3,5,2,6,1,7,0};  /* default order */
long noeval;
int  qprint;               /* if != 0 then print info */
int move(        );        /* ( int v[],int c, char p) moves in col c and */
                           /* checks  for 4 in line by player p   */
                           /*  win is     CROSS  or   NOUGHT   */
int term(      );          /* ( char * ptv, p) ptv points to c,r; no move*/
int heur(      );          /* ( char * ptv,c,r,p) ptv points to base,move c,r*/
void display(        ) ;   /* ( int v[]) displays NOCOLS*NOROWS square */
int  askmove(     ) ;      /* ( int v[]) asks for move by CROSS  */
int ve(  );                /* (char *ptv, int l, char p,...) */
int veh(  );               /* (char *ptv, int l, char p,...) */
int movec( );              /* (int v[] int l int lh p ) best move by p */

main()
{
       char v[DIMCOLS][DIMROWS];           /* state of play: 0 is empty */
                          /* guard zone (empty) col=0 & NC+1, row = 0 & NR+1 */
                          /* play is 1,..r,.,NOROWS   1,..c,..NOCOLS   */
        int win, c,r,lev,i,lh;              /* win is 1 or -1 at end     */
        long nowt;
        extern int dc[DIMCOLS];  /* DIMROWS mult table */

/* INITIALISE */
        qprint = 0;
        slevc = LEVWC;
        slevh = LEVHC;
        time(&nowt);
        printf(" Time %s \n",ctime(&nowt) );
        i = nowt;
        srand( i     );
        dc[0] = 0;
        for ( i = 1 ; i < DIMCOLS ; ++i ) {
              dc[i] = dc[i-1] + DIMROWS;
        }
        win = 0;
        for (c = 0 ; c < DIMCOLS ; ++c ) {
              for (r = 0 ; r < DIMROWS ; ++r ) {
                    i   = rand();  /* "warm up" rand since seeds are close */
                    v[c][r] = 0 ;
              }
        }
        /* printf(" rn = %12d \n",i);  */
        lev = 0;
        if ( rand() < RANDBY2 ){           /* computer starts */
                lh = min(slevh,NOBALLS-lev);
                c = movec(v, min(slevc,NOBALLS-lev),lh,NOUGHT);
                printf(" Computer moves to column: %1d \n",c);
                move(v, c, NOUGHT);
                lev = 1;
        }

/* GAME */
        display( v,lev );          /* your first move */
        c = askmove(v );
        if(c == -1){
                lh = min(slevh,NOBALLS-lev);
                c = movec(v, min(slevc,NOBALLS-lev),lh,CROSS);
        }
        win = move(v,c, CROSS);

        for (;;    ){
                        display( v,++lev );
                        lh = min(slevh,NOBALLS-lev);
                        c = movec(v, min(slevc,NOBALLS-lev),lh,NOUGHT);
                        printf(" Computer moves to column: %1d \n",c);
                        win = move(v, c, NOUGHT);
                        if( win == NOUGHT) break;
                        if(lev == NOBALLS-1 )break;

                        display( v,++lev);
                        c = askmove(v);
                        if(c == -1){
                            lh = min(slevh,NOBALLS-lev);
                            c =movec(v,min(slevc,NOBALLS-lev),lh,CROSS);
                        }
                        win = move(v,c, CROSS);
                        if( win == CROSS) break;
                        if(lev == NOBALLS-1) break;
        }

/* RESULT */
        display( v ,++lev);
        if ( win == CROSS )
                printf("  Cross wins  \n");
        if ( win == NOUGHT )
                printf(" Nought wins \n");
        if ( win == 0      )
                printf(" DRAWN GAME  \n");
}

/* DISPLAY  NOCOLS*NOROWS labelled col,row        */
void display(v,n )
char v[DIMCOLS][DIMROWS] ;
int n ;
{
     int r,c;
     extern int slevc,slevh;
     char w;

     printf(" After %2d moves with %2d balls left. \n",n,NOBALLS-n);
     for (r = NOROWS; r >= 1; --r )  {
        for (c = 1; c <= NOCOLS; ++c )  {
                if ( v[c][r] == EMPTY )
                        w = '.';
                if ( v[c][r] == CROSS )
                        w = 'x';
                if ( v[c][r] == NOUGHT  )
                        w = '0';
                printf("| %1c ",w);
         }
         printf("|\n");
     }
     for ( c = 1; c <= NOCOLS; ++c ){
        printf("  %1d ",c);
     }
     printf(" search lev= %d , %d \n\n",slevh,slevc) ;
}
/* ASKMOVE: ask for next position  */
int  askmove(v   )
char v[DIMCOLS][DIMROWS];
{
        int c;
        extern int slevc,slevh,qprint;

        printf("  Enter your move (x) : position 1-%1d \n",NOCOLS) ;

        do  {
        c = getchar() -'0' ;
        if(c == -1  - '0' ) return -1;    /* if getchar error */
        if(c == '?' - '0') return -1;
        if(c == '+' - '0') ++slevc;     /* computer win/loose level */
        if(c == '-' - '0') --slevc;
        if(c == 'p' - '0') ++slevh;     /* computer heuristic level */
        if(c == 'm' - '0') --slevh;
        if(c == 'q' - '0') qprint=1-qprint; /* toggle info */
        }
        while( c > NOCOLS || c < 1  || v[c][NOROWS] != 0); /* space in top row*/

        return c;
}
/*  MOVE in col c and check for winning line  of LINE for player p */
int move( v, c, p )    /* c 1 to NOCOLS, p CROSS or NOUGHT */
char v[DIMCOLS][DIMROWS] ,p  ;
int c;
{
        int r,win;
       char*ptv;

        r = 0;
        while ( v[c][++r] != EMPTY ){      /* find first empty row in col c */
        }

        if( r > NOROWS ) return 128;       /* invalid: column full */
        v[c][r] = p;                        /* move */

        ptv = &v[c][r];
        win = term(ptv,p);
        if(win == 1) return p;
        return 0;
}
/*  TERM  col c row r:  check for winning line  of LINE for player p */
int term( ptv  ,p )    /* ptv points to c,r; p CROSS or NOUGHT */
char *ptv   ,p ;
{
       char *ptvv;
        extern long noeval;
        int nc;
   /*    v[c][r]= *(ptv+DIMROWS*c + r)  */

        /* idea is guard zone of v == EMPTY around NOCOLS*NOROWS play region */
                             /* vertical - down only */
        ++noeval;
        nc = 1;
        ptvv = ptv;
        while( *(--ptvv)  == p ) {
                   ++nc;
        }
        if( nc >= LINE ) return 1;
                             /* horizontal */
        nc = 1;
        ptvv=ptv+DIMROWS;
        while( *(ptvv)    == p) {
                ptvv += DIMROWS;
                ++nc;
        }
        ptvv=ptv-DIMROWS;
        while( *(ptvv)    == p) {
               ptvv -= DIMROWS;
               ++nc;
        }
        if(nc >= LINE ) return 1;
                             /* diagonal   */
        nc = 1;
        ptvv = ptv + DIMROWP;
        while( *(ptvv) == p) {
                ptvv += DIMROWP;
                ++nc;
        }
        ptvv = ptv - DIMROWP;
        while( *(ptvv) == p) {
               ptvv -= DIMROWP;
               ++nc;
        }
        if(nc >= LINE ) return 1;
                             /* diagonal   */
        nc = 1;
        ptvv = ptv + DIMROWM;
        while( *(ptvv) == p) {
                ptvv += DIMROWM;
                ++nc;
        }
        ptvv = ptv - DIMROWM;
        while( *(ptvv) == p) {
               ptvv -= DIMROWM;
               ++nc;
        }
        if(nc >= LINE ) return 1;

        return 0;    /* no match to 4 in line */
}
/*  VE: alpa beta post order game tree evaluation, level l, player p */
int ve(ptv,l,p,lb,d)
char *ptv,p;
int l,lb,d;
{
        int t,ans,c,ic;
        extern long noeval;
        extern int dc[DIMCOLS];
        extern int perm[DIMCOLS];
       char *ptvc, *ptvcr;

                        /* loop over adresses of column base 1,..NOCOLS */
        for (ptvc = ptv + DIMROWS ; ptvc < ptv + DIMCMBYR ; ptvc += DIMROWS){

                if( *(ptvc+ NOROWS) == EMPTY ) { /* valid move: top row free */
                        ptvcr = ptvc;
                        while( *(++ptvcr)  ) {  /* != EMPTY  */
                        }                       /* ptvcr is now row of move */
                        t = term(ptvcr,p);
                        if( t == 1) return 1;  /* quick win option */
                }
        }
        if(l == 1) return 0;
        ans = lb;
        for (ic = 1; ic <= NOCOLS; ++ic) {
                c = perm[ic];
                ptvc = ptv + dc[c];
                if( *(ptvc+ NOROWS) == EMPTY ) { /* valid move: top row free */
                        if( ans >= d ) {
                                return ans;     /* move too good: cut */
                        }
                        if( l == 2 && ans == 0 ){   /* so only win improves */
                                return 0;
                        }
                        ptvcr = ptvc;
                        while( *(++ptvcr)  ) {  /* != EMPTY  */
                        }                       /* ptvcr is now row of move */

                                *ptvcr  = p;        /* move */
                                t = -ve(ptv,l-1,-p,-d,-ans);
                                *ptvcr  = 0;       /* unmove */

                        if(t >  ans )
                                ans = t;
                }
        }
        return ans;
}
/*  MOVEC: make best move  look l win/loose steps ahead for player p */
int  movec(v,l,lh,p)         /* lh heuristic steps first */
char v[DIMCOLS][DIMROWS],p;
int l,lh;
{
       char  *ptv, *ptvc, *ptvcr;
        int c, cm, ic, r, ans, best,st[DIMCOLS],add[DIMCOLS],t,jb,th;
        long sumeval,noevmax,noevmin;
        extern int perm[DIMCOLS];
        extern int dc[DIMCOLS],qprint;
        extern long noeval;

        ptv = &v[0][0]; /* pick most likely moves: use heuristic level lh */
        noeval = 0;
        if( lh <= 0 ) lh = 1;
        ptvc = ptv;
        for(c = 1; c <= NOCOLS; ++c){
                add[c] = c;
                ptvc += DIMROWS;
                if( *(ptvc + NOROWS) == EMPTY ) {
                        r = 0;
                        while ( v[c][++r] != EMPTY){
                        }                 /* c,r is now location */
                        if( lh <= 1) {           /* last level */
                                t   = heur(ptv,c,r,p);
                        }
                        else {
                                th  = heur(ptv,c,r,p);
                                if( th  >= 500 )  {   /* win */
                                    t = 999;
                                }
                                else {
                                    ptvcr = &v[c][r];
                                    *ptvcr  = p;       /* move */
                                    t = - veh(ptv,-th,lh-1,-p,-999,999);
                                    *ptvcr  = 0;       /* unmove */
                                }
                        }
                        st[c] = t;
                        if(qprint) printf(" %d: %d  ",c,t);
                }
                else {
                        st[c] = -1999; /* invalid */
                }
        }
        if(qprint) printf("  %lu h-evals \n",noeval);
        for( cm = NOCOLS; cm > 0; --cm){
          t = -9999;
          for (c = 1; c <= cm; ++c) {      /* max 1,..cm */
                if(st[c] > t) {
                        t = st[c];
                        jb = c;
                }
          }
          perm[NOCOLS-cm+1] = add[jb];     /* perm is best move order */
          if( jb != cm ) {
                st[jb] = st[cm];     /* squeeze up */
                add[jb]=add[cm];
          }
        }

        sumeval = 0;
        ans = -1;
        noevmin = 999999;
        noevmax = 0;
        best = perm[1];
        for (ic = 1; ic <= NOCOLS; ++ic) {
                noeval = 0;
                c = perm[ic];
                ptvc = ptv + dc[c];
                if( *(ptvc + NOROWS) == EMPTY ) {
                        r = 0;
                        while( *(ptvc + (++r)) ) {  /* != EMPTY  */
                        }                       /* ptvc,r is now row of move */
                        ptvcr = ptvc + r;
                        t   = term(ptvcr,p);
                        if( l > 1) {              /* not last level */
                                if( t   == 1   )  {    /*  win */
                                     return c;
                                }
                                else {   /* cut on draw not win */
                                    *ptvcr  = p;        /* move */
                                    t = -ve(ptv,l-1,-p,-1,max(-ans,0));
                                    *ptvcr  = 0;       /* unmove */
                                }
                        }
                        if(t >  ans ) {       /* better move      */
                                ans = t;      /* takes first draw */
                                best = c;
                        }
                        if(ans == -1) {
                                if(noeval > noevmax) {
                                        noevmax = noeval;
                                        best = c;  /* longest if loose */
                                }
                        }
                        if(ans ==  1 && t == 1) {
                                if(noeval < noevmin) {
                                        noevmin = noeval;
                                        best = c;  /* shortest if win */
                                }
                        }
                if(qprint) printf(" %d: %d/%lu ",c,t,noeval);
                }
         sumeval += noeval;
         }
         if (qprint) printf("\n  noeval= %lu \n",sumeval);
         return best;      /*  best move */
}
/*  HEUR  col c row r:  Eval heuristic position value for player p */
/*  counts number of potential lines; weight WT1,WT2,WT3      */
/*  for 1 2 or 3 in line and none of opponent. Score is with c,r   */
/*  added minus without.                                           */
int heur( ptv,c,r,p )    /* ptv points to base; p CROSS or NOUGHT */
char *ptv   ,p ;
int c,r;
{
       char *ptvv, pv;
        int np[LINE],no[LINE],npl,nop,i,j,nbel,nm;
        int d,w,dir,   ncab,ncbel,nrab,nrbel;
        extern long noeval;
        extern int dc[DIMCOLS];
        static int wt[] = {0,WT1,WT2,WT3,WT4,WT5};
        static int dwt[] = {WT1,WT2-WT1,WT3-WT2,WT4-WT3,WT5-WT4};

    ++noeval;
    w = 0;
    ncbel = min(c-1,LINEM);
    nrbel = min(r-1,LINEM);
    ncab  = min(NOCOLS-c,LINEM);
    nrab  = min(NOROWS-r,LINEM);
    for( dir = 0; dir <= 3  ; ++dir) {
        if(dir == 0) {
                             /* vertical:   |        */
        d = 1;
        nbel = nrbel;                   /* i != nbel since original site */
        nm = nbel + nrab - LINEM;
        ptvv = ptv + dc[c] + r - nbel;
        }
        if(dir == 1) {
                             /* horizontal:  ----      */
        d = DIMROWS;
        nbel = ncbel;
        nm = nbel + ncab - LINEM;
        ptvv = ptv + dc[c-nbel] + r;
        }
        if(dir == 2) {
                             /* diagonal:   /        */
        d = DIMROWP;
        nbel = min(ncbel,nrbel);             /* min3(c-1,r-1,LINEM) */
        nm = nbel + min(ncab,nrab) - LINEM;  /* min3(NOCOLS-c,NOROWS-r,LINEM) */
        if(nm < 0 ) goto nolines;
        ptvv = ptv + dc[c-nbel] + r - nbel;
        }
        if(dir == 3) {
                             /* diagonal:  \         */
        d = DIMROWM;
        nbel = min(ncbel,nrab);               /*   min3(c-1,NOROWS-r,LINEM)  */
        nm = nbel + min(ncab,nrbel) - LINEM;  /*    min3(NOCOLS-c,r-1,LINEM) */
        if(nm < 0 ) goto nolines;
        ptvv = ptv + dc[c-nbel] + r + nbel;
        }

 /* nm+1 lines of four, starting ptvv, with nbel'th being move position */
        for( j = 0; j <= nm ; ++j ) {
                np[j] = 0;           /* initialise stores */
                no[j] = 0;
        }                                        /*  012345 ->i    */
        for( i = 0; i <= nm + LINEM ; ++i ) {    /*  ****    j=0   */
            if( i != nbel ) {                    /*   ****   j=1   */
                pv = *ptvv;                      /*    ****  j=2   */
                if ( pv == p){
                    for( j = max(0,i-LINEM); j <= min(i,nm) ; ++j) {
                            ++np[j];
                    }
                }
                else if(pv == -p) {
                    for( j = max(0,i-LINEM); j <= min(i,nm) ; ++j) {
                            ++no[j];
                    }
                }
                /* else EMPTY so no change in np or no */
            }
            ptvv += d;           /* to next location */
        }

        /* so np[0] is number p's in line 0; no[0] is -p's , etc */
        for ( j = 0 ; j <= nm ; ++j){
                npl = np[j];
                nop = no[j];
                if(npl == 0) {
                    w = w + wt[nop];  /* spoil opponents line, wt[0] = 0 */
                }
                if(nop == 0 ) {
                    w = w + dwt[npl];  /* improve own line */
                }
                /* both nop and npl non zero gives wt zero */
        }
      nolines:   ; /* skip to here if all diagonals are invalid */
    }
        return w;
}
/*  VEH: alpa beta post order game tree evaluation, level l, player p */
int veh(ptv,w,l,p,lb,d)      /* heuristic evaluation of positions */
char *ptv,p;               /* ptv to base */
int l,lb,d,w;    /* w is incremental position value of level ABOVE */
{
        int t,th,ans,c,r;
        extern long noeval;
       char *ptvc, *ptvcr;

        ans = lb;
        ptvc = ptv;
        for ( c = 1 ; c <= NOCOLS ; ++c ) {
                ptvc +=    DIMROWS;    /* base (EMPTY) of col 1,.. */
                if( *(ptvc+ NOROWS) == EMPTY ) { /* valid move: top row free */
                        if( ans >= d ) {
                                return ans;     /* move too good: cut */
                        }
                        r = 0;
                        while( *(ptvc + (++r) )  ) {  /* != EMPTY  */
                        }                       /* ptv,c,r is now row of move */
                        if( l == 1) {           /* last level */
                                t   = w + heur(ptv,c,r,p);
                                ++noeval;
                        }
                        else {
                                th  = w + heur(ptv,c,r,p);
                                if( th  >= 500 )  {   /* win */
                                    t = 999;
                                    ++noeval;
                                }
                                else {
                                    ptvcr = ptvc + r;
                                    *ptvcr  = p;       /* move */
                                    t =  - veh(ptv,-th,l-1,-p,-d,-ans);
                                    *ptvcr  = 0;       /* unmove */
                                }
                        }
                        if(t >  ans )
                                ans = t;
                }
        }
        return ans;
}