#import <stdlib.h>

#import <Foundation/Foundation.h>

@interface Connect4Model : NSObject <NSCopying>
{
@private

  char **board;
  int width;
  int height;
  int turn;
}

/**
 * Creates a board of the default size.  The board is initially empty.
 */

-(id) init;

/**
 * Creates a board of the given size.  The board is initially empty.
 *
 * @param w a positive integer
 * @param h a positive integer
 */

-(id) initWithWidth:(int)w andHeight:(int)h;

/**
 * Creates a deep copy of this board.
 *
 * @return a deep copy of this board
 */

-(id) copyWithZone:(NSZone*)zone;

/**
 * Determines if a move in the given column is legal.
 * A move is legal if and only if there is space left in the column.
 *
 * @param c a column index
 * @return true iff the move is legal
 */

-(BOOL) isLegalMove:(int)c;

/**
 * Updates this state by making a move in the given column.
 *
 * @param c a column index on this board
 */

-(void) makeMoveAtCol:(int)c;

/**
 * Undoes a move in the given column.
 *
 * @param c a column index on this board
 */

-(void) undoMoveAtCol:(int)c;

/**
 * Returns the index of the player who is on the move.
 *
 * @return the index of the player on the move
 */

-(int)getPlayerOnMove;

/**
 * Returns the width of this board.
 *
 * @return the width of this board
 */

-(int) getWidth;

/**
 * Returns the height of this board.
 *
 * @return the height of this board
 */

-(int) getHeight;

/**
 * Returns the index of the player who has a piece at the given
 * position on this board.  If there is no piece at the given
 * position then the return value is -1.
 *
 * @param r the index of a row on this board
 * @param c the index of a column on this board
 * @return the index of the player with a piece at that position
 */

-(int)getPieceAtRow:(int)r andCol:(int)c;

/**
 * Determines if the given space is on this board.
 *
 * @param col an integer
 * @return true iff that position is on this board
 */

-(BOOL) isValidCol:(int)c;

/**
 * Determines if the given column is full.
 *
 * @param col the index of a column on this board
 * @retrun true iff that column is full
 */

-(BOOL) isFull:(int)col;

/**
 * Returns all the legal moves on this board.  The list is returned as
 * an NSArray containing NSNumber
 * objects where each NSNumber represents an integer column index.
 * The returned array will be autoreleased.
 *
 * @return a list of the legal moves on this board
 */

-(NSArray*) getLegalMoves;

/**
 * Determines if a game with this board is over. 
 *
 * @return true iff this board represents a terminal state
 */

-(BOOL) isGameOver;

/**
 * Determines if all spaces are full on this board.
 *
 * @return true iff all spaces are full
 */

-(BOOL) allFull;

/**
 * Determines who has won this game.  If the game is not over, then
 * this method returns 0.  If someone has won, this method returns
 * the game theoretic value from the current player's point of view.
 *
 * @return the winner
 */

-(int) getWinner;

/**
 * Returns a heuristic value for this board.  The value is from the
 * point of view of the current player.
 *
 * @return a heuristic value
 */

-(double) getHeuristicValue;

/**
 * Returns the minimax value of this state.  The minimax tree is
 * explored to the given depth, at which point the heuristic value is
 * used.
 *
 * @param d a nonnegative integer
 * @return the minimax value of this state
 */

-(double) minimaxValueWithMaxDepth:(int)d;

/**
 * Returns the alpha-beta value of this using the given window and
 * depth bound.  Nodes at the depth bound will be evaluated by the
 * heuristic.
 *
 * @param alpha
 * @param beta
 * @param d a nonnegative integer
 * @return the alpha-beta value of this state
 */

-(double) alphaBetaValue:(double)alpha :(double)beta :(int)d;

/**
 * Returns the best move as found by alpha-beta pruning with the given
 * depth bound.  Nodes at the depth bound are evaluated using the
 * heuristic.  If the window is sufficiently wide (-1, 1) and the depth
 * bound is sufficiently large (42) then the returned value will equal the
 * (unbounded depth) minimax value.
 *
 * @param d a nonnegative integer
 * @return the index of the best column to move in
 */

-(int) alphaBetaMoveWithMaxDepth:(int)d;

