Captain's Mistress game written in C, with an AI that utilizes Alpha-Beta depth-limited pruning.

captainm.c

#include <limits.h>
#include <stdio.h>

#define DEPTH (7)

long int max(long int a,long int b){return(a>b?a:b);}
long int min(long int a,long int b){return(a<b?a:b);}
short player();
short ai();

/* The Captain's Mistress game board, with 7 channels 6 slots deep */
short board[7][6];

/* Displays the board to stdout, with Xs as the human player and Os as the AI 
 * player.  Also displays the channel numbers above the board. */
void show()
{
  int col,row;
  puts("  0   1   2   3   4   5   6  ");
  puts("|---|---|---|---|---|---|---|");
  for (row = 0; row < 6; row++) {
    putchar('|');
    for (col = 0; col < 7; col++) {
      if (board[col][row])
	printf(" %c |", (board[col][row] == 1 ? 'X' : 'O'));
      else
	printf("   |");
    }
    puts("\n|---|---|---|---|---|---|---|");
  }
}

/* Drop a piece into the board in a certain channel, returning the row into 
 * which it was dropped.  */
short board_drop(short col, short piece) {
  int r = 5;
  for (; r > -1; r--) {
    if (!board[col][r]) {
      board[col][r] = piece;
      return r;
    }
  }
  return -1;
}

/* Determines if the board is solved.  Return 0 if it is not solved, 1 if the 
 * human player has won, 2 if the AI player has won, and 3 if the board is 
 * full with no player winner. */
short is_solved()
{
  short r,c;
  // check horizontal wins
  for (c = 0; c < 4; c++)
    for (r = 0; r < 6; r++)
      if (board[c][r] && board[c][r]==board[c+1][r] && 
	  board[c+1][r]==board[c+2][r] && board[c+2][r]==board[c+3][r])
	return (board[c][r]);
  // check vertical wins
  for (r = 0; r < 3; r++)
    for (c = 0; c < 7; c++)
      if (board[c][r] && board[c][r]==board[c][r+1] && 
	  board[c][r+1]==board[c][r+2] && board[c][r+2]==board[c][r+3])
	return (board[c][r]);
  // check ^. wins
  for (c = 0; c < 4; c++)
    for (r = 0; r < 3; r++)
      if (board[c][r] && board[c][r]==board[c+1][r+1] && 
	  board[c+1][r+1]==board[c+2][r+2] && board[c+2][r+2]==board[c+3][r+3])
	return (board[c][r]);
  // check .^ wins
  for (c = 0; c < 4; c++)
    for (r = 3; r < 6; r++)
      if (board[c][r] && board[c][r]==board[c+1][r-1] && 
	  board[c+1][r-1]==board[c+2][r-2] && board[c+2][r-2]==board[c+3][r-3])
	return (board[c][r]);
  for (c = 0; c < 7; c++)
    for (r = 0; r < 6; r++)
      if (!board[c][r])
	return 0;
  return 3;
}


int main()
{
  short solved = 0;
  while (1) {
    show(board);
    player(board);
    solved = is_solved();
    if (solved) break;
    ai(board);
    solved = is_solved();
    if (solved) break;
  }
  show(board);
  if (solved == 3)
    puts("WOW, NICE JOB!");
  else
    puts("GOOD GAME!");
  return 0;
}


/* Return the heuristic for the 4-length sequence of tiles held in array 'a'.  
 */
long int ab_heuristic_calc(short *a, short player, short opponent) {
  if ((a[0]+a[1]+a[2]+a[3]) == player*3) {
    if (a[0]!=opponent && a[1]!=opponent && a[2]!=opponent && a[3]!=opponent)
      return 3;
  }
  else if ((a[0]+a[1]+a[2]+a[3]) == opponent*3) {
    if (a[0]!=player && a[1]!=player && a[2]!=player && a[3]!=player)
      return -4;
  }
  return 0;
}
/* Return the heuristic for the board given a certain player. */
long int ab_heuristic(short player) {
  short opponent = (player==2 ? 1 : 2);
  short r,c;
  long int heuristic = 0;
  short setup[4];
  // check horizontal
  for (c = 0; c < 4; c++) {
    for (r = 0; r < 6; r++) {
      setup[0] = board[c][r];
      setup[1] = board[c+1][r];
      setup[2] = board[c+2][r];
      setup[3] = board[c+3][r];
      heuristic += ab_heuristic_calc(setup, player, opponent);
    }
  }
  // check vertical
  for (r = 0; r < 3; r++) {
    for (c = 0; c < 7; c++) {
      setup[0] = board[c][r];
      setup[1] = board[c][r+1];
      setup[2] = board[c][r+2];
      setup[3] = board[c][r+3];
      heuristic += ab_heuristic_calc(setup, player, opponent);
    }
  }
  // check ^.
  for (c = 0; c < 4; c++) {
    for (r = 0; r < 3; r++) {
      setup[0] = board[c][r];
      setup[1] = board[c+1][r+1];
      setup[2] = board[c+2][r+2];
      setup[3] = board[c+3][r+3];
      heuristic += ab_heuristic_calc(setup, player, opponent);
    }
  }
  // check .^
  for (c = 0; c < 4; c++) {
    for (r = 3; r < 6; r++) {
      setup[0] = board[c][r];
      setup[1] = board[c+1][r-1];
      setup[2] = board[c+2][r-2];
      setup[3] = board[c+3][r-3];
      heuristic += ab_heuristic_calc(setup, player, opponent);
    }
  }
  return heuristic;
}
/* Alpha-Beta depth-limited search for the board. */
long int ab(short depth, long int a, long int b, short player) {
  short solved = is_solved();
  // if solved, stop
  if (solved == 1 || solved == 2) {
    return (solved == 2 ? 1024 : -2048);
  } if (solved == 3) {
    return 0;
  }
  // if at the maximum depth, yield the heuristic
  if (depth == 0) {
    return ab_heuristic(player);
  }
  short row, col = 0;
  // iterate through each column, recursing and finding the best move
  for (; col < 7; col++) {
    if (board[col][0])
      continue;
    row = board_drop(col, player);
    if (player == 1)
      b = min(b, ab(depth-1, a, b, 2));
    else
      a = max(a, ab(depth-1, a, b, 1));
    board[col][row] = 0;
    if (b <= a)
      break;
  }
  return (player == 1 ? b : a);
}
/* Let the AI have a move, adding one AI tile to the playing board. */
short ai() {
  printf("Please Wait for Me to move...");
  fflush(stdout);
  long int max_val = LONG_MIN;
  short max_index = 0;
  short row;
  short col = 0;
  // iterate through each column, finding the best column to place a piece in
  for (; col < 7; col++) {
    putchar('.');
    fflush(stdout);
    if (board[col][0])
      continue;
    row = board_drop(col, 2);
    long int heuristic = ab(DEPTH, LONG_MIN, LONG_MAX, 1);
    board[col][row] = 0;
    if (heuristic > max_val) {
      max_index = col;
      max_val = heuristic;
    }
  }
  putchar('\n');
  board_drop(max_index, 2);
  return max_index;
}

/* Allow the player to make a move, causing one player piece to be added to 
 * the board */
short player() {
  short location;
  while (1) {
    printf("Place piece at: ");
    scanf("%hd", &location);
    if (location < 0 || location > 6)
      puts("Invalid location...");
    else if (board[location][0])
      puts("No opening in this channel...");
    else {
      board_drop(location, 1);
      return location;
    }
  }
}