对我的人工智能算法设置内存限制？

Question

我正在致力于一个俄罗斯方块AI的实现。它是一个自己玩游戏的GUI应用程序。用户可以操纵一些参数来影响AI所做的决定。基本算法如下：

• 启动一个新线程并克隆当前游戏状态，以避免过度锁定。
• 生成所有未来游戏状态的列表。它们成为当前游戏状态的子节点。
• 为每个子节点生成它的未来游戏状态。
• 继续递归地执行此操作，直到达到预定义的深度为止。
• 一旦达到所请求的深度，找到最佳的结束节点并递归地找到它的父节点，直到您有了第一级子节点。
• 删除不在子节点和结束节点之间的路径上的所有子节点。
• 此路径现在是预先计算的移动列表。
• 主游戏执行预先计算的移动列表(带有一些花哨的动画)。

在搜索深度4之前，这是很好的工作方式。之后，我开始出现内存问题。可能的游戏状态数可以从9个增加到34个。因此，4级搜索的最坏情况是34^4游戏状态。Windows似乎无法处理5级搜索(挂在2+ GB上)。

因此，如果我想使用更深入的搜索，我需要使用一种策略，我删除没有希望的分支，并继续那些将导致一个好成绩的分支。但这使得估计最大可接受的搜索深度变得更加困难。因此，我认为我最好指定一个内存限制，而不是深度限制。

我考虑使用一个内存池，并使用“放置新”来在池的内存段上创建我的对象。然而，游戏网格被实现为一个STL向量。因此，为了在池上分配它，我需要实现一个自定义分配器。

这似乎是一个相当大的挑战，也许我忽略了一个更简单的解决方案。所以我想听听你对如何最好地处理这件事的见解。

能为我提供一些这些设施吗？(我已经找到了波科的MemoryPool。)有什么好的网络资源可以帮我走吗？

这是源代码和Windows二进制示例。

Answer 1

您可以创建一个内存池，等等，但这并不能使计算游戏状态实例变得更容易或更困难。您确实需要确保在您的决策树中，无论是否有一个池，您都不需要遍历一定数量的活动状态。Boost也有一个：0/libs/pool/doc/index.html

听起来你并没有对这棵树做任何修剪，这会让你变得更深。评估每一个未来的游戏状态，放弃那些不太可能发展成任何有用的状态，不要浪费你的时间去做这个分支。

Answer 2

尽管缺乏上下文，你在做什么样的搜索问题？深度第一，宽度第一，A*？我的建议是：

使用信号量限制一次完成的处理量，然后在对处理进行评估后释放它。我不推荐包含信号量的特定库，因为线程不是内置到C++中的，但是请查看框架的文档。