ミニマックスアルゴリズム

Question

どのように私は、各プレイヤーの再生のためのユーティリティ関数のを決定します、三目並べゲームの例：

私はミニマックスアルゴリズムに関する素朴な疑問がありますか？それは自動的にそれをしない、それはありませんか？私は、ゲーム内の値は、それ自体でそれらを学ぶことができないハードコードをしなければならないそれをしない？

Answer 1

いいえ、MiniMaxのは学習しません。これは、ブルートフォース木探索のよりスマートなバージョンです。

Answer 2

通常は、直接効用関数を実装します。この場合、アルゴリズムは、それはあなたが明示的な実装にハードコーディングされていたという情報を使用することになり、ゲームをプレイする方法を学びません。

しかし、遺伝的プログラミングする（GP）またはいくつかの同等の技術を使用することが可能ですユーティリティ関数を自動的に導出します。この場合、あなたは明示的な戦略をエンコードする必要はありません。代わりに、進化はよくゲームをプレイする独自の方法を発見するでしょう。

あなたはどちらか（おそらく非常に遅い）単一の適応プログラムにあなたのミニマックスコードとGPコードを組み合わせることができ、またはあなたは、最初にGPを実行する優れたユーティリティ関数を検索し、ちょうどあなたとあなたのミニマックスコードにこの機能を追加することができます任意ハンドコード機能するであろう。

Answer 3

三目並べを失うために最後までゲームを実行し、勝利のために1を割り当て、0引き分けと-1に小さな十分です。

そうしないと、発見的位置の値を決定する機能を提供する必要があります。例えば、チェスに大きな要因は、材料の値であるだけでなく、誰が中心を制御または片は移動することができる方法を容易に

学習用として、あなたは位置の異なる側面に重み係数を追加し、繰り返しゲームをプレイすることで、それらのを最適化しようとすることができます。

Answer 4

はどのように各プレイするためのユーティリティ関数を決定するのですか？の

慎重;-)この記事のショーどのようにわずかに欠陥の評価（可能プライの木に先読みに「深い」十分に行かないかの元に1つ。、またはいくつかのボード位置の相対的strenghをキャプチャするために失敗した1）機能全体として弱いアルゴリズム（より頻繁に失うもの）をもたらす。

のそれはそれ自体でそれらを学ぶことができない、それ？の

ん いいえ、それはしていません。方法は、コンピュータがボード位置の相対的な強さを学ぶ作るために、しかし、があります。 のドナルドMitchieと彼のMENACEプログラムのを覗くことにより、たとえば、あなたは、確率論的プロセスが任意ののアプリオリの知識ではなく、ゲームのルールなしにボードを学ぶために使用することができますどのように表示されます。面白い部分は、これは、コンピュータで実現することができる一方で、数百色のビーズとマッチボックスがゲーム空間の比較的小さなサイズのおかげで、様々な対称性にも感謝必要とされる全て、ということです。

チックタックつま先に適用される

は再生する方法を、コンピュータを教えるようにクールな方法を学んだ後、私たちはそうのMinMaxに戻って行くことに興味がないかもしれません。すべての後ののMinMaxは、決定木を剪定する比較的簡単な方法であるの、ほとんど三目並べの小さなゲーム空間で必要とされていません。しかし、我々は;-) ...

[のMinMaxに戻る]なければならない場合

私たちは、次のプレイに関連する「マッチ箱」（すなわち、すべての深いつもりはない）に見て、そして追加の要因として、各正方形に関連したビーズの割合を使用することができます。私たちは、2または3が移動深いと言うとシンプルに基づいてそれぞれの次の動きを評価-1（（一般的に損失が通常で終わるか、引くでしょう浅いルックアヘッド深さ）、その後、伝統的な木を評価するが、わずかに行くことができます損失）、0（、）/ 1（勝利）の評価を、未知を描きます。その後、ビーズの割合と（言うの添加によって、確かに乗算することにより）簡単な評価を組み合わせることで、我々は効果的にそれを評価することができないときに、それは場合に使用されているような方法で、より似ている形でのMinMaxを使用することができますその最後までゲーム木ます。

ボトムライン：チックタックつま先の場合は、のMinMaxが唯一の私たちは、ゲームの決定論的な性質を削除すると（私たちは特定の効用関数の有効性を探るうえで、たとえば）より面白くなると、簡単に関連付けられています評価完全なツリー。ゲームを作るもう一つの方法は、[数学]興味深いのはミスをする相手と遊ぶことです...