c++ - 为我的 AI 算法设置内存限制？

Question

我正在研究俄罗斯方 block AI 实现。它是一个自己玩游戏的 GUI 应用程序。用户可以操纵一些影响人工智能决策的参数。基本算法如下:

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

这在搜索深度 4 之前一直运行良好。之后我开始遇到内存问题。可能的游戏状态数可以从 9 到 34。因此，第 4 级搜索的最坏情况是 34^4 个游戏状态。 Windows XP 似乎无法处理 5 级搜索(它在 2+ GB 时挂起)。

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

我考虑使用内存池并使用“placement new”在池的内存段上创建我的对象。然而，游戏网格是作为 STL vector 实现的。因此，为了在池中分配它，我需要实现一个自定义分配器。

这似乎是一个相当大的挑战，也许我忽略了一个更简单的解决方案。因此，我想听听您对如何最好地处理这个问题的见解。

boost 或其他库可以为我提供其中的一些功能吗？ (我已经找到了 Poco 的 MemoryPool。)是否有任何好的在线资源可以帮助我开始？

仅供引用:这是 source code和一个 sample binary for Windows .

Answer 1

您可以创建一个内存池等，但这实际上不会使计算游戏状态实例变得更容易或更困难。您确实需要确保您不会在决策树中超过一定数量的事件状态，无论是否有池。 Boost 确实有一个:http://www.boost.org/doc/libs/1_44_0/libs/pool/doc/index.html

听起来你并没有真正对树进行任何修剪，这会让你更深入。评估每个 future 的游戏状态并放弃不太可能发展成任何有用的东西，不要浪费时间在那个分支上。