4

三目並べゲームのMini-maxを探していましたが、再帰がどのように機能するのか理解できませんでしたか？さて、基本的にここに私の質問があります：

  1. ミニマックスはどのようにして誰の番かを知るのですか？自分のターンを生成しているプレーヤーを示す最良の方法は何ですか？
  2. 可能な動きをどのように生成しますか？
  3. ターミナルノードにいることをどのように知っていますか？また、ターミナルノードをどのように生成しますか？

たとえば、この擬似コードでは

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 α

Anodeボードは正しいですか？そして、コードが再帰的に下がらなければならない層の深さはどれくらいですか？また、max関数とは何ですか？ノードはどこから生成されていますか？

これまでのところ、ボードを作成するための次のコードがあります。

class Board{
    public:
        Board();
        ~Board(){};
    public: // The board
        // In the board, 1 is x, 2 is o, 0 is empty square.
        int board[3][3];
};

しかし、誰の番かをどうやって知ることができますか？また、ボードの子ノードを生成するにはどうすればよいですか？

4

3 に答える 3

5

最初に、例として三目並べを使用します。

  • ミニマックスアルゴリズムは、プレーヤーが交互にターンするゲームに最適ですが、プレーヤーがターンごとに複数の動きをする可能性があるゲームに適合させることができます。簡単にするために、前者を想定します。その場合、ノードごとに「移動するX」または「移動するO」を格納する必要はありません。これは、ノードの深さのパリティによって決定できるためです（ステップ数が偶数か奇数か）。上からのステップ数）。
  • 各位置から可能な移動を生成するには、それが誰の移動であるか（以前と同様に決定できます）、および特定の位置からの合法的な移動のルールを知っている必要があります。三目並べのような単純なゲームの場合、位置を指定すると、現在の位置のコピーと、現在のプレーヤーに属する新しいピースで構成されるすべての状態を、空の各正方形に順番に列挙するだけで十分です。オセロのようなゲームの場合は、各プレースメントをチェックしてルールに従っていることを確認し、ルールの結果に応じて最終的な位置を更新する必要があります（オセロの場合は、たくさんのピースの色を反転します）。一般に、追跡している各有効な位置から、新しいピースのすべての可能な配置を列挙し、ルールセットで許可されている位置を確認します。
  • ゲームツリーのサイズはEarthのストレージ容量を簡単に超える可能性があるため、通常、ツリー全体を生成することはありません。反復の最大深度は常に設定します。したがって、ターミナルノードは、単純に最大深度のノード、または合法的な移動が存在しないノードです（tic-tac-toeの場合、すべての正方形が塗りつぶされたボード）。事前にターミナルノードを生成する必要はありません。それらはゲームツリーの構築中に自然に生成されます。Tic-tac-toeは、ゲームツリー全体を生成できるほど単純ですが、Othelloなどのtic-tac-toeコードを使用しないでください。

擬似コードを見る：

  • max(a, b)aまたはの大きい方を返す関数ですb。これは通常、数学ライブラリなどによって提供されます。
  • はdepth、検索する最大の深さです。
  • 計算しているヒューリスティック値は、ボードの値を表す数値です。ゲームツリー全体を列挙できるほど単純な三目並べのようなゲームの場合1、分析を行うプレーヤーに-1勝つボード位置、他のプレーヤーに勝つボード位置を指定できます。そして0、決定的な立場ではありません。一般に、ヒューリスティックを自分で作成するか、広く受け入れられているものを使用する必要があります。
  • 親ノードに基づいて、分析中にその場でノードを生成します。ルートノードは、常に分析を行う位置です。

グラフやツリーをまだ使用していない場合は、最初に使用することをお勧めします。特に、ツリープリミティブはこの問題に不可欠です。

特定のノードの順番を決定する例を求めるこのスレッドのコメントへの回答として、この疑似Pythonを提供します。

who_started_first = None

class TreeNode:
    def __init__(self, board_position = EMPTY_BOARD, depth = 0):
        self.board_position = board_position
        self.children = []
        self.depth = depth
    def construct_children(self, max_depth):
        # call this only ONCE per node!
        # even better, modify this so it can only ever be called once per node
        if max_depth > 0:

            ### Here's the code you're actually interested in.
            if who_started_first == COMPUTER:
                to_move = (COMPUTER if self.depth % 2 == 0 else HUMAN)
            elif who_started_first == HUMAN:
                to_move = (HUMAN if self.depth % 2 == 0 else COMPUTER)
            else:
                raise ValueError('who_started_first invalid!')

            for position in self.board_position.generate_all(to_move):
                # That just meant that we generated all the valid moves from the
                # currently stored position. Now we go through them, and...
                new_node = TreeNode(position, self.depth + 1)
                self.children.append(new_node)
                new_node.construct_children(max_depth - 1)

各ノードは、「ルート」ノードからの絶対深度を追跡できます。次の動きのためにボードの位置をどのように生成するかを決定しようとすると、深さのパリティ（の結果self.depth % 2）と誰が最初に動いたかの記録に基づいて、誰の動きであるかを確認します。

于 2012-07-28T19:32:03.273 に答える
2

三目並べのミニマックスアルゴリズムを書いたので、あなたが探しているものについて少しアイデアを提供することができます。

質問に直接答えるには：

  1. 私のミニマックスアルゴリズムはそれを決定しませんでした。アルゴリズムが使用しているプレーヤーを決定する引数を受け入れました。

  2. 移動するプレーヤーを知って、ボード上のすべての空白の正方形をループし、それぞれについて、その正方形に現在のプレーヤーのトークンを含むノードを生成します。そこから再帰的に進みます。

  3. ゲームが終了したかどうか、引き分けか勝利かを示す値を返す関数を使用しました。

私の基本的なアルゴリズムはこれを行いました：

  • 入力：移動するプレーヤー、およびボードの状態。
  • ボードに残っているすべての空白スペースを見つけます。
    • そのスペースでのプレイヤーの動きで新しいボードを生成します。
    • ゲームが終了した場合は、ゲームの結果を含むノードを生成します。
    • それ以外の場合は、アルゴリズムを実行して、他のプレーヤーと新しいボードを渡し、対戦相手の理想的な動きの結果でノードを生成します。
  • どのノード（移動）が最良の最悪のケースにつながるかを判断します。
  • 出力：最良の動き、およびそれからのゲームの結果に関する情報。
于 2012-07-28T19:44:37.227 に答える
2

1）ミニマックスはどのようにして誰の番かを知るのですか？自分のターンを生成しているプレーヤーを示す最良の方法は何ですか？

あなたにはそのdepth議論があります。深さが偶数の場合は1人のプレーヤーのターン、奇数の場合は他のプレーヤーのターンです。

2）どのように可能な動きを生成しますか？

ゲームのルールを使用します。三目並べでは、可能な移動とは、自分のマークをフリーセルに配置することを意味します。

3）ターミナルノードにいることをどのように知っていますか？また、ターミナルノードをどのように生成しますか？

ターミナルノードは、誰かが勝ったノードです。それらは再帰によって生成されます。各再帰呼び出しには、ボードの現在の状態を指定する必要があります。それがあなたの擬似コードのパラメータだnodeと思います。childしたがって、その状況で誰かが勝った場合、それはターミナルです。そうでない場合は、すべての合法的な動きを試みて、再発します。

于 2012-07-28T19:33:49.883 に答える