「ダミーのための」Minimaxの説明

Question

私はアルゴリズムに新しく、ミニマヤを理解しようとしていました。私は多くの記事を読んでいましたが、まだそれをチック・タック・トゥに実装する方法はありませんPythonでゲーム。 擬似コードやいくつかのPythonコードを使って、できるだけ簡単に説明してもらえますか？

どのように動作するかを理解するだけです。私はそれについて多くのことを読んで、私は基本を理解しましたが、私はまだそれが動きを返す方法を得ることができません。

（http://en.literateprograms.org/Tic_Tac_Toe_(Python）のような私のチュートリアルやサンプルをリンクしないでくださいが、私は彼らが良いことを知っていますが、私は単にバカの説明が必要です。

はお時間:)

Answer 1

2人プレイのゲームでは、1人のプレーヤーがある形式のスコアを最大化しようとしていて、もう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のための最適な戦略は、にBから移動するために常にV（Bi）が最大である、すなわち、遊泳度の値V（B）に対応するように、および同様に、最小後続者の位置を選択するように、

しかし、通常、チェスのようなゲームで計算することはできません。配偶子の価値を計算するには、最終的な位置までツリー全体を列挙し、そのツリーは通常非常に大きいからです。したがって、標準的なアプローチは、ボードの位置を、配偶子の値とうまく関連しているスコアにマップする「評価関数」をコインにすることです。例えば。チェスプログラムでは、評価関数は材料優位性、オープンカラムなどに対してプラスのスコアを与える傾向があります。ミニマックスアルゴリズムは、ボード位置の実際の（計算不可能な）配座率の値ではなく、評価関数のスコアを最小限に抑えます。

ミニマムへの重要な標準的な最適化は「アルファベータプルーニング」です。ミニマックス検索と同じ結果が得られますが、高速です。 Minimaxは、すべての検索レベルでスコアの符号が逆転する「negamax」の形でキャストすることもできます。これはミニマックスを実装する代わりの方法ですが、プレーヤーを統一的に扱います。他のゲームツリーの検索方法には、反復深化、プルーフナンバー検索などがあります。

Answer 2

ミニマックスをありがとうターンを交互に2つのプレーヤーのゲームの潜在的な移動空間を探索する方法です。あなたは勝つことを試みており、あなたの相手は勝つことを妨げようとしています。

鍵の直感は、現在あなたのターンであれば、相手があなたに協力しないため、勝利を保証する2つの移動シーケンスが役に立たないということです。あなたは勝利のチャンスを最大にする動きをしようとし、相手はあなたの勝利の可能性を最小限に抑える動きをします。

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