means-end analysis
Here’s the secret connection between prioritizing your goals and novelty maps: Once you have explicit goals, another thing you can do is reason about them.
You’re playing on Crystallis. Human players somehow realize, without having to think about it, “I’ll need gas, so I should set workers to mine in the direction of a geyser.” How could a bot figure out the same thing? Imagine that you want to be able to play on any map, even a novelty map with strange features.
The bot should already know “I’ll need gas,” so the question is how it can figure out the way to get it. The bot also needs a model of the game, so that it can understand the effects of its actions and plan a sequence of actions to reach its goal. It needs to know that minerals can block movement and that workers can mine out minerals.
Means-end analysis was introduced into AI sometime around 1960 in the famous General Problem Solver program. It says, given a goal, seek means (aka actions) to reduce differences between the current situation and the goal. One way to put means-end analysis to work is in “plan repair,” which means finding workarounds for problems. It’s part of the AI topic of planning. If you like academic papers, here’s a list: Citeseer on plan repair.
Suppose the bot is terran. It already knows a basic plan to get gas: 1. Send an SCV to a geyser. 2. Build a refinery. 3. Transfer gas from the refinery to a command center with SCVs. If bot uses its model of the game to see whether the basic plan works, it will find that the first step fails; the SCV can’t get to the geyser. Can the plan be repaired? Working backward from the goal of being at the geyser, the bot might reason: If I can mine out this mineral block next to the geyser, then I can reach it. Can I mine out that mineral block? No, but these other mineral blocks are next to it, can I mine one of them out? If the bot keeps searching backward (using a means-end heuristic to speed things up: the mineral block closest to the command center is the one that minimizes the difference between the current situation and the goal), it will eventually find a path of mineral blocks to mine out to reach the gas. Problem solved.
The bot might also ask: Can I fly an SCV to the geyser? To fly it by dropship, I would need a dropship, which costs gas; no can do. Or I could float a command center and make an SCV, but there’s no place to land it; no can do. Or the bot might figure out how to push SCVs through the minerals enough times to reach the geyser, which probably is part of best play. If it’s clever enough, it might be able to compute an efficient combination of mining out minerals and pushing SCVs through the last minerals to start getting gas a little earlier.
Plan repair can work to solve many kinds of goals in many kinds of situations. A bot with that skill could play novelty maps at least passably, and could solve planning problems that come up in normal games. Obviously it’s a very complicated skill, and one that bot authors will not be in a hurry to implement. But I think it’s a destination we should aim to reach eventually. And the first step, of course, is to make your bot’s goals explicit.
Next: After the map is mined out.
Comments