# Improve (adding randomness) minmax algorithm for Connect Four

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:

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

• 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... Sep 23 '15 at 15:31
• 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. Sep 24 '15 at 12:56
• 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 Sep 24 '15 at 13:01
• You can download the project now. So, have i to modify the structure of my minmax algorithm? Sep 24 '15 at 13:54

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.

• What i want: if there are moves with the same score, choose one of them randomly. Actually, the computer does always the same choice. Sep 23 '15 at 16:36
• VERY unlikely you'll get the same score, you also need to make sure it doesn't randomly choose a stupid thing @Loris Sep 23 '15 at 16:53
• 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. Sep 23 '15 at 18:56
• @Loris that doesn't really help. You should have a score for each branch, just keep the top 4. Sep 23 '15 at 19:36
• 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. Sep 24 '15 at 8:17