Minimax問題 - 連接四。

我正在努力做最小極限運動，我只是試圖用它連接四個AI。當我只深入探索一個節點時，我的工作原理是什麼，但我無法弄清楚它爲什麼一旦變得更深入就會混亂。Minimax問題 - 連接四。

private int minimax(Gameboard gameBoard, int alpha, int depth, char color) { 
    Gameboard gb = new Gameboard(gameBoard); 
    int value = 0; 
    int bestChoice = 0; 
    int bestValue = alpha; 
    // determine which use the value is for 
    if (gb.computerColor == color) { 
     value = 1; 
    } else { 
     value = -1; 
    } 
    if (gb.CheckForWinner(gb.lastSpacePlayed)) { 
     if(gb.winner == gb.computerColor){ 
      bestValue = (1000000000 - depth); 
     }else{ 
      bestValue = (-1000000000 - depth); 
     } 

    } 

    // get the bestValue at our maximum recrusion depth 
    else if (depth == maxDepth) { 
     int moveWeight = (threatLevel(gb, color)); 
     if (moveWeight != 0) { 
      bestValue = value * (moveWeight - depth); 
     } else { 
      bestValue = moveWeight; 
     } 
    } else { 
     // Generate moves for each col and find the best score from each of 
     // the generated moves. 
     for (int c = 0; c < 7; c++) { 
      Gameboard game = new Gameboard(gb); 
      int selectedPlace = game.PlacePiece(c, color); 

      // Recursive call the generated game grid and compare the 
      // current value to move value 
      // If move is higher, make it the new current value. 

      if (selectedPlace != -1) { 
       char tempColor; 
       // change the user for the child node after a piece is played 
       if (color == 'Y') { 
        tempColor = 'R'; 
       } else { 
        tempColor = 'Y'; 
       } 
       // call the function so we can explore to maximum depth 
       if (depth < maxDepth) { 
        int v = minimax(new Gameboard(game), -1000000, depth + 1, tempColor); 
        if (v > bestValue) { 
         bestChoice = c; 
         bestValue = v; 
        } 
        System.out.println(v); 
       } 
      } 
     } 
    } 
    if (depth == 0) { 
     if (threatLevel(gb, gb.lastSpacePlayed.getColor()) == 0) { 
      return gb.spaces.get(0).get(3).getColor() == gb.playerColor ? 2 
        : 3; 
     } else { 
      return bestChoice; 
     } 
    } else { 
     return bestValue; 
    } 

}

我開始它作爲這樣return minimax(gameBoard, -1000000, 0, gameBoard.computerColor);

我的理解只是遍歷所有兒童和返回值的最大值，如果節點是一樣的家長，如果最小值節點不是。任何方向將不勝感激。

來源

2016-08-17 user3298823

它看起來像你試圖實施一些阿爾法修剪？嘗試首先實施原始極大極小。另外，你是否介意發佈GameBoard類和威脅級別函數，以便我可以擺弄這個？ – Cruncher

你不應該檢查minimax裏面的「computerColor」。 Minimax不應該在意。從最低要求角度來看，它始終是球員。它不應該返回一個負面/正面的價值，如果它被稱爲對手或你自己。因爲它的目標是告訴你如果你做出這個動作，你的對手可以做出的最好的舉動（這就是爲什麼它被稱爲極小極限，其目標是儘可能地讓他們的最佳動作獲得最大的勝利機會），而最大的負面價值實際上是一個更小的數量和更糟糕的舉動。 – Cruncher

哦，我剛剛提交了一個答案。不過，我會看看。同時嘗試我的版本，看看它是否有效。 – Cruncher

