21 December 2008

Convergence of Spheres, Science and Gaming

No, not trigonometry. In this case Mark CC, writer of Good Math, Bad Math has a very good post on Fitness Landscapes, Evolution, and Smuggling Information. Now I am very intentionally keeping political comments on topics such as Intelligent Design out of this blog (I've got another blog for such things), but in this case I see considerable overlap in the application of Evolutionary algorithms for solving "best move" problems in a game. I realize that most games probably are not so complex as genetics/biology/evolution, but as a solution to the problem it is still relevant. Consider the problem of deciding how to move units in a game of Battletech (though many games would do):
GENCON 2007 Solaris Melee Challenge Battletech game math fitness landscapeFor each hex where a player might move a Battlemech, the player will typically consider how good that hex is from the standpoint of attacking the other player, and how bad it might be from the viewpoint of the other player counter-attacking. The player will evaluate many moves, and generally choose one that is most-beneficial and least-harmful. If we wanted to get analytical about it, we might even assign a number to each hex representing the value of that particular move (really we would need a number for each hex, facing, choice of targets, and maybe more if there are multiple ways to accomplish the same move, but the added complexity doesn't contribute anything here, so I'll leave it out).

fitness landscape mathIf you can picture the number in each hex as a height, making the tallest hex on the map the best move, then we have a representation of the game (the current move) as a sort of fitness landscape. This "landscape" probably looks very different from the Battletech game map, and I think of it as an abstract representation (possibly in many dimensions) of the choices to be made in the game. Basically your best move is always to move towards the highest point in this landscape.
In a simple scenario where each player has one Battlemech it is actually not too hard to picture how such a landscape might look. However, when the scenario is more complex and each side has multiple 'Mechs to move this landscape can get very complicated indeed, and the choice of movement for one unit affects the landscape for all the others. If we want to get really deep, we might think about the entire game as a sort of landscape instead of just a single move.

This representation of a game as a landscape is the "converence" I was getting at in the post title, where a method (or at least the representation) from science has meaning for a game. I've never worked with genetic algorithms myself, but it seems like they might be very well suited to solving "best move" problems in games too. More importantly though, this gave me an opportunity to introduce the concept of a game landscape. Thinking about games in this way is probably an unusual concept for most gamers, but it is incredibly useful to be able to think about a game with the sort of mathematical representation that this allows.

5 comments:

Anonymous said...

Holy Cow, my head is spinning! Interesting post. I would HATE to be tasked to program such an algorithm. Luckily us humans can intuitively "throw out" the obvious low worth moves, or rather, look especially close at the high worth moves (where are the closest woods I can get into? Is there any partial cover nearby?).

Cheers,
Brian

Dan Eastwood said...

Actually, I think it would be pretty cool to tinker with the algorithm, and it's probably no harder than programing the game in the first place. Of course, that isn't exactly easy!

You are absolutely right about human ability identify high worth moves. In fact given the number of potential moves to choose from it is absolutely amazing. I intend to put some numbers on that problem, but I've got a few other topics I need to touch on before I can get to that. Stay tuned. :-)

mrs.missalaineus said...

your blog rocks! although i should qualify my opinion by mentioning that ring theory was my favorite class! just for fun once i tried to build a simulation of scrabble to try to relate the probability of drawing the q with the probability of winning the game. nothing ever came out of this other then me being a pretty good scrabbler. it's a shame more people dont see that math is in everything!

miss alaineus

Dan Eastwood said...

Wow! My hit count has more than doubled since this morning. Looks like I've been selected for today's Blogs of Note.

Egg? Nerd?? Moi??? Could be ... :-)

Miss Alaineus: Creating such a simulation is a great way to learn all about a game. More power to you! Ring theory though, is probably a bit out of my reach (I had to look it up on Wikipedia). Do you think there is a tie-in with games?

kenstepp said...

Wow. A lot of extra time. Its interesting though.
Ken Stepp