c++ - 实时确定概率表示的 2D 网格上的最佳得分移动

Question

我将其发布到 StackOverflow、cstheory.stackexchange.com 和 math.stackexchange.com，因为我不确定它最适合哪里。我希望没关系。

我有一个二维网格(大小因 map 而异，从 10X10 到 20X20，一定是正方形)，其中每个单元格包含每个单元(10 到 50，具体取决于 map )的概率(0 到 1)在那个位置。

有 2 种主要类型的单位，大单位的行为由您希望能帮助我的算法控制，还有小单位只能移动或改变其( bool )状态在大单位的帮助下。所有单位都属于团队，但任何大单位都可以移动任何小单位。比赛根据较小单位的位置和状态计分。每个单元都知道自己的坐标。

如果在多个指定单元格中的任何一个单元格中有一个小单位，就会获得积分，而奖金会根据占用的相邻单元格的数量来奖励 - 注意相邻并不一定意味着相邻单元格坐标，并且将根据 map 确定。

我已经有一个路径系统，所以这不是问题，计算移动的时间成本也不是问题，尽管出于性能原因应该至少调用它。

我的意图是让规划系统输出一系列所需的状态/ Action 。例如，位于 43 度角的 (9,4)，然后位于 12 度角的 (12,4)，并启用那里的小单元。

我正在尝试为大约 5 个竞争主要单位中的每一个确定最佳移动，以在时间用完时优化他们团队的最终位置。这些单元具有填充概率位置的模拟传感器，因此收集信息是一个有效的步骤。

理想情况下，该算法会向前看几步，并考虑诸如某个特定 Action 是否使您处于执行下一步的良好位置之类的事情 - 这种位置的“优势”只是路径的倒数成本。

性能在这里相当重要，我可能愿意用解决方案质量来换取显着的性能提升。

到目前为止，这是我的想法:

• 最完整的解决方案是详尽搜索，但性能排除了这一点。

• 我应该计算每个合理可能的当前状态的重要性，以便确定需要找出哪些信息很重要。

• 如果可能的话，现代 PC 上平均每个单元的运行时间应该 <= 25 毫秒 - 不是一成不变的 - 这是 C++，所以它相当快。

• 采用国际象棋算法可能是一个不错的方法。

• 我不会这个，我应该去网上问问。

• 最好的方法几乎肯定是估算。

• 如果一个 Action 有 10% 的机会获得比其他 Action 高 20 倍的分数，那么冒险是值得的 - 除非另一个 Action 几乎可以保证良好的完成位置并且时间快用完了。

• 我的问题有点冗长。

• 我觉得到目前为止我一定有更多的想法，但我想不出它们是什么。

• 最后一点押韵。

• 如果你还在看这篇文章，那么我可能愿意嫁给你。

虽然如果有人为此提供完整的解决方案会很棒，但我绝对愿意接受我能得到的任何帮助/提示，​​并且会接受让我走得最远的答案，无论有多远.我对算法而不是代码感兴趣，我可以自己处理这些代码，因为我现在是个大女孩了。

Answer 1

您似乎对较大的状态空间和规则存在问题，这些规则 - 至少乍一看 - 并不是特别简单。我已经看到了两种声称的方法，这两种方法都涉及在时间上重复模拟前向 - 蒙特卡洛树搜索 (http://en.wikipedia.org/wiki/Monte-Carlo_tree_search) 和近似动态规划 (http://adp.princeton.edu/Papers/Powell-NRLWhat%20you%20should%20know%20about%20approximate%20dynamic%20programming.pdf)。

蒙特卡洛树搜索在构建游戏程序方面有着良好的记录。