2017-01-16 50 views
1

我讀了一篇關於極大極小的教程,並嘗試製作一個tac tac toe AI。 但由於某些原因,代碼無法正常工作,這是我找不到的。 ai可以放置碎片,但它不是一個聰明的ai。我預料它是無與倫比的。深度越高,ai的數量就越多。 「遊戲」是我的另一個課程,實際的遊戲是。我的Tic Tac Toe AI有什麼問題?

private Game game; 
private Piece[][] board; 
private Piece ai = Piece.CIRCLE; 
private Piece player = Piece.CROSS; 

public AI(Game game) { 
    this.game = game; 
    this.board = game.getBoard(); 

} 

public int[] move() { 
    int[] result = minimax(1, ai); 

    return new int[] {result[1], result[2]}; 
} 

private int[] minimax(int depth, Piece piece) { 
    List<int[]> possibleMoves = generateMoves(); 

    int bestScore = (piece == ai) ? Integer.MIN_VALUE : Integer.MAX_VALUE; 
    int currentScore; 
    int bestRow = -1; 
    int bestCol = -1; 

    if (possibleMoves.isEmpty() || depth == 0) { 
     // Game over or depth reached 
     bestScore = evaluate(); 
    } 
    else { 
     for (int[] move : possibleMoves) { 
      // Try this move for the player 
      board[move[0]][move[1]] = player; 
      if (piece == ai) { // ai is maximizing player 
       currentScore = minimax(depth - 1, player)[0]; 

       if (currentScore > bestScore) { 
        bestScore = currentScore; 
        bestRow = move[0]; 
        bestCol = move[1]; 
       } 
      } 
      else { // player is minimizing player 
       currentScore = minimax(depth - 1, ai)[0]; 

       if (currentScore < bestScore) { 
        bestScore = currentScore; 
        bestRow = move[0]; 
        bestCol = move[1]; 
       } 
      } 

      // Undo move 
      board[move[0]][move[1]] = null; 
     } 
    } 

    return new int[] {bestScore, bestRow, bestCol}; 
} 

private List<int[]> generateMoves() { 
    List<int[]> possibleMoves = new ArrayList<int[]>(); 

    // If game over 
    if (game.getWinner() != null) { 
     return possibleMoves; // return empty list 
    } 

    // Add possible moves to list 
    for (int x = 0; x < 3; x++) { 
     for (int y = 0; y < 3; y++) { 
      if (game.getBoard()[x][y] == null) { 
       possibleMoves.add(new int[] {x, y}); 
      } 
     } 
    } 

    return possibleMoves; 
} 

private int evaluate() {   
    int score = 0; 
    // Evaluate 
    score += evaluateLine(0, 0, 0, 1, 0, 2); // row 0 
    score += evaluateLine(1, 0, 1, 1, 1, 2); // row 1 
    score += evaluateLine(2, 0, 2, 1, 2, 2); // row 2 
    score += evaluateLine(0, 0, 1, 0, 2, 0); // col 0 
    score += evaluateLine(0, 1, 1, 1, 2, 1); // col 0 
    score += evaluateLine(0, 2, 1, 2, 2, 2); // col 0 
    score += evaluateLine(0, 0, 1, 1, 2, 2); // diag 1 
    score += evaluateLine(0, 2, 1, 1, 2, 0); // diag 2 

    return score; 
} 

// Return +100, +10, +1 for 3-, 2-, 1-in-a-line for ai 
// Return -100, -10, -1 for 3-, 2-, 1-in a line for player 
// Else return 0 
private int evaluateLine(int row1, int col1, int row2, int col2, int row3, int col3) { 
    int score = 0; 

    // First cell 
    if (board[row1][col1] == ai) { 
     score = 1; 
    } 
    else if (board[row1][col1] == player) { 
     score = -1; 
    } 

    // Second cell 
    if (board[row2][col2] == ai) { 
     if (score == 1) { // board1 is ai 
      score = 10; 
     } 
     else if (score == -1) { // board1 is player 
      return 0; 
     } 
     else { // board1 is empty 
      score = 1; 
     } 
    } 
    else if (board[row2][col2] == player) { 
     if (score == -1) { // board1 is player 
      score = -10; 
     } 
     else if (score == 1) { // board1 is ai 
      return 0; 
     } 
     else { // board1 is empty 
      score = -1; 
     } 
    } 

    // Third cell 
    if (board[row3][col3] == ai) { 
     if (score > 0) { // board1 and/or board2 is ai 
      score *= 10; 
     } 
     else if (score < 0) { // board1 and/or board2 is player 
      return 0; 
     } 
     else { // board1 and/or board2 is empty 
      score = 1; 
     } 
    } 
    else if (board[row3][col3] == player) { 
     if (score < 0) { // board1 and/or board2 is player 
      score *= 10; 
     } 
     else if (score > 1) { // board1 and/or board2 is ai 
      return 0; 
     } 
     else { // board1 and/or board2 is empty 
      score = -1; 
     } 
    } 

    return score; 
} 

回答

1

minimax根據行/列對而不是分數返回移動。所以

currentScore = minimax(depth - 1, player)[0]; 

是沒有意義的。它可能導致的任何舉動排3看起來比任何轉至行1或2行。

minmax需要交
回,除了最好的移動的得分要好。

+1

它返回int [] {bestScore,bestRow,bestCol}所以得分是[0] – DingDongDang132

3

一對夫婦的事情,我注意到:

  • 在遍歷可能的行動去第一行說board[move[0]][move[1]] = player;。那應該是piece而不是player,現在你的AI認爲只有人類玩家的棋子纔會成爲棋盤上的棋子。
  • Minimax應該很容易在不到一秒的時間內搜索完整的遊戲樹。因此,我建議允許按照自己喜歡的方式進行深度搜索,而不是將搜索深度限制爲1.這樣也可以消除創建啓發式評估函數的需要;你只會給出一個很大的得分,0分爲平局,而一個非常負分的失分。我推薦這個的主要原因是我懷疑評估函數可能有問題,儘管我不確定,因爲我沒有詳細檢查它。如果你確實堅持儘早終止搜索並使用啓發式評估函數,則需要確保函數是「對稱的」。與此同時,我的意思是從一名球員的角度評價董事會應該總是導致正好-1倍同一局的得分從對手的角度進行評估。