0
\$\begingroup\$

This question already has an answer here:

I am trying to create me one of those connect four games. I was doing some research on it and i found it to be quite a nice little self project. So I made strides in getting the game to run. So it works like a two person game but i don't really like the idea of two players. My goal is to create a player vs computer connect four. I took it upon myself and do some reasearch as to how to get an AI vs Human game and I came across using the MinMax algorithm to accomplish my goal. I am a bit lost when it comes to implementing the MinMax algorithm. I came accross which seems to be a marvellous implementation of minmax Here. I have been struggling for the past few days to implement the minmax algorithm in my code. As i said earlier, For now my code is a two player human vs human game. How do I create an AI vs Human game?

Here is my code:

    import java.util.Arrays;
    import java.util.Scanner;
    import java.util.stream.Collectors;
    import java.util.stream.IntStream;

     public class ConnectFour {
        private static final char[] players = new char[] { 'X', 'O' };

        private final int width, height;
        private final char[][] grid;
        private int lastCol = -1, lastTop = -1;

        public ConnectFour(int width, int height) {
            this.width = width;
            this.height = height;
            this.grid = new char[height][];
            for (int h = 0; h < height; h++) {
                Arrays.fill(this.grid[h] = new char[width], '.');
            }
        }

        public String toString() {
            return IntStream.range(0, this.width)
                            .mapToObj(Integer::toString)
                            .collect(Collectors.joining()) + "\n" +
                   Arrays.stream(this.grid)
                         .map(String::new)
                         .collect(Collectors.joining("\n"));
        }

        /**
         * Prompts the user for a column, repeating until a valid
         * choice is made.
         */
        public void chooseAndDrop(char symbol, Scanner input) {
            do {
                System.out.print("\nPlayer " + symbol + " turn: ");
                int col = input.nextInt();

                if (! (0 <= col && col < this.width)) {
                    System.out.println("Column must be between 0 and " +
                                       (this.width - 1));
                    continue;
                }
                for (int h = this.height - 1; h >= 0; h--) {
                    if (this.grid[h][col] == '.') {
                        this.grid[this.lastTop=h][this.lastCol=col] = symbol;
                        return;
                    }
                }

                System.out.println("Column " + col + " is full.");
            } while (true);
        }

        /**
         * Detects whether the last chip played was a winning move.
         */
        public boolean isWinningPlay() {
            if (this.lastCol == -1) {
                throw new IllegalStateException("No move has been made yet");
            }
            char sym = this.grid[this.lastTop][this.lastCol];
            String streak = String.format("%c%c%c%c", sym, sym, sym, sym);
            return contains(this.horizontal(), streak) ||
                   contains(this.vertical(), streak) ||
                   contains(this.slashDiagonal(), streak) ||
                   contains(this.backslashDiagonal(), streak);
        }

        /**
         * The contents of the row containing the last played chip.
         */
        private String horizontal() {
            return new String(this.grid[this.lastTop]);
        }

        /**
         * The contents of the column containing the last played chip.
         */
        private String vertical() {
            StringBuilder sb = new StringBuilder(this.height);
            for (int h = 0; h < this.height; h++) {
                sb.append(this.grid[h][this.lastCol]);
            }
            return sb.toString();
        }

        /**
         * The contents of the "/" diagonal containing the last played chip
         * (coordinates have a constant sum).
         */
        private String slashDiagonal() {
            StringBuilder sb = new StringBuilder(this.height);
            for (int h = 0; h < this.height; h++) {
                int w = this.lastCol + this.lastTop - h;
                if (0 <= w && w < this.width) {
                    sb.append(this.grid[h][w]);
                }
            }
            return sb.toString();
        }

        /**
         * The contents of the "\" diagonal containing the last played chip
         * (coordinates have a constant difference).
         */
        private String backslashDiagonal() {
            StringBuilder sb = new StringBuilder(this.height);
            for (int h = 0; h < this.height; h++) {
                int w = this.lastCol - this.lastTop + h;
                if (0 <= w && w < this.width) {
                    sb.append(this.grid[h][w]);
                }
            }
            return sb.toString();
        }

        private static boolean contains(String haystack, String needle) {
            return haystack.indexOf(needle) >= 0;
        }

        public static void main(String[] args) {






            int XColumnPosition;
            int maxDepth = 4;
            MinimaxAI OPlayer = new MinimaxAI(maxDepth, Board.O); // failed attempt to add minmax


            try (Scanner input = new Scanner(System.in)) {
                int height = 6, width = 8, moves = height * width;
                ConnectFour board = new ConnectFour(width, height);
                System.out.println("Use 0-" + (width - 1) + " to choose a column.");
                System.out.println(board);

                for (int player = 0; moves-- > 0; player = 1 - player) {
                    char symbol = players[player];
                    board.chooseAndDrop(symbol, input);
                    System.out.println(board);
                    if (board.isWinningPlay()) {
                        System.out.println("Player " + symbol + " wins!");
                        return;
                    }
                }
                System.out.println("Game over, no winner.");
            }
        }
    }

