井字游戏 A.I。在 Java 中使用 minimax 不起作用

Question

我正在尝试构建 A.I。对于使用 minimax 算法的 Tic-tac-toe，但它 returns 奇怪的移动 - 有时它只是 returns 我认为第一个可用的移动（左上，中上，右上......），但其他时间只是 returns 看起来 "random" 移动。但据我所知，移动不是随机的，而且 A.I。在相同条件下播放始终相同。

当有 2 名人类玩家时，游戏可以运行。整个游戏很大，所以我创建了 AITest class 来展示行为的重要部分。它让两个A.I。玩家玩游戏并打印棋盘。请注意，这是单独的 class 并且不是根据最佳实践编写的，并且经过了极大的简化（不检查 win...）。但是应该很明显的是A.I。很傻。

感谢您的任何建议。

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;
    }
}

Answer 1

MinMax非常依赖于有一个好的评价函数（"scores"一块板子的函数，告诉你它有多好）。您的评估函数应如下所示：

如果比赛获胜，获胜者将获得很多积分。赢了比赛什么都不重要
否则，对可用于更多获胜着法的占据牌给予部分计分。比如中牌可以用在4个胜位，角用3个，边用2个，所以如果你有选择，对方不能胜出的话，用中牌更好。

您当前的评估函数已损坏，因为它仅实现#1，并且仅当棋盘已满。要看到很大的改进，请在 minimax() 中检查可用移动之前检查任何一方的胜利 ，并且 如果任何一方获胜 , return 的值为 getScore().

井字游戏 A.I。在 Java 中使用 minimax 不起作用

Tic-tac-toe A.I. in Java using minimax doesn't work

java

tic-tac-toe

minimax