/**
 * Returns the Monte Carlo value of this state.  The value is the mean
 * value of playing the given number of games using moves chosen randomly
 * and uniformly.  If a game is not completed using the given number of
 * turns then the heuristic is applied to evaluate it.
 *
 * @param variations the number of random sequences of moves to try;
 * a positive integer
 * @param max the maximum number of random moves on each variation;
 * a positive integer
 * @return the Monte Carlo value of this state
 */

-(double) monteCarloValueWithVariations:(int)variations andMaxTurns:(int)max;

/**
 * Returns the result of one Monte Carlo completion of this state.
 * If the game is not completed after the given number of moves then
 * the heuristic value is used.
 *
 * @param max the maximum number of random moves to play; a positive integer
 * @return the MonteCarlo value of this state
 */

-(double) monteCarloValueWithMaxTurns:(int)max;

/**
 * Returns the best move from this state as found by a Monte Carlo simulation.
 * The simulation will play the given number of variations each consisting
 * of up to the given number of moves.  The moves are chosen randomly and
 * uniformly.  Any game that is not complete by the given number of turns
 * is evaluated by the heiristic function.
 *
 * @param variations the number of random sequences of moves to try;
 * a positive integer
 * @param max the maximum number of random moves on each variation;
 * a positive integer
 * @return the column of the best move
 */

-(int) monteCarloMoveWithVariations:(int)variations andMaxTurns:(int)max;

@end

c4model.m

#import <stdlib.h>

#import "c4model.h"

@interface Connect4Model (Private)
/**
 * Determines the game-theoretic value of a state in which the given mark
 * has won and it is the given player's turn.  The value is from the
 * point of view of the current player.  The marks corresponnding to
 * players are assumed to be 'X' for P0 and 'O' for P1.
 *
 * @param mark 'X' or 'O'
 * @param num 0 or 1
 * @return the value of a state with that winner on that player's turn
 */
 
+(int) determineValue:(char)mark onTurn:(int)num;

/**
 * Determines if either player has 4 in a row starting at the given
 * position and going in the given direction.
 *
 * @param r a row index on this board
 * @param c a column index on this board
 * @param dr -1, 0, or 1
 * @param dc -1, 0, or 1
 * @return true iff a player has a win at that location in that direction
 */
 
-(BOOL) checkWinAtRow:(int)r andCol:(int)c inDirR:(int)dr andC:(int)dc;
@end

@implementation Connect4Model

-(id) init
{
  return [self initWithWidth:7 andHeight:6];
}

-(id) initWithWidth:(int)w andHeight:(int)h
{
  [super init];

  if (w <= 0 || h <=0)
    {
      [self error:"Dimensions must be positive"];
    }

  width = w;
  height = h;
  turn = 0;

  board = malloc(sizeof(char *) * height);
  for (int r = 0; r < height; r++)
    {
      board[r] = malloc(sizeof(char) * width);
      for (int c = 0; c < width; c++)
	{
	  board[r][c] = '.';
	}
    }
  
  return self;
}

-(void) dealloc
{
  for (int r = 0; r < height; r++)
    {
      free(board[r]);
    }
  free(board);

  [super dealloc];
}

-(id) copyWithZone:(NSZone*)zone
{
  Connect4Model* clone = [Connect4Model allocWithZone:zone];
  [clone init];

  clone->width = width;
  clone->height = height;
  clone->turn = turn;

  clone->board = malloc(sizeof(char *) * height);
  for (int r = 0; r < height; r++)
    {
      clone->board[r] = malloc(sizeof(char) * width);
      for (int c = 0; c < width; c++)
	{
	  clone->board[r][c] = board[r][c];
	}
    }

  return clone;
}

-(BOOL) isLegalMove:(int)c
{
  // check for game over

  if ([self getWinner] != 0)
    {
      return NO;
    }

  // check for valid column

  if (![self isValidCol:c])
    {
      return NO;
    }

  // check for room left in col

  if ([self isFull:c]) 
    {
      return NO;
    }

  // nothing else could go wrong; move is legal

  return YES;
}

-(void) makeMoveAtCol:(int)c
{
  // find top of stack in column c
  
  int r = 0;

  while (r < height && board[r][c] == '.')
    {
      r++;
    }

  if (turn == 0)
    {
      board[r - 1][c] = 'X';
      turn = 1;
    }
  else
    {
      board[r - 1][c] = 'O';
      turn = 0;
    }
}

