mini-maxアルゴリズムのJava動的ツリー

Question

私のAIモジュールのmini-maxアルゴリズムに使用されるツリーの実装に問題があります。

私が書く必要があるツリーには、root（0） - AI move（1） - player move（2）とAI move（3）という4つのレベルがあります。すべてのレベルには子どものnが含まれ、（ボードの状態、フィールドレート、移動する座標）などのフィールドがあります。ツリーの3番目のレベルの私の計算では、子供の可能な数は約25.000になります。これをどのように実装すればよいですか？

Iオブジェクトの3つの異なるArrayList S、特定のレベルのために、各リスト実装した瞬間：

• firstDepthList - ）を可能ボードの状態を持つオブジェクト、フィールドレートが含まれており、移動する座標。
• secondDepthListには、ボードの状態が可能なオブジェクト（すべての要素がfirstDepthList）、フィールドレートと座標が移動するオブジェクトが含まれています。
• thirdDepthList 要素ごとに上記のようなオブジェクトが含まれています。secondDepthListです。もちろん、 ボードのリストをリンクして連続性を保ちます。

もっと良い解決策をお勧めしますか？

Answer 1

ミニマックスアルゴリズムでは、最大値（または最小値、レベル番号に依存）が1つだけ必要です。すべてのツリーを格納する必要はありません。

再帰関数として実装できます。そして、多くの状態を作成せず、使用しているボードの状態は1つだけです（例えば、AからBへのチェスの動きは元に戻ります）

double getRating(BoardState state, int currentPlayer, int depth){ 
    //current player has to be 1 or -1 
    if (depth <= 0){ 
     return state.positionRating(); 
    } 
    double bestRating = -Double.MAX_VALUE; 
    for(Move m: state.possibleMoves(currentPlayer)){ 
     state.apply(m); // modify state 
     double rating = currentPlayer * getRating(state, -currentPlayer, depth-1); 
     // player 1 wants to have biggest number, player -1: lowest 
     bestRating = Math.max(bestRating, rating); 
     state.revert(m) // restore state 
    } 
return bestState*currentPlayer; 
}