Minmax for ConnectFour

Question

I am trying to implement a minmax algorithm to create an AI for connect four. I'm having quite a bit of trouble with it though as I feel like I have overcomplicated things (and it doesn't work properly), perhaps someone here can help. I'm going to post my code first and then the issue I'm having with it below.

This is the initial call to the minmax algorithm

public int getColumnForMove(ConnectFour game) 
{
    game.minimax(2, game.getCurrentPlayer(), game);
    int column = game.getBestMove();
    return column;
}

This is the initial minimax method (it is inside the ConnectFour class which is not where the initial method is called from that is in a separate AI class) that is called and a subclass that holds each column the user moves into as well as the min/max'ed score if it moves into that column.

class ColumnsAndScores
{
    int column;
    int score;

    ColumnsAndScores(int column, int score)
    {
        this.column = column;
        this.score = score;
    }

}

List<ColumnsAndScores> cas = new ArrayList<>();

public void minimax(int depth, int turn, ConnectFour game)
{
    cas = new ArrayList<>();
    minimaxHelper(depth, depth, turn, game);
}

The following are methods that get the min or max score from each set of possible moves:

public int getMax(List<Integer> list)
{
    int max = Integer.MIN_VALUE;
    int index = -1;

    for (int i = 0; i < list.size(); i++)
    {
        if (list.get(i) > max)
        {
            max = list.get(i);
            index = i;
        }
    }

    return list.get(index);
}

public int getMin(List<Integer> list)
{
    int min = Integer.MAX_VALUE;
    int index = -1;

    for (int i = 0; i < list.size(); i++)
    {
        if (list.get(i) < min)
        {
            min = list.get(i);
            index = i;
        }
    }

    return list.get(index);
}

This is the actual minimax method (it has a bunch of commented out code that shows it should return a range of values depending on how good the board is if its not a clear cut win or loss but right now I'm just trying to have it make decisions based on a win or loss (if none of that happens in the requested depth it makes a random move)).

public int minimaxHelper(int originalDepth, int depth, int turn, ConnectFour game) 
{   
    //holds future game states
    ConnectFour futureGameState;

    //holds the current scores
    List<Integer> scores = new ArrayList<>(); 

    //if (not at the lowest depth)
    if (depth !=0)
    {
        if (checkForWin(turn))
        {
            //return Integer.MAX_VALUE or Integer.MIN_VALUE respectively based on who's turn it is
            return (turn % 2 == 0) ? Integer.MAX_VALUE : Integer.MIN_VALUE;

        }

        //recursively call getColumnForMove(depth--, otherTurn) for each column if the column isnt full
        for (int i = 1; i <= ConnectFour.NUM_OF_COLUMNS; i++)
        {
            futureGameState = new ConnectFour();
            futureGameState.setCurrentGameState(game.getCurrentGameState());
            futureGameState.setCurrentPlayer(game.getCurrentPlayer());
            if (futureGameState.isValidMove(i))
            {
                futureGameState.makeMove(i);
                futureGameState.switchPlayer();
                scores.add(minimaxHelper(originalDepth, depth - 1, futureGameState.getCurrentPlayer(), futureGameState));
            }
            else //if move isnt valid return the worst possible value so this column doesnt get chosen
            {
                return (turn % 2 == 0) ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }

            if (depth == originalDepth)
            {
                ColumnsAndScores newScore;
                if (turn % 2 == 0)
                    newScore = new ColumnsAndScores(i, getMax(scores));
                else
                    newScore = new ColumnsAndScores(i, getMin(scores));

                cas.add(newScore);
            }

        }

        if (turn % 2 == 0)
            return getMax(scores);
        else
            return getMin(scores);

    }
    else
    {
        if (checkForWin(turn))
        {
            //return Integer.MAX_VALUE or Integer.MIN_VALUE respectively based on who's turn it is
            return (turn % 2 == 0) ? Integer.MAX_VALUE : Integer.MIN_VALUE;

        }
        else
        {
            return 0;
        }
        //else
            //if 3 in a row with 2 open spaces that have pieces under those spaces
                //return 100
            //else if 3 in a row with 1 open space that has a piece under that space
                //return 80;
            //else if 3 in a row
                //return 60;
            //else if 2 in a row 
                //return 40
            //else
                //return 0
    }

}

and finally this is a method that is called by the AI to get the best move from the list that minimax added the ColumnAndScores too.

public int getBestMove()
{
    int highestScore = Integer.MIN_VALUE;
  int best = -1;

  for (int i = 0; i < cas.size(); ++i) { 
      if (highestScore < cas.get(i).score) {
         highestScore = cas.get(i).score;
          best = i;
      }
  }

  if (highestScore == 0)
    return 1 + ((int) (Math.random() * 7));
  else
    return best;
}

While I believe there are a couple of logic errors the thing I am having the most difficulty with at the moment is that when I dofutureGameState = new ConnectFour(); futureGameState.setCurrentGameState(game.getCurrentGameState());

This should put it into a separate instance so that when I then make a move it should only last for that branch of the tree and not corrupt the actual game being played but that isn't the case. It is changing the actual state of the game being passed in.

Answer 1

The issue is most probably caused by the implementation of ConnectFour, something like

private int[][] state;
public void setCurrentGameState(int[][] newState) {
    this.state = newState;
}

That's okay, but causes your "copy" of the game state to actually reference the same int[][] state, thus any modifications to it will apply to both states. What you want is

public class ConnectFour implements Cloneable<ConnectFour> {
    private static final int NUM_ROWS = 6;
    private static final int NUM_COLS = 7;
    private int[][] state = new int[NUM_ROWS][NUM_COLS];
    // ...
    public ConnectFour clone() {
        int[][] stateCopy = new int[NUM_ROWS][NUM_COLS];
        for (int i = 0; i < NUM_ROWS; i++)
            for (int j = 0; j < NUM_COLS; j++)
                stateCopy[i][j] = this.state[i][j];
        ConnectFour cloned = new ConnectFour();
        cloned.setCurrentGameState(stateCopy);
        // copy other fields over to cloned
        return cloned;
    }
}

Answer 2

I'm just going to address one issue. You should try not to have too many per question, and include the code relevant to your question, such as your ConnectFour class here.

If you want to make a copy of the board you can modify without changing the original, you need to make a deep copy, not a copy of the reference. To make a shallow copy of your house, you make a copy of your house key. If you give it to someone, you shouldn't be surprised to see changes when you get home. To make a deep copy of your house, you get a second lot and build a new house from blueprints and photos of your house. If you give a key to the new house to someone, he/she might not notice the difference immediately, but any changes shouldn't affect you directly, and changes you make won't affect the recipient.

"Deep copy" is actually ambiguous because your object may contain object members that have object members. When you make a deep copy, you have to decide whether to make deep copies or shallow copies of any member objects. If your ConnectFour class contains an ArrayList of Move objects, each of which is a wrapper for an int representing a column, you have 3 choices:

• You can copy a reference to the ArrayList.
• You can make a new ArrayList with references to the same set of moves.
• You can make a new ArrayList with references to copies of the moves.

Anyway, my guess is that you don't yet have nested member objects, so your deep copy method can look something like the following:

public class ConnectFour{
    private int[][] board = new int[6][7];

    public setCurrentGameState(int[][] state){ 
        for(int i = 0; i<6; i++)
            for(int j=0; j<7; j++)
                board[i][j] = state[i][j];
    }
    ...