2

数年前、研究者たちは、チェッカーに対するブルートフォースの包括的なソリューションを完成させたと発表しました。

私は、より少ない状態を持つ必要がある別の同様のゲームに興味を持っていましたが、妥当な時間枠で完全なソルバーを実行することはまだ非常に非現実的です。部分的な解決策でも貴重な情報が得られる可能性があるため、試してみたいと思います。

概念的には、すべての既知の位置とそれに続く位置を含むゲーム状態のデータベースが必要です。1 つまたは複数のクライアントが、データベースから未調査の状態を取得し、可能な動きを計算し、新しい状態をデータベースに挿入できます。終盤の状態が見つかると、それに至るまでのすべての状態をミニマックス情報で更新して、決定木を構築できます。探索する可能性の高い分岐を選択するという賢明な決定が下された場合、最も重要な分岐の情報を構築し、時間をかけて徐々に構築して完成させることができます。

このアイデアのメリットや実現可能性を無視して、そのようなデータベースを実装する最良の方法は何ですか? 各状態の文字列表現を格納する簡単なプロトタイプを SQL Server で作成しました。それは機能しましたが、一度に 1 つの状態を引き出し、すべての動きを計算するため、私のソルバー クライアントの実行は非常に遅くなりました。メモリ内でより大きなチャンクを実行する必要があるように感じますが、検索スペースは明らかに大きすぎて、すべてを一度にメモリに格納できません。

この種の仕事に適したデータベース システムはありますか? 多数の挿入、多数の読み取り (状態 (または同等の状態) が既に存在するかどうかを確認するため) を行い、更新はほとんど行いません。

また、多くのクライアントが多くの作業を複製することなく、さまざまなブランチの解決に取り組むことができるように、どのように並列化できますか? 割り当てをチェックアウトし、数百万の状態を生成し、それを送信してメイン データベースに統合するプログラムのようなものを考えています。そのようなものがうまく機能するかどうか、またはそのようなことを行うための方法に関する以前の研究があるかどうかはわかりません.

4

3 に答える 3

2

間違いなく、 RabbitMQなどのある種のタスク キュー サービスが必要です。おそらく、計算したデータを格納できるデータベースと組み合わせて使用​​します。または、Amazon のSQSなどのホストされたサービスを使用することもできます。クライアントは、キューからアイテムを消費し、サクセサーを生成してキューに入れ、消費したアイテムの結果をキューに追加します。状態が最終状態の場合、データベースを参照することで、親要素までスコアリング情報を伝達できます。

注意すべき 2 つの注意事項:

  1. キュー内のアイテムの数は、ツリーを探索するにつれて指数関数的に増加する可能性が高く、各作業アイテムによってさらにいくつかのアイテムがキューに入れられます。非常に長いキューに備えてください。
  2. ゲームによっては、同じゲーム ステートへの複数のパスが存在する可能性があります。重複をチェックして排除する必要があります。データベースは、ツリーではなくグラフ (おそらくサイクルを含む) になるように構造化する必要があります。
于 2011-05-29T00:22:14.857 に答える
2

ゲームを解決するために、データベース内の状態ごとに本当に知る必要があるのは、そのゲーム理論値です。つまり、移動する番のプレーヤーが勝つか、負けるか、強制引き分けかです。この情報を状態ごとにエンコードするには、2 ビットが必要です。

次に、エンドゲーム データベースを構築したい一連のゲーム状態に対して、できるだけコンパクトなエンコーディングを見つけます。エンコーディングに 20 ビットかかるとしましょう。その場合、ハードディスクに2 21ビット、つまり 2 13バイトの配列があれば十分です。ゲーム終了時の位置を分析するときは、まず、対応する値がデータベースに既に設定されているかどうかを確認します。そうでない場合は、すべての後続ノードを計算し、それらのゲーム理論値を再帰的に計算してから、元のノードのゲーム理論値の最小値/最大値を使用して計算し、データベースに保存します。(注: 勝ち/負け/引き分けのデータを 2 ビットで保存する場合、「不明」を示すビット パターンが 1 つ残っています。たとえば、00 = 不明、11 = 引き分け、10 = 勝ちを移動するプレーヤー、01 = 移動するプレーヤー移動は負けます）。

たとえば、三目並べを考えてみましょう。9 つの正方形があります。すべてが空、「X」または「O」の場合があります。この単純な分析では、状態ごとに 3 9 = 2 14.26 = 15 ビットが得られるため、2 16ビットの配列が得られます。

于 2011-05-29T20:55:40.090 に答える
1

最初に頭に浮かんだのは、Lindaスタイルの共有「ホワイトボード」です。ここでは、さまざまなプロセスがホワイトボードの「問題」を消費し、ホワイトボードに新しい問題を追加し、ホワイトボードに「解決策」を追加できます。

おそらく、Cassandraプロジェクトは Linda の最新バージョンです。

分散コンピュータ システム全体で問題を並列化する試みが数多く行われています。Folder@Homeは、バイナリ ブロブの「コア」を実行してタンパク質のフォールディングの問題を解決するフレームワークを提供します。Distributed.netは、分散型問題解決の現代化を開始した可能性があり、開始できるクライアントを持っている可能性があります。

于 2011-05-28T03:40:42.723 に答える