Please note that I don't update this web site anymore. You can visit my new personal blog at www.williamwilling.com.

Game Theory

Tuesday, February 8, 2005

One of the books I'm currently reading and enjoying is Game Theory - A Non-Technical Introduction by Morton D. Davis. Although game theory was originally used in modeling economic behaviour, I find it to be a great source of inspiration while designing games. For example, after reading the first chapter, I came up with a simple two-player game and which I will share with you. But first, I'd like to present you with a summary of the first chapter, so that you have an idea what all this is about.

Two-person, zero-sum games

A two-person game is a game with two players. I thought I should tell you that, otherwise you might get confused later on. :-)

A zero-sum game is a game where one man's gain is the other man's loss, and vice-versa. For example, the game of poker is zero-sum. The winning player wins exactly as much money as the losing players lose (combined). In other words, the total amount of money that is distributed between the players stays the same throughout the game. The game of Monopoly is not zero-sum (unless you count the bank as a player), since the total amount of money in the game varies.

Morton Davis describes a very simple game between you and your opponent. You are presented with a table that contains some dollar values. To make a habit out of stating the obvious: the game works just as well with other currencies, including peas, buttons, nuts, points and duty shifts. The table might look something like this.

  I II III
A 5 -2 1
B 6 4 2
C 0 7 -1

You pick a row and your opponent picks a column and you write your choice down on a piece of paper. You then look at your choices and find out what value comes with those. A positive value means your opponent pays you the indicated amount of dollars (or peas, buttons, nuts, points or duty shifts) and a negative value means it's your bad luck to pay. For example, if you choose B and your opponent chooses II, you win four dollars (or peas, buttons, etc.). If you choose C and your opponent chooses III, you have to pay a dollar (...).

I can't resist telling you that there are other ways of making your choice known than writing it down on a piece of paper. I can resist, however, to list some of the alternatives, so you'll have to rely on your own imagination.

At this point you probably realize that we - i.e. Morton and I ;-) - are talking about a two-person, zero-sum game.

Strategy

As it turns out, the above table doesn't constitute a very interesting game. Well, not for you opponent, at least. It's easy to improve on this, but that's not the point. I just want to introduce some theory based on this game. Keep in mind that you are trying to pick as high a number as possible and that your opponent is trying to pick as low a number as possible.

Suppose your opponent knows which row you are going to choose (the cheater!) and you know that he knows. Which row should you choose? Whichever row you choose, your opponent will always respond by picking the minimum value in that row, unless he is particularly foolish. So, you should pick the row with the highest minimum, which is row B. Take your time to digest this information. :-)

Row B has a minimum value of 2. This value is called the maximin. If you take the minimum of each row (i.e. -2, 2 and -1), then 2 is the maximum of those minimum values.

If the roles are reversed and you know beforehand which column your opponent is going to choose (a brilliant strategy, that), then your opponent faces a similar choice. However, since your opponent is looking for the lowest number, he has to consider the maximum values in each column (i.e. 6, 7 and 2) and choose the minimum of those maximum values, which is 2. This value is called the minimax.

Balance is boring

As you can see, the maximin equals the minimax in this case. When this happens, we speak of an equilibrium point. In the proposed table the equilibrium point is at B-III and has a value of 2, meaning that you always win two dollars or whatever it is you're playing for. Equilibrium points totally ruin a game. Your best strategy is to choose row B, your opponents best strategy is to choose column III and that is the end of it.

I have just spent a considerable part of my working hours explaining to you a totally boring game. Anyone who has had the benefit of formal education - sitting in a room with your classmates, listening to a teacher indulge in the intricacies of an unintelligible subject, not to mention the sound of his own voice - knows that games are supposed to combat boredom, not induce it. So, let's put the book away for a while and improve on what we have so far.

My own little game

