2

この質問についてGoogleとStackoverflowを検索しましたが、ミニマックス関数がどのように機能するかまだわかりません。

ウィキペディアのエントリに関数の疑似コード バージョンがあることがわかりました。

function integer minimax(node, depth)
    if node is a terminal node or depth <= 0:
        return the heuristic value of node
    α = -∞
    for child in node:                       # evaluation is identical for both players 
        α = max(α, -minimax(child, depth-1))
    return α

Google で見つけた他のいくつかのミニマックス関数は、基本的に同じものです。これを C++ で実装しようとしていますが、これがこれまでに思いついたものです。

double miniMax(Board eval, int iterations)
{
    //I evaluate the board from both players' point of view and subtract the difference
    if(iterations == 0)
        return boardEval(eval, playerNumber) - boardEval(eval, opponentSide());

    /*Here, playerTurn tells the findPossibleMoves function whose turn it is;
    I mean, how do you generate a list of possible moves if you don't even know
    whose turn it's supposed to be? But the problem is, I don't see where I can
    get playerTurn from, as there are only 2 parameters in all the examples of
    minimax I've seen*/
    vector<int> moves = eval.findPossibleMoves(playerTurn);

    //I'm assuming -∞ in the wikipedia article means a very low number?
    int result = -999999999;

    //Now I run this loop to evaluate each possible move
    /*Also, the Lua example in the wiki article has
      alpha = node.player==1 and math.max(alpha,score) or math.min(alpha,score)
      Is alpha a boolean there?!*/
    for(int i = 0; i * 2 < moves.size(); i++)
    {
        //I make a copy of the board...
        Board temp = eval;

        /*and make the next possible move... once again playerTurn crops up, and I
        don't know where I can get that variable from*/
        temp.putPiece(moves[i * 2], moves[i * 2 + 1], playerTurn);

        /*So do I create a function max that returns the bigger of two doubles?*/
        result = max(result, -miniMax(temp, iterations - 1));
    }

    return result;
    /*So now I've returned the maximum score from all possible moves within a certain
    # of moves; so how do I know which move to make? I have the score; how do I know
    which sequence of moves that score belongs to?*/
}

ご覧のとおり、私はこのミニマックス関数についてかなり混乱しています。少なくとも、これを助けるためのヒントを教えてください。

ありがとう！:)

4

5 に答える 5

3

ウィキペディアのそのサンプルは、アルファ/ベータ プルーニングを使用して NegaMax を実行しています。

ネーミングをまっすぐにすることで助けになるかもしれません：

  • 基本は MiniMax です。リテラル実装には、両側に 1 つずつ、順番に (相互に再帰的に) 実行される 2 つのメソッドが含まれます。

  • -怠惰なプログラマーはこれを、戦略的に配置されたオペレーターを持つ 1 つのメソッドである NegaMax に変えます。

  • アルファ/ベータ プルーニングは、死んだ枝を検出するために (複数の深さにわたって) ベスト ムーブのウィンドウを追跡します。

あなたplayerTurnのターンは誰の番かを決定するために使用されます。NegaMax では、深さ (反復) が奇数または偶数であることからこれを導き出すことができます。ただし、2 つのパラメーター (myColor、otherColor) を使用して、各レベルで切り替える方が簡単です。

于 2010-09-02T20:02:13.917 に答える
1

miniMax() 関数は、これまでに見つけた最良の動きを記憶する必要があります。したがって、このコードの代わりに:


  /*So do I create a function max that returns the bigger of two doubles?*/
  result = max(result, -miniMax(temp, iterations - 1));

次のようにする必要があります。


  /*So do I create a function max that returns the bigger of two doubles?*/
  double score = -miniMax(temp, iterations - 1);
  if (score > result)
  {
     result = score;
     bestMove = i;
  }

もちろん、変数「bestMove」と、見つかった最良の動きを呼び出し元に返す方法が必要です。

于 2010-09-02T19:56:12.453 に答える
1

playerTurn変数を引数としてに追加し、現在のプレイヤーの最初の動きを再帰的にminiMax呼び出します。miniMax

また、opponentSideの関数である必要がありますplayerTurn。

于 2010-09-02T19:57:06.130 に答える
1

ゲーム ツリーの検索を開始するのに適した場所は、チェス プログラミング wikiです。移動についての質問: 2 つの max-function を持つのが最も一般的だと思います。2 つの max 関数の違いは、1 つはスコアのみを返し、もう 1 つはスコアとベスト ムーブを返すことです。再帰呼び出し順序は次のようになります。

maxWithBestMoveReturn(...) --> min(...) --> max(...) --> min(...)

Alpha Beta アルゴリズムの疑似コードを含む優れた論文がいくつかあります。

コメントであなたの質問に: and math.max(alpha,score) or math.min(alpha,score) Is alpha a boolean there?!

アルファ ベータ アルゴリズムでは、アルファはウィンドウ バウンドではありません。アルファ値は新しい値で更新されます。alpha と beta は negamax-Function の再帰呼び出しで交換されるため、alpha 変数は次の再帰呼び出しで beta 変数を参照します。

playerTurn 変数に関する 1 つの注意: ミニマックスまたはアルファ ベータ アルゴリズムでは、この情報は必要ありません。だから私は情報を与えます - 次は誰ですか - ボード構造に。関数 findPossibleMoves と boardEval は、Board-Structure から必要なすべての情報を取得します。

再帰ブレーク条件の 1 つの注意事項: コードを正しく理解していれば、iterations == o. これは、アルゴリズムが目的の深度に達したことを意味すると思います。しかし、アルゴリズムがこの深さに到達する前に可能な手が残っていない場合はどうなるでしょうか。多分あなたは次のように書くべきです：

vector<int> moves = findPossibleMoves(...);
if (!moves.size())
    return boardEval(...);
于 2010-09-02T20:26:16.553 に答える
0

疑似コードでは、ノード変数には、現在のボードの位置 (または何でも) に関するすべての情報が含まれている必要があります。この情報には、誰の順番で移動するかが含まれます。

于 2010-09-02T20:25:48.867 に答える