private int minimax(Gameboard gameBoard, int depth, char color) { 
    Gameboard gb = new Gameboard(gameBoard); 
    int bestChoice = 0; 
    int bestValue = 0; 

    //If we've won, return highest possible value. If we've lost, return lowest. 
    if (gb.CheckForWinner(gb.lastSpacePlayed)) { 
     if(gb.winner == color){ 
      return Integer.MAX_VALUE 
     }else{ 
      return Integer.MIN_VALUE 
     } 

    } 
    //if we hit maximum depth, resort to our heuristic method. 
    else if (depth == maxDepth) { 
     return threatLevel(gb, color); 
    } else { 
     // Generate moves for each col and find the best score from each of 
     // the generated moves. Keep track of the worst one. 
     int worstBestResponse = Integer.MAX_INT 
     boolean tie = true; 
     for (int c = 0; c < 7; c++) { 
      Gameboard game = new Gameboard(gb); 
      int selectedPlace = game.PlacePiece(c, color); 

      // Recursive call the generated game grid and compare the 
      // current value to move value 
      // If move is higher, make it the new current value. 

      if (selectedPlace != -1) { 
       tie = false; 
       char tempColor; 
       // change the user for the child node after a piece is played 
       if (color == 'Y') { 
        tempColor = 'R'; 
       } else { 
        tempColor = 'Y'; 
       } 
       // call the function so we can explore to maximum depth 
       if (depth < maxDepth) { 
        int v = minimax(new Gameboard(game), depth + 1, tempColor); 
        if (v < worstBestResponse) { 
         worstBestResponse = v; 
        } 
       } 
      } 
     } 

     if(tie) { 
      //if game is a tie, we return 0, to show no favour. 
      return 0; 
     } else { 
      //After determining the value of the opponents best response, we return the negative value of it. That is, what's bad for them is good for us and visa versa. 
      return -worstBestResponse; 
     } 
    } 
}

我相信像這樣的東西更多的是你要找的東西。這是假定威脅級別是一種啓發式方法，用於確定誰在給定遊戲中獲勝。

我已經拿出了該方法可能具有的關於它的根源的任何知識。它只應該爲任何「色彩」的人生根。我還清理了你的任意大整數以顯示輸贏。 MAX_VALUE和MIN_VALUE更優雅。

無論如何，嘗試了這一點，並以0深度調用它讓我知道如果您有任何疑問

來源

2016-08-18 00:23:27 Cruncher

如果你的做法是不工作，你可以嘗試模仿上wiki或僞代碼的基本結構here。在Java中，我有：

/** 
    * initialize MiniMax(0, player1) where player1 is computer 
    * @param deg depth 
    * @param player either MAX or MIN 
    * @return int {score,column} 
    */ 
    int[] MiniMax(int deg, char player) { 

     // list of possible columns to place a checker 
     List<int[]> moves = nextMoves(); 
     int v; 
     char prev; 

     if (player==player1) prev = player2; 
     else prev = player1; 

     // IF depth = 0 OR there is a connect 4 OR the board is full (draw) THEN 
     //  return your static evaluation (heuristic) 
     // if the current position has a connect 4, return -inf or inf 
     // depending on if player is MIN or MAX respectively 
     if (checkPos(prev) || (deg == this.deg) || moves.isEmpty()) 
      return new int[] {eval(),bestMove}; 

     //MAX 
     else if (player==player1) { 
      v = -inf; 
      for (int[] move : moves) { // move = {row,column} 

       board[move[0]][move[1]] = player1; // make move 
       int score = MiniMax(deg+1,player2)[0]; 
       board[move[0]][move[1]] = ' '; // undo move 

       if (score>v) { 
        v = score; 
        bestMove = move[1]; 
       } 

      } 
      return new int[] {v,bestMove}; 
     } 

     //MIN 
     else { 
      v = inf; 
      for (int[] move : moves) { // move = {row,column} 

       board[move[0]][move[1]] = player2; // make move 
       int score = MiniMax(deg+1,player1)[0]; 
       board[move[0]][move[1]] = ' '; // undo move 

       if (v>score) { 
        v = score; 
        bestMove = move[1]; 
       } 
      } 
      return new int[] {v,bestMove}; 
     } 
    }

這可能是使用字符數組或東西，而不是class，代表執委會有用。儘管最有效的方法是將電路板表示爲long，因爲您可以使用4位移位來檢查是否存在連接四。這裏有一些馬虎java顯示上述的東西工作：

import java.util.ArrayList; 
import java.util.List; 

public class Connect4 { 
    static final int WIDTH = 7; 
    static final int HEIGHT = 6; 
    private static final int inf = 9999999; 
    private static final char player1 = 'X'; 
    private static final char player2 = 'O'; 
    char[][] board = new char[WIDTH][HEIGHT]; 
    private int deg; 
    int bestMove; 


