1

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

我有一个 2D 网格(每个地图的大小不同,范围从 10X10 到 20X20,必须是正方形),其中每个单元格包含每个单元(10 到 50,具体取决于地图)的概率(0 到 1)在那个地点。

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

在多个指定单元中的任何一个中拥有一个小单元都会获得积分,并且根据占用的相邻单元的数量奖励奖金 - 注意相邻并不一定意味着相邻单元的坐标,并且将根据地图确定。

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

我的意图是让计划系统输出一系列所需的状态/动作。例如,在 (9,4) 处以 43 度角,然后在 (12,4) 处以 12 度角启用小单元。

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

理想情况下,该算法会向前看几步,并考虑诸如特定动作是否使您处于执行下一步动作的好位置之类的事情-位置的这种“优点”将与路径成本相反。

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

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

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

  • 我应该计算每个合理可能的当前状态的重要性,这样我就可以确定哪些信息是重要的。

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

  • 适应国际象棋算法可能是一个好方法。

  • 我不擅长这个,我应该上网问问。

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

  • 如果一个动作有 10% 的机会获得 20 倍于任何其他动作的点数,那么冒险是值得的——除非另一个动作几乎可以保证良好的结束位置并且时间快到了。

  • 我的问题有点冗长。

  • 我觉得到目前为止我一定有更多的想法,但我无法为我的生活思考它们是什么。

  • 最后一点押韵了。

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

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

4

2 回答 2

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)。

蒙特卡洛树搜索有用于构建游戏程序的记录。

于 2014-02-19T05:49:08.280 回答
0

老实说,我认为实现这项工作的最快方法是从简单开始并逐步建立。

我建议你从基本的博弈论开始,尤其是博弈树。设计一个可以玩这种游戏的玩家,向前看固定数量的移动。然后实现 A*(“A 星算法”)以使其更快。阅读启发式方法,在不解决整个未来树的情况下猜测状态的值。

然后尝试你想要的游戏的一个大大简化的版本(例如,从两个团队开始,每个大单位,四个小单位,完美的信息)。从那里你可以一次增加一点复杂性。如果您在任何这些步骤上遇到困难,我将很乐意提供帮助(或至少尝试)。

于 2014-02-19T04:33:27.413 回答