1

そこで最近、ゼロサムゲームで使われているミニマックス関数を見ていました。私はそれを完全に理解しましたが、実際の機能のためにボードがどのように実装されているかを除いて：

たとえば、私が見つけたこのサンプル実装には、次の宣言があります。

int miniMax(Board eval, int iterations)

私の唯一の質問は、正確にはBoard何ですか？それは構造体、クラス、配列、またはその他の構造体ですか？また、三目並べのようなミニマックス用のサンプルボードをどのように実装しますか（例として）？ウィキペディアまたはグーグルで何も見つかりませんでした。

4

2 に答える 2

3

ボードは現在のボードゲームです。これは、ゲームのボードを表すために使用する任意の構造にすることができます。

最初に呼び出されると、ミニマックス関数は、これまでに行われたさまざまなプレイ（ゲームの現在の状態）によって到達された現在のボード構成を受け取ります。ミニマックス機能では、ボードを変更します。各変更は、ゲームのルールに従って可能な動きを表す必要があります。これらの変更されたボードのそれぞれは、新しいミニマックス呼び出しへの引数として渡される必要があります。特定の深さ（つまり、反復回数）に達したら、評価関数を使用して最適な動きを選択し、変更されたすべてのボードにスコアを付け、スコアが最も高いボードを選択します。

あなたが読んでいるアルゴリズムは一般的であり、どんなゲームでも機能する可能性があります。ボードは、利便性、つまり、表現したいゲームのボードに最適なものに応じて定義できます。

三目並べの場合、ボードを3x3配列で表すと、ボードを変更できます。

int miniMax(char board[3][3], int iterations)

または、正方形ごとに2ビットを使用してボードを表現したい場合があります。

typedef struct {
    unsigned square1: 2;
    unsigned square2: 2;
    unsigned square3: 2;
    unsigned square4: 2;
    unsigned square5: 2;
    unsigned square6: 2;
    unsigned square7: 2;
    unsigned square8: 2;
    unsigned square9: 2;
} Board;

ただし、三目並べの場合、最大深度が9であるため、軽量のボード表現は必要ありません。ボードゲームを表現するために使用する任意の構造である可能性があることを理解できるように、例を示します。

ミニマックス関数を扱う予定で、ゲームが三目並べよりもはるかに複雑な場合は、大きな改善であるアルファベータ法の使用を真剣に検討する必要があります。

編集：まったく異なるものである評価関数と混同される可能性があるため、ボードを「評価」と呼ぶべきではないと思います。

于 2012-07-25T04:08:27.113 に答える
2

ボードは、あなたが書いているように、ミニマックスや他の多くの決定木アルゴリズムで使用される一般的な構造です。

これは、ゲームの特定の状態に関する情報を含む構造であることが意図されています。アルゴリズム自体では、論理的な観点から、このパラメーターは、ボード上を移動して新しいボードスナップショットを生成するという意味で変更できない必要があります（古いものは変更されません）。より良い戦略を見つけるためにあなたが評価している動き。

実際、ボードには2つの要素があります。ルールのセット（移動を行うことで状態を効果的に変更するために適用できます）と、反復ごとに変化する状態（ボード自体がまだ同じ）そしてそれは、プレイヤーにとっての動きの良さを評価するために使用されるオブジェクトです（最大深度に達したときに、状態だけで動きの良さを推定する必要があります）。

したがって、それは何でもかまいません。それは単なる概念的なパラメータです。もっと実用的なものが本当に必要な場合は、次のように想像します。

class BoardSnapshot {
  Board b;

  float alpha;    
  State state;
  int evaluate();
}

class Board {
  List<Players> players;
  List<Rules> rules;

  State applyMove(State current, Player player, Rule rule, params ...);
}

そのため、現在の状態なしで初期化しBoardSnapshot、ルールを適用して、現在選択されている木の枝のスナップショットとなる新しい状態を生成します。

于 2012-07-25T03:06:13.310 に答える