I intend to participate in the StarCraft AI Competition. I figured there are lots of AI buffs here that could toss some pieces of wisdom at me. Shower me with links you deem relevant and recommend books to read.
Generally, what approaches should I explore and what dead ends should I avoid? Essentially, tell me how to discard large portions of porential-starcraft-AI thingspace quickly.
Specifically, the two hardest problems that I see are:
Writing an AI that can learn how to move units efficiently on its own. Either by playing against itself or just searching the game tree. And I’m not just looking for what the best StarCraft players do—I’m searching for the optimum.
The exact rules of the game are not known. By exact I mean Laplace’s Demon exact. It would take me way too long to discover them through experimentation and disassembly of the StarCraft executable. So, I either have to somehow automate this discovery or base my AI on a technique that doesn’t need that.
Pay attention to the timing of your edit/compile/test cycle time. Efforts to get this shorter pay off both in more iterations and in your personal motivation (interacting with a more-responsive system is more rewarding). Definitely try to get it under a minute.
A good dataset is incredibly valuable. When starting to attack a problem—both the whole thing, and subproblems that will arise—build a dataset first. This would be necessary if you are doing any machine learning, but it is still incredibly helpful even if you personally are doing the learning.
Succeed “instantaneously”—and don’t break it. Make getting to “victory”—a complete entry—your first priority and aim to be done with it in a day or a week. Often, there’s temptation to do a lot of “foundational” work before getting something complete working, or a “big refactoring” that will break lots of things for a while. Do something (continuous integration or nightly build-and-test) to make sure that you’re not breaking it.
Great! That competition looks like a lot of fun, and I wish you the best of luck with it.
As for advice, perhaps the best I can give you is to explain the characteristics the winning program will have.
It will make no, or minimal, use of game tree search. It will make no, or minimal, use of machine learning (at best it will do something like tuning a handful of scalar parameters with a support vector machine). It will use pathfinding, but not full pathfinding; corners will be cut to save CPU time. It will not know the rules of the game. Its programmer will probably not know the exact rules either, just an approximation discovered by trial and error. In short, it will not contain very much AI.
One reason for this is that it will not be running on a supercomputer, or even on serious commercial hardware; it will have to run in real time on a dinky beige box PC with no more than a handful of CPU cores and a few gigabytes of RAM. Even more importantly, only a year of calendar time is allowed. That is barely enough time for nontrivial development. It is not really enough time for nontrivial research, let alone research and development.
In short, you have to decide whether your priority is Starcraft or AI. I think it should be the latter, because that’s what has actual value at the end of the day, but it’s a choice you have to make. You just need to understand that the reward from the latter choice will be in long-term utility, not in winning this competition.
That’s disheartening, but do give more evidence. To counter: participants of DARPA’s Grand Challenge had just a year too, and their task was a notch harder. And they did use machine learning and other fun stuff.
Also, I think a modern gaming PC packs a hell of a punch. Especially with the new graphics cards that can run arbitrary code. But good catch—I’ll inquire about the specs of the machines the competition will be held on.
The Grand Challenge teams didn’t go from zero to victory in one year. They also weren’t one-man efforts.
That having been said, and this is a reply to RobinZ also, for more specifics you really want to talk to someone who has written a real-time strategy game AI, or at least worked in the games industry. I recommend doing a search for articles or blog posts written by people with such experience. I also recommend getting hold of some existing game AI code to look at. (You won’t be copying the code, but just to get a feel for how things are done.) Not chess or Go, those use completely different techniques. Real-time strategy games would be ideal, but failing that, first-person shooters or turn-based strategy games—I know there are several of the latter at least available as open source.
Oh, and Johnicholas gives good advice, it’s worth following.
The Grand Challenge teams didn’t go from zero to victory in one year.
Stanford’s team did.
They also weren’t one-man efforts.
Neither is mine.
I do not believe I can learn much from existing RTS AIs because their goal is entertaining the player instead of winning. In fact, I’ve never met an AI that I can’t beat after a few days of practice. They’re all the same: build a base and repeatedly throw groups of units at the enemy’s defensive line until run out of resources, mindlessly following the same predictable route each time. This is true for all of Command & Conquer series, all of Age of Empires series, all of Warcraft series, and StarCraft too. And those are the best RTS games in the world with the biggest budgets and development teams.
Was these games’ development objective to make the best AI they could that would win in all scenarios? I doubt that would be the most fun for human players to play against. Maybe humans wanted a predictable opponent.
In games with many players (where alliances are allowed), you could make the AI’s more likely to ally with each other and to gang up on the human player. This could make an 8-player game nearly impossible. But the goal is not to beat the human. The goal is for the AI to feel real (human), and be fun.
As you point out, the goal in this contest is very different.
Ah, I had assumed they must have been working on the problem before the first one, but their webpage confirms your statement here. I stand corrected!
Neither is mine.
Good, that will help.
I do not believe I can learn much from existing RTS AIs because their goal is entertaining the player instead of winning. In fact, I’ve never met an AI that I can’t beat after a few days of practice. They’re all the same: build a base and repeatedly throw groups of units at the enemy’s defensive line until run out of resources, mindlessly following the same predictable route each time.
Yeah. Personally I never found that very entertaining :-) If you can write one that does better, maybe the industry might sit up and take notice. Best of luck with the project, and let us know how it turns out.
What’s the recommended way to format quoted fragments on this site to distinguish them from one’s own text? I tried copy pasting CannibalSmith’s comment, but that copied as indentation with four spaces, which when I used it, gave a different result.
The Grand Challenge teams didn’t go from zero to victory in one year. They also weren’t one-man efforts.
That having been said, and this is a reply to RobinZ also, for more specifics you really want to talk to someone who has written a real-time strategy game AI, or at least worked in the games industry. One thing I can say is, get hold of some existing game AI code to look at. (You won’t be copying the code, but just to get a feel for how things are done.) Not chess or Go, those use completely different techniques. Real-time strategy games would be ideal, but failing that, first-person shooters or turn-based strategy games—I know there are several of the latter at least available as open source.
Oh, and Johnicholas gives good advice, it’s worth following.
Strictly speaking, this reads a lot like advice to sell nonapples. I’ll grant you that it’s probably mostly true, but more specific advice might be helpful.
You might also look at some of the custom AIs for Total Annihilation and/or Supreme Commander, which are reputed to be quite good.
Ultimately though the winner will probably come down to someone who knows Starcraft well enough to thoroughly script a bot, rather than more advanced AI techniques. It might be easier to use proper AI in the restricted tournaments, though.
I intend to participate in the StarCraft AI Competition. I figured there are lots of AI buffs here that could toss some pieces of wisdom at me. Shower me with links you deem relevant and recommend books to read.
Generally, what approaches should I explore and what dead ends should I avoid? Essentially, tell me how to discard large portions of porential-starcraft-AI thingspace quickly.
Specifically, the two hardest problems that I see are:
Writing an AI that can learn how to move units efficiently on its own. Either by playing against itself or just searching the game tree. And I’m not just looking for what the best StarCraft players do—I’m searching for the optimum.
The exact rules of the game are not known. By exact I mean Laplace’s Demon exact. It would take me way too long to discover them through experimentation and disassembly of the StarCraft executable. So, I either have to somehow automate this discovery or base my AI on a technique that doesn’t need that.
I have some advice.
Pay attention to the timing of your edit/compile/test cycle time. Efforts to get this shorter pay off both in more iterations and in your personal motivation (interacting with a more-responsive system is more rewarding). Definitely try to get it under a minute.
A good dataset is incredibly valuable. When starting to attack a problem—both the whole thing, and subproblems that will arise—build a dataset first. This would be necessary if you are doing any machine learning, but it is still incredibly helpful even if you personally are doing the learning.
Succeed “instantaneously”—and don’t break it. Make getting to “victory”—a complete entry—your first priority and aim to be done with it in a day or a week. Often, there’s temptation to do a lot of “foundational” work before getting something complete working, or a “big refactoring” that will break lots of things for a while. Do something (continuous integration or nightly build-and-test) to make sure that you’re not breaking it.
Great! That competition looks like a lot of fun, and I wish you the best of luck with it.
As for advice, perhaps the best I can give you is to explain the characteristics the winning program will have.
It will make no, or minimal, use of game tree search. It will make no, or minimal, use of machine learning (at best it will do something like tuning a handful of scalar parameters with a support vector machine). It will use pathfinding, but not full pathfinding; corners will be cut to save CPU time. It will not know the rules of the game. Its programmer will probably not know the exact rules either, just an approximation discovered by trial and error. In short, it will not contain very much AI.
One reason for this is that it will not be running on a supercomputer, or even on serious commercial hardware; it will have to run in real time on a dinky beige box PC with no more than a handful of CPU cores and a few gigabytes of RAM. Even more importantly, only a year of calendar time is allowed. That is barely enough time for nontrivial development. It is not really enough time for nontrivial research, let alone research and development.
In short, you have to decide whether your priority is Starcraft or AI. I think it should be the latter, because that’s what has actual value at the end of the day, but it’s a choice you have to make. You just need to understand that the reward from the latter choice will be in long-term utility, not in winning this competition.
That’s disheartening, but do give more evidence. To counter: participants of DARPA’s Grand Challenge had just a year too, and their task was a notch harder. And they did use machine learning and other fun stuff.
Also, I think a modern gaming PC packs a hell of a punch. Especially with the new graphics cards that can run arbitrary code. But good catch—I’ll inquire about the specs of the machines the competition will be held on.
The Grand Challenge teams didn’t go from zero to victory in one year. They also weren’t one-man efforts.
That having been said, and this is a reply to RobinZ also, for more specifics you really want to talk to someone who has written a real-time strategy game AI, or at least worked in the games industry. I recommend doing a search for articles or blog posts written by people with such experience. I also recommend getting hold of some existing game AI code to look at. (You won’t be copying the code, but just to get a feel for how things are done.) Not chess or Go, those use completely different techniques. Real-time strategy games would be ideal, but failing that, first-person shooters or turn-based strategy games—I know there are several of the latter at least available as open source.
Oh, and Johnicholas gives good advice, it’s worth following.
Stanford’s team did.
Neither is mine.
I do not believe I can learn much from existing RTS AIs because their goal is entertaining the player instead of winning. In fact, I’ve never met an AI that I can’t beat after a few days of practice. They’re all the same: build a base and repeatedly throw groups of units at the enemy’s defensive line until run out of resources, mindlessly following the same predictable route each time. This is true for all of Command & Conquer series, all of Age of Empires series, all of Warcraft series, and StarCraft too. And those are the best RTS games in the world with the biggest budgets and development teams.
But I will search around.
Was these games’ development objective to make the best AI they could that would win in all scenarios? I doubt that would be the most fun for human players to play against. Maybe humans wanted a predictable opponent.
They want a fun opponent.
In games with many players (where alliances are allowed), you could make the AI’s more likely to ally with each other and to gang up on the human player. This could make an 8-player game nearly impossible. But the goal is not to beat the human. The goal is for the AI to feel real (human), and be fun.
As you point out, the goal in this contest is very different.
Ah, I had assumed they must have been working on the problem before the first one, but their webpage confirms your statement here. I stand corrected!
Good, that will help.
Yeah. Personally I never found that very entertaining :-) If you can write one that does better, maybe the industry might sit up and take notice. Best of luck with the project, and let us know how it turns out.
Please fix this post’s formatting. I beg you.
What’s the recommended way to format quoted fragments on this site to distinguish them from one’s own text? I tried copy pasting CannibalSmith’s comment, but that copied as indentation with four spaces, which when I used it, gave a different result.
Click on the reply button and then click the help link in the bottom right corner. It explains how to properly format your comments.
Okay, thanks, fixed.
The Grand Challenge teams didn’t go from zero to victory in one year. They also weren’t one-man efforts.
That having been said, and this is a reply to RobinZ also, for more specifics you really want to talk to someone who has written a real-time strategy game AI, or at least worked in the games industry. One thing I can say is, get hold of some existing game AI code to look at. (You won’t be copying the code, but just to get a feel for how things are done.) Not chess or Go, those use completely different techniques. Real-time strategy games would be ideal, but failing that, first-person shooters or turn-based strategy games—I know there are several of the latter at least available as open source.
Oh, and Johnicholas gives good advice, it’s worth following.
Strictly speaking, this reads a lot like advice to sell nonapples. I’ll grant you that it’s probably mostly true, but more specific advice might be helpful.
There’s some discussion and early examples here: http://www.teamliquid.net/forum/viewmessage.php?topic_id=105570
You might also look at some of the custom AIs for Total Annihilation and/or Supreme Commander, which are reputed to be quite good.
Ultimately though the winner will probably come down to someone who knows Starcraft well enough to thoroughly script a bot, rather than more advanced AI techniques. It might be easier to use proper AI in the restricted tournaments, though.