    static char[][] copy(char[][] aArray) { 
     char[][] copy = new char[aArray.length][aArray[0].length]; 
     for (int idy = 0; idy < aArray.length; ++idy) { 
      for (int idx = 0; idx < aArray[0].length; ++idx) { 
       copy[idy][idx] = aArray[idy][idx]; 
      } 
     } 
     return copy; 
    } 
    void prints() { 
     System.out.println(); 
     for (int i = 0; i < 6; i++) { 
      System.out.println("============================="); 
      for (int j = 0; j < 7; j++) { 
       if (j == (WIDTH - 1)) { 
        if (board[i][j]==' ') { 
         System.out.println("| |"); 
        } 
        else { 
         if(board[i][j]==player1) System.out.println("| " +"\u001B[32m"+board[i][j]+"\u001B[0m" + " |"); 

         else System.out.println("| " +"\u001B[34m"+board[i][j]+"\u001B[0m" + " |"); 
        } 
       } 
       else { 

        if (board[i][j]==' ') { 
         System.out.print("| "); 
        } 
        else { 
         if(board[i][j]==player1) System.out.print("| " +"\u001B[32m"+board[i][j]+"\u001B[0m" + " "); 

         else System.out.print("| " +"\u001B[34m"+board[i][j]+"\u001B[0m" + " "); 
        } 
       } 

      } 
     } 
     System.out.println("============================="); 
    } 


    //STATIC EVALUATION 
    int eval3(char player) { 
     if (checkPos(player)) { 
      return inf; 
     } 

     int count; 
     int open; 
     int evaluation = 0; 

     //evaluation = number of open 3 in rows 
     //go through all possible 4in rows and check 

     //horz 
     for (int i = 0; i < HEIGHT; i++) { 
      for (int j = 0; j < 4; j++) { 
       count = 0; 
       open = 0; 
       if (board[i][j]==player) count++; 
       else if(board[i][j]==' ') open++; 

       if (board[i][j + 1]==player) count++; 
       else if(board[i][j + 1]==' ') open++; 

       if (board[i][j + 2]==player) count++; 
       else if(board[i][j + 2]==' ') open++; 

       if (board[i][j + 3]==player) count++; 
       else if(board[i][j + 3]==' ') open++; 

       if ((count == 3) && (open == 1)) evaluation++; 
      } 
     } 

     //vert 
     for (int j = 0; j < WIDTH; j++) { 
      for (int i = 0; i < 3; i++) { 
       count = 0; 
       open = 0; 
       if (board[i][j]==player) count++; 
       else if (board[i][j]==' ') open++; 

       if (board[i + 1][j]==player) count++; 
       else if (board[i+1][j]==' ') open++; 

       if (board[i + 2][j]==player) count++; 
       else if (board[i + 2][j]==' ') open++; 

       if (board[i + 3][j]==player) count++; 
       else if (board[i + 3][j]==' ') open++; 

       if ((count == 3) && (open == 1)) evaluation++; 
      } 
     } 


     // pos slope diag 
     for (int j = 0; j < 4; j++) { 
      for (int i = 3; i < HEIGHT; i++) { 
       count = 0; 
       open = 0; 
       if (board[i][j]==player) count++; 
       else if (board[i][j]==' ') open++; 

       if (board[i - 1][j + 1]==player) count++; 
       else if (board[i - 1][j + 1]==' ') open++; 

       if (board[i - 2][j + 2]==player) count++; 
       else if (board[i - 2][j + 2]==' ') open++; 

       if (board[i - 3][j + 3]==player) count++; 
       else if (board[i - 3][j + 3]==' ') open++; 

       if ((count == 3) && (open == 1)) evaluation++; 
      } 
     } 

     // neg slope diag 
     for (int j = 0; j < 4; j++) { 
      for (int i = 0; i < (3); i++) { 
       count = 0; 
       open = 0; 
       if (board[i][j]==player) count++; 
       else if (board[i][j]==' ') open++; 

       if (board[i + 1][j + 1]==player) count++; 
       else if (board[i + 1][j + 1]==' ') open++; 

       if (board[i + 2][j + 2]==player) count++; 
       else if (board[i + 2][j + 2]==' ') open++; 

       if (board[i + 3][j + 3]==player) count++; 
       else if (board[i + 3][j + 3]==' ') open++; 

       if ((count == 3) && (open == 1)) evaluation++; 

      } 
     } 
     return evaluation; 
    } 
    int eval() {return eval3(player1) - eval3(player2);} 
    boolean checkPos(char cur) { 
     //horz 
     for (int i = 0; i < HEIGHT; i++) { 
      for (int j = 0; j < 4; j++) { 
       if ( board[i][j]==cur && 
         board[i][j + 1]==cur && 
         board[i][j + 2]==cur && 
         board[i][j + 3]==cur) { 
        return true; 
       } 
      } 
     } 


     //vert 
     for (int j = 0; j < WIDTH; j++) { 
      for (int i = 0; i < 3; i++) { 
       if ( board[i][j]==cur && 
         board[i + 1][j]==cur && 
         board[i + 2][j]==cur && 
         board[i + 3][j]==cur) { 
        return true; 
       } 
      } 
     } 


     // pos slope diag 
     for (int j = 0; j < 4; j++) { 
      for (int i = 3; i < HEIGHT; i++) { 
       if ( board[i][j]==cur && 
         board[i - 1][j + 1]==cur && 
         board[i - 2][j + 2]==cur && 
         board[i - 3][j + 3]==cur) { 
        return true; 
       } 

      } 
     } 


     // neg slope diag 
     for (int j = 0; j < 4; j++) { 
      for (int i = 0; i < 3; i++) { 
       if ( board[i][j]==cur && 
         board[i + 1][j + 1]==cur && 
         board[i + 2][j + 2]==cur && 
         board[i + 3][j + 3]==cur) { 
        return true; 
       } 
      } 
     } 

     return false; 
    } 
    List<int[]> nextMoves() { 
     List<int[]> result = new ArrayList<>(); 
     for (int j = 0; j < WIDTH; j++) { 
      //if column j isnt full then add 
      if (board[0][j]==' ') result.add(new int[] {findY(j),j}); 
     } 
     return result; 
    } 
    int findY(int col) { 
     int i = board.length - 1; 
     while (i > -1) { 
      if (board[i][col]==' ') break; 
      i--; 
     } 
     return i; 
    } 


