我应该如何在数据库中存储稀疏决策树(移动列表)？

Question

很长一段时间以来，我一直在考虑为棋盘游戏制作一个AI，最近我开始收集资源和算法。这个游戏是非随机的，大多数时候，一个玩家有<3步，有时>20步。我想存储关键的动作，或模糊的动作，以便AI从错误中学习，下次不会再犯同样的错误。肯定会赢或输的走法不需要存储。所以我实际上在游戏开始时有一个稀疏的决策树。我想知道应该如何将此决策树存储在数据库中？数据库不需要是SQL，我不知道哪个数据库适合这个特定的问题。

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

Answer 1

因为您将遍历这棵树，所以对我来说，neo4j似乎是一个很好的解决方案。SQL不是一个好的选择，因为查询需要大量的连接。据我所知，您正在询问一种在数据库中存储某些图形的方法，而neo4j是一个专门用于图形的数据库。对于稀疏性，您可以使用PropertyContainers将基元数组或字符串数组附加到图的边以编码移动序列(我说的稀疏性和跳过节点是指您的树边是移动序列而不是单个移动吗？)。

Answer 2

首先，您尝试做的事情听起来像是一个基于案例的推理( case based Reasoning)问题，参见：http://en.wikipedia.org/wiki/Case-based_reasoning#Prominent_CBR_systems。CBR将有一个决策数据库，理论上您的系统将选择可用的最佳结果。

因此，我建议使用neo4j，这是一个nosql图形数据库。http://neo4j.org/

因此，为了表示游戏，每个位置都是图中的一个节点，并且每个节点都应该包含从该位置开始的潜在移动。您可以跟踪随着游戏进展而学习的评分指标，以便AI更了解情况。

Answer 3

我会使用像RavenDB这样的文档数据库(NOSQL)，因为您可以在数据库中存储任何数据结构。

文档不像普通SQL数据库那样是扁平化的，它允许您直接存储像树一样的分层数据：

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

在这里您可以看到一个示例JSON树，它可以存储在RavenDB中。

RavenDB还有一个用于查询分层数据的内置功能：http://ravendb.net/faq/hierarchies

请查看documentation以获取有关RavenDB工作原理的更多信息。

资源：

• What type of NoSQL database is best suited to store hierarchical data?