artificial-intelligence - ミニマックス相手を倒す

Question

他の AI と競合する AI を作成する必要があります。

どちらの AI も同じハードウェアで実行され、処理時間とメモリ量は同じです。対戦相手の AI が、アルファ ベータ プルーニングを伴うミニマックス アルゴリズムを使用することはわかっています。

私の質問は、そのような相手を打ち負かすためのいくつかのアプローチは何ですか? 自分でミニマックスを使用すると、両方の AI が互いの動きを完全に予測し、ゲーム固有のプロパティ (最初の動きが勝つなど) に基づいてゲームが解決されます。

明らかな解決策は、より良い評価を可能にする可能性のある動きをどうにかして先に見ることです。プロセッサ時間は同じであるため、より深く評価することはできませんでした (反対の AI コードが等しく最適化されていると仮定して)。事前に計算されたツリーを使用してさらに利点を得ることができましたが、スーパー コンピューターがなければ、重要なゲームを「解く」ことはできませんでした。

アルファベータが剪定したような最適でないノードを意図的に選択することには、何らかの価値がありますか? これにより、対戦相手が戻ってツリーを再評価する必要があるため、CPU 時間のペナルティが発生する可能性があります。ペナルティが発生するだけでなく、ミニマックス ツリー + アルファ ベータを評価して、アルファ ベータが直接的な利益を得ることなくどのノードを削除するかを確認する必要があります。

そのような対戦相手に対して最適化するための他の戦略は何ですか?

Answer 1

まず、最適ではない戦略を選択しても何の価値もありません。対戦相手が最適なプレイをすると仮定すると (これはミニマックス検索の基本的な前提です)、対戦相手はミスを利用する動きをします。優れたゲーム エンジンには、大失敗に対する対抗手段を含むハッシュ化された反論テーブル エントリが含まれているため、乱暴な動きをしても時間の無駄にはなりません。悪い動きをすると、コンピューターの対戦相手は良い動きをより速く見つけることができます。

オセロのようなゲームで実現する重要なことは、ゲームの後半まで最適な動きが何であるかを確信できないということです。これは、ほとんどの場合、検索ツリーが大きすぎてすべての勝ちまたは負けの位置を徹底的に検索できないためです。そのため、ミニマックスはどの動きが勝利または敗北につながるかを確実に伝えることができません。検索を停止する場所をヒューリスティックに決定し、それらのノードを任意に「ターミナル」と呼び、ポジションの勝敗の可能性を推測する評価関数を実行することしかできません。

評価関数の仕事は、通常、ゲーム ツリーをさらに検索せずに計算できる静的メトリックを使用して、位置の値を評価することです。ピース数、位置の特徴、エンドゲームのテーブルベース、さらには対戦相手の心理学もここで役割を果たすことができます. 一般に、評価関数にインテリジェンスを追加すればするほど、エンジンのパフォーマンスが向上します。しかし、静的評価のポイントは、コストがかかりすぎる置換検索です。評価関数の処理が多すぎたり、非効率的であったりすると、同じ情報を取得するために必要なゲーム ツリーの検索よりも遅くなる可能性があります。評価関数に何を入れるか、検索の代わりに静的評価をいつ使用するかを知ることは、優れたゲーム エンジンを作成する技術の大部分です。