0
\$\begingroup\$

I have implemented the minmax algorithm for the Connect Four game. It works well (almost...), but if the player does the same moves, the computer will do the same moves as well, for each match. There is no randomness in the computer choices. This is the code for the minmax:

private int[] minmax(int depth, Seed player) {
    // Generate possible next moves in a List of int[2] of {row, col}.
    List<int[]> nextMoves = generateMoves();

    // mySeed is maximizing; while oppSeed is minimizing
    int bestScore = (player == mySeed) ? Integer.MIN_VALUE : Integer.MAX_VALUE;
    int currentScore;
    int bestRow = -1;
    int bestCol = -1;

    if (nextMoves.isEmpty() || depth == 0) {
        // Gameover or depth reached, evaluate score
        bestScore = evaluate();
    } else {
        for (int[] move : nextMoves) {
            // Try this move for the current "player"
            cells[move[0]][move[1]].setContent(player);
            if (player == mySeed) { // mySeed (computer) is maximizing player
                currentScore = minmax(depth - 1, oppSeed)[0];
                if (currentScore > bestScore) {
                    bestScore = currentScore;
                    bestRow = move[0];
                    bestCol = move[1];
                }
            } else { // oppSeed is minimizing player
                currentScore = minmax(depth - 1, mySeed)[0];
                if (currentScore < bestScore) {
                    bestScore = currentScore;
                    bestRow = move[0];
                    bestCol = move[1];
                }
            }
            // Undo move
            cells[move[0]][move[1]].setContent(Seed.EMPTY);
        }
    }
    return new int[] { bestScore, bestRow, bestCol };
}

/**
 * Find all valid next moves. Return List of moves in int[2] of {row, col}
 * or empty list if gameover
 */
private List<int[]> generateMoves() {
    List<int[]> nextMoves = new ArrayList<int[]>(); // allocate List

    boolean[] columns = {false,false,false,false,false,false,false};

    // If gameover, i.e., no next move
    if (hasWon(mySeed) || hasWon(oppSeed)) {
        return nextMoves; // return empty list
    }

    // Search for possible moves and add to the List
    for(int row = GameMain.ROWS - 1; row >= 0; row--) {
        for(int col = 0; col < GameMain.COLS; col++) {
            if(columns[col] == false && cells[row][col].getContent() == Seed.EMPTY) {
                columns[col] = true;
                nextMoves.add(new int[] { row, col });
            }
        }
    }

    return nextMoves;
}

/**
 * The heuristic evaluation function for the current board
 * 
 * Counts open 3 in a row for each player
 */
private int evaluate() {
    int score = 0;

    // very good move for computer
    if(hasWon(mySeed)) {
        return Integer.MAX_VALUE;
    }

    // very bad move, player wins!
    if(hasWon(oppSeed)) {
        return -Integer.MIN_VALUE;
    }

    // counts open 3 in a row for the computer and the player
    int myThree = openThree(mySeed);
    int oppThree = openThree(oppSeed);

    score = myThree - oppThree; // if negative, player advantage, otherwise computer advantage

    return score; 
}

I have omitted the openThree method for brevity.

Bug: the computer skips his turn when is destined to lose.

Ps: the main code for minmax is taken from a tutorial.

This is a situation in which the computer skips his turn:

enter image description here

Red is the player, blue is the computer.

The computer does not freeze, he can continue to play, but not always. For example in this situation if i place my red circle over 15, the computer will skip his turn again, while if i place my red circle over 9, the computer will win placing his blue circle over this last one placed by me.

Project zip

\$\endgroup\$
  • \$\begingroup\$ I know how I would play connect four; if there is a spot that the player consistently leaves open, then I will always take it and it seems natural for a computer to take it... \$\endgroup\$ – JDSweetBeat Sep 23 '15 at 15:31
  • \$\begingroup\$ Okay can I have a copy of your code (put it in a zip file and upload) because I'm genuinely curious now. It shouldn't have the option to skip even. \$\endgroup\$ – Alec Teal Sep 24 '15 at 12:56
  • \$\begingroup\$ Okay I'll do a second answer - I think it's because if the algorithm has a depth of zero you return no moves. You need to throw an exception (or do something special) if you call minmax and there are NO moves, but you also need A MOVE - you may find the best but you do not show existence \$\endgroup\$ – Alec Teal Sep 24 '15 at 13:01
  • \$\begingroup\$ You can download the project now. So, have i to modify the structure of my minmax algorithm? \$\endgroup\$ – Loris Sep 24 '15 at 13:54
2
\$\begingroup\$

I'm not going to read your code but I will talk about how (old) electronic chess sets do it.

When they're searching for a move to play often they will choose the best move they've found, however for variation (which usually you don't want, but I play chess really quite well, a lesser player may get bored or something) you can put them in modes where they'll do something like:

  • Choose a move with the same "score" as the one you just made (effectively balancing the game)
  • Choose a random move from the best at most 4 moves found, provided those moves all have similar scores. (Say there are only 2 good moves, the rest = insta-loose, it'd be STUPID if by random chance it choose a stupid move)

Hope this helps.

\$\endgroup\$
  • \$\begingroup\$ What i want: if there are moves with the same score, choose one of them randomly. Actually, the computer does always the same choice. \$\endgroup\$ – Loris Sep 23 '15 at 16:36
  • \$\begingroup\$ VERY unlikely you'll get the same score, you also need to make sure it doesn't randomly choose a stupid thing @Loris \$\endgroup\$ – Alec Teal Sep 23 '15 at 16:53
  • \$\begingroup\$ My heuristic counts the number of open threes in a row for each player. At the beginning more than one "branch" of minmax has a score of 0. \$\endgroup\$ – Loris Sep 23 '15 at 18:56
  • \$\begingroup\$ @Loris that doesn't really help. You should have a score for each branch, just keep the top 4. \$\endgroup\$ – Alec Teal Sep 23 '15 at 19:36
  • \$\begingroup\$ Ok thank you for your help. Just another thing. In your opinion, why sometimes my AI does not choose any cell? It skips the turn and i don't know why. \$\endgroup\$ – Loris Sep 24 '15 at 8:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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