About

This project is designed to visualize how effective the Minimax AI algorithm is. This is created on Chinese Checkers and for a maximum of 6 players. However this algorithm is very effective for any non real time AI.

My Tasks

My task is to essentially implement all the features of a typical minimax algorithm. Be it from expanding the board state to creating a smart score that the algorithm chooses from. I have also coded everything else in this project, but for the sake of relevance i will only present the things that are related to the Minimax algorithm.

MVC (Model-View-Controller)

The chosen framework for this project is the MVC model. The Controller handles the request flow. The Model handles the data and the View handles the presentation.

The Model is the central component of the patterns and is independent of the user interface. The model's purpose within the framework is to manage data, logic and rules. The View is any form of visual representation of the information. The Controller is responsible for receiving inputs and converting the input into commands for the model and the view.

It's a great framework because it structures the project and makes the workflow easy. This is because it separates the project into 3 sections. As a result this also makes the project a lot less prone to error. If for example an error happens with the visual presentation of the game, you only have to debug and trace the codes within the view. If an error with the way the inputs are handled occurs it has to be within the Controller.

Expanding

Expansion is the process of minimax where the Ai picks the best possible moves based on clones of the board it has been provided. This is done by storing the state after every move and picking the move that returns the highest score.

Score

I calculate the score for my AI by scoring them based on distance. Basically how far the pieces are from the goal. Since this method loops through all the positions I set a score based on the distance from every piece to the goal. I return a score based on every piece's position.

 
  float CalcScore()
  {
    float num = 0;
    var end = Utility.PositionToCoordinates(pos);
  
    foreach (Position p in positions[currentPlayerIndex])
    {
      var start = Utility.PositionToCoordinates(p);
      float dist = Mathf.Abs(Vector2.Distance(end, start));
      num -= dist;
    }
  
    return num;
  }
   
  

Minimax Algorithm

With information provided from the Expansion and Scoring methods it is very easy to implement the algorithm now. The algorithm essentially creates board clones using the Expand method and rates them based on score. Finally picking the board that scored highest.

 
private State Minimax(State state, int playerIndex, int originalPlayerIndex, int depth)
{
  if (depth == 0)
    return (state);

  if (playerIndex == State.players.Count)
    playerIndex = 0;

  if (playerIndex == -1)
    return state;

  if (playerIndex == originalPlayerIndex)
  {
    double bestScore = Int32.MinValue;
    foreach (Istate s in chilStates)
    {
      childState = Minimax(s, playerIndex + 1, originalPlayerIndex, depth - 1);

      double score = childState.Score(player);
      if (childState != null && score > bestScore)
      {
        nextState = s;
        bestScore = score;
      }
    }
  }
  return ((State)nextState);
}