10 December 2008

Mathematics of Netrek

The other day I wrote a review of Netrek, a very simple (and the first!) online multiplayer game where the best dynamics of the game far exceed to simplicity of the game itself. (There is an important lesson here – a game does not have to be complex in order to be good). It had not occurred to me to consider the math that relates to this game, but I’ve spent much of my Thanksgiving vacation thinking about it. This post won’t be a complete analysis be any means, but it will serve to introduce a number of topics I hope to discuss in greater detail somewhere down the line. There are three basic aspects of Netrek that I want to describe: Player versus Player, Team versus Team, and Resource Allocation.

Player versus Player: One-on-one, ship-to-ship combat (dogfighting) is perhaps the most basic component of Netrek. Players combat each other with phasers and torpedoes, trying to inflict enough damage to destroy the other ship first. There is an aspect of Point Objective Games here, with the added complexity that shields regenerate and ships repair. This complexity aside, it comes down to a contest of skill between players, rather like a Chess match. Chess has a ratings system, Elo Scoring, which is used to describe the past performance of a player, and (ideally) has some usefulness in predicting the winner of a match between two players who have never met before. Elo scoring uses a scale where a 200 point difference between player ratings is interpreted as a 75% chance that the player with the higher rating will win (assuming the ratings accurately represent player skill). Chess is considered to be a very “deep” game, with a very great range or many levels of skill between the worst and best players, and this deepness can be measured (in part) by the range in scores. Beginning Chess players might have a rating of 800-1000 points, while the World Championship Chess players have ratings of 2500 or more (Go has even greater depth by this measure). Netrek also has considerable depth on player skill, and it would be interesting if this sort of ratings system could be implemented to measure it. Mathematics based measurements of player skill in games is one of those topics I intend to discuss at greater length in future posts.

Team versus Team: This is where the game of Netrek really shines. And if we could measure the skill of a “team” with a sort of Elo score in the same way we might measure individual players’ skill, I’m pretty sure the depth of Netrek would approach that of Chess. Tournament mode (T-mode) play in Netrek has an underlying mathematical structure that is actually fairly simple. I want to deconstruct the game and point out where the basic mathematics applies to the team games.
Suppose we have the following simple game: 20 Coins are laid out on a table with 10 heads and 10 tails. [edit: here the coins respresent planets, and each side wants to capture all the planets.] Two players, one represented by heads and the other by tails, each turn both players choose one coin and flip it, with the object of making all the coins either heads or tails (with 50/50 chance). Obviously the heads-player will select any coin showing tails and flip it, trying to get it to come up heads, and the tails player will do the opposite. This game is essential a discrete random walk, and with every turn (one flip for each player) there is a 25% chance a player will gain a coin, 25% chance they will lose a coin, and a 50% chance that things stay the same. This is in concept very close to a completely random T-mode Netrek game. (This might also be stated as a Markov chain.).

A purely random game like this could go on for quite some time (it might even be infinite), but suppose there were some element of skill involved so that one player (lets say heads) is a little bit more likely to get the desired result than the other. So now maybe each turn there is a 35% chance the heads-player will gain one coin, a 20% chance the tails-player will lose one coin, and a 45% chance that things stay the same [edit: both win, or both lose.] Out of every 20 turns we would expect that heads would gain 7 coins (35% of 20) while losing 4 (20% of 20) for a net gain of 3 coins. We should expect the heads player will win in 67 turns, on average.

Netrek takes this same mathematical structure and adds a lot to it (players of varying skill, a variety of ships and planets, etc.). I wonder if it is possible to measure the “team playing” skill of players in the same way as Elo scoring might be used to measure the individual dogfighting skills of players? This would be rather complicated, and likely impractical, but it is interesting to think about.

Resource Allocation: This is the final aspect I want to write about today, and the part that leads to the wonderful complexity of team play in Netrek (It will also be the least mathematical discussion). Resources in this game are not equal; The team with more planets has greater potential to gather armies and try to take planets. More planets than players mean that is it not possible to defend every planet equally. Players are not equally skilled, but have varying levels of ability at individual and team play. Finally, controlling a greater number of planets increases the distance the leading team must travel to front-line-combat, and players are out of position for a longer period of time (though Starbases help).

This last part has an effect not seen in most games; the closer one team is to winning (in an otherwise balanced game) the harder it is to successfully take more planets, because the losing side can respond to defend remaining planets much more quickly – and it tends to make the game self-balancing. I am not a very good Netrek player (I confess to being a twink), and I have never participated in a real “clue” game involving 16 really good players, but my understanding is that in these games an outright victory is rare; most games are given a set time limit where the team in control of the most planets at the end of time is declared the winner. This is entirely consistent with Netrek being a self-balancing game.

One common complaint I recall players making is about how hard it is to actually win a T-mode game. There are many reasons for this, certainly more than I have discussed, but I would propose the following: In a really balanced game with equally skilled players on each side, it may be nearly impossible to actually win, either by Genocide (all planets) or Timer (all but three planets for ~20 minutes). Therefore, most wins probably occur in unbalanced games.

[There is an alternate version of this post, co-authored by Zach Uram, Netrek player extraordinaire, that goes deeper in the game history and mechanics. Give that a read too, and check out Zach's blog at http://www.fidei.org/2011/01/mathematics-of-netrek.html.
Post a Comment