8

ボードゲーム用の AI を作ろうとずっと考えていて、最近リソースとアルゴリズムを集め始めました。ゲームはランダムではなく、ほとんどの場合、1 人のプレーヤーの移動回数は 3 回未満であり、20 回を超える場合もあります。AIが間違いから学び、次回同じ間違いをしないように、重要な動き、またはあいまいな動きを保存したいと思います。確実に勝敗が決する手札は保存しなくてもよい。したがって、実際には、ゲームの開始時にまばらな決定木があります。この決定木をデータベースに保存する方法を教えてください。データベースは SQL である必要はありません。この特定の問題に適したデータベースがわかりません。

編集:決定木をメモリに解析するように言わないでください。チェスと同じくらい複雑なゲームを想像してください。

4

10 に答える 10

1

ツリーをトラバースするので、neo4jは私にとって良い解決策のようです。クエリに必要な結合が多数あるため、SQLは適切な選択ではありません。私が質問を理解しているように、あなたはいくつかのグラフをデータベースに保存する方法を求めています、そしてneo4jは明示的にグラフのためのデータベースです。スパースネスの場合、PropertyContainersを使用して、プリミティブまたは文字列の配列をグラフのエッジにアタッチして、移動のシーケンスをエンコードできます（スパースネスとノードのスキップによって、ツリーのエッジが単一ではなく移動のシーケンスであることを意味します）移動しますか？）。

于 2011-08-22T10:41:04.330 に答える
0

メモリ マップド ファイルをストレージとして使用できます。まず、「コンパイラ」を作成します。このコンパイラは、テキスト ファイルを解析し、コンパクトなバイナリ表現に変換します。メイン アプリケーションは、この最適化されたバイナリ ファイルをメモリにマップします。これにより、メモリサイズの制限に関する問題が解決されます

于 2011-08-22T17:24:27.633 に答える
0

チェス エンジンと比較すると、それらはおそらくライブラリを開くことを除いて、メモリから再生されます。チェスは複雑すぎて決定決定木を保存できません。チェス エンジンは、ヒューリスティック評価を潜在的および一時的な将来の位置(移動ではない) に割り当てることによってプレイします。将来の位置は、ある種の制限された深さ検索によって検出され、しばらくの間メモリにキャッシュされる可能性がありますが、検索スペースが大きすぎて格納するには大きすぎて、再計算が可能であるよりもルックアップが高速であるため、多くの場合、単純に各ターンで再計算されます。

于 2011-08-23T00:55:24.747 に答える
0

単純なデータベース テーブルの設計から始めます。

決定: CurrentState BINARY(57) | NewState BINARY(57) | スコアINT

CurrentState と NewState は、ゲーム ステートのシリアル化されたバージョンです。Score は NewState に与えられる重みです (正のスコアは良い動き、負のスコアは悪い動きです) AI はこれらのスコアを適切に更新できます。

Renju は 15x15 ボードを使用します。各位置は黒、白、または空にすることができるため、ボードをシリアル化するには Ceiling( (2bits * 15*15) / 8 ) バイトが必要です。T-SQL では BINARY(57) になる SQL では

あなたの AI は、保存されている現在の動きを次のように選択します...

SELECT NewState FROM Decisions WHERE CurrentState = @SerializedState ORDER BY Score DESC

現在のゲーム状態から保存されているすべての次の動きのリストが、最高スコアから最低スコアの順に表示されます。

検索を容易にし、重複を避けるために、テーブル構造には (CurrentState, NewState) に複合一意インデックス (主キー) があります。

これは最善/最適なソリューションではありませんが、DB の知識が不足しているため、実装が最も簡単で、良いスタートを切ることができると思います。

于 2011-08-22T17:26:03.800 に答える
0

チェッカーを解く AI、チヌークを知っていますか? これは、考えられるすべてのエンドゲームのデータベースをコンパイルすることによって行われます。これはまさにあなたがしていることではありませんが、そこから学ぶかもしれません。

于 2011-08-23T00:58:10.967 に答える
0

これには、チェス エンジンでオープニング ブックを処理する従来の方法を使用します。

  1. 可能なすべての動きを生成する
  2. 移動ごとに:
    1. その動きをする
    2. データベースで結果の位置を調べます
    3. 移動を元に戻す
  3. あなたのデータベースで最高のスコアを持っていた移動を行います

動きを見上げる

チェス エンジンは通常、Zobist ハッシュを介して現在のゲーム状態のハッシュ関数を計算します。これは、ゲーム状態の適切なハッシュ関数を構築する簡単な方法です。

