2

私はconnect4AIに取り組んでおり、多くの人がこのデータセットを使用していて、8プライでのすべての法的位置とその最終的な結果が含まれているのを見ました。

検索アルゴリズムとしてアルファ/ベータプルーニングを使用した標準のミニマックスを使用しています。このデータセットは私のAIにとって本当に役立つ可能性があるようです。しかし、私はそれを実装するための最良の方法を見つけようとしています。最善のアプローチは、リストを処理し、ボードの状態を最終的な結果（勝ち、負け、引き分け）のハッシュとして使用することだと思いました。

このようなデータセットを使用するAIを設計するための最良の方法は何ですか？ボードの状態をハッシュし、それを従来の検索アルゴリズム（ミニマックスなど）で正しい軌道に乗せるという私の考えはありますか？またはより良い方法がありますか？

更新：私は最終的に大規模な移動データベースをプレーンなテスト形式に変換しました。1はXと-1 Oを表します。次に、ボードの状態の文字列、最終的な結果を表す整数を使用し、それをstd::unsorted_map（を参照してください。私が遭遇した問題のために、順序付けられていないマップでオーバーフローをスタックします）。マップのパフォーマンスは素晴らしかった。それは迅速に構築され、ルックアップは高速でした。しかし、私は検索を正しく行うことができませんでした。ゲームのターン数が8未満のときにデータベースを検索してから、通常のアルファベータに切り替えるという問題に取り組む正しい方法はありますか？

4

1 に答える 1

3

あなたのアプローチは正しいようです。

最初の8ムーブについては、アルファベータアルゴリズムを使用し、ルックアップテーブルを使用して、深さ8の各ノードの値を評価します。テーブルを
「使い果たした」（ゲームで8ムーブを超えた）場合は、切り替える必要があります。通常のアルファベータアルゴリズムに変換されます。これは、最終状態で終了します（ゲームツリーに残ります）。

これは非常に役立ちます。理由は次のとおりです。
ツリーの検索の複雑さは次のとおりです。O(B^d)ここBで、は分岐係数（状態ごとの可能な移動の数）でありd、最後まで必要な深さです。
このアプローチを使用することにより、次の理由により、最大の待機時間（最長の移動を計算する必要があります）の両方Bを効果的に減らすことができます。d

  1. 最大深度は大幅に縮小しd-8（最後の動きのみ）、効果的に減少しdます！
  2. このゲームでは、数回の移動後に分岐係数自体が縮小する傾向があります（多くの移動が不可能になるか、敗北につながるため、探索しないでください）。これは減少しBます。
  3. B^8最初の動きでは、開発されたノードの数も。の代わりに縮小しますB^d。

したがって、これらの理由により、このアプローチを使用することにより、最大待機時間が大幅に短縮されます。

また、注意：最適化が不十分な場合は、ルックアップテーブルをいつでも拡張できます（9,10、...最初の移動）。もちろん、必要なスペースが指数関数的に増加します。これは、検討する必要のあるトレードオフです。ニーズに最適なものを選択します（メインメモリが十分でない場合は、ゲーム全体をファイルシステムに保存することも検討する必要があります）

于 2012-12-04T22:22:45.567 に答える