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.
Post a Comment