游戏树的C++实现

Question

我将以C++结构来代表国际象棋游戏。我认为，最好的选择将是一个树形结构（因为在每个深处我们有几个可能的动作）。

这是一个很好的方法吗？

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

如何有效地将这种数据存储在文件中？有没有办法确保整个树结构将存储在内存的相同部分，这将允许使用mmap函数？

Answer 1

要将数据存储在同一部分内存中，您可能希望为您使用的std::vector<TreeElement *>提供一个Allocator对象，并从您的块中分配该对象。

为了能够序列化它，而不是存储实际的指针，你可能会考虑在块中存储偏移量。然后，当您读取数据时，您可以将块起始地址添加到每个偏移量以将其重新转换为地址。

根据您使用的操作系统/编译器，可能已经有一些支持。例如，微软的编译器支持__based指针，这几乎就是我所描述的：一个基地址，并且基于该地址的每个指针实际上只是一个偏移量，而不是一个完整的指针。提及mmap表示可能不直接提供给您，但是它可能是您正在使用的编译器/操作系统具有类似的内容。否则，您可能必须自己完成这项工作（例如，使用based_pointer课程）。

真正的问题是你为什么试图序列化移动树。在一个典型的情况下，您最好只保存当前的棋盘位置（或者等同于移动历史记录），并根据需要重新生成移动树。这足够小，它很容易储存。

Answer 2

我认为使用std :: vector并不是创建树的最佳方式，单链表的样式树构造可能更简单也是最好的。