Here are the rules of the game I came up with.

  1. The game is played on a four-by-four grid. Columns are indicated by Roman numerals and rows are indicated by letters. Player one plays columns, player two plays rows.
  2. At the start of the game, each player receives sixteen tokens. The tokens are clearly recognizable as belonging to a certain player. The grid starts out empty.
  3. The players take turns putting down tokens on the grid. At every turn a player can only put down tokens in a grid square that is still empty. A player can put down tokens in only one grid square each turn. A player can only put down tokens he hasn't put down on the grid yet. A player is free to choose the number of tokens he puts down, as long as he doesn't put down more tokens than he has (uhm, yeah).
  4. If one of the players has used of all of his tokens, the other player can distribute his remaining tokens over the empty grid squares as he sees fit.
  5. When both players run out of tokens, player one silently chooses a column and player two silently chooses a row. After the choices have been made, both players show their choices to one another.
  6. The grid square that lies at the crossing of the choosen row and column indicates who wins and how much. If the grid square is occupied by tokens of player one, the amount of tokens indicates the number of dollars player two has to pay player one. If the grid square is occupied by tokens of player two, the amount of tokens indicates the number of dollars player one has to pay player two.
  7. It's equally valid to play for money in other currencies or for peas, buttons, nuts, points or duty shifts, as long as both players agree. Playing for houses, companies, hostages, countries or family members is not encouraged.

The end of this game is the same as the game described by Morton Davis, however the distribution of the table is now in the hands of the players. You can make some adjustments to the game. For example, you can adjust the size of the grid. I do recommend that you keep the number of rows and columns equal, but a little experimentation shouldn't hurt too much (as long as you follow rule number 7). Four-by-four is the minimum grid size that allows for interesting play. Enlarging the grid might keep you busy a whole lot longer, but as long as the teacher hasn't finished his story, that counts as a benefit.

Another possible adjustment is to change the number of tokens each player starts with. I found that making the number of tokens equal to the number of grid squares offers a solid amount of strategical choice. Decreasing the number of tokens can leave you with too little tokens near the end. Increasing the number of tokens will only affect the average number of tokens in a square, but I suspect it doesn't alter the gameplay all that much. If you're playing for money, it could get you poorer or richer a bit quicker, though.

This is a game of pure strategy, and luck - other than your opponent's savvy - plays no part in it. That's how I like my games, but unfortunately very few of my friends feel the same way. This is alright, though, because now I can claim being the smartest without having to prove it. The down side is that I haven't played this game enough to be able to say something about possible strategies. There might even be a winning strategy or a strategy that always leaves a draw, like with Tic-Tac-Toe. Be sure to let me know what your findings are.

I haven't thought of a name for this game yet. Suggestions are welcome.

Remember, if you're sent to the principal's office because you were playing this game in class, just make sure he understands all the rules. If you play your tokens right, the principal might end up having to put in the after-school hours for you.

Back to blog index

Comments

GBGames says:

Regarding gameplay: you're right about avoiding boredom by preventing equillibrium. What you basically want to do is make the player make interesting choices. In the first example, the choice wasn't interesting. You knew what to do. It's like those jumping puzzles that people hate. You know what you have to do, and you know you can do it, but it becomes a battle against the game control setup, which is never fun. The choices from one game to another aren't the same, so it won't get stale as quickly as the first example you gave. However, the choices are only interesting if there are in fact choices. Can there be two tiles that would be equally valid for each player? That makes it a more interesting game. However, if the pieces land where you have the same format as the first example, where there is only one choice, it fails again. Thinking about it, having the players submit the pieces can give it some strategy. If only one choice is available at the end, it was the result of one player possibly outwitting the other. And the placing of pieces itself makes for interesting choices. But one of the keys to preventing a game from being boring is to make sure the player has interesting choices. In Game Architecture and Design, you can look into the Scissors, Paper, Stone examples (why Stone? I thought it was supposed to be Rock?) for ideas on how to take a game at equillibrium and make the choices more interesting.

Friday, February 11, 2005 5:37 PM

Joost Ronkes Agerbeek says:

From your comment, I get the impression that you haven't played the game yet. When I did, I found that you do have quite a lot of interesting choices. You make the most important choices while placing your tokens on the grid. Choosing a grid or column can be interesting too, since it's very unlikely there will be an equilibrium point, but what you do before that is what really matters. If at the end there is an equilibrium point, than one of the players was not paying attention. At least, that's what I expect, but I can't rule out the possibility that there is a winning strategy. I hope further reading of the book will help me get a better grasp of the strategic aspect of my game.

Sunday, February 13, 2005 1:24 PM

Tell me what you think

Since I'm not updating this site anymore, I disabled comments. You can visit me at my new site: www.williamwilling.com.