Java用のMinimaxアルゴリズムをConnect 4用に実装

Question

私はminimax（そしてalpha beta pruning）を使ってConnect 4のゲームを構築しようとしています。しかし、私が持っている大きな概念的な問題は、実際にミニマックスアルゴリズムを利用する方法です。私がやる方法は、intを返すminimaxアルゴリズムを実行する1つの関数を持つAIクラスがあることです。

public int minimax(Board board, int depth, int alpha, int beta, String player) { 

    if(depth == 0 || board.getScore() >= 512) { 
     return board.getScore(); 
    } 

    else if(player.equals("computer")) { 
     int temp = -1000000; 
     for(Integer[] moves : board.availableMoves) { 
      board.putPiece(player, moves[0]); 
      temp = Math.max(temp, minimax(board, depth-1, alpha, beta, "human")); 
      board.removePiece(moves[0], moves[1]); 
      alpha = Math.max(alpha, temp); 
      if (alpha >= beta) { 
       break; 
      } 

     } 
     return temp; 
    } 

    else { 
     int temp = 1000000; 
     for(Integer[] moves : board.availableMoves) { 
      board.putPiece(player, moves[0]); 
      temp = Math.min(temp, minimax(board, depth+1, alpha, beta, "computer")); 
      board.removePiece(moves[0], moves[1]); 
      beta = Math.min(beta, temp); 
      if(alpha >= beta) { 
       break; 
      } 
     } 
     return temp; 
    } 
} 

これは、computerMove（）というGameクラスの関数によって呼び出されます。

public int computerMove() { 
    Board tempBoard = board; 
    int bestMove = 0; 
    AI ai = new AI(); 
    ai.minimax(board, difficulty, -1000000, 1000000, "computer"); 

    return bestMove; 
} 

しかし、返されるintはどうすればよいですか？どのように実際に作品を移動するためにそれを利用するのですか？返されるintは、単に私が得ることができる最高のボードですよね？それは、特に私が行うべき場所やボードについて何も教えてくれません。

何かすべてのヘルプは大歓迎です。

おかげで、

Answer 1

冊すべてがちょうどスコアを返すように言うが、それは実際にゲームをプレイするための非現実的です。もちろんどこでも最良の動きを維持するオーバーヘッドはプログラムの速度を遅くする可能性があります。したがって、一般に、最初の拡張レベルを実行するドライバ関数を使用し、さらに最適な動きを追跡します。これは効果的に実装をargmax functionにラッピングしています。これは、スコアの代わりにトップレベルで最良の動きを返すという素晴らしい方法です。この例はa little project I worked on last yearにあります。コードはC＃にありますが、それはあなたがそのアイデアを得るのに十分に近いです。

また、コードを変更して、スコアと最適な移動を持つタプル（複数のフィールドを持つクラス）を返すことができます。これはargmaxラッパーを書くよりも簡単です（そしてIMOを少しきれいにする）が、余分なエンジニアリングがなければminimax関数がかなり遅くなります。パフォーマンスが最優先事項でない場合、これはおそらく方法です。

あなたの実装には少なくとも1つのバグがあります。深さは、誰がプレイしているかにかかわらず、常に減少するはずです。人間の枝では、人間のプレイヤーのために増加しています。これは、デプスが決して0にならないことを意味し、プレイヤーが勝者であると決定された場合にのみベースケースがヒットします。さらに、アルファベットを使用する場合は、ボードの評価が誰であるかを知ることが重要であり、誰が最大のプレイヤーであるかを知ることが重要です。そうしないとバグを見つけるのが難しくなります。あなたはここにそのコードを表示していませんが、毎回私がそれを得るので、私はそれを指摘したいと思います。