问题描述
我设计一个实时策略战争游戏,其中的AI将负责在大六角图控制大量的单位(可能超过1000个)。
I'm designing a realtime strategy wargame where the AI will be responsible for controlling a large number of units (possibly 1000+) on a large hexagonal map.
一个单元有许多行动要点,可花费在移动,攻击敌方单位和各类专项行动(例如建立新的单位)。例如,5行动点坦克可以在射击范围内的敌人花3运动,然后2。不同的单位有不同的动作等不同的成本。
A unit has a number of action points which can be expended on movement, attacking enemy units or various special actions (e.g. building new units). For example, a tank with 5 action points could spend 3 on movement then 2 in firing on an enemy within range. Different units have different costs for different actions etc.
一些其他注意事项:
- 人工智能的输出是一个命令到任何给定的单元
- 动作点被分配在一个时间段的开始,但也可以在时间周期内的任何花费(这是为了允许实时多人游戏)。因此,什么也不做,保存后的行动要点是一个潜在的有效策略(例如一个炮塔不能动等待敌人来射击范围内)
- 在该游戏更新实时,但AI可以在任何时候获得的游戏状态一致的快照(感谢游戏状态是Clojure的持久数据结构之一)
- 在我不期待最优的行为,只是一些并不明显的愚蠢,并提供合理的乐趣/挑战对战
你有什么可以推荐的具体算法/办法,将允许效率和合理的智能行为之间的适当平衡条款?
What can you recommend in terms of specific algorithms/approaches that would allow for the right balance between efficiency and reasonably intelligent behaviour?
推荐答案
首先,你的目标应该是使你的游戏回合制在一定程度上为AI(即你能以某种方式模拟它回合制,即使它可能不完全转基于在RTS您可以打破时间离散的间隔成圈。)其次,你应该确定的AI应该多少信息工作与。也就是说,如果AI被允许欺骗和了解它对手的每一个动作(从而使得有更强的),或者如果它应该知道更少或更多。第三,你应该定义一个国家的成本函数。这个想法是,较高的性价比是指一个糟糕的状态,为计算机在
First you should aim to make your game turn based at some level for the AI (i.e. you can somehow model it turn based even if it may not be entirely turn based, in RTS you may be able to break discrete intervals of time into turns.) Second, you should determine how much information the AI should work with. That is, if the AI is allowed to cheat and know every move of its opponent (thereby making it stronger) or if it should know less or more. Third, you should define a cost function of a state. The idea being that a higher cost means a worse state for the computer to be in.
的事情是,成本函数将由究竟你定义状态是受到很大的影响。在该州的信息越多,你的连接code更好的平衡你的爱将,但更困难这将是它执行,因为这将不得不寻找成倍更多的附加状态变量您包括(以详尽搜索。)
The thing is, the cost function will be greatly influenced by what exactly you define the state to be. The more information you encode in the state the better balanced your AI will be but the more difficult it will be for it to perform, as it will have to search exponentially more for every additional state variable you include (in an exhaustive search.)
如果你提供了一个状态的定义和成本函数您的问题转变为人工智能一个普遍的问题,可以与您所选择的任何算法加以解决。
If you provide a definition of a state and a cost function your problem transforms to a general problem in AI that can be tackled with any algorithm of your choice.
下面是什么,我认为会很好地总结:
Here is a summary of what I think would work well:
-
进化算法可以工作得很好,如果你把足够的精力,但他们将增加了一层复杂性,这将创造空间之间的错误可能出错的其他东西。他们还需要适应度函数等的调整极端的数额,我没有太多的经验与这些工作,但如果他们都像神经网络(我相信他们是因为这两个都是启发灵感来自生物学模型)任何你会很快发现他们是善变的,并从一致为止。最重要的是,我怀疑他们补充了我描述3选项任何好处。
Evolutionary algorithms may work well if you put enough effort into them, but they will add a layer of complexity that will create room for bugs amongst other things that can go wrong. They will also require extreme amounts of tweaking of the fitness function etc. I don't have much experience working with these but if they are anything like neural networks (which I believe they are since both are heuristics inspired by biological models) you will quickly find they are fickle and far from consistent. Most importantly, I doubt they add any benefits over the option I describe in 3.
通过成本函数和国家规定,将在技术上有可能为你申请梯度下降(在假设状态函数微分和状态变量的定义域是连续的),但是这可能会产生劣结果,因为梯度下降最大的弱点就是陷入局部极小。举一个例子,这种方法将是易于像总是尽快攻击敌人,因为没有消灭它们的非零机会。很明显,这可能不是所期望的行为的游戏,但是,梯度下降是一个贪婪的方法,不知道更好。
With the cost function and state defined it would technically be possible for you to apply gradient decent (with the assumption that the state function is differentiable and the domain of the state variables are continuous) however this would probably yield inferior results, since the biggest weakness of gradient descent is getting stuck in local minima. To give an example, this method would be prone to something like attacking the enemy always as soon as possible because there is a non-zero chance of annihilating them. Clearly, this may not be desirable behaviour for a game, however, gradient decent is a greedy method and doesn't know better.
这个选择是我最推荐的最高之一:模拟退火。模拟退火会(恕我直言)有1的所有优点,而不会增加复杂性,同时为更强大的比2.在本质SA仅仅是一个随机游走之间的状态。因此,除了成本和状态,你必须定义一个方法来状态之间任意转换。 SA也是不容易停留在局部极小,同时产生了很好的效果相当一致。与SA所需的唯一调整将是冷却的时间表 - 这决定SA将如何快速收敛。 SA的最大优势,我觉得是它的概念很简单,产生更好的结果凭经验大多数其他的方法我都试过了。在联盟的相关信息,可以发现这里一长串通用实施的底部。
This option would be my most highest recommended one: simulated annealing. Simulated annealing would (IMHO) have all the benefits of 1. without the added complexity while being much more robust than 2. In essence SA is just a random walk amongst the states. So in addition to the cost and states you will have to define a way to randomly transition between states. SA is also not prone to be stuck in local minima, while producing very good results quite consistently. The only tweaking required with SA would be the cooling schedule--which decides how fast SA will converge. The greatest advantage of SA I find is that it is conceptually simple and produces superior results empirically to most other methods I have tried. Information on SA can be found here with a long list of generic implementations at the bottom.
不管你到底选择什么样的方法,它的将是非常重要的下降打破你的问题,到州和成本函数正如我刚才所说。作为一个经验法则我将开始与20-50状态变量作为状态搜索空间是指数在这些变量的数量。
Regardless of what method you choose in the end, its going to be very important to break your problem down into states and a cost function as I said earlier. As a rule of thumb I would start with 20-50 state variables as your state search space is exponential in the number of these variables.
这篇关于算法的实时策略战争游戏的AI的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!