面對棋盤遊戲實現極大極小化的性能問題

我想實現極小極小遊戲算法。也許我的前提是錯誤的，這不是應該嘗試的。是嗎？面對棋盤遊戲實現極大極小化的性能問題

的程序工作，但有一個很大的性能問題：

深度= 0，1或2的結果是立竿見影的。
深度= 3結果需要15秒。
深度= 4 - 尚未得到結果。

這是我實現：

private Move findBestMove(Chessboard chessboard, int depth, 
     boolean maximizingPlayer) { 
    if (depth == 0) { 
     return new Move(chessboard.calculateHeuristicValue()); 
    } else { 
     Move bestMove; 
     if (maximizingPlayer) { 
      bestMove = new Move(Integer.MIN_VALUE); 
      for (Move possibleMove : findAllPossibleMoves(chessboard, 
        !(maximizingPlayer^whiteTurn))) { 
       Move move = findBestMove(
         possibleMove.getResultChessboard(), depth - 1, 
         !maximizingPlayer); 
       if (move.getValue() > bestMove.getValue()) { 
        possibleMove.setValue(move.getValue()); 
        bestMove = possibleMove; 
       } 
      } 
     } else { 
      bestMove = new Move(Integer.MAX_VALUE); 
      for (Move possibleMove : findAllPossibleMoves(chessboard, 
        !(maximizingPlayer^whiteTurn))) { 
       Move move = findBestMove(
         possibleMove.getResultChessboard(), depth - 1, 
         !maximizingPlayer); 
       if (move.getValue() < bestMove.getValue()) { 
        possibleMove.setValue(move.getValue()); 
        bestMove = possibleMove; 
       } 
      } 
     } 
     return bestMove; 
    } 
}

也許有在算法的實現或對象的設計或在其使用中的故障。我不能把它放在手指上。所以，我想確保在嘗試優化代碼或調整程序的內存配置之前，我沒有看到任何重大問題。

注意：沒有內存分析的經驗。

來源

2015-07-03 Limbo Exile

minimax是指數型的。爲了減少探索的分支數量，你可以使用alphabeta修剪 – njzk2

在國際象棋中，有20種可能性進行第一次移動（16個由典當和4個騎士）。

爲了簡單起見，我們假設對於下一步移動也是如此。

對於深度1，MinMax只考慮20次移動。
對於深度2，MinMax考慮20次移動和20次移動答案，400次可能移動，沒有問題。
對於深度3，MinMax考慮20^3 = 8.000個可能的移動。您的機器已經有15秒鐘了。
對於深度4，MinMax考慮20^4 = 160.000可能的移動。這將需要比前一個長約20倍...

只是搜索空間變得太大 - 它隨着輸入（深度）大小成指數增長。時間複雜度是O（20 ^深度）。

但是，我們不必通過搜索所有的空間來找到真正的好動作。

Alpha-beta pruning是MinMax的流行優化。

如果這還不夠，我會考慮切換到其他算法 - 例如Monte Carlo Tree Search（與UCT）。

移動數據庫也可以幫助 - 而不是計算你已經準備好（預先計算）的第一招。

着名Deep Blue誰在1997年打敗卡斯帕羅夫使用它們，你可以檢查它還使用了什麼here。

來源

2015-07-03 19:53:10

面對棋盤遊戲實現極大極小化的性能問題

回答

相關問題