Search This Blog

Wednesday, February 13, 2008

& Artificial Intelligence Class

So, the spring semester has begun. In fact, the spring semester is about 22% over already. It looks like I'm going to have to do term paper and/or project in each of my four classes - advanced game programming, graphics programming, artificial intelligence, and software engineering. This post deals specifically with the prospect of the AI term project. On the first day of class, I'd already come up with two abstract ideas to do (ideas for topics, but not specific projects), and two concrete ones, of varying sizes. I'll mention some about each of them. All of them have basic requirements of at least practical use, smartass value, or fun coding them (some have more than one of these).

The most practical project would be something related to E Terra. This was one of the general ideas that I didn't have a specific project in mind. The E Terra macro-AI (e.g. computer players) is going to be an absolute bitch to write, given the fundamental differences between E Terra and other strategy games. In terms of search space, it's like comparing Go to Checkers - there are simply too many possibilities to consider all of them, given the broad control of the race E Terra permits. Long term plans need to be developed, and then modified in reaction to actions of other players. Much more attention must be paid to what the enemy is doing, because the time it takes to counter something novel another player does is much longer than in traditional real-time strategy games; there's no bouncing back after the reaver drop, so to speak.

However, while the macro-AI is by far the most difficult, there are lots of micro-AIs that need to be written, as well - small (and relatively easy) self-contained tasks that form the building blocks of play. While these are more manageable, the question remains as to whether there's a single micro-AI that is complex enough to be used as a term project. Some specific micro-AIs that will be required:
- Pathfinding. Units must be able to find the most desirable path from one place to another, based on the knowledge of what's in between those two points.
- Threat assessment. A unit or a group of units has just discovered a group of enemy units. Can it overpower the enemy group? Can it outrun the group? Should it attack the group? Should it run away to safety (e.g. its nest, where presumably many other units will be)? Can it/should it try to lure the enemy group to a stronger group of allies and then fight?
- Combat. Selection of special abilities to use and when.
- Idling. Should the unit eat some food while it's busy doing nothing? Wander around randomly? Go to sleep?

Next is something related to linguistics, a member of the 'fun' category. Plenty of things to choose from, though specific ideas that are manageable aren't readily apparent. Unfortunately, it's unlikely that I'd be able to do something with practical use alone, in an undergraduate course, in the time permitted.

Next is something I'm somewhat attracted to of non-negligible practical value as well as significant smartass value: a simple file format cracker. A program where you give it several different examples of some file format, and it determines the file format structure as best it can. Obviously there would be significant limits to what any such AI could accomplish without true intelligence; e.g. it might be able to tell you the data types of values as well as what they seem to be (flags, file offsets, sizes, counts, "random" data, etc.), but it wouldn't be able to tell you the meaning of most values; similarly, it would have absolutely no way to crack encrypted or compressed structures (though, for that matter, even a skilled reverse-engineer wouldn't be able to do that, either, if they only had a hex editor).

This would be based on my assessment of my own thought processes while reverse-engineering file formats (especially the Mega Man Anniversary Edition and Guild Wars archive formats, which I reverse-engineered using nothing but a hex editor). Most of the stuff is pretty basic: looking for telltale clues about the location and format of fields, determining the stride of arrays, and then using statistical analysis and heuristics to guess what individual fields are.

Finally, something with extreme smartass value, which I think would also be highly amusing to develop: a dating/relationship simulator. While only the most extreme of nerds play such games outside Japan (and, in fact, most people outside Japan have never even heard of them), this genre of video game is spectacularly popular in Japan (possibly the most popular). Some examples of anime that are based on dating sim games (as far as I know): Clannad (currently airing), ef ~ A Tale of Memories (download), and Kanon (download).

I've considered writing a story made for a dating sim before, for the reason that I bet I could do irreparable harm to the genre. Not to mention the fact that it's been done so many times that it provides a real challenge for a writer (along with the school comedy genre of anime, which I'm also considering trying my hand at). Of course such a project here would focus on the AI portion - the simulation of emotions and thought processes of love interests - rather than any type of specific storyline.

1 comment:

Anonymous said...

I was always interested in E Terra. Games that have even approached the audacity of what you're trying such as Populous or turn-based strategy (4X) games have always gotten rave reviews for being able to capture at least some part of human improvisation.

It's also pretty fun to fight an AI that can outthink you. I have a few suggestions for the specific micro-AI issues you mentioned:

- Pathfinding: This one isn't too much of a pain, I think. There are probably free tutorials on how to do this now although looking at the Rise of Nations/Rise of Legends games as a superb example.

- Threat Asessment: Probably the easiest way would be to assign an arbitrary value to each group of soldiers and let them figure it out if they meet. However, you'd also have to hand a platoon of warriors more options than fight/flight such as a wedge attack, flanking move, luring into the underbrush (especially if you're having archers), or actually signaling for help.

- Combat: I suggest having special "trainer" units, which could be any number of religious or cultural leaders in a village, teach soldiers in a specific ability. It would also increase the times that a soldier would use that special ability such as quickmarch, cutting down trees to build a stockade, or just learning how to forage (which determined whether an army lived or died in classical history).

- Idling: Ordered a unit to look for things to build, attack, or eat by default is always good. If you're actually going to be using reproduction as a factor, then they'd be looking for someone to well, have sex with.

It always bothered me that units would just magically walk out of a building in a town. Also, have them say funny things when idle.

Have you also given thought to using existing game engines to make an alpha of E Terra before making one from scratch?

And finally, no, the last thing America needs is dating games. (Between that and American Idol, we'd never leave the house.)