このアプローチの大きな利点は、転置を処理することです。つまり、代替パスを介して同じ状態に到達できる場合、それらの代替パスについて心配する必要はなく、ゲームの状態自体についてのみ心配する必要があります。

チェスエンジンがこれを行う方法

ほとんどのチェス エンジンは、記録されたゲームからコンパイルされた静的なオープニング ブックを使用するため、これらのハッシュをスコアにマップする単純なバイナリ ファイルを使用します。例えば

struct book_entry {
    uint64_t hash
    uint32_t score
}

次に、エントリはハッシュでソートされます。オペレーティング システムのキャッシングのおかげで、ファイルの単純なバイナリ検索で、必要なエントリが非常に迅速に見つかります。

スコアの更新

ただし、エンジンに継続的に学習させたい場合は、より複雑なデータ構造が必要になります。この時点では、通常、自分で行う価値はなく、利用可能なライブラリを使用する必要があります。おそらくLevelDBを使用しますが、キーと値のペアを保存できるものであれば何でも問題ありません (Redis、SQLite、GDBM など)。

スコアの学習

スコアを正確に更新する方法は、ゲームによって異なります。多くのデータが利用可能なゲームでは、移動後に勝ったゲームのパーセンテージを保存するなどの単純なアプローチが機能します。データが少ない場合は、その位置からゲーム ツリーを検索した結果をスコアとして保存できます。Q 学習などの機械学習手法も可能ですが、実際にこれを行うプログラムは知りません。

于 2011-12-17T12:04:07.620 に答える
0

ツリーで処理するデータ構造もその複雑さもはっきりとはわかりません。

しかし、ここにあなたが興味を持っているかもしれないいくつかの考えがあります：

  • 決定木を疎行列にマッピングします。結局のところ、木はグラフです
  • 疎行列のプロパティを利用して、保存/検索戦略を考案します。
于 2011-12-11T18:53:11.613 に答える
0

まず、あなたがやろうとしていることは、ケースベースの推論(CBR)の問題のように聞こえます: http://en.wikipedia.org/wiki/Case-based_reasoning#Prominent_CBR_systemsを参照してください。CBR には意思決定のデータベースがあり、システムは理論上、利用可能な最良の結果を選択します。

したがって、nosql グラフ データベースである neo4j を使用することをお勧めします。http://neo4j.org/

したがって、ゲームを表すために、各位置はグラフ内のノードであり、各ノードにはその位置からの潜在的な動きが含まれている必要があります。AI がより多くの情報を得られるように、ゲームの進行に応じて学習されるスコアリング メトリックを追跡できます。

于 2011-08-21T22:07:03.877 に答える
0

データベースに任意のデータ構造を格納できるため、RavenDBのようなドキュメント データベース (NOSQL) を使用します。

ドキュメントは通常の SQL データベースのようにフラットではなく、ツリーのような階層データを直接格納できます。

{ 
   decision: 'Go forward', 
   childs: [ 
      { decision: 'Go backwards' },
      { 
         decision: 'Stay there',
         childs: [
            { decision: 'Go backwards' }
         ]
      }
   ]
}

ここでは、RavenDB に格納できる JSON ツリーの例を示します。

RavenDB には、階層データを照会する組み込み機能もあります: http://ravendb.net/faq/hierarchies

RavenDB の仕組みの詳細については、ドキュメントを参照してください。

資力：

于 2011-08-22T17:13:41.673 に答える
-1

あなたの質問は、決定木をシリアル形式に変換して、場所に書き込み、後でツリーを再構築するために使用する方法について尋ねていると思います。

toString() 関数 (または同等の関数) を使用して、ツリーの事前順序トラバーサルを使用して、決定木の各ノードに保存されているデータをテキスト記述子に変換してみてください。事前注文トラバーサルとは、最初にノードで toString() 操作を実行し、出力をデータベースまたはファイルに書き込み、次にその子ノードで指定された順序で同じ操作を再帰的に実行するアルゴリズムを実装することを意味します。まばらなツリーを扱っているため、toString() 操作には、サブツリーの存在または非存在に関する情報も含める必要があります。

ツリーの再構築は簡単です。最初に格納された値はルート ノードであり、2 番目は左サブツリーのルート メンバーなどです。各ノードに格納されたシリアル データは、次に入力されたノードがどのサブツリーに属すべきかに関する情報を提供する必要があります。

于 2011-08-07T13:36:26.400 に答える