Starcraft AI competition
users.soe.ucsc.edu
users.soe.ucsc.edu
Product didn't go anywhere, but the architecture could easily be copied. It would be ridiculously cool to build this into Star Craft. There would be so many more people exposed to the AIs if all the knowledge needed to "program" them was in the game play itself.
Thinking out loud, for a fighting game you have two obvious measurable criteria (your health bar and the health of your opponent) which constitute a 2D coordinate system. Any action you take which is expected to reduce your opponent's health more than your own is going to be a beneficial one (unless it will push you to death, in which case you need to go for attacks that have minimal cost to your own health).
The game state would be the positions of both players on the x-axis and the health bars for both players. If you had jumping and kneeling, you might want to record positions & momentums for both players in x & y.
Now a very simple kind of AI could look for periodic subsequences that could return it to the same position while causing more damage to the opponent than to itself. That is, do some sequence of moves (strike, jump, block, etc.) and then return to the original game state except that both health bars have changed.
Then do this again, as you've "reduced it to a previously solved problem".
This of course would be too simple a thing to do because the opponent's responses would (a) be nonrandom and (b) he would not return to the exact same position. So you would need to build up a statistical database of expected countermoves to each moves (and update that for each new opponent). You would also probably want a similarity function for game states.
I guess overall this shouldn't be too difficult to do if you recorded the game states of many real games between two players, because the game rules don't change over time. Once you've got a few difficult-to-counter loops that cost them more health than they cost you, you can run them over and over again.
I agree with some of it... you'd need to keep track of the the location of each player on the x-axis and y-axis, momentums, etc... Additionally you'd want to keep track of the "visible" actions. For example, if the human hits the soft punch button, you can see the fist cocking before the punch. Similarly for other actions.
This gives you various points in the state space. The way I see doing this is:
1) Make the continuous variables discrete. You need enough granularity to have good responses of course...
2) Use genetic programming to pick reactions in each state. However, the reaction in each state is not a single action but a probability distributions over various actions (move left, move right, jump, punch, kick, etc...).
The randomness is key. I spent some time talking to a guy who plays in tournaments and he said that the absolute worst thing you can do is get into a cycle or become predictable.
Apparently it is possible to script Starcraft using a C++ API.
http://www.broodwarai.com/forums/index.php?showtopic=322 http://code.google.com/p/bwapi/
I've always wanted to get into RTS games but I am just not very good at the mouse--I always get bogged down by failing to click on the right units and issue the right commands at the right times, and I've fond that once you make a few mistakes you usually don't recover, or you are back to square one.
Board games and turn-based games don't share this problem of course, but they aren't quite the adrenaline pumpers either... not worse, just different :-)
Impressive stuff. Others in the video responses below.
All you need to run it is the latest competition code: http://code.google.com/p/marioai/
Is this taboo?
(PS - I'm not flaming them. I was an SC addict about 8 years ago untill WOW came out and everyone seemed to have lost interest.)
Would be awesome if the AIs had a difficulty tweak that allowed them to be used in actual SC games :)