And here is the MinMAx class:

 class MinimaxAI {

    //Variable that holds the maximum depth the MiniMax algorithm will reach for this player
    private int maxDepth;
    //Variable that holds which letter this player controls
    private int playerLetter;

    public int getMaxDepth() {
        return maxDepth;
    }

    public void setMaxDepth(int maxDepth) {
        this.maxDepth = maxDepth;
    }

    public int getPlayerLetter() {
        return playerLetter;
    }

    public void setPlayerLetter(int playerLetter) {
        this.playerLetter = playerLetter;
    }

    public MinimaxAI() {
        maxDepth = 4;
        playerLetter = Board.X;
    }

    public MinimaxAI(int maxDepth, int playerLetter) {
        this.maxDepth = maxDepth;
        this.playerLetter = playerLetter;
    }

    //Initiates the MiniMax algorithm
    public Move MiniMax(Board board) {
        //If the X plays then it wants to MAXimize the heuristics value
        if (playerLetter == Board.X) {
            return max(new Board(board), 0);
        }
        //If the O plays then it wants to MINimize the heuristics value
        else {
            return min(new Board(board), 0);
        }
    }

    // The max and min functions are called interchangingly, one after another until a max depth is reached
    public Move max(Board board, int depth) {
        Random r = new Random();

        /* If MAX is called on a state that is terminal or after a maximum depth is reached,
         * then a heuristic is calculated on the state and the move returned.
         */
        if((board.checkGameOver()) || (depth == maxDepth))
        {
            Move lastMove = new Move(board.getLastMove().getRow(), board.getLastMove().getCol(), board.evaluate());
            return lastMove;
        }
        //The children-moves of the state are calculated
        ArrayList<Board> children = new ArrayList<Board>(board.getChildren(Board.X));
        Move maxMove = new Move(Integer.MIN_VALUE);
        for (Board child : children) {
            //And for each child min is called, on a lower depth
            Move move = min(child, depth + 1);
            //The child-move with the greatest value is selected and returned by max
            if(move.getValue() >= maxMove.getValue()) {
                if ((move.getValue() == maxMove.getValue())) {
                    //If the heuristic has the same value then we randomly choose one of the two moves
                    if (r.nextInt(2) == 0) {
                        maxMove.setRow(child.getLastMove().getRow());
                        maxMove.setCol(child.getLastMove().getCol());
                        maxMove.setValue(move.getValue());
                    }
                }
                else {
                    maxMove.setRow(child.getLastMove().getRow());
                    maxMove.setCol(child.getLastMove().getCol());
                    maxMove.setValue(move.getValue());
                }
            }
        }
        return maxMove;
    }

    //Min works similarly to max
    public Move min(Board board, int depth) {
        Random r = new Random();

        if((board.checkGameOver()) || (depth == maxDepth)) {
            Move lastMove = new Move(board.getLastMove().getRow(), board.getLastMove().getCol(), board.evaluate());
            return lastMove;
        }
        ArrayList<Board> children = new ArrayList<Board>(board.getChildren(Board.O));
        Move minMove = new Move(Integer.MAX_VALUE);
        for (Board child : children) {
            Move move = max(child, depth + 1);
            if(move.getValue() <= minMove.getValue()) {
                if ((move.getValue() == minMove.getValue())) {
                    if (r.nextInt(2) == 0) {
                        minMove.setRow(child.getLastMove().getRow());
                        minMove.setCol(child.getLastMove().getCol());
                        minMove.setValue(move.getValue());
                    }
                }
                else {
                        minMove.setRow(child.getLastMove().getRow());
                        minMove.setCol(child.getLastMove().getCol());
                        minMove.setValue(move.getValue());
                }
            }
        }
        return minMove;
    }

 }
\$\endgroup\$

marked as duplicate by Almo, Philipp, DMGregory, Sean Middleditch, Vaillancourt Jan 4 '17 at 21:01

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    \$\begingroup\$ What's the question exactly? \$\endgroup\$ – Vaillancourt Dec 19 '16 at 2:37
  • \$\begingroup\$ Code dump question. we need more specific question. \$\endgroup\$ – Almo Dec 19 '16 at 3:26
  • \$\begingroup\$ @Almo I apolgize for my lack of clarity. I would like to implement an AI vs Human oppose to Human vs Human to my game. \$\endgroup\$ – Thomas C Dec 19 '16 at 4:08
  • \$\begingroup\$ The problem with Min Max is usually the "good stuff" happens deeper than you can search for in a reasonable time, so what do you do if you can't see the light at the end of the tunnel. Look for a paper on Connect 4 written by Victor Allis. That should get you to the promised land. \$\endgroup\$ – Mike White Dec 19 '16 at 7:15
  • \$\begingroup\$ @ThomasC why don't you just use your normal player vs player code but on the AI's turn just do a random number. It will be a simpler start you can probably then see more to expand on. \$\endgroup\$ – lozzajp Dec 19 '16 at 9:25
0
\$\begingroup\$

I understand that the OP is mostly asking for the integration of his AI in his program, rather than the algorithm itself as he said using min-max already

My first intuition for a Connect-four game would be to have a game loop processing the turns.

while (gameOn)
{
    // Get user or AI input
    // Process the input
}

As you have 2 players, you would need to know which turn it is. You can have a variable for that.

int playerNb = 0;
while (gameOn)
{
    if (playerNb == 0)
        // Get user input
    else
        // Get AI input

    // Process the input
    // Change playerNb to 1 or 0
}

Then just implement your algorithm in the GetAIInput() method. A min-max algorithm may be well-suited for this problem, but I would suggest you try different approaches so you can see how the AI reacts each time. That will be a really good exercise which will help you understand the basis of AI development if you are new to this.

\$\endgroup\$
  • \$\begingroup\$ Hey mate thanks for that explanation. It makes much more sense to me. \$\endgroup\$ – Thomas C Dec 19 '16 at 17:09
  • \$\begingroup\$ I have a question, in your representation i see you have while(gameOn) ... What is gameOn? a Variable or a function? \$\endgroup\$ – Thomas C Dec 19 '16 at 18:26
  • \$\begingroup\$ It is a variable. I suggest you read some tutorials about game loops and stuff related, it will be easier then to focus on creating the AI \$\endgroup\$ – realUser404 Dec 20 '16 at 9:17

Not the answer you're looking for? Browse other questions tagged or ask your own question.