11

私はアルゴリズムにかなり慣れていないので、ミニマックスを理解しようとしていました.多くの記事を読みましたが、Pythonで三目並べゲームに実装する方法がまだわかりません. おそらく疑似コードまたはPythonコードを使用して、できるだけ簡単に説明していただけますか?

それがどのように機能するかを理解する必要があります。私はそれについて多くのことを読み、基本を理解しましたが、それがどのように動きを返すことができるのかまだわかりません.

(http://en.literateprograms.org/Tic_Tac_Toe_(Python)) のようなチュートリアルやサンプルをリンクしないでください。それらが優れていることは知っていますが、ばかげた説明が必要です。

お時間をいただきありがとうございます:)

4

2 に答える 2

9

「ミニマックス」の考え方は、2 人のプレーヤーのゲームで、1 人のプレーヤーが何らかの形式のスコアを最大化しようとし、別のプレーヤーがそれを最小化しようとすることです。たとえば、Tic-Tac-Toe では、X の勝利は +1 としてスコア付けされ、O の勝利は -1 としてスコア化される場合があります。X は最大プレーヤーで、最終スコアを最大化しようとし、O は最小プレーヤーで、最終スコアを最小化しようとします。

X は最大プレイヤーと呼ばれます。これは、X の手の場合、X はその動きの後の結果を最大化する動きを選択する必要があるためです。O 人のプレイヤーの場合、O はその手の結果を最小化する手を選択する必要があります。これらのルールは再帰的に適用されるため、たとえば、プレイできるボード ポジションが 3 つしかない場合、X の最良のプレイは、O に可能な限り高い値を持つ最小値の動きを選択させるものです。

言い換えると、ボード位置 B のゲーム理論上の最小値 V は次のように定義されます。

 V(B) = 1   if X has won in this position
 V(B) = -1  if O has won in this position
 V(B) = 0   if neither player has won and no more moves are possible (draw)

それ以外は

 V(B) = max(V(B1), ..., V(Bn)) where board positions B1..Bn are
        the positions available for X, and it is X's move
 V(B) = min(V(B1), ..., V(Bn)) where board positions B1..Bn are
        the positions available for O, and it is O's move

X の最適な戦略は常に、V(Bi) が最大になるように B から Bi に移動することです。つまり、ゲーム理論値 V(B) に対応し、O の場合も同様に、最小の後継者の位置を選択します。

ただし、これはチェスのようなゲームでは通常は計算できません。ゲームの理論値を計算するには、ゲーム ツリー全体を最終位置まで列挙する必要があり、そのツリーは通常非常に大きいためです。したがって、標準的なアプローチは、ボードの位置をスコアにマッピングする「評価関数」を作成することです。スコアは、ゲーム理論値と相関することが期待されます。例えば、チェスプログラムでは、評価関数は物質的なアドバンテージ、開いた列などに対して正のスコアを与える傾向があります。ミニマックスアルゴリズムは、ボードの位置の実際の (計算不可能な) ゲーム理論値ではなく、評価関数のスコアを最小化します。

ミニマックスに対する重要な標準的な最適化は、「アルファ ベータ プルーニング」です。ミニマックス検索と同じ結果が得られますが、より高速です。ミニマックスは、検索レベルごとにスコアの符号が反転する「ネガマックス」の観点からキャストすることもできます。これは、ミニマックスを実装する別の方法にすぎませんが、プレーヤーを統一された方法で処理します。その他のゲーム ツリーの検索方法には、反復深化、証明数検索などがあります。

于 2012-05-17T15:29:14.783 に答える
3

ミニマックスは、交代する 2 人のプレーヤーのゲームで潜在的な動きのスペースを探索する方法です。あなたは勝とうとしていて、対戦相手はあなたの勝利を妨げようとしています。

重要な直感は、現在あなたの番である場合、対戦相手があなたに協力しないため、勝利を保証する 2 つの動きのシーケンスは役に立たないということです。あなたは勝つ可能性を最大にする動きをしようとし、相手はあなたの勝つ可能性を最小限にする動きをします。

そのため、自分が行った自分にとって悪い手や、対戦相手が行った自分にとって良い手から分岐を探索することはあまり役に立ちません。

于 2012-05-16T22:22:25.490 に答える