-(void) undoMoveAtCol:(int)c
{
  // find top of stack in column c
  
  int r = 0;

  while (r < height && board[r][c] == '.')
    {
      r++;
    }

  board[r][c] = '.';

  if (turn == 0)
    {
      turn = 1;
    }
  else
    {
      turn = 0;
    }
}

-(BOOL) isValidCol:(int)c
{
  return (c >= 0 && c < width);
}

-(BOOL) isFull:(int)c
{
  return (board[0][c] != '.');
}

-(NSArray*) getLegalMoves
{
  NSMutableArray* moves = [[[NSMutableArray alloc] init] autorelease];

  for (int c = 0 ; c < width; c++)
    {
      if (![self isFull:c])
	{
	  [moves addObject:[NSNumber numberWithInt:c]];
	}
    }

  return moves;
}

-(BOOL) isGameOver
{
  // first, check for a draw

  if ([self allFull])
    {
      return YES;
    }
  
  int winner = [self getWinner];

  return (winner != 0);
}

-(BOOL) allFull
{
  int c = 0;

  while (c < width && [self isFull:c])
    {
      c++;
    }

  return (c == width);
}

-(int) getWinner
{
  // now check for a winner at each top or left or bottom/left or top/left
  // position

  for (int startR = 0; startR < height; startR++)
    {
      for (int startC = 0; startC < width; startC++)
	{
	  if (board[startR][startC] != '.')
	    {
	      // check for vertical win
	      
	      if (startR + 4 <= height
		  && [self checkWinAtRow:startR andCol:startC inDirR:1 andC:0])
		{
		  return [Connect4Model determineValue:board[startR][startC] onTurn:turn];
		}
	  
	      // check for horizontal win
	      
	      if (startC + 4 <= width
		  && [self checkWinAtRow:startR andCol:startC inDirR:0 andC:1]) 
		{
		  return [Connect4Model determineValue:board[startR][startC] onTurn:turn];
		}
	      
	      // check for diag top/left -> bot/right win
	      
	      if (startC + 4 <= width && startR + 4 <= height
		  && [self checkWinAtRow:startR andCol:startC inDirR:1 andC:1]) 
		{
		  return [Connect4Model determineValue:board[startR][startC] onTurn:turn];
		}
	      
	      // check for diag bot/left -> top/right win
	      
	      if (startC + 4 <= width && startR - 4 >= -1
		  && [self checkWinAtRow:startR andCol:startC inDirR:-1 andC:1]) 
		{
		  return [Connect4Model determineValue:board[startR][startC] onTurn:turn];
		}
	    }
	}
    }

  return 0;
}

-(BOOL) checkWinAtRow:(int)r andCol:(int)c inDirR:(int)dr andC:(int)dc
{
  int step = 1;

  while (step < 4 && board[r + step * dr][c + step * dc] == board[r][c])
    {
      step++;
    }

  return (step == 4);
}

-(BOOL) scorePossibleWinAtRow:(int)r andCol:(int)c inDirR:(int)dr andC:(int)dc
{
  int step = 0;
  char mark = '.';
  int stepR = r;
  int stepC = c;
  int count = 0;

  while (step < 4 && (mark == '.' || board[stepR][stepC] == mark))
    {
      if (board[stepR][stepC] != '.')
	{
	  mark = board[stepR][stepC];
	  count++;
	}
      step++;
      stepR += dr;
      stepC += dc;
    }

  if (step == 4)
    {
      if (mark == '.')
	{
	  return 0;
	}
      else if (mark == turn)
	{
	  return count;
	}
      else
	{
	  return -count;
	}
    }
  else
    {
      return 0;
    }
}

