MiniMax Algorithm

Question

This is my C implementation of the Minimax Algorithm to play tic-tac-toe. I consider myself a C beginner so any feedback on style, best practices, or efficiency is more than welcome.

# define HUMAN_PLAYER 'X'
# define AI_PLAYER 'O'
# define NONE '\0'

typedef struct Point {
  int x, y;
} Point;

typedef struct Board {
  Point location;
  Point boundary;
  int size;
  int current_player;
  int last_player;
  int nmoves_played;
  int ai_mode;
  char last_cell_symbol;
  char **cells;
} Board;

typedef struct MiniMaxMove {
    int score;
    int x;
    int y;
} MiniMaxMove;

int has_won(Point last_destination, char player, Board *board) {
  // columns
  for (int i = 0; i < board->size; i++) {
      if (board->cells[last_destination.x][i] != player)
          break;
      if (i == board->size - 1) {
          return 1;
      }
  }

  // rows
  for (int i = 0; i < board->size; i++) {
      if (board->cells[i][last_destination.y] != player)
          break;
      if (i == board->size - 1) {
          return 1;
      }
  }

  // diagonal
  if (last_destination.x == last_destination.y) {
      for (int i = 0; i < board->size; i++) {
          if (board->cells[i][i] != player)
              break;
          if (i == board->size - 1) {
              return 1;
          }
      }
  }

  // anti diagonal
  if (last_destination.x + last_destination.y == board->size - 1) {
      for (int i = 0; i < board->size; i++) {
          if (board->cells[i][(board->size-1)-i] != player)
              break;
          if (i == board->size - 1){
              return 1;
          }
      }
  }

  return 0;
}

int is_a_draw(Board *board) {
    if (board->nmoves_played == (pow(board->size, 2) - 1)) {
        return 1;
    }

    return 0;
}


MiniMaxMove minimax(Point last_destination, char player, Board *board) {
  if (has_won(last_destination, HUMAN_PLAYER, board)) {
      return (MiniMaxMove) { .score = -10 };
  } else if (has_won(last_destination, AI_PLAYER, board)) {
      return (MiniMaxMove) { .score = 10 };
  } else if (is_a_draw(board)) {
      return (MiniMaxMove) { .score = 0 };
  }

  MiniMaxMove *moves = malloc(sizeof(MiniMaxMove *) * board->size * board->size);
  size_t moves_size = 0;

  for (int i = 0; i < board->size; i++) {
      for (int j = 0; j < board->size; j++) {
          if (board->cells[i][j] == '\0') {
              MiniMaxMove move;
              move.x = i;
              move.y = j;

              board->cells[i][j] = player;

              // caclulate the score for the opponent
              if (player == AI_PLAYER) {
                  MiniMaxMove mm_move = minimax(last_destination, HUMAN_PLAYER, board);
                  move.score = mm_move.score;
              } else if (player == HUMAN_PLAYER) {
                  MiniMaxMove mm_move = minimax(last_destination, AI_PLAYER, board);
                  move.score = mm_move.score;
              }

              // reset the board to what it was
              board->cells[i][j] = '\0';

              moves[moves_size++] = move;

          }
      }
  }

  int best_move_idx;
  if (player == AI_PLAYER) {
      int best_score = -10000;
      for (unsigned int i = 0; i < moves_size; i++) {
          if (moves[i].score > best_score) {
              best_score = moves[i].score;
              best_move_idx = i;
          }
      }
  } else {
      int best_score = 10000;
      for (unsigned int i = 0; i < moves_size; i++) {
          if (moves[i].score < best_score) {
              best_score = moves[i].score;
              best_move_idx = i;
          }
      }
  }

    return moves[best_move_idx];
}

Answer 1

From a quick glance, the code looks pretty OK; good use of structs, relatively self-contained functions, nice indentation. So it's mainly some small stuff that can be improved:

Use static const variables instead of #define

Instead of

# define HUMAN_PLAYER 'X'

Write:

static const char HUMAN_PLAYER = 'X';

Consider using enums

Instead of passing a char around to represent the player, you could use an enum instead. This makes it clear that it is a separate type. For example:

typedef enum player {
  NONE = '\0',
  HUMAN_PLAYER = 'X',
  AI_PLAYER = 'O',
} player_t;

Use bool types where appropriate

Instead of returning the integers 1 and 0 to indicate success and failure, use the bool type. For example:

#include <stdbool.h>
...
bool has_won(Point last_destination, char player, Board *board) {
  // columns
  for (int i = 1; i < board->size; i++) {
    if (board->cells[last_destination.x][i] != player)
      break;
    if (i == board->size - 1) {
      return true;
    }
  }
}

Simplify if (foo) return true; else return false

Just return foo directly! For example:

bool is_a_draw(Board *board) {
  return board->nmoves_played == pow(board->size, 2) - 1;
}

Avoid floating point functions when working with integers

The expression pow(board->size, 2) will convert your integers to doubles, and later on they will probably be converted back to something else. It is best to avoid this, and just write board->size * board->size. If you square integers often, write a simple function that does this:

int square(int x) {
  return x * x;
}

Or in this case, you could maybe store the square of the board size in its own variable.

Use sizeof(variable) instead of sizeof(type) where possible

As @chux already mentioned, you have an error using sizeof. It is always best to repeat the variable name instead of its type, and ensure you take the size of the struct itself, not of the pointer. So:

MiniMaxMove *moves = malloc(sizeof *moves * board->size * board->size);

Don't use arbitrary limits

You are setting some arbitrary limits for best_score:

int best_score = -10000;

This in effect puts a limit on your board size. Either you should use the actual lowest value possible for an int here:

#include <limits.h>
...
int best_score = INT_MIN;

Or initialize it using the first score found:

  int best_move_idx = 0;
  int best_score = moves[0].score;
  if (player == AI_PLAYER) {
    for (unsigned int i = 1; i < moves_size; i++) {
      if (moves[i].score > best_score) {
        ...

Always free the memory you allocated

You called malloc(), but I don't see a free(). In your case, I would do the following to clean up the array properly, while not causing a problem with the return statement:

  ...
  MiniMaxMove best_move = moves[best_move_idx];
  free(moves);
  return best_move;
}

Avoid allocating memory if it is not necessary

Looking closer at the code, you don't actually need to allocate the array moves at all. In the first for-loop in minimax(), you add items to the array, and then later you are just trying to find the best item in the array. You could instead just keep track of only the best item found so far in the first for-loop! So instead of:

moves[moves_size++] = move;

Don't allocate the array moves, just keep one MiniMaxMove best_move around, and replace the above line with something like:

if (player == AI_PLAYER) {
  if (move.score > best_move.score) {
     best_move = move;
  }
} else {
  if (move.score < best_move.score) {
     best_move = move;
  }
}