Friday, May 6, 2011

Dice games confuse me -- testing a strategy in Python

My friend (let's call him Coleman) told me about a dice game today, and how using probability you could increase your win percentage. I didn't believe him, and I set out to prove him wrong.

First, let me explain the game. Two people each roll a die. Each can look at their opponent's roll, but not their own. They can have no communication once the die have been rolled (but can collaborate beforehand). The object of the game is for each to guess what their own die is; they both win if they each guess correctly, otherwise they lose.

I assumed that without any knowledge of what their die is, each person has a 1/6 chance of guessing correctly. This means that the pair have a 1/36 chance of both guessing correctly and winning the game.

Coleman tried to tell me he could do better. If the two people agree to each guess what their opponent's die is showing, they have a 1/6 chance of winning. This didn't make sense - what your opponent rolled has zero to do with what you rolled, and there is no way that choosing their roll would give you a better outcome.

Time to test it - Monte Carlo style! I wrote a script that plays the game; it first plays guessing randomly, then guesses "intelligently" by following the strategy above. My gut told me that the two would have the same outcome, but my head was telling my gut to shutup and go have a sandwich.

Here's the result of playing randomly:
We get 2.8% (around 1/36); just as expected!

Now let's try playing by the strategy. My gut says it will also be 1/36...
16.7% -- around 1/6! What... how... ???

So Coleman was right. Here is how I convinced myself that the math was actually true - let's see if it makes sense outside of my head. By agreeing to play by the strategy, you're changing the game. Before, the game was two people each guessing a die roll correctly; this has a 1/36 chance of working. With the strategy, the game becomes two people roll the same number. This happens every 1/6 games. So you change the game with your strategy, and get a much better win percentage.

You can check out the Monte Carlo script I used here. I'm gonna go find some dice, and hit Coleman with a sandwich.

Thursday, May 5, 2011

Relearning Data Structures with Python

I realized the other day that I had learned about tons of data structures in class, but I've never used some of them in production. So, I set out to write simple implementations of a hash table and binary tree. After all, after I've made one in practice I'm more likely to make one when it's actually useful.

The focus in this exercise was clean implementation. Keep the code as short as possible, not sacrificing for readability. I think I've struck a good balance.

I've found that since I've learned Clojure, I'm more likely to use functional style coding in other languages. For example, here's my hash_function in Python:
Note the use of map. I was even using reduce for a while, but Python's sum led to a cleaner implementation. Also note that I'm using the decorator @staticmethod. Functional style calls for functions that have well defined inputs and outputs without side effects - declaring this method to be static explicitly shows that I am following that principle.

Compare that to how I would have written this six months ago:
The new, functional way is much cleaner. 

There are definitely many things I could add for my next steps. Some structure changing methods (dynamically allocated hash table? self balancing tree?) could be pretty cool.

You can check out the source on github. There is a tester file that shows how to use the class (and even provides some profiling code I used). To enable a tester, call it from the main function in