4

我正在创建一个类似国际象棋的程序的变体，它需要同时生成和遍历一个非常大的树状结构。每个节点有 10 个 bool、一个 int、8 个 ulong、一个 short[64] 和 2 个 ulong[64]。根节点接收一些初始参数，然后从那里以编程方式（递归）确定有效的子节点。

基本上，当用户和程序轮流从子节点遍历到子节点时，我的程序会不断地增长这棵树。每次“选择”一个新的子节点时，它的父节点和兄弟节点都不再需要并被丢弃。当树（平均）达到大约 60 的深度（从初始根节点开始）时，有效子节点的数量自然会开始减少，直到大约 75 的深度，树解析为一个最终节点，没有更多的孩子。

这背后的逻辑起初看起来相当简单，但我经常遇到 OutOfMemoryException ，这完全扼杀了任何进一步的进展。

以下是每“一代”有效儿童的某些平均值：

Generation    New Nodes
1             1    
2             20
3             4,000
4             30,000
5             2,200,000
6             > 50,000,000

在我的实际程序中，我什至无法完全扩展第五代。当我不保留节点特定数据时（一旦节点的数据被用于确定它自己的子节点，我就会清除它）我可以完全扩展第 5 代，但在第 6 代中途遇到了非常坚固的墙。

理想情况下，我希望我的程序最终达到并在“当前”节点之后维护 8 代节点。我看的越多，这似乎就越不可能。

我厌倦了用 sqlite 数据库运行它，但它不能足够快地生长树。

有谁知道处理非常大的树结构的任何潜在替代方案？

4

2 回答 2

1

您的问题没有一般性的答案。我会假设计算这棵大树以确定您的计算机程序的最佳移动吗？

在这种情况下，定义一系列动作的效用函数可能会对您有所帮助，它可以衡量在游戏中做出这一系列动作的价值。如果目标是达到最高分数或类似的东西，那么该分数是一个很好的效用函数。

有时您无法提出准确的效用函数，在这种情况下，一种常见的方法是对效用进行启发式评估。基本上它是一个近似值，或者是最好的猜测。启发式越好，对手就越好。

您想要进行效用测量的原因是执行修剪。例如，深度优先遍历树几次并计算最小和最大效用。这些值可以帮助您修剪完整的算法，这意味着您可以使用这些边界来确定您的树遍历算法是否可以在完成之前终止。

同样，这完全取决于您的游戏机制以及您如何遍历树，但希望这可以让您朝着正确的方向思考。

于 2012-06-22T20:36:36.973 回答
0

通常，您在构建树时会进行评估，这已经为您提供了边缘权重。使用这些权重来查看哪些路径将评估比其他路径更强的路径并在这些边缘上工作，只要你能看到哪些更有价值。由于您的算法中已经存在第五代的问题，因此您只能选择深入研究权重较高的分支，然后选择其中一个，忽略许多其他分支。只是一个想法......也许你可以在第三代上运行它，选择走哪条路。据我所知，这可能会让您只使用更多可移动的棋子进行移动，因为它们可能会对游戏产生更大的影响，与第五代移动相比，这可能不是最佳解决方案。非常有趣的问题！

您应该调查国际象棋编程：国际象棋编程维基

这里有更多关于引擎的内容：引擎上的国际象棋编程维基

还有一个论坛，讨论不同的方法！

于 2012-06-22T20:53:21.063 回答