    /** 
    * @param deg depth 
    * @param player either MAX or MIN 
    * @return int {score,column} 
    */ 
    int[] MiniMax(int deg, char player) { 

     // list of possible columns to place a checker 
     List<int[]> moves = nextMoves(); 
     int v; 
     char prev; 

     if (player==player1) prev = player2; 
     else prev = player1; 

     // IF depth = 0 OR there is a connect 4 OR the board is full (draw) THEN 
     //  return your static evaluation (heuristic) 
     // if the current position has a connect 4, return -inf or inf 
     // depending on if player is MIN or MAX respectively 
     if (checkPos(prev) || (deg == this.deg) || moves.isEmpty()) 
      return new int[] {eval(),bestMove}; 



     //MAX 
     else if (player==player1) { 
      v = -inf; 
      for (int[] move : moves) { // move = {row,column} 

       board[move[0]][move[1]] = player1; // make move 
       int score = MiniMax(deg+1,player2)[0]; 
       board[move[0]][move[1]] = ' '; // undo move 

       if (score>v) { 
        v = score; 
        bestMove = move[1]; 
       } 

      } 
      return new int[] {v,bestMove}; 
     } 

     //MIN 
     else { 
      v = inf; 
      for (int[] move : moves) { // move = {row,column} 

       board[move[0]][move[1]] = player2; // make move 
       int score = MiniMax(deg+1,player1)[0]; 
       board[move[0]][move[1]] = ' '; // undo move 

       if (v>score) { 
        v = score; 
        bestMove = move[1]; 
       } 

      } 
      return new int[] {v,bestMove}; 
     } 

    } 

    public static void main(String[] args) { 
     Connect4 c = new Connect4(); 
     c.deg = 5; 

     char[][] b = { 
       {' ',' ',' ',' ',' ',' ',' '}, 
       {' ',' ',' ',' ',' ',' ',' '}, 
       {' ',' ',' ',' ',' ',' ',' '}, 
       {' ',' ',' ',' ',' ',' ',' '}, 
       {' ','X','X','X',' ',' ',' '}, 
       {' ','O','X','X','X',' ',' '} 
     }; 

     c.board = copy(b); 
     c.prints(); 
     System.out.println("best value = " + c.MiniMax(0, player1)[1]); 

    } 
}

來源

2016-08-18 04:57:56

Minimax問題 - 連接四。

回答

相關問題