1

我一直在尝试通过使用井字游戏来学习 MiniMax,因为这似乎是最常用的示例之一。我从不修剪开始尝试掌握它。我有 2 个 AI 互相对抗,但 X 总是获胜。我认为问题在于他们没有进行防守,我不太确定如何实施。下面是代码,我还有一些其他的类文件,但我认为除非有要求,否则不需要它们。非常感谢。

import java.util.*;

public class TicTacToe {

    GameState gameState;      // Current game state
    int totalNodesExpanded;   // Total number of nodes expanded in
                  // search so far
    int levelNodesExpanded;   // Number of nodes expanded to explore this
                  // level of the tree (i.e. all
                  // non-pruned successors of the current
                  // state) 

    public TicTacToe() {
    gameState = new GameState();
    ArrayList<Coordinate> moves = new ArrayList<Coordinate>();
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
        moves.add(new Coordinate(i,j));
        }
    }
    gameState.player = "X";
    gameState.moves = moves;
    totalNodesExpanded = 0;
    levelNodesExpanded = 0;
    }

    /*
     * Return a list of the states reachable in one move from the
     * current state.
     */
    public ArrayList getSuccessorStates(GameState state) {
    ArrayList<GameState> result = new ArrayList<GameState>();
    for (int i = 0; i < state.moves.size(); i++) {
        Coordinate c = (Coordinate) state.moves.get(i);
        GameState s = makeMove(state, c);
        s.moveMade = c;
        result.add(s);
    }
    return result;
    }

    /*
     * Perform a move to "c" from the given "state" (checking that the
     * move is valid in the current state) 
     */
    public GameState makeMove(GameState state, Coordinate c) {
    GameState result = null;
    ArrayList newMoves = (ArrayList) state.moves.clone();
    if (newMoves.contains(c)) {
        newMoves.remove(c);
        result = new GameState();
        result.moves = newMoves;
        TicTacToeBoard newBoard = (TicTacToeBoard) state.board.clone();
        if (state.player.equals("X")) {
        newBoard.markX(c.x, c.y);
        result.player = "O";
        } else {
        newBoard.markO(c.x, c.y);
        result.player = "X";
        }
        result.board = newBoard;
    } else {
        System.out.println("ERROR: attempt to make invalid move");
    }
    return result;
    }

    /*
     * Make the next move, determined using minimax.
     * Print out information about the search progression.
     */
    public void makeMiniMaxMove() {
    totalNodesExpanded += levelNodesExpanded;
    levelNodesExpanded = 0;
    GameState state = gameState;
    ArrayList<GameState> states = getSuccessorStates(state);
    int best = 0;
    int temp = 0;
    for (GameState s : states) {
        if (state.player.equals("X")) {
            best = -1;
            temp = min(s);
            if (temp > best) {
                best = temp;
                gameState.next = s;
            }
            if (best == 1)
                break;
        }
        else {
            best = 1;
            temp = max(s);
            if (temp < best) {
                best = temp;
                gameState.next = s;
            }
            if (best == -1) 
                break;
            }
    }

    GameState nextState = gameState.next;
    System.out.println("Nodes considered: " + levelNodesExpanded);
    System.out.println("Move chosen: " + nextState.moveMade);
    gameState = makeMove(gameState, nextState.moveMade);
    }

    private int max(GameState state) {
        if (state.board.lineExists() && state.player.equals("X"))
            return 1;
        else if (state.board.boardFull() == true)
            return 0;
        else if (state.board.lineExists() && !state.player.equals("X"))
            return -1;

        levelNodesExpanded++;

        ArrayList<GameState> states = getSuccessorStates(state);
        int best = -1;
        for (GameState s : states) {
            int temp = min(s);
            if (temp > best) {
                best = temp;
                gameState.next = s;
            }
            if (best == 1)
                break;
        }
        return best;
    }

    private int min(GameState state) {
        if (state.board.lineExists() && state.player.equals("O"))
            return -1;
        else if (state.board.boardFull() == true)
            return 0;
        else if (state.board.lineExists() && !state.player.equals("O"))
            return 1;

        levelNodesExpanded++;

        ArrayList<GameState> states = getSuccessorStates(state);
        int best = 1;
        for (GameState s : states) {
            int temp = max(s);
            if (temp < best) {
                best = temp;
                gameState.next = s;
            }
            if (best == -1)
                break;
        }
        return best;
    }

    public static void main(String[] args) {

    TicTacToe board1 = new TicTacToe();
    System.out.println("board:\n" + board1.gameState.board + "\n");
    while (!(board1.gameState.board.lineExists() ||
         board1.gameState.board.boardFull())) {
        System.out.println("Current player: " + board1.gameState.player);
        System.out.println("Possible moves: " + board1.gameState.moves);
        board1.makeMiniMaxMove();
        System.out.println("board:\n" + board1.gameState.board + "\n");
    }
    System.out.println("Total nodes expanded: " 
               + board1.totalNodesExpanded);

    System.out.println("\n\n\n");
    }
}
4

0 回答 0