1

最小/最大で三目並べを作成しているので、アルファ ベータ プルーニングに拡張できます。したがって、最小/最大の間に、パスが +1 (X 勝利) -1 (O 勝利) または 0 (ドロー) につながるかどうかを見つけますが、次のようなボード構成の場合:

0 ターン中は、その動きが勝利につながるため、左下を選択します。ブロックの各テーブルをチェックする必要がある場合、それはそれほど速く実行されず、最小/最大をどのように実装する必要があるとは思いません。

0|x|0
-|x|-
-|-|-

最小/最大がそれを検出するほど賢くない理由を誰かが説明できますか? 左のノードを見て、+1/-1/0 を返すと思いました。

4

2 に答える 2

2

編集：「純粋な」ミニマックスとミニマックス+ヒューリスティックを混同してきました。これを解決するために回答を編集しました。

たぶん、minmax を定義するのに役立つでしょう。カリフォルニア大学バークレー校の学生による記事から:

minimax(player,board)
    if(game over in current board position)
        return winner
    children = all legal moves for player from this board
    if(max's turn)
        return maximal score of calling minimax on all the children
    else (min's turn)
        return minimal score of calling minimax on all the children

ミニマックスでは、利益を最大化するのではなく、損失を最小化しようとします。だから、「あなた」の番ですmin's。この定義では、正方形を選択して負ける可能性がある場合は、 とマークされます-1。同点でも絶対に負けない場合は、 とマークされます0。それが保証された勝利である場合にのみ、それはマークされ1ます。

ブロックの各テーブルをチェックする必要がありますか

スコアとアルゴリズムを正しく定義している場合 (適切なプレーヤーを適切なロジックに一致させている場合)、「ブロックをチェックする」必要はありません。プレーヤーがブロックしなかったゲームのサブツリーは、暗黙的に評価する必要があります-1。これは、ある時点で (おそらく非常に迅速に) 損失と評価され、その損失がバブルアップするためです。

このアルゴリズム (および予期しない結果が得られる可能性がある場所) の本当の問題は、すべてのサブツリーが損失の可能性がある場合です。その時点で、ヒューリスティックを使用して、取るべき動きに関するより良い情報を取得する必要があります。{-1, 0, 1}いくつかの動きで勝つことができるため、単に.

于 2011-07-04T19:55:00.607 に答える
0

あなたの問題についてはよくわかりません。前に指摘したように、複数のパスが勝利につながるか、すべてのパスが敗北につながる場合、最小/最大には問題があります。このような場合、勝利パスまたは損失パスを選択することは数学的に正しいです。ただし、完璧ではない敵とプレイする場合は、最短の勝利パスと最長の敗北パスを選択する方が賢明な場合がよくあります (敵が完璧にプレイせず、間違った選択を選択することを期待するため)。

この動作は、再帰ごとに減衰を使用して最小/最大で実装するのが非常に簡単です。つまり、再帰呼び出しから何かを返すたびに、結果に 0.9 などを掛けます。これにより、ネガティブ パスが長いほどスコアが高くなり、ポジティブ パスが長いほどスコアが低くなります。

ただし、ヒューリスティックを使用して抜け出すと、問題が発生します。

于 2011-07-05T11:21:35.063 に答える