/* connect5.c (prog.c) - Connect-5 game - Don Yang (uguu.org)

   02/19/00
                                                                           */
#include<stdio.h>
#include<time.h>

/* Constants */
#define MARGIN          2

/* Globals (all data are global) */
int board[32 * 32];
int x, y, z, i, j, k, l, rnd;
int size = 5;
int vx[8] = {  1,  1,  1,  0, -1, -1, -1,  0};
int vy[8] = {-32,  0, 32, 32, 32,  0,-32,-32};
int weight[32] = {
   2, 14, 70, 199, 799,   2, 8, 28, 90, 799,    2, 2, 4, 10, 799,
   4, 18, 94, 348, 999,   2, 10, 44, 220, 999,  2, 2, 4, 10, 999 };
int bestmove[1024], moves;
int maxscore, currentscore;

/* Input routine */
void input()
{
   printf("\n\n%% ");
   scanf(" %c%d", &x, &y);

   x = (x | 32) - 'a';
   y--;
}

/* Output routine */
void output()
{
   /* Print top ruler */
   for(x = !printf("\n   "); x < size; printf("%c ", 'a' + x++));

   /* Print cells */
   for(y = 0; y < size;)
      for(x = !printf("\n%2d ", ++y);
          x < size;
          printf("%c ",
             board[(y + 3) * 32 + 4 + x++]));
}

/* Expand board */
void expandboard()
{
   if( size < 24 )
      for(i = 0; i < MARGIN; i++)
         for(j = 0; j < size; j++)
         {
            /* Top left */
            if( board[(i + 4) * 32 + j + 4] - '.' )
            {
               for(k = 32 * 32 - 1; k >= 4 * 32 + 4;
                   board[k--] = board[k - 33]);
               size++;
               expandboard();
               return;
            }

            /* Top right */
            if( board[(j + 4) * 32 + (size - i - 1) + 4] - '.' )
            {
               for(k = 32 * 32 - 1; k >= 4 * 32 + 4;
                   board[k--] = board[k - 32]);
               size++;
               expandboard();
               return;
            }

            /* Bottom right */
            if( board[(size - i - 1 + 4) * 32 + (size - j - 1) + 4] - '.' )
            {
               size++;
               expandboard();
               return;
            }

            /* Bottom left */
            if( board[(size - j - 1 + 4) * 32 + i + 4] - '.' )
            {
               for(k = 32 * 32 - 1; k >= 4 * 32 + 4;
                   board[k--] = board[k - 1]);
               size++;
               expandboard();
               return;
            }
         }
}

/* Calculate computer move */
void think()
{
   maxscore = moves = 0;

   for(x = 4 * 32 + 4; x < 28 * 32 + 28; x++)
      if( x % 32 >= 4 && x % 32 < 28 && board[x] == '.' )
      {
         currentscore = 0;
         for(y = 'o'; y < 'y'; y += 'x' - 'o')
         {
            board[x] = y;
            for(z = 0; z < 8; z++)
            {
               for(l = x - (j = vx[z] + vy[z]);
                   board[l] == y;
                   l -= j);
               k = board[l] - '.' ? 5 : 0;
               for(i = 0; board[l += j] == y && i < 5; i++);
               currentscore += weight[
                  (y - 'x' ? 15 : 0) +
                  (k += board[l] - '.' ? 5 : 0) +
                  i - 1];
            }
         }
         board[x] = '.';
         if( currentscore > maxscore )
         {
            maxscore = currentscore;
            moves = 0;
         }
         if( currentscore == maxscore )
            bestmove[moves++] = x;
      }
}

/* Victory test */
int victory()
{
   for(x = j = 132; x < 924 && j - 5; x++)
      if( (z = board[x]) - '.' )
         for(y = 0; y < 4 && j - 5; y++)
            for(i = j = 1; i < 5 && j < 5;
                j += board[x + (vx[y] + vy[y]) * i++] - z ? 0 : 1);
   return j == 5;
}

/* Main program */
void main()
{
   /* Reset board */
   for(x = 0; x < 32 * 32; board[x++] = '.');

   /* Main loop */
   for(weight[(rnd = time(0)) & 0x1f]++; !victory();)
   {
      /* Get player input */
      expandboard();
      output();
      input();
      board[(y + 4) * 32 + x + 4] = 'x';
      rnd += x;
      if( rnd < 0 )
         rnd = -rnd;

      if( victory() )
         break;

      /* Get computer input */
      expandboard();
      think();
      board[bestmove[rnd % moves]] = 'o';
   }

   x--;
   y--;
   for(i = 0; i < 5;
       board[x + (vx[y] + vy[y]) * i++] &= ~32);
   output();

   puts(z == 'x' ? "\nYou win" : "\nYou lose");
}