Search code examples
javaperformanceartificial-intelligenceminmax

Connect 4 code with min max find unique problem


I'm looking for a way to solve Connect 4. I'm trying now with min max with a depth of 6. It's not working and it keeps resulting in the same column (the first one).

I'm pretty desperate so I'll be very happy if you could find the mistakes.

public int findBestMove() {

        ArrayList<ArrayList<Integer>> myMoves = new ArrayList<ArrayList<Integer>>();

        for (int i = 0; i < mWidth; i++) {
            if (isColumnAvailable(i)) {
            ArrayList<Integer> t = new ArrayList<>();
            t.add(i);
            t.add(MinMax(6, mBoard, false));
            myMoves.add(t);
            
        }
        }

        int maxMoveScore = -10000;
        int bestMove = 0;
        
        for (int i = 0; i < myMoves.size(); i++) {
            int score = myMoves.get(i).get(1);
            if (score > maxMoveScore) {
                maxMoveScore = tryit;
                bestMove = myMoves.get(i).get(0);
                
            }
        
        }
        
        return bestMove;
    }

    private int MinMax(int depth,int[][] board, boolean maximizingPlayer) {
        if (depth <= 0)
            return 0;

        int winner =checkForWin() ;
        if (winner == 2)
            return depth;
        if (winner == 1)
            return -depth;
        if (isBoardFull()) {
            return 0;
        }

        int bestValue;
        
        if (maximizingPlayer)
            bestValue = -1;
        else
            bestValue = 1;
        for (int i = 0; i < mWidth; i++) {
            if (!isColumnAvailable(i))
                continue;
            int v = MinMax(depth - 1, board, !maximizingPlayer);
            bestValue = maximizingPlayer ? Math.max(bestValue, v) : Math.min(bestValue, v);
            
        }

        return bestValue;

    }

2- is the number of the AI
1- is the human player
0- is empty


Solution

  • Connect 4 is a solved game (spoiler, player 1 wins when played perfectly). You can read all about how the solution was accomplished in A Knowledge-based Approach of Connect-Four. It's quite a fascinating read because they did it at a time when computation resources were significantly harder to come by.

    The general idea is to build a huge database of known value positions, then min-max with alpha-beta pruning until you reach one of the positions in the database. Building this database was difficult due to computational and storage resources at the time this happened but you could probably achieve something similar today with less effort.

    While this doesn't directly answer your question, hopefully the reference will be a good place to start your research because it includes analysis of a lot of common situations in connect 4 which you can use to help you improve your evaluation function.