7

ミニマックスアルゴリズムに関して簡単な質問があります。たとえば、三目並べゲームの場合、各プレーヤーがプレイする効用関数をどのように決定しますか？それは自動的には行われませんよね？ゲーム内の値をハードコーディングする必要がありますが、それ自体では値を学習できませんね。

4

4 に答える 4

10

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

于 2009-10-19T14:00:39.753 に答える
3

通常、ユーティリティ関数を直接実装します。この場合、アルゴリズムはゲームのプレイ方法を学習せず、実装で明示的にハードコーディングした情報を使用します。

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

ミニマックス コードと GP コードを単一の (おそらく非常に遅い) 適応プログラムに結合するか、最初に GP を実行し、適切なユーティリティ関数を見つけてから、この関数をミニマックス コードに追加することができます。 -コード化された関数。

于 2009-10-21T22:19:02.630 に答える
2

Tic-Tac-Toe は、ゲームを最後まで実行し、勝利の場合は 1、引き分けの場合は 0、敗北の場合は -1 を割り当てるのに十分小さいです。

それ以外の場合は、位置の値をヒューリスティックに決定する関数を提供する必要があります。たとえばチェスでは、素材の価値だけでなく、誰が中心をコントロールしているか、駒がどれだけ簡単に動くかが大きな要因となります。

学習に関しては、ポジションのさまざまな側面に重み係数を追加し、ゲームを繰り返しプレイして最適化を試みることができます。

于 2009-10-19T14:05:07.777 に答える
2

各プレイの効用関数をどのように決定しますか?

慎重に ;-) この記事では、わずかに欠陥のある評価関数 (たとえば、考えられる層のツリーを先読みするのに十分「深く」進まないもの、またはボードの相対的な強さを捉えることができないもの) について説明します。位置) は、全体的に弱いアルゴリズム (より頻繁に負けるアルゴリズム) になります。

それはそれ自体でそれらを学習することはできませんね?

いいえ、そうではありません。ただし、ボードの位置の相対的な強さをコンピューターに学習させる方法はいくつかあります。たとえば、Donald Mitchie と彼の MENACE プログラムを調べると、ゲームのルール以外のアプリオリな知識がなくても、確率過程を使用して盤面を学習できることがわかります。おもしろいことに、これはコンピューターで実装できますが、ゲーム空間のサイズが比較的小さく、さまざまな対称性があるため、必要なのは数百個の色のビーズとマッチ箱だけです。

コンピューターに遊び方を教えるクールな方法を学んだ後は、三目並べに適用されるほど MinMax に戻ることにあまり興味がないかもしれません。結局、MinMax は決定木を剪定する比較的単純な方法であり、三目並べの小さなゲーム スペースではほとんど必要ありません。ただし、必要がある場合は ;-) [MinMax に戻る]...

次のプレイに関連する「マッチボックス」を調べて (つまり、まったく深くならない)、各マスに関連するビーズのパーセンテージを追加の要素として使用できます。次に、従来のツリーを評価できますが、たとえば、2 つまたは 3 つの移動の深さ (通常、通常は損失または引き分けで終わる浅い先読みの深さ) のみに進み、単純な -1 (負け)、0 (引き分け/不明)、+1 (勝利) の評価。次に、ビーズのパーセンテージと単純な評価を組み合わせることで (掛け算ではなく足し算によって)、評価できない場合に使用される方法に似た方法で MinMax を効果的に使用することができます。ゲームツリーを最後まで。

結論: Tic-Tac-Toe の場合、MinMax は、完全に簡単に評価できるゲームの決定論的な性質を取り除いた場合にのみ、より興味深いものになります (たとえば、特定の効用関数の有効性を調査するのに役立ちます)。木。[数学的に] ゲームを面白くするもう 1 つの方法は、ミスを犯す相手と対戦することです...

于 2009-10-19T14:06:09.813 に答える