8

想为棋盘游戏做一个AI已经很久了，最近开始收集资源和算法。游戏是非随机的，大多数时候，一个玩家有< 3 步，有时，有> 20 步。我想存储关键动作或模棱两可的动作，以便人工智能从错误中吸取教训，下次不会犯同样的错误。无需存储肯定会赢或输的动作。所以我实际上有一个用于游戏开始的稀疏决策树。我想知道我应该如何将这个决策树存储在数据库中？数据库不需要是 SQL，我不知道哪个数据库适合这个特定的问题。

编辑：请不要告诉我将决策树解析到内存中，想象一下游戏就像国际象棋一样复杂。

4

10 回答 10

1

当您将遍历树时，neo4j 对我来说似乎是一个很好的解决方案。SQL 不是一个好的选择，因为查询需要很多连接。据我了解，您正在寻求一种将一些图形存储在数据库中的方法，而 neo4j 是一个专门用于图形的数据库。对于稀疏性，您可以使用 PropertyContainers 将基元数组或字符串附加到图形的边缘以对移动序列进行编码（我说得对，通过稀疏和跳过节点意味着您的树边是移动序列而不是单个动作？）。

于 2011-08-22T10:41:04.330 回答
0

我会用在国际象棋引擎中处理开局的传统方式来解决这个问题：

  1. 生成所有可能的动作
  2. 对于每一步：
    1. 做出那个动作
    2. 在数据库中查找结果位置
    3. 撤消移动
  3. 采取在您的数据库中得分最高的行动

抬头看一个动作

国际象棋引擎通常通过Zobrist 哈希计算当前游戏状态的哈希函数，这是为游戏状态构建良好哈希函数的简单方法。

这种方法的最大优点是它处理了转置，也就是说，如果可以通过备用路径达到相同的状态，您无需担心那些备用路径，只需担心游戏状态本身。

国际象棋引擎如何做到这一点

大多数国际象棋引擎使用从记录的游戏中编译的静态开局书，因此使用将这些哈希映射到分数的简单二进制文件；例如

struct book_entry {
    uint64_t hash
    uint32_t score
}

然后这些条目按哈希排序，并且由于操作系统缓存，对文件进行简单的二进制搜索将很快找到所需的条目。

更新分数

但是，如果您希望引擎不断学习，则需要更复杂的数据结构；此时通常不值得自己做，您应该使用可用的库。我可能会使用LevelDB，但是任何可以让您存储键值对的东西都可以（Redis、SQLite、GDBM 等）

学习分数

您如何准确地更新分数取决于您的游戏。在有大量可用数据的游戏中，一种简单的方法（例如仅存储导致位置的移动后获胜的游戏百分比）是有效的；如果您的数据较少，您可以将游戏树搜索的结果从相关位置存储为分数。机器学习技术（例如Q 学习）也是一种可能性，尽管我不知道在实践中实际执行此操作的程序。

于 2011-12-17T12:04:07.620 回答
0

如果我与国际象棋引擎进行比较，那些是凭记忆玩的，也许除了打开图书馆。国际象棋太复杂，无法存储决定性的决策树。国际象棋引擎通过将启发式评估分配给潜在的和暂时的未来位置（而不是移动）来进行游戏。未来的位置是通过某种有限的深度搜索找到的，可能会在内存中缓存一段时间，但由于搜索空间太大而无法以比重新计算更快的查找方式存储，因此通常每轮都会重新计算。

于 2011-08-23T00:55:24.747 回答
0

你知道奇努克——解决跳棋的人工智能吗？它通过编译每个可能的残局的数据库来做到这一点。虽然这不是您正在做的事情，但您可以从中学习。

于 2011-08-23T00:58:10.967 回答
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 回答
0

您可以使用内存映射文件作为存储。首先，创建“编译器”。该编译器将解析文本文件并将其转换为紧凑的二进制表示。主应用程序会将这个二进制优化文件映射到内存中。这将解决您的内存大小限制问题

于 2011-08-22T17:24:27.633 回答
0

从一个简单的数据库表设计开始。

决策：CurrentState BINARY(57) | NewState BINARY(57) | 分数 INT

CurrentState 和 NewState 是游戏状态的序列化版本。分数是赋予 NewState 的权重（正分数是好动作，负分数是坏动作）你的 AI 可以适当地更新这些分数。

Renju，使用 15x15 板，每个位置可以是黑色、白色或空的，因此您需要 Ceiling( (2bits * 15*15) / 8 ) 字节来序列化板。在 SQL 中，这将是 T-SQL 中的 BINARY(57)

你的 AI 会选择它存储的当前动作......

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

您将获得从当前游戏状态中存储的所有下一步移动的列表，按从最高分到最低分的顺序排列。

您的表结构将在 (CurrentState, NewState) 上有一个复合唯一索引（主键），以方便搜索并避免重复。

这不是最佳/最佳解决方案，但由于您缺乏数据库知识，我相信这将是最容易实施并为您提供良好开端的方法。

于 2011-08-22T17:26:03.800 回答
-1

我假设您的问题是询问如何将决策树转换为可以写入某个位置并稍后用于重建树的串行格式。

尝试使用树的前序遍历，使用 toString() 函数（或其等效函数）将存储在决策树每个节点的数据转换为文本描述符。通过前序遍历，我的意思是实现一种算法，首先在节点上执行 toString() 操作，然后将输出写入数据库或文件，然后以指定的顺序递归地在其子节点上执行相同的操作。因为您正在处理稀疏树，所以您的 toString() 操作还应该包括有关子树存在或不存在的信息。

重构树很简单——第一个存储的值是根节点，第二个是左子树的根成员，以此类推。为每个节点存储的串行数据应提供有关下一个输入节点应属于哪个子树的信息。

于 2011-08-07T13:36:26.400 回答