10

私は、TicTacToe を解決する小さなプログラムを作成して、簡単なゲームでいくつかの剪定手法の効果を試すことにしました。ミニマックスを使用してそれを解決する完全なゲーム ツリーは、549,946 の可能なゲームしかありません。α-β プルーニングにより、評価に必要な状態の数は 18,297 に減少しました。次に、数値を 2,592 に下げる移調表を適用しました。今、私はその数がどれだけ低くなるかを見たいと思っています。

私が適用したい次の強化は、戦略的削減です。基本的な考え方は、同等の戦略的価値を持つ州を結合することです。たとえば、最初の手で、X が最初にプレイした場合、別のコーナーではなく 1 つのコーナーを選択することについて戦略的に違いはありません (対戦相手が最適にプレイすると仮定)。同じ状況では、ボードの壁の中心についても同じことが言え、中心も重要です。重要な状態のみに減らすことで、最初の移動で評価する状態が 9 つではなく 3 つのみになることになります。この手法は、ゲーム ツリーの最上部付近の状態を削除するため、非常に便利です。このアイデアは、CMU のグループによって作成された GameShrink メソッドから生まれました。一般的な形式を書くことを避けようとしているだけで、TicTacToe にテクニックを適用するために必要なことだけを行っています。

これを達成するために、ハッシュ関数 (転置テーブル用) を変更して、(回転関数と反転関数を使用して) 戦略的に同等の位置をすべて列挙し、各ボードの最低値のみを返すようにしました。残念ながら、私のプログラムは、X が最初に行ったときに、空のボードから 5 つの手で強制的に勝つことができると考えています。長いデバッグセッションの後、プログラムが常に戦略的に重要な最も低い移動の移動を返していることが明らかになりました (私は状態の一部として転置テーブルに最後の移動を保存します)。この機能を追加するためのより良い方法、または既に行ったことを使用して現在の状況に適用できる正しい動きを判断する簡単な方法はありますか?

4

7 に答える 7

5

私の直感は、あなたがこの問題を攻撃するためにあまりにも大きなハンマーを使っているということです. 9 つのスポットのそれぞれには、X または O または空という 2 つのラベルのうちの 1 つしかありません。その場合、最大で 3^9 = 19,683 のユニークなボードがあります。すべてのボードに 3 つの同等の反射があるため、実際には 3^9 / 4 ～ 5k のボードしかありません。無効なボードを捨てることでこれを減らすことができます (X の列と O の列が同時にある場合)。

したがって、コンパクトな表現では、すべてを列挙するのに 10kb 未満のメモリしか必要ありません。ゲームグラフ全体を評価してメモリに保存します。

ミニマックス値をトップダウンではなくボトムアップで計算することにより、すべてのボードに真のミニマックス値をラベル付けできます (ツリー検索方法のように)。一般的な概要は次のとおりです。ゲームが始まる前に、すべての固有のボードの最小値を計算し、最初にそれらすべてにラベルを付けます。ミニマックスの動きを作るには、現在の状態に続くボードを見て、最高のミニマックス値を持つ動きを選ぶだけです。

初期ラベリングの実行方法は次のとおりです。すべての有効な一意のボードを生成し、反射を捨てます。ここで、移動数が最も多い (9) ボードにラベルを付け始め、移動数が最も少ない (0) ボードまで繰り返します。終盤のボードには、勝ち、負け、引き分けのラベルを付けます。X が移動する番である非エンドゲーム ボードの場合: 1) X の勝利である後継ボードが存在する場合、このボードに勝利のラベルを付けます。2) 後続のボードで勝ちがなく、引き分けが存在する場合、このボードを引き分けとラベル付けします。3) 後続のボードに勝ちも引き分けもない場合、このボードは負けと見なされます。O のターンにラベルを付けるときのロジックも同様です。

実装に関する限り、状態空間のサイズが小さいため、「存在する場合」のロジックを 5k のすべての状態に対する単純なループとしてコーディングします。しかし、漸近的な実行時間のためにこれを本当に微調整したい場合は、どのボードの状態がどのボードの状態につながるかの有向グラフを作成し、エッジの逆方向にトラバースしてミニマックス ラベル付けを実行します。

于 2010-06-22T04:54:08.733 に答える
2

反射と回転について考えているときは、正しい軌道に乗っています。ただし、間違った場所に適用しています。転置表または転置表コードに追加しないでください。最初から論理的に同等の状態を排除するために、ムーブ生成関数内に配置してください。

転置テーブルと関連するコードを可能な限り小さく効率的に保ちます。

于 2010-06-15T18:09:37.720 に答える
1

最低値の位置とともに (逆の) 転置を返す必要があります。そうすれば、次の位置を取得するために、予想される動きに逆の転置を適用できます。

于 2010-06-09T22:47:48.297 に答える
0

これについて言えることはたくさんありますが、ここではツリーサイズを縮小するためのヒントを1つだけ紹介します。MattGinsbergは、ボード上で等価性を削減するPartitionSearchと呼ばれる方法を開発しました。それはブリッジでうまく機能し、彼は例として三目並べを使用します。

于 2010-06-22T18:30:25.163 に答える
0

転置テーブルを変更可能にする必要があるのはなぜですか? 最善の手は履歴に依存しません。

于 2010-06-09T22:40:18.080 に答える