Hacker News Reader

Comment by StavrosK | Hacker News Reader

> I can't quite understand if you're saying GA's are neural networks, or just that both of them are overused.

I was saying that both are overused.

> one of the big problems is that the heuristics for a heuristic algorithm must be designed by with human insights

By "heuristics" I don't strictly mean "rule-based", but you can do a good job in reducing the search space by a large amount if you program in some common sense that will discard obviously bad moves.

It would be surprising if the devs did understand all the interactions, as it would mean that the search space is trivial. SC2 is not that much different from chess, and, to my knowledge, the best chess-playing AIs don't use genetics. They get much further with trees and precalculated start- and endgame moves.

View on HN

Indeed. Though the crucial difference is, that chess is a game of complete information, while StarCraft hides your enemy. It's much harder to do tree search without complete information.

As a comparison, look at the recent progress made in computer Go that employs Monte Carlo simulations. (And Genetic Algorithms are closer to Monte Carlo than to tree searches.)

I believe it's only harder when you want to optimise for the outcome (winning), since it's hard to know what your opponent will do if you can't see them. However, if you optimise for total offensive/defensive power, I think you can do quite well with trees!

Not only trees but also linear or integer programming approaches. (That's where my theoretical background lies, by the way.)

Chess has a much smaller board, turn-based play, and no unit unit production or races, so it's a bad comparison.

> By "heuristics" I don't strictly mean "rule-based", but you can do a good job in reducing the search space by a large amount if you program in some common sense that will discard obviously bad moves.

I believe that the fitness function used for evaluating build orders does this. It is very difficult to accurately evaluate how good a specific strategy is at a specific point in time, especially when you have imperfect information about your enemy. The code used to decide which build orders survive almost certainly used heuristics.

Yes, but that's the fitness function you want to maximise (i.e. the end result you will get with each "individual"). I'm saying that you might want to use heuristics in maximising that, rather than a GA.

This AI isn't intended to play the game however; by analogy with chess, this is intended to determine the best opening to use, when you have no knowledge of your opponent's moves. Hence min-max trees make no sense (since there are no "turns"), and we can't use precalculated moves, since those are what we're trying to figure out.

Reply on news.ycombinator.com