7 ms·

Show HN: AI Planning for Starcraft

78 points by primaryobjects 12y ago

noiv 12y ago
Interesting. Although going over an abstract representation harms the performance in a RTS game. I finally chose Nau's HTN planner to plan entire villages in a few milliseconds. The core in JavaScript fits on one screen page: https://github.com/agentx-cgn/Hannibal/blob/master/source/simulation/ai/hannibal/htn-planner.js#L112 https://github.com/agentx-cgn/Hannibal/blob/master/source/si...
pests 12y ago
Note: This is not only related to Starcraft but planning problems in general. Starcraft is just one of the examples.
ljk 12y ago
usually players build multiple SCVs to speed things up. Is there a reason why there's only one mining?
- ponderingH 12y ago
  I suspect it has to do with the definition of "Optimal" in this case. It has likely been defined as "least number of steps". It would be cool to see how it would play if the goal was changed to "shortest amount of time".
- ericdykstra 12y ago
  A few people have made genetic algorithm programs to calculate optimal (in terms of speed) build orders given certain conditions. Here's one I have used: https://code.google.com/p/evolutionchamber/ https://code.google.com/p/evolutionchamber/ A genetic algorithm, of course, is much different than using AI to solve the problem, but I think it's an interesting project nonetheless.
ggreer 12y ago
These planning algorithms are pretty cool, and they got me thinking about AIs in RTS tournaments. RTS games seem like a perfect fit for human/computer pairs. Automation would completely change micro. The computer reacts instantly, has perfect accuracy, and never gets tired or distracted. It would enable tactics that no human could perform unaided. The human would have fewer distractions while making strategic decisions that current RTS AIs are terrible at: Where to build, where to mass units, defense placement, etc. I looked around a little, but didn't find any StarCraft-equivalent to Advanced Chess[1]. If such a thing doesn't exist, it's a shame. The combination of better strategy and ludicrous APM would completely change gameplay. 1. http://en.wikipedia.org/wiki/Advanced_Chess http://en.wikipedia.org/wiki/Advanced_Chess
- tgb 12y ago
  I agree. Meanwhile, screeps.com is a fairly interesting AI-only RTS. (At the moment it's more of a tower defense kind of game with more to come.)
- Iv 12y ago
  Yep, I keep thinking that RTS game are the one field where AI assistants would be incredibly valuable. But talking about AIs in RTS tournament, you may be interested in a tournament of AIs playing starcraft: http://sscaitournament.com/ http://sscaitournament.com/ They have a live channel with often pretty cool fights.
- lnanek2 12y ago
  Well, there was no GUI involved, but such man machine hybrid wars did often occur in MUDs, particularly ones with player killing and guilds. You would often have a set of alts controlled by scripts doing automated tasks like crafting iron from ingredients and selling it in town whereas meanwhile in combat you would have the mud client automatically drink health potions when low on health, auto attack when an enemy player walked in, etc.. I think World of Warcraft had a similar bot getting popular before it was banned.
  - endgame 12y ago
    The Iron Realms MUDs have a combat system that's so complex and demanding on reaction time that you can buy (with real world money, from other players) full curing systems that track how fast you can cure things, how close you are to inflicting limb breaks on your opponent and all sorts of other stuff.
Iv 12y ago
Don't get me wrong, I find it very cool that people try to popularize STRIPS planning among programmers and that automated planning gets more known. However, please don't say that you can "solve" Starcraft this way. To get a decent starcraft AI you will need more than the ability to make plans to build battlecruisers: you will need the ability to choose the best plan for the recognized situation, to take decisions under uncertainty and to make compromises between objectives.
- fit2rule 12y ago
  You can plan every single thing. Whats your real problem?
  - rjaco31 12y ago
    You can plan buildings, training & simple orders (go harvest crystal). You definitely cannot plan all the micro that any fight will involve.
  - Iv 12y ago
    For chess to be called "solved" you would need to have a winning strategy for every winnable position. The same is true for Starcraft. What this person provides is a (very non-optimal) algorithm to build anything within the tech tree of starcraft, but building is just one part of the game, and the only easily pannifiable one.
erikb 12y ago
I'm very happy that another guy got interested in AI and is backing it up with some code. Keep up the good work! But maybe join a free web AI course if you are really interested in this topic. A* on a decision graph is really an old thing for AI. Sorry to disappoint. It's one of the things you do for homework if you visit an AI course.

noiv 12y ago

Interesting. Although going over an abstract representation harms the performance in a RTS game. I finally chose Nau's HTN planner to plan entire villages in a few milliseconds. The core in JavaScript fits on one screen page: https://github.com/agentx-cgn/Hannibal/blob/master/source/simulation/ai/hannibal/htn-planner.js#L112 https://github.com/agentx-cgn/Hannibal/blob/master/source/si...

pests 12y ago

Note: This is not only related to Starcraft but planning problems in general. Starcraft is just one of the examples.

ljk 12y ago

usually players build multiple SCVs to speed things up. Is there a reason why there's only one mining?

ponderingH 12y ago
I suspect it has to do with the definition of "Optimal" in this case. It has likely been defined as "least number of steps". It would be cool to see how it would play if the goal was changed to "shortest amount of time".
ericdykstra 12y ago
A few people have made genetic algorithm programs to calculate optimal (in terms of speed) build orders given certain conditions. Here's one I have used: https://code.google.com/p/evolutionchamber/ https://code.google.com/p/evolutionchamber/ A genetic algorithm, of course, is much different than using AI to solve the problem, but I think it's an interesting project nonetheless.

ggreer 12y ago

These planning algorithms are pretty cool, and they got me thinking about AIs in RTS tournaments. RTS games seem like a perfect fit for human/computer pairs. Automation would completely change micro. The computer reacts instantly, has perfect accuracy, and never gets tired or distracted. It would enable tactics that no human could perform unaided. The human would have fewer distractions while making strategic decisions that current RTS AIs are terrible at: Where to build, where to mass units, defense placement, etc. I looked around a little, but didn't find any StarCraft-equivalent to Advanced Chess[1]. If such a thing doesn't exist, it's a shame. The combination of better strategy and ludicrous APM would completely change gameplay. 1. http://en.wikipedia.org/wiki/Advanced_Chess http://en.wikipedia.org/wiki/Advanced_Chess

tgb 12y ago
I agree. Meanwhile, screeps.com is a fairly interesting AI-only RTS. (At the moment it's more of a tower defense kind of game with more to come.)
Iv 12y ago
Yep, I keep thinking that RTS game are the one field where AI assistants would be incredibly valuable. But talking about AIs in RTS tournament, you may be interested in a tournament of AIs playing starcraft: http://sscaitournament.com/ http://sscaitournament.com/ They have a live channel with often pretty cool fights.
lnanek2 12y ago
Well, there was no GUI involved, but such man machine hybrid wars did often occur in MUDs, particularly ones with player killing and guilds. You would often have a set of alts controlled by scripts doing automated tasks like crafting iron from ingredients and selling it in town whereas meanwhile in combat you would have the mud client automatically drink health potions when low on health, auto attack when an enemy player walked in, etc.. I think World of Warcraft had a similar bot getting popular before it was banned.
- endgame 12y ago
  The Iron Realms MUDs have a combat system that's so complex and demanding on reaction time that you can buy (with real world money, from other players) full curing systems that track how fast you can cure things, how close you are to inflicting limb breaks on your opponent and all sorts of other stuff.

Iv 12y ago

Don't get me wrong, I find it very cool that people try to popularize STRIPS planning among programmers and that automated planning gets more known. However, please don't say that you can "solve" Starcraft this way. To get a decent starcraft AI you will need more than the ability to make plans to build battlecruisers: you will need the ability to choose the best plan for the recognized situation, to take decisions under uncertainty and to make compromises between objectives.

fit2rule 12y ago
You can plan every single thing. Whats your real problem?
- rjaco31 12y ago
  You can plan buildings, training & simple orders (go harvest crystal). You definitely cannot plan all the micro that any fight will involve.
- Iv 12y ago
  For chess to be called "solved" you would need to have a winning strategy for every winnable position. The same is true for Starcraft. What this person provides is a (very non-optimal) algorithm to build anything within the tech tree of starcraft, but building is just one part of the game, and the only easily pannifiable one.

erikb 12y ago

I'm very happy that another guy got interested in AI and is backing it up with some code. Keep up the good work! But maybe join a free web AI course if you are really interested in this topic. A* on a decision graph is really an old thing for AI. Sorry to disappoint. It's one of the things you do for homework if you visit an AI course.