Gaming Graph Theory

The Seven Bridges of Königsberg is an important historical problem in mathematics, explored by Leonhard Euler in 1735, that laid the foundations of graph theory and topology.

The city of Königsberg in Prussia (now Kaliningrad, Russia) was set on both sides of the Pregel River, and included two large islands which were connected to each other and the mainland by seven bridges.

 Mathematically the problem can be stated like this:

Given the graph above, is it possible to construct a path (or a cycle – a path starting and ending on the same vertex) which visits each edge exactly once?

Euler proved that it was not possible. He proved that for the existence of what he coined “Eulerian trails”, it is necessary that no more than two vertices have an odd degree; this means the Königsberg graph is not Eulerian. Mathematically, if there are no vertices of odd degree, all Eulerian trails are circuits. If there are exactly two vertices of odd degree, all Eulerian trails start at one of them and end at the other. A graph that has an Eulerian trail but not an Eulerian circuit is called semi-Eulerian.

This type of mathematics can be quite abstract for students (and teachers) and most find it quite difficult even when presented in context of network optimization, railway systems, traffic flow, shortest path problems etc. 

One Touch Drawing by Ecapyc Inc. is a nice puzzle game on iOS that deals exclusively with Graph Theory. It could be a nice way to get students thinking about Graph Theory before the topic is introduced and then used as a context for discussion and problem solving to give the topic more meaning to students. I have only played the first few levels, the the difficulty ramps quite quickly. Recommended.

The Numbers Game: Putting Yourself In Other’s Shoes

Perspective is essential.

In life, in your work and in everything that you do. It’s also essential in game theory when attempting to reduce a game to it’s simplest form via a process known as iterative deletion of dominated strategies.

The lecture below gives a simple game that illustrates this idea:

During class you are given a sheet of paper on which you must write a number between 1 & 100. The average number of everyone in the class will be calculated. To ‘win’, the number you choose must be 2/3 of the class average.

This game forces you to consider other people’s perspective. In order to think logically you need to put yourself in other people’s shoes, imagining what they are likely to do, and then determining your own strategy in response to your assumptions about the other player(s). 

This is a great game to introduce to a class of any age, regardless of experience in game theory, game thinking or mathematics. It’s simple enough that everyone can play, develop their idea of a winning strategy and engage in discussion around ‘why’ and ‘what if.’ Game Theory requires students to put themselves in other’s shoes – a valuable skill in life.

The solution to this particular game can be found by an iterative process whereby you systematically delete dominated strategies by considering other player’s actions. However the solution is not as obvious as you may first think.

Watch the video for a detailed analysis of a ‘solution.’

For a detailed description of some ideas on Game Theory check out Brian Weatherson’s notes.

Game Theory is not the Theory of Games

(see previous Games? In Learning? I’m Confused…)

Game Theory is a branch of applied Mathematics which looks at competitive situations where two or more people have conflicting interests – it is not the theory of using games in learning.

Game Theory has been applied in many situations and contexts through history, most notably the Cold War, Global Politics, Economics and of course games like Poker, Rock, Paper, Scissors, Nim and Liars Dice (see this post – Red Dead Redemption)

The Prisoners Dilemma is synonymous when introducing Game Theory. Summarized briefly:

Two criminals, Prisoner A & Prisoner B are put in different rooms and given a similar deal. If one implicates the other, he may go free whilst the other receives a 10 year sentance. If neither of the crimanals talk, both are given 1 year sentances, and if both implicate each other, they each receive a 5 year sentence. 

Each criminal has an optimum strategy of implicating the other, and thus in equilibrium each receives a harsh punishment, but both would be better off if each remained silent. (This is assuming that both Prisoner A & B are rational) 

There are various iterations of the Prisoners Dilemma and it has been seen in popular media in various guises over the years:

(See Golden Balls & Game Theory for a nice explanation here)

John Nash, a famous mathematician and Nobel Laureate, whose work in game theory provided insight into the forces that govern chance and events inside the complex system of daily life, was made famous by popular media in the movie, A Beautiful Mind. This excerpt from the movie looks at Nash as he begins to formulate his idea of the Nash Equilibrium – for which he would later win a Nobel prize for his contributions in Game Theory.

A Nash Equilibrium is a state in the game where no player has an incentive to deviate. Each player’s equilibrium strategy is known by the other players, and no player has anything to gain by changing only his own strategy. When all the players in this case go for the blonde, every player can increase his payoff by deviating. 

One of my favourte instances of Game Theory is the Truel. Breifly:

Mr. Black, Mr. Gray, and Mr. White are fighting in a truel. They each get a gun and take turns shooting at each other until only one person is left. Mr. Black, who hits his shot 1/3 of the time, gets to shoot first. Mr. Gray, who hits his shot 2/3 of the time, gets to shoot next, assuming he is still alive. Mr. White, who hits his shot all the time, shoots next, assuming he is also alive. The cycle repeats. If you are Mr. Black, where should you shoot first for the highest chance of survival?

(Hint: Think from the points of view of Mr. Gray and Mr. White, not just Mr. Black.)

See a Truel in action in the Clint Eastwood Western The Good, The Bad, The Ugly.

So Game Theory is a branch of Mathematics that uses vocabulary like Nash Equilibrium, complete/incomplete information, zero sum, variable sum, optimal strategy, deviation, expected value etc. – it’s not the Theory of using Games in learning.

Next Post: Game-Based Learning

Red Dead Redemption: Liars Dice

One of the mini-games in Read Dead Redemption is Liar’s Dice.

Liars dice is a game of incomplete information which distinguishes it from games like chess and backgammon where you can always see what your opponent is doing. The art of liars dice is filling the gaps in the incomplete information provided by your opponents bidding, and at the same time preventing your opponents from discovering any more than what you want them to know about your roll.

Originating in South America and originally going by the name of Perudo, this game is inherently engaging for students.

Rules:

•2 to 4 people are the ideal number of players

•Each player starts with 5 six-sided dice and something to conceal their roll

•All players initially roll their dice for everybody to see. Highest numerical total starts play

•The ‘One’ is wild

•All players now roll their dice so that they are concealed from the other players

•Each player in the game, proceeding clockwise, must make consecutively higher bids or call ‘liar’.

•A bid consists of a number and the value of a die. For example a bid of ‘Three Sixes’ could be followed by “Four fives” or “Six fours”

•As long as the bid is either numerically greater or contains more of the one bid it is valid. For example, if player 1 bids ‘Four Sixes’ player 2 could bid either ‘Five Sixes’ or ‘Five Fives’ as 5 x 5 = 25 which is greater than 4 x 6 =24

•If the opening bid consists of ‘Ones’, ‘Ones’ are no longer wild

•When a player is called ‘liar’, all players reveal their dice. For example, if you bid ‘Four Sixes’ and someone calls you ‘liar’ your bid is correct if between all players at the table, there are at least ‘Four Sixes’

•If you are caught ‘lying’ you lose a dice and play resumes. If there is at least the number of dice that you bid the person who unsuccessfully called you a ‘liar’ loses a dice and play resumes

•The last player with dice is the winner (of course, as with any game, there are variations to these rules)

The skill of liars dice consists of knowing when to tell the truth and when to ‘bluff’ and also when to call someone’s bluff. Obviously the optimum strategy is to mix bluffing with statistical estimation of what’s on the table.

Since the other players have to base their estimation of the dice on what you bid, if you can get away with a bluff in the early rounds you can affect their estimates of what’s on the table. 

For example, all players roll their dice. Player 1 has 3 3 4 5 2, Player 2 has 6 6 3 2 4 and Player 3 has 6 1 3 3 5. Player 1 opens the bidding and bids ‘Three Sixes’. Player 2 has two sixes himself so bids ‘Four sixes’. Player 3 also has a six and a one so bids ‘Five Sixes’. Player 1 holds no sixes so can fairly confidently call liar with the odds being in his favour.

The early bluff is misleading information designed to skew the perception of the other players. When a player makes a bid that the information he has does not support, that bid is likely to be accurate based on simple probability, but other players will think the bid was made because the player had some part of the bid in his own dice. This in turn causes the other players to inflate their own bids based around that value, increasing the likelihood that those bids will be false.

Once other players are aware that you like to bluff with an opening bid, it can be to your advantage to start semi-bluffing. Lets say you have the opening bid and you roll 6 6 1 3 2. Bid ‘Five Sixes’. Player 2 thinks that you are bluffing and calls you ‘liar’. The probability is definitely in your favour that Player 2 and Player 3 have each got either a one or a six.

Position is one of the key elements affecting virtually every bid in liars dice. The game is heavily weighted in favour of the player acting first. Aggressiveness in this position ensures that you control the round. For example, an opening bid of ‘Three Twos’ is relatively weak and gives the other players a lot of room to move, potentially exposing yourself to a precarious situation later in the round. By demonstrating weakness on the opening bid, you have relinquished your powerful position to the next player who can then take control of the round. A much more dominating and aggressive bid might be ‘Five Fives’ or ‘Four Sixes’. An aggressive opening like this one puts pressure on the other players immediately and gives you control of the round.

A complete strategy of liars dice is inherently complex because it takes into account not only the dice that each player is holding but also the state of the game in general. After experimentation you will find that certain players exhibit certain tendencies and that their are subtle differences in game play between a game involving two players and a game involving more than two.

Good liars dice players, to one degree or another tend to possess knowledge of game theory and the following characteristics:

•Mathematical proficiency – Ability to accurately calculate probabilities

•Reading skill – Ability to determine if a player is telling the truth or is obviously bluffing

•Flexibility – The ability to modify their approach to the game based on their opponents and what their opponents ‘know’ of their game

•Awareness – Constantly scanning opponents, looking for clues that assist in decision making

•Aggression – An attacking dominating style

The movie, Pirates of the Caribbean: Dead Mans Chest, also gives a variation of Liars Dice (seen below) and an online version of ‘Pirates Dice’ has been created by Disney, where you get to wager your soul as you play against Davey Jones and his crew.

I have provided here a brief overview of an opinion on liars dice. It is not meant to be comprehensive, but instead is provided to guide thinking when developing your own strategy and to help you guide students in their own exploration of this game. 

Feedback welcome.