ゲームツリーのC++実装

Question

私はチェスゲームをC++構造体として表現しようとしています。私は、最良の選択肢はツリー構造（各深度にはいくつかの可能な動きがあるため）であると思います。

これは良いアプローチですか？

struct TreeElement{ 
    SomeMoveType move; 
    TreeElement *parent; 
    std::vector<TreeElement*> children; 
}; 

効率的にこのようなデータをファイルに保存しますか？ツリー構造全体がメモリの同じ部分に格納され、mmap関数を使用できるようにする方法がありますか？

Answer 1

メモリの同じセクションにデータを格納するには、使用するstd::vector<TreeElement *>のAllocatorオブジェクトを指定し、そのブロックから割り当てる必要があります。

実際のポインタを格納する代わりに、シリアル化できるようにするには、ブロックにオフセットを格納することを検討してください。次にデータを読み込むと、ブロックの開始アドレスを各オフセットに追加してアドレスに戻すことができます。

使用しているOS /コンパイラによっては、すでにサポートされているものがあります。たとえば、マイクロソフトのコンパイラは__basedポインタをサポートしていますが、それは私が記述したものです。ベースアドレスと、そのアドレスに基づく各ポインタは実際にはオフセットであり、フルポインタではありません。 mmapの記載は、それがおそらくあなたに直接利用できないことを示していますが、が可能です。あなたが使用しているコンパイラ/ OSには類似したものがあります。それ以外の場合は、自分でジョブを実行する必要があります（例：based_pointerクラス）。

実際の質問は、なぜあなたが移動ツリーをまったくシリアル化しようとしているかということです。典型的なケースでは、現在のボードの位置（または同等のことに、移動履歴）を保存し、必要なときに移動ツリーを再生成する方が良いでしょう。十分に小さいので、保存するのが簡単です。

Answer 2

私はstd :: vectorを使うことはツリーを作成する最善の方法ではないと思います。単独でリンクされたリストスタイルツリーの構築はおそらく単純で最善です。