-(double) getHeuristicValue
{
  // TODO: make this more efficient: scorePossible win will return +/- 4
  // if someone has won, so we don't have to go over all the possible
  // 4-in-a-row locations twice as we do below (once in getWinner and
  // then again in the loops)

  // return actual value if game is over...

  int winner = [self getWinner];
  
  if (winner != 0)
    {
      return winner;
    }

  if ([self allFull])
    {
      return 0;
    }

  // ...otherwise, see who has control of all the possible 4-in-a-row
  // locations and how close they are to them (1 of 4, 2 of 4, 3 of 4)

  int onMoveScore;
  int offMoveScore;

  for (int startR = 0; startR < height; startR++)
    {
      for (int startC = 0; startC < width; startC++)
	{
	  // get score for vertical run
	  
	  if (startR + 4 <= height)
	    {
	      int score = [self scorePossibleWinAtRow:startR andCol:startC inDirR:1 andC:0];

	      if (score < 0)
		{
		  offMoveScore += -score;
		}
	      else
		{
		  onMoveScore += score;
		}
	    }
	  
	  // check for horizontal win
	      
	  if (startC + 4 <= width)
	    {
	      int score = [self scorePossibleWinAtRow:startR andCol:startC inDirR:0 andC:1];
	      
	      if (score < 0)
		{
		  offMoveScore += -score;
		}
	      else
		{
		  onMoveScore += score;
		}
	    }
	  
	  // check for diag top/left -> bot/right win
	  
	  if (startC + 4 <= width && startR + 4 <= height)
	    {
	      int score = [self scorePossibleWinAtRow:startR andCol:startC inDirR:1 andC:1];
	      
	      if (score < 0)
		{
		  offMoveScore += -score;
		}
	      else
		{
		  onMoveScore += score;
		}
	    }
	  
	  // check for diag bot/left -> top/right win
	  
	  if (startC + 4 <= width && startR - 4 >= -1)
	    {
	      int score = [self scorePossibleWinAtRow:startR andCol:startC inDirR:-1 andC:1];
	      
	      if (score < 0)
		{
		  offMoveScore += -score;
		}
	      else
		{
		  onMoveScore += score;
		}
	    }
	}
    }
  
  if (onMoveScore == 0 && onMoveScore == 0)
    {
      return 0.0;
    }
  else
    {
      return (double)onMoveScore / (onMoveScore + offMoveScore) - 0.5;
    }
}

+(int) determineValue:(char)mark onTurn:(int)num
{
  if (mark == 'X' && num == 0)
    {
      return 1;
    }
  else if (mark == 'O' && num == 1)
    {
      return 1;
    }
  else if (mark != '.')
    {
      return -1;
    }
  else
    {
      return 0;
    }
}

-(int) alphaBetaMoveWithMaxDepth:(int)d
{
  double max; // lower than any possible value
  int bestMove = -1;

  NSEnumerator* e = [[self getLegalMoves] objectEnumerator];
  NSNumber* object;
  while ((object = [e nextObject]) != nil)
    {
      int col = [object intValue];

      [self makeMoveAtCol:col];

      double value = -[self minimaxValueWithMaxDepth:d];

      printf("%d:%f ", col, value);

      [self undoMoveAtCol:col];

      if (bestMove == -1 || value > max)
	{
	  max = value;
	  bestMove = col;
	}
    }

  printf("\n");

  return bestMove;
}
 
-(double) minimaxValueWithMaxDepth:(int)d
{
  return [self alphaBetaValue:-1 :1 :d];
}

-(double) alphaBetaValue:(double)alpha :(double)beta :(int)d
{
  NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];

  if ([self getWinner] != 0 || [self allFull])
    {
      return [self getWinner];
    }
  
  if (d == 0)
    {
      return [self getHeuristicValue];
    }

  NSEnumerator* e = [[self getLegalMoves] objectEnumerator];
  NSNumber* move;
  while (alpha < beta && (move = [e nextObject]) != nil)
    {
      // make the move

      int moveCol = [move intValue];

      [self makeMoveAtCol: moveCol];

      // get alpha-beta value of new state

      double a = -[self alphaBetaValue:-beta :-alpha :d - 1];  

      // undo move

      [self undoMoveAtCol: moveCol];

      if (a > alpha)
	{
	  alpha = a;
	}

      if (alpha >= beta)
	{
	  [pool release];
	  return alpha;
	}
    }

  [pool release];
  return alpha;
}

-(double) monteCarloValueWithVariations:(int)variations andMaxTurns:(int)max
{
  double totValue = 0.0;

  for (int v = 0; v < variations; v++)
    {
      NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];

      totValue += [self monteCarloValueWithMaxTurns:max];

      [pool release];
    }

  return totValue / variations;
}

-(double) monteCarloValueWithMaxTurns:(int)max
{
  // check for game over

  int winner = [self getWinner];

  if (winner != 0)
    {
      return winner;
    }

  if ([self allFull])
    {
      return 0.0;
    }

  // apply heuristic if at depth bound

  if (max == 0)
    {
      return [self getHeuristicValue];
    }

  // make a random move and find Monte Carlo value of the resulting state

  NSArray* moves = [self getLegalMoves];
  
  int i = random() % [moves count];
  NSNumber* move = [moves objectAtIndex:i];
  int col = [move intValue];

  [self makeMoveAtCol:col];

  double value = -[self monteCarloValueWithMaxTurns:max - 1];

  [self undoMoveAtCol:col];

  return value;
}

-(int) getPlayerOnMove
{
  return turn;
}

-(int) getWidth
{
  return width;
}

-(int) getHeight
{
  return height;
}

-(int)getPieceAtRow:(int)r andCol:(int)c
{
  switch (board[r][c])
    {
    case 'X':
      return 0;
      
    case 'O':
      return 1;

    default:
      return -1;
    }
}

-(int) monteCarloMoveWithVariations:(int)variations andMaxTurns:(int)max
{
  double bestValue; // lower than any possible value
  int bestMove = -1;

  NSEnumerator* e = [[self getLegalMoves] objectEnumerator];
  NSNumber* object;
  while ((object = [e nextObject]) != nil)
    {
      int col = [object intValue];

      [self makeMoveAtCol:col];

      double value = -[self monteCarloValueWithVariations:variations andMaxTurns:max - 1];

      [self undoMoveAtCol:col];

      if (bestMove == -1 || value > bestValue)
	{
	  bestValue = value;
	  bestMove = col;
	}
    }

  return bestMove;
}

@end

main.m

#import <Foundation/Foundation.h>
#import <AppKit/AppKit.h>

#import "c4delegate.h"

int main(int argc, const char **argv)
{
  [NSApplication sharedApplication];

  // NSApp is a global variable declared elsewhere that is set by
  // NSApplication.sharedApplication to whatever that method returns

  [NSApp setDelegate: [[Connect4Delegate alloc] init]];

  return NSApplicationMain(argc, argv);
}

c4delegate.h

#import <AppKit/AppKit.h>

#import "c4delegate.h"

@interface Connect4Delegate : NSObject

-(void) applicationWillFinishLaunching:(NSNotification*) not;

-(void) startBlack:(id)sender;

-(void) startRed:(id)sender;
@end

c4delegate.m

#import "c4delegate.h"
#import "c4view.h"
#import "c4model.h"

@implementation Connect4Delegate

-(void) applicationWillFinishLaunching:(NSNotification*) not
{
  NSMenu* menu = [[[NSMenu alloc] init] autorelease];

  [menu addItemWithTitle:@"Play Black"
	action:@selector(startBlack:)
	keyEquivalent: @"b"];

  [menu addItemWithTitle:@"Play Red"
	action:@selector(startRed:)
	keyEquivalent: @"r"];

  [menu addItemWithTitle:@"Quit"
	action:@selector(terminate:)
	keyEquivalent: @"q"];

  [NSApp setMainMenu:menu];
}

-(void) startBlack:(id)sender
{
  NSWindow* win = [[NSWindow alloc] initWithContentRect:NSMakeRect(100, 100, 400, 400)
				    styleMask: (NSTitledWindowMask
						| NSMiniaturizableWindowMask
						| NSClosableWindowMask
						| NSResizableWindowMask)
				    backing: NSBackingStoreBuffered
				    defer: NO];

  Connect4Model* model = [[Connect4Model alloc] init];

  [win setTitle:@"Connect 4"];
  [win makeKeyAndOrderFront:nil];
  [win setContentView: [[Connect4View alloc] initWithModel:model withHuman:0]];

  [model release];
}

-(void) startRed:(id)sender
{
  NSWindow* win = [[NSWindow alloc] initWithContentRect:NSMakeRect(100, 100, 400, 400)
				    styleMask: (NSTitledWindowMask
						| NSMiniaturizableWindowMask
						| NSClosableWindowMask
						| NSResizableWindowMask)
				    backing: NSBackingStoreBuffered
				    defer: NO];

  Connect4Model* model = [[Connect4Model alloc] init];

  [win setTitle:@"Connect 4"];
  [win makeKeyAndOrderFront:nil];
  [win setContentView: [[Connect4View alloc] initWithModel:model withHuman:1]];

  [model release];
}
@end

c4view.h

#import <AppKit/AppKit.h>

#import "c4model.h"

@interface Connect4View : NSView
{
@private
  Connect4Model* model;
  int humanPlayer;
}

-(id) initWithModel:(Connect4Model*)m withHuman:(int)i;
-(void) drawRect:(NSRect) rect;
-(void) dealloc;
-(void) mouseDown:(NSEvent*) event;
@end

c4view.m

#import <stdio.h>

#import "c4view.h"

@interface Connect4View (Private)
-(int) getCellSize;
@end

@implementation Connect4View

-(id) initWithModel:(Connect4Model*)m withHuman:(int)i
{
  [super init];

  model = [m retain]; // TODO: release when window goes away
  humanPlayer = i;

  // make first move for computer if appropriate

  if (humanPlayer == 1)
    {
      [model makeMoveAtCol:[model monteCarloMoveWithVariations:100 andMaxTurns:20]];
    }

  return self;
}

-(void) drawRect:(NSRect) rect
{
  // figure out which dimension is the limiting one

  int cellSize = [self getCellSize];

  // draw the grid

  for (int r = 0; r < [model getHeight]; r++)
    {
      for (int c = 0; c < [model getWidth]; c++)
	{
	  int x = c * cellSize;
	  int y = ([model getHeight] - r - 1) * cellSize;

	  NSBezierPath* outline = [NSBezierPath bezierPathWithRect: NSMakeRect(x, y, cellSize - 1, cellSize - 1)];
	  [[NSColor blueColor] set];
	  [outline stroke];

	  int mark = [model getPieceAtRow:r andCol:c];
	  if (mark != -1)
	    {
	      NSBezierPath *piece = [NSBezierPath bezierPathWithOvalInRect: NSMakeRect(x + 1, y + 1, cellSize - 2, cellSize - 2)];

	      if (mark == 0)
		{
		  [[NSColor blackColor] set];
		}
	      else
		{
		  [[NSColor redColor] set];
		}

	      [piece fill];
	    }
	}
    }
}

-(void) dealloc
{
  [model release];

  [super dealloc];
}

-(void) mouseDown:(NSEvent*) event
{
  // get location of click and convert from window's coords to this view's

  NSPoint loc = [self convertPoint:[event locationInWindow] fromView:nil];

  // compute grid location that was clicked on (only col really matters
  // for connect 4)

  int cellSize = [self getCellSize];
  int row = [model getHeight] - 1 - loc.y / cellSize;
  int col = loc.x / cellSize;

  if (row >= 0 && row < [model getHeight] && col >= 0 && col < [model getWidth]
      && [model isLegalMove:col])
    {
      // update model with human's move
      
      [model makeMoveAtCol:col];

      // make computer's move

      if ([model getWinner] == 0 && ![model allFull])
	{
	  [model makeMoveAtCol:[model monteCarloMoveWithVariations:100 andMaxTurns:20]];
	}
      
      // request redraw
      
      [self setNeedsDisplay:YES];
    }
}
@end

@implementation Connect4View (Private)
-(int) getCellSize
{
  int width = [self bounds].size.width;
  int height = [self bounds].size.height;
  
  int cellW = width / [model getWidth];
  int cellH = height / [model getHeight];
  return (cellW < cellH ? cellW : cellH);
}
@end

GNUmakefile

GNUSTEP_MAKEFILES = /usr/share/GNUstep/Makefiles
ADDITIONAL_OBJCFLAGS = "-std=c99"

include $(GNUSTEP_MAKEFILES)/common.make

APP_NAME = Connect4
Connect4_APPLICATION_ICON = connect4.png
Connect4_RESOURCE_FILES = connect4.png
Connect4_OBJC_FILES = c4delegate.m c4view.m c4model.m main.m

include $(GNUSTEP_MAKEFILES)/application.make