什么模型最适合实时策略游戏的优化？
最近有一篇文章讨论了如何使用遗传算法来优化《星际争霸 II》中的“构建顺序”。
http://lbrandy. com/blog/2010/11/using-genic-algorithms-to-find-starcraft-2-build-orders/
星际争霸比赛的初始状态是预先确定的且恒定的。与国际象棋一样，比赛早期阶段做出的决定会对棋手在比赛中后期的表现产生长期影响。因此，各种开放可能性或“建造订单”正在接受严格的研究和审查。在上述文章发表之前，计算机辅助构建订单创建可能不像最近那么受欢迎。
我的问题是...遗传算法真的是优化构建顺序建模的最佳方法吗？
构建顺序是一系列操作。有些操作有先决条件，例如“在创建建筑 C 之前需要建筑 B，但您可以随时拥有建筑 A”。所以染色体可能看起来像 AABAC。
我想知道遗传算法是否真的是解决这个问题的最佳方法。尽管我对这个领域不太熟悉，但我很难将基因的概念硬塞到一个由一系列动作组成的数据结构中。这些不是可以像头和脚一样混合搭配的独立选择。那么繁殖和杂交之类的东西有什么价值呢？
我认为无论国际象棋人工智能使用什么都会更合适，因为任何给定时间的选择数组在某种程度上都可以被视为树状。
An article has been making the rounds lately discussing the use of genetic algorithms to optimize "build orders" in StarCraft II.
http://lbrandy.com/blog/2010/11/using-genetic-algorithms-to-find-starcraft-2-build-orders/
The initial state of a StarCraft match is pre-determined and constant. And like chess, decisions made in this early stage of the match have long-standing consequences to a player's ability to perform in the mid and late game. So the various opening possibilities or "build orders" are under heavy study and scrutiny. Until the circulation of the above article, computer-assisted build order creation probably wasn't as popularity as it has been recently.
My question is... Is a genetic algorithm really the best way to model optimizing build orders?
A build order is a sequence of actions. Some actions have prerequisites like, "You need building B before you can create building C, but you can have building A at any time." So a chromosome may look like AABAC.
I'm wondering if a genetic algorithm really is the best way to tackle this problem. Although I'm not too familiar with the field, I'm having a difficult time shoe-horning the concept of genes into a data structure that is a sequence of actions. These aren't independent choices that can be mixed and matched like a head and a foot. So what value is there to things like reproduction and crossing?
I'm thinking whatever chess AIs use would be more appropriate since the array of choices at any given time could be viewed as tree-like in a way.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
嗯，这是一个非常好的问题。也许星际争霸中的前几个动作确实可以以几乎任何顺序执行，因为与敌人的接触并不像国际象棋中那样立即，因此记住前几个动作的顺序并不像国际象棋那样重要。就是要知道前面几个动作中包含了哪些动作。但这个链接似乎暗示着其他情况，这意味着“基因”确实并不那么适合交换，除非我在编码中遗漏了一些狡猾的东西。
总的来说，看看您提供的链接，我认为遗传算法对于这种情况来说是一个糟糕的选择，它可以在某些部分进行精确的数学建模，而搜索树可以在其他部分扩展。它们很可能比对可能性空间进行详尽的搜索更好，但也可能不是——特别是考虑到存在多个群体，而较贫穷的群体只是浪费处理时间。
然而，我所说的“糟糕的选择”是指相对于更合适的方法来说，它的效率低下；这并不是说它仍然不能在一秒之内产生 98% 的最佳结果。在这种情况下，计算机的强力是有用的，正确地建模搜索空间通常比使用最有效的算法更重要。
Hmm, that's a very good question. Perhaps the first few moves in Starcraft can indeed be performed in pretty much any order, since contact with the enemy is not as immediate as it can be in Chess, and therefore it is not as important to remember the order of the first few moves as it is to know which of the many moves are included in those first few. But the link seems to imply otherwise, which means the 'genes' are indeed not all that amenable to being swapped around, unless there's something cunning in the encoding that I'm missing.
On the whole, and looking at the link you supplied, I'd say that genetic algorithms are a poor choice for this situation, which could be accurately mathematically modelled in some parts and the search tree expanded out in others. They may well be better than an exhaustive search of the possibility space, but may not be - especially given that there are multiple populations and poorer ones are just wasting processing time.
However, what I mean by "a poor choice" is that it is inefficient relative to a more appropriate approach; that's not to say that it couldn't still produce 98% optimal results in under a second or whatever. In situations such as this where the brute force of the computer is useful, it is usually more important that you have modelled the search space correctly than to have used the most effective algorithm.
正如 TaslemGuy 指出的那样，遗传算法不能保证是最优的，尽管它们通常会给出良好的结果。
为了获得最佳结果，您必须搜索所有可能的操作组合，直到找到通过树状表示的最佳路径。然而，在《星际争霸》中做到这一点很困难，因为实现目标有很多不同的途径。在国际象棋中，您将棋子从 e2 移动到 e4，然后对手移动。在《星际争霸》中，您可以在瞬间移动一个单位 x 或 x+1 或 x+10 或...
国际象棋引擎可以查看棋盘的许多不同方面（例如，它有多少棋子以及对手有多少棋子） ，指导其搜索。如果它知道大多数可用的操作比其他操作更糟糕，那么它可以忽略它们。
对于构建订单创建者来说，只有时间才是真正重要的。是建造另一架无人机来更快地获取矿物更好，还是立即启动产卵池更快？不像国际象棋那样简单。
此类决策很早就发生了，因此您必须搜索每种替代方案才能得出结论，然后才能做出更好的决定，这将需要很长时间。
如果我自己编写一个构建顺序优化器，我可能会尝试制定一个启发式方法来估计当前状态的好坏程度（接近目标状态），就像国际象棋引擎所做的那样：
这试图保持分数平局完成百分比以及星际争霸常识（保持较低的资源，建造无人机，不要建造超出你需要的供应）。当然，变量 a 到 f 需要调整。
在您获得可以在一定程度上估计情况价值的启发式方法之后，我将使用 最佳优先search 或IDDFS 来搜索可能性树。
编辑：
我最近发现了一篇论文，它实际上描述了星际争霸中的构建顺序优化，甚至是实时的。作者使用深度优先搜索和分支定界 和基于技术树估计达到目标所需的最小工作量的启发式方法（例如小狗需要产卵池）以及收集所需矿物质所需的时间。
As TaslemGuy pointed out, Genetic Algorithms aren't guaranteed to be optimal, even though they usually give good results.
To get optimal results you would have to search through every possible combination of actions until you find the optimal path through the tree-like representation. However, doing this for StarCraft is difficult, since there are so many different paths to reach a goal. In chess you move a pawn from e2 to e4 and then the opponent moves. In StarCraft you can move a unit at instant x or x+1 or x+10 or ...
A chess engine can look at many different aspects of the board (e.g. how many pieces does it have and how many does the opponent have), to guide it's search. It can ignore most of the actions available if it knows that they are strictly worse than others.
For a build-order creator only time really matters. Is it better to build another drone to get minerals faster, or is it faster to start that spawning pool right away? Not as straightforward as with chess.
These kinds of decisions happen pretty early on, so you will have to search each alternative to conclusion before you can decide on the better one, which will take a long time.
If I were to write a build-order optimizer myself, I would probably try to formulate a heuristic that estimates how good (close the to the goal state) the current state is, just as chess engines do:
This tries to keep the score tied to the completion percentage as well as StarCraft common knowledge (keep your ressources low, build drones, don't build more supply than you need). The variables a to f would need tweaking, of course.
After you've got a heuristic that can somewhat estimate the worth of a situation, I would use Best-first search or maybe IDDFS to search through the tree of possibilities.
Edit:
I recently found a paper that actually describes build order optimization in StarCraft, in real time even. The authors use depth-first search with branch and bound and heuristics that estimate the minimum amount of effort required to reach the goal based on the tech tree (e.g. zerglings need a spawning pool) and the time needed to gather the required minerals.
遗传算法可以是，有时也可以不是，最优或非最优解决方案。基于遗传算法的复杂性，有多少变异，组合的形式，以及遗传算法的染色体如何解释。
因此，根据人工智能的实施方式，遗传算法可能是最好的。
您正在寻找一种实现遗传算法的单一方法，而忘记了遗传编程、数学的使用、高阶函数等。遗传算法可以非常复杂，并且通过使用巧妙的组合系统进行杂交，非常智能。< br>
例如，神经网络经常通过遗传算法进行优化。
查找“基因编程”。它很相似，但使用树结构而不是字符行，这允许更复杂的交互，从而更好地繁殖。对于更复杂的事情，它们通常效果更好。
Genetic Algorithm can be, or can sometimes not be, the optimal or non-optimal solution. Based on the complexity of the Genetic Algorithm, how much mutation there is, the forms of combinations, and how the chromosomes of the genetic algorithm is interpreted.
So, depending on how your AI is implemented, Genetic Algorithms can be the best.
You are looking at a SINGLE way to implement genetic algorithms, while forgetting about genetic programming, the use of math, higher-order functions, etc. Genetic algorithms can be EXTREMELY sophisticated, and by using clever combining systems for crossbreeding, extremely intelligent.
For instance, neural networks are optimized by genetic algorithms quite often.
Look up "Genetic Programming." It's similar, but uses tree-structures instead of lines of characters, which allows for more complex interactions that breed better. For more complex stuff, they typically work out better.
已经有一些研究使用分层强化学习来构建分层的操作顺序，从而有效地最大化奖励。我还没有找到太多实现这一想法的代码，但有几篇论文描述了基于 MAXQ 的算法，这些算法已用于明确处理实时策略游戏领域，例如 此 和
There's been some research done using hierarchical reinforcement learning to build a layered ordering of actions that efficiently maximizes a reward. I haven't found much code implementing the idea, but there are a few papers describing MAXQ-based algorithms that have been used to explicitly tackle real-time strategy game domains, such as this and this.
这种遗传算法仅优化游戏的一个非常特定部分的策略：游戏的前几个构建动作的顺序。它还有一个非常具体的目标：尽快拥有尽可能多的蟑螂。
影响这个系统的唯一方面似乎是（我不是星际争霸玩家）：
建筑物
这是一个相对有限、定义相对明确的问题，具有较大的搜索空间。因此，它非常适合遗传算法（以及相当多的其他优化算法）。完整的基因是一组特定的构建顺序，以第七条蟑螂结束。据我了解，你可以“玩”这个特定的基因，看看它完成的速度有多快，这样你就有了一个非常清晰的适应性测试。
您还对构建顺序有一些很好的限制，因此您可以比随机地更智能地组合不同的基因。
以这种方式使用的遗传算法是一个非常好的工具，可以为星际争霸游戏的第一阶段找到更优化的构建顺序。由于其随机性，它也擅长找到令人惊讶的策略，这可能是作者的另一个目标。
要使用遗传算法作为 RTS 游戏中的算法，您必须找到一种方法来编码对情况的反应，而不仅仅是简单的旧构建顺序。这还涉及正确识别情况，这本身就是一项艰巨的任务。然后你必须让这些基因玩数千场星际争霸游戏，相互对抗，（可能）与人类对抗，选择并组合胜利者（或长期失败者）。这也是遗传算法的一个很好的应用，但是在您进入遗传算法部分之前，它涉及解决相当多的非常困难的问题。
This Genetic algorithm only optimizes the strategy for one very specific part of the game: The order of the first few build actions of the game. And it has a very specific goal as well: To have as many roaches as quickly as possible.
The only aspects influencing this system seem to be (I'm no starcraft player):
buildings
This is a relatively limited, relatively well defined problem with a large search space. As such it is very well suited for genetic algorithms (and quite a few other optimization algorithm at that). A full gene is a specific set of build orders that ends in the 7th roach. From what I understand you can just "play" this specific gene to see how fast it finishes, so you have a very clear fitness test.
You also have a few nice constraints on the build order, so you can combine different genes slightly smarter than just randomly.
A genetic algorithm used in this way is a very good tool to find a more optimal build order for the first stage of a game of starcraft. Due to its random nature it is also good at finding a surprising strategy, which might have been an additional goal of the author.
To use a genetic algorithm as the algorithm in an RTS game you'd have to find a way to encode reactions to situations rather than just plain old build orders. This also involves correctly identifying situations which can be a difficult task in itself. Then you'd have to let these genes play thousands of games of starcraft, against each other and (possibly) against humans, selecting and combining winners (or longer-lasting losers). This is also a good application of genetic algorithms, but it involves solving quite a few very hard problems before you even get to the genetic algorithm part.