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

发布于 2024-11-28 05:03:25 字数 263 浏览 3 评论 0原文

我长期以来一直在考虑为棋盘游戏制作人工智能，最近我开始收集资源和算法。游戏是非随机的，并且大多数时候，存在 <<一名玩家 3 步，有时超过 20 步。我想存储关键的动作或不明确的动作，以便人工智能从错误中吸取教训，下次不会犯同样的错误。确定获胜或失败的棋步无需存储。所以我实际上有一个用于游戏开始的稀疏决策树。我想知道如何将这个决策树存储在数据库中？数据库不需要是SQL，我不知道哪个数据库适合这个特定问题。

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

清引 2024-12-05 05:03:25

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

回复收藏 0 原文

摇划花蜜的午后 2024-12-05 05:03:25

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

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

因此，为了表示您的游戏，每个位置都是图中的一个节点，并且每个节点应该包含从所述位置出发的潜在移动。您可以跟踪随着游戏进展而学习的评分指标，以便人工智能了解更多信息。

回复收藏 0 原文

杀手六號 2024-12-05 05:03:25

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

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

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

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

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

请查看文档以获取 RavenDB 如何工作的更多信息。

资源：

哪种类型的 NoSQL 数据库最适合存储分层数据？

I would use a document database (NOSQL) like RavenDB because you can store any data structure in the database.

Documents aren't flat like in a normal SQL database and that allows you to store hierarchical data like trees directly:

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

Here you can see an example JSON tree which can be stored in RavenDB.

RavenDB also has a built-in feature to query hierarchical data:
http://ravendb.net/faq/hierarchies

Please look at the documentation to get more information how RavenDB works.

Resources:

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

回复收藏 0 原文

雨夜星沙 2024-12-05 05:03:25

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

回复收藏 0 原文

猫弦 2024-12-05 05:03:25

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

决定：
当前状态二进制(57) |新状态二进制(57) | Score INT

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

连珠，使用 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）上有一个复合唯一索引（主键），以方便搜索并避免重复。

这不是最好/最优化的解决方案，但由于您缺乏数据库知识，我相信它将是最容易实现的，并给您一个良好的开端。

Start with a simple database table design.

Decisions:
CurrentState BINARY(57) | NewState BINARY(57) | Score INT

CurrentState and NewState are a serialized version of the game state. Score is a weight given to the NewState (positive scores are good moves, negative scores are bad moves) your AI can update these scores appropriately.

Renju, uses a 15x15 board, each location can be either black, white or empty so you need Ceiling( (2bits * 15*15) / 8 ) bytes to serialize the board. In SQL that would be a BINARY(57) in T-SQL

Your AI would select the current moves it has stored like...

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

You'll get a list of all the stored next moves from the current game state in order of best score to least score.

Your table structure would have a Composite Unique Index (primary key) on (CurrentState, NewState) to facilitate searching and avoid duplicates.

This isn't the best/most optimal solution, but because of your lack of DB knowledge I beleive it would be the easiest to implement and give you a good start.

回复收藏 0 原文

单身狗的梦 2024-12-05 05:03:25

如果我与国际象棋引擎进行比较，它们是根据记忆进行游戏的，也许除了打开库之外。国际象棋太复杂，无法存储决策树。国际象棋引擎通过对潜在的和暂时的未来位置（而不是移动）分配启发式评估来进行游戏。未来的位置是通过某种有限深度搜索找到的，可能会在内存中缓存一段时间，但通常会在每一轮中重新计算，因为搜索空间太大，无法以比重新计算更快的方式进行存储。

回复收藏 0 原文

不再见 2024-12-05 05:03:25

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

回复收藏 0 原文

很酷不放纵 2024-12-05 05:03:25

我无法清楚地想象您在树中处理的数据结构及其复杂性。

但这里有一些您可能感兴趣的想法：

将决策树映射到稀疏矩阵，树毕竟是图
利用稀疏矩阵属性设计存储/检索策略。

回复收藏 0 原文

转角预定愛 2024-12-05 05:03:25

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

生成所有可能的动作
为每个动作：
1. 采取行动
2. 在数据库中查找结果位置
3. 撤消移动
进行数据库中得分最高的移动

查找移动国际

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

这种方法的一大优点是它可以处理换位，即如果可以通过备用路径到达相同的状态，则您无需担心这些备用路径，只需担心游戏状态本身。

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

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

struct book_entry {
    uint64_t hash
    uint32_t score
}

，然后按哈希对条目进行排序，并且借助操作系统缓存，进行简单的二进制搜索< /a> 通过文件会很快找到需要的条目。

更新分数

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

学习分数

更新分数的具体方式取决于您的游戏。在有大量可用数据的游戏中，一种简单的方法是有效的，例如仅存储导致位置的移动后获胜的游戏百分比；如果数据较少，您可以将从相关位置开始的博弈树搜索结果存储为分数。诸如Q学习之类的机器学习技术也是一种可能性，尽管我不知道一个在实践中真正做到这一点的程序。

I would approach this with the traditional way an opening book is handled in chess engines:

Generate all possible moves
For each move:
1. Make that move
2. Look the resulting position up in your database
3. Undo the move
Make the move that had the highest score in your database

Looking up a move

Chess engines usually compute a hash function of the current game state via Zobrist hashing, which is a simple way to construct a good hash function for gamestates.

The big advantage of this approach is that it takes care of transpositions, that is, if the same state can be reached via alternate paths, you don't need to worry about those alternate paths, only about the game states themselves.

How chess engines do this

Most chess engines use static opening books that are compiled from recorded games and hence use a simple binary file that maps these hashes to a score; e.g.

struct book_entry {
    uint64_t hash
    uint32_t score
}

The entries are then sorted by hash, and thanks to operating system caching, a simple binary search through the file will find the needed entries very quickly.

Updating the scores

However, if you want the engine to learn continously, you will need a more complicated data structure; at this point it is usually not worth doing yourself, and you should use an available library. I would probably use LevelDB, but anything that lets you store key-value pairs is fine (Redis, SQLite, GDBM, etc.)

Learning the scores

How exactly you update the scores depends on your game. In games with a lot of data available, a simple approach such as just storing the percentage of games won after the move that resulted in the position works; if you have less data, you can store the result of a game tree search from the position in question as score. Machine learning techniques such as Q learning are also a possibility, although I do not know of a program that actually does this in practice.

回复收藏 0 原文

终陌 2024-12-05 05:03:25

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

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

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

回复收藏 0 原文

~没有更多了~