I'm trying to build A.I. for Tic-tac-toe using minimax algorithm but it returns weird moves - sometimes it just returns what I think is first available move (top left, top mid, top right...), but other times it just returns what seems like "random" move. But as far as I can tell the moves aren't random and the A.I. plays always the same under the same conditions.
The game works when there are 2 human players. The whole game is big so I created AITest class which should show the important part of behavior. It lets two A.I. players play and prints the board. Please note that this is separate class and isn't written according to best practices and is heavily simplified (doesn't check for win...). But it should be obvious that the A.I. is stupid.
Thank you for any advice.
package tic_tac_toe;
import java.awt.Point;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class AITest {
public enum Tile {
EMPTY, O, X;
}
// [row][column]
private static Tile[][] board;
private static int moveCount = 0;
private Tile mySeed;
private Tile opponentSeed;
public static void main(String[] args) {
board = new Tile[3][3];
for (int y = 0; y < board.length; y++) {
for (int x = 0; x < board.length; x++) {
board[y][x] = Tile.EMPTY;
}
}
AITest ai = new AITest(Tile.X);
AITest opponent = new AITest(Tile.O);
// simulate some moves
for (int i = 0; i < 15; i++) {
checkReset();
int[] move = ai.getNextMove(board);
board[move[0]][move[1]] = Tile.X;
printBoard();
checkReset();
int[] opponentMove = opponent.getNextMove(board);
board[opponentMove[0]][opponentMove[1]] = Tile.O;
printBoard();
}
}
private static void checkReset() {
moveCount++;
if (moveCount == 9) {
for (int y = 0; y < board.length; y++) {
for (int x = 0; x < board.length; x++) {
board[y][x] = Tile.EMPTY;
}
}
moveCount = 0;
}
}
private static void printBoard() {
StringBuilder sb = new StringBuilder();
sb.append("-----------------------\n");
Map<Tile, String> map = new HashMap<>();
map.put(Tile.EMPTY, "e");
map.put(Tile.O, "O");
map.put(Tile.X, "X");
for (Tile[] row : board) {
for (Tile t : row) {
sb.append(map.get(t) + "|");
}
sb.append("\n");
}
System.out.println(sb.toString());
}
public AITest(Tile seed) {
mySeed = seed;
opponentSeed = (mySeed == Tile.X) ? Tile.O : Tile.X;
}
public int[] getNextMove(Tile[][] board) {
int[] result = minimax(board, mySeed);
// row, column
return new int[] { result[1], result[2] };
}
private int[] minimax(Tile[][] board, Tile player) {
// mySeed is maximizing, opponentSeed is minimizing
int bestScore = (player == mySeed) ? Integer.MIN_VALUE
: Integer.MAX_VALUE;
int currentScore;
int bestRow = -1;
int bestCol = -1;
List<Point> possibleMoves = getPossibleMoves(Arrays.copyOf(board,
board.length));
if (possibleMoves.isEmpty()) {
bestScore = getScore(board, player);
} else {
for (Point move : possibleMoves) {
// try the move
board[move.y][move.x] = player;
if (player == mySeed) {
currentScore = minimax(board, opponentSeed)[0];
if (currentScore > bestScore) {
bestScore = currentScore;
bestRow = move.y;
bestCol = move.x;
}
} else {
currentScore = minimax(board, mySeed)[0];
if (currentScore < bestScore) {
bestScore = currentScore;
bestRow = move.y;
bestCol = move.x;
}
}
// undo the move
board[move.y][move.x] = Tile.EMPTY;
}
}
return new int[] { bestScore, bestRow, bestCol };
}
private List<Point> getPossibleMoves(Tile[][] board) {
List<Point> possibleMoves = new ArrayList<>();
for (int y = 0; y < board.length; y++) {
for (int x = 0; x < board.length; x++) {
if (board[y][x] == Tile.EMPTY) {
possibleMoves.add(new Point(x, y));
}
}
}
return possibleMoves;
}
private int getScore(Tile[][] board, Tile player) {
if (isWinner(board, mySeed)) {
return 1;
}
if (isWinner(board, opponentSeed)) {
return -1;
}
return 0;
}
private boolean isWinner(Tile[][] board, Tile player) {
// rows
for (int i = 0; i < board.length; i++) {
if (checkLine(player, board[i])) {
return true;
}
}
// columns
for (int i = 0; i < board.length; i++) {
if (checkLine(player, board[0][i], board[1][i], board[2][i])) {
return true;
}
}
// diagonals
return checkLine(player, board[0][0], board[1][1], board[2][2])
|| checkLine(player, board[0][2], board[1][1], board[2][0]);
}
private boolean checkLine(Tile player, Tile... line) {
for (Tile tile : line) {
if (tile != player) {
return false;
}
}
return true;
}
}
MinMax is very dependent on having a good evaluation function (the function that "scores" a board, to tell you how good it is). Your evaluation function should be as follows:
You current evaluation function is broken, because it only implements #1, and only if the board is full. To see a great improvement, check for either sides' victory before checking for available moves in minimax(), and if any side has won, return with the value of getScore().