我打算编写代表人工智能的程序,用于玩玩家的棋盘游戏.我希望将每个玩过的游戏保留在前缀树中,以搜索类似的游戏.但我担心这棵树会变得太大而无法留在记忆中.那么存储它的最佳方式是什么.并且能够快速搜索它.我不认为将其写入文件是一个很好的解决方案.可能是DB的一位王者？
解决方法
您正在寻找的是嵌入式数据库,其中大部分都是用C语言编写的,但也有一些是C#包装器.我推荐
Berkeley DB for .NET(这是
Oracle’s Berkeley DB左右的包装).
我建议你为每个前缀树生成一个唯一的哈希值,其中生成的哈希值将具有正确表示类似前缀树的位置：换句话说,两个相似前缀树的哈希值应该彼此非常接近.你所指的游戏被称为Tic-Tac-Toe,因此散列类似的Tic-Tac-Toe游戏应该很容易,这里有一些参考(我没有真正读过它们,我只是快速搜索一下“哈希Tic-Tac-Toe”和那些结果)：
> I think this might be java example
> TicTacToe strategic reduction
> http://cg.scs.carleton.ca/~luc/1997notes/topic14/
然后将散列存储在Berkeley DB中,前缀树存储在aux文件中,或者如果需要,也可以将其存储在值中.由于Berkeley DB存储键值对,您可以将哈希设置为键,将值设置为任何值(即前缀树或包含前缀树的aux文件的路径).然后你要做的就是查找类似的哈希值并从aux文件中检索相应的树.
Berkeley DB按顺序存储类似的键,因此您可以依赖于它不会移动键并破坏哈希的局部性这一事实.由于本地不会被破坏,您可以进行额外的优化并检索大量的键值对,并减少查找次数并寻求您在磁盘上执行的操作.
