Ethan Gunderson

I was recently asked to create a tic-tac-toe game with an unbeatable AI. The first thought that crossed my mind was “Just brute force it!”. Obviously this wasn’t a prime solution, and after a quick google search, I found that the standard algorithm for this scenario is the minimax.

A minimax algorithm is a recursive algorithm for choosing the next move in an n-player game, usually a two-player game. A value is associated with each position or state of the game. This value is computed by means of a position evaluation function and it indicates how good it would be for a player to reach that position. The player then makes the move that maximizes the minimum value of the position resulting from the opponent’s possible following moves. If it is A’s turn to move, A gives a value to each of his legal moves.


The algorithm itself is pretty simple. It plays out any possible remaining moves on a given game board, analysing the board for winners. This is a relatively easy computation for a game like tic-tac-toe, however, the difficulty greatly increases with game like Connect 4, Checkers and becomes nearly impossible in Chess.

My C# implementation consists of a GameBoard and AI class. The GameBoard is an abstract class which contains all of the information nessacary to analyse for winners and make moves.

using System.Collections.Generic;
 
namespace tic_tac_toe
{
  public enum Player
  {
    X = 1,
    O = -1,
    Open = 0,
  }
 
  /// <summary>
  /// Abstract class for creating new game boards, contains all of the logic needed for the AI to play the game.
  /// </summary>
  public abstract class GameBoard
  {
    /// <summary>
    /// Array that contains all of the spaces on the board.
    /// </summary>
    public Player[,] squares;
 
    /// <summary>
    /// Gets or sets a space on the board.
    /// </summary>
    public abstract Player this[int x, int y] { get; set; }
 
    /// <summary>
    /// Determines if all spaces on the board are full.
    /// </summary>
    public abstract bool IsFull { get; }
 
    /// <summary>
    /// Gets the maximum size of the board.
    /// </summary>
    public abstract int Size { get; }
 
    /// <summary>
    /// List of the open spaces available on the current board.
    /// </summary>
    public abstract List<space> OpenSquares { get; }
 
    /// <summary>
    /// Determines if there is a winner on the current board.
    /// </summary>
    public abstract Player Winner { get; }
 
    /// <summary>
    /// Makes a deap copy of the current board
    /// </summary>
    public abstract GameBoard Clone();
  }
 
  /// <summary>
  /// Describes a space on the board.
  /// </summary>
  public struct Space
  {
    public int X;
    public int Y;
    public double Rank;
    public Space(int x, int y)
    {
      this.X = x;
      this.Y = y;
      Rank = 0;
    }
  }
}
</space>

The AI class itself is only has single method, GetBestMove. GetBestMove walks through all available spots on the board, making a move on each spot, and then calling itself with the updated board and the next player to make a move. When the board is complete, the AI will have assigned every open space with a ranking that determines the likelihood of the final outcome if that space is taken next.

using System.Collections.Generic;
 
namespace tic_tac_toe
{
  class AI
  {
    /// <summary>
    /// Implementation of the minimax algorithm.  Determines the best move for the current 
    /// board by playing every move combination until the end of the game.
    /// </summary>
    public static Space GetBestMove(GameBoard gb, Player p)
    {
      Space? bestSpace = null;
      List<space> openSpaces = gb.OpenSquares;
      GameBoard newBoard;
 
      for (int i = 0; i < openSpaces.Count; i++)
      {
        newBoard = gb.Clone();
        Space newSpace = openSpaces[i];
        newBoard[newSpace.X, newSpace.Y] = p;
 
        if (newBoard.Winner == Player.Open && newBoard.OpenSquares.Count > 0)
        {
          Space tempMove = GetBestMove(newBoard, ((Player)(-(int)p)));  //a little hacky, inverts the current player
          newSpace.Rank = tempMove.Rank;
        }
        else
        {
          if (newBoard.Winner == Player.Open)
            newSpace.Rank = 0;
          else if (newBoard.Winner == Player.X)
            newSpace.Rank = -1;
          else if (newBoard.Winner == Player.O)
            newSpace.Rank = 1;
        }
 
        //If the new move is better than our previous move, take it
        if (bestSpace == null ||
           (p == Player.X && newSpace.Rank < ((Space)bestSpace).Rank) ||
           (p == Player.O && newSpace.Rank > ((Space)bestSpace).Rank))
        {
          bestSpace = newSpace;
        }
      }
      return (Space)bestSpace;
    }
  }
}</space>

While this code is not as polished as I would like it to be, I think it does a pretty good just of demonstrating the minimax algorithm.

The full Visual Studio 2008 Solution can be found here

Share and Enjoy:
  • Print this article!
  • Digg
  • Facebook
  • Tumblr
  • Twitter

3 Comments

  1. Ari Block says:
    September 12, 2009 at 8:56 pm

    cool

    Reply
  2. Owen Rumney says:
    February 11, 2010 at 4:46 pm

    Hi

    Great article and well written.

    I’ve built a dummy app to understand the algorithm.

    I’m stepping through the code and everytime I set the newBoard in GetBestMove, my squares array resets to all Open and the new Player value.

    I can only think my Clone isn’t good enough, can you have a look and give me your thoughts?

    Thanks,
    Owen

    public override GameBoard Clone()
    {
    GameBoard clone = new TicTacToeGameBoard();
    clone.squares = new Player[3, 3];
    for (int xIndex = 0; xIndex < 3; xIndex++)
    {
    for (int yIndex = 0; yIndex < 3; yIndex++)
    {
    clone.squares[xIndex, yIndex] = squares[xIndex, yIndex];

    }
    }

    return clone;
    }

    Reply

Leave Your Reply

:D :) :o :eek: :( :lol: :wink: :arrow: :idea: :?: :!: :evil: :p