Go First Dice Problem

The Problem:

I encountered an interesting riddle recently called the "go first dice problem". The challenge is to come up with a set of dice (one per player) such that:

• No two faces share the same label.
• The dice can be used to determine a fair turn order for the players after a single roll. That is, the player with the highest roll goes first, the second highest goes second, etc. A set of dice is fair if and only if every possible turn ordering is equally likely given random rolls.

More Information:

There are some stack exchange threads discussing the problem:

• math.stackexchange.com
• codegolf.stackexchange.com
• stackoverflow.com

Eric Harshbarger (puzzle designer/Lego sculptor/programmer/mathematician/Scrabble player) sells a set of 12 sided dice that solve the go first problem for four players: http://www.ericharshbarger.org/dice/#gofirst_4d12. As far as I know there is no known solution for five players. For fewer than five players:

• 2 players: minimum 2 faces
• 3 players: minimum 6 faces
• 4 players: minimum 12 faces

The Challenge:

Find a set of go first dice for five players. This will require at least 30 faces per die.

I have been working on trying to solve this (with a computer) for a few days. The search space is too large for a naïve brute-force search, so I think to make this computationally feasible you need to either:

• find a clever way to constrain the solution space (to make it small enough to exhaustively search), or
• come up with a heuristic so that your program is more likely to search in regions where a solution exists.

The Prize:

I will offer a small prize to whoever solves this challenge first. The prize will be a set of Eric's go first dice for four players - shipping paid by me to anywhere in the world. To claim the prize just email me with the solution and I will run a program to validate it. You can only claim the prize if you are actually the person who found the solution (e.g. don't copy it from someone). There is no set end date to this offer (as long as Eric continues selling the dice).

Metamoku

The first release of Metamoku is ready! Try it out at: www.metamoku.com

Metamoku should work across different browsers, operating systems, and devices (including smart phones and tablets). Let me know if you encounter problems on any platform. Note that you can also play team games if multiple people choose the same color. When I was developing the game I was unsure whether it would actually be fun or contain non-trivial strategies. After playing some test matches with friends I think the game does have some interesting strategic components (especially the team matches). I currently don't have any major features/tasks left to implement. I will probably continue tweaking gameplay parameters as I get more experience playing games.

Dark Souls PvP

I recently started my second playthrough of Dark Souls. Dark Souls is the best game I have ever played. I originally played Dark Souls on the PS3 - this time I am playing the PC port ("Prepare to Die" edition). That means now I can take screenshots!

Notice that the dragon's tail is missing - I did that.

Unhappy dragon.

This hallway is where I had an unforgettable experience. Another player had invaded my world to assassinate me (1v1 PvP). This is a pretty rare event when I play, so it is exciting when it happens. Luckily, this was the perfect place and time for him to invade - I had full health and the location could not be better. This narrow hallway leads to a dead-end, which means there is only one way in or out. That prevents my opponent from sneaking up with a surprise attack. My character is a pyromancer, which means that I am most effective at mid-range attacks. This hallway was perfect for my character because it forces the other player to walk directly into my spell range. So I waited in the hallway for him to attack. He spotted me from the end of the hallway and tried to lure me out - he can see my Pyromancy Flame so he knows that I have the advantage here. His weapon is some sort of dagger. Since I refuse to leave the hallway, eventually he cautiously approaches. When it looks like he is in my spell range, I start casting fire orbs at him. Impressively, he manages to stay far enough back to narrowly avoid my spells. When I advance he moves back, and when I move back he advances. So I continue casting the spell since I have plenty to spare. My spell is powerful enough that a single hit would make it very difficult for him to recover. Suddenly after one of my fire orbs misses him, he starts sprinting towards me. I cast another orb and it is headed directly at him. At the perfect time he does a dive roll under the orb and it narrowly misses him. He rolls past my side and stands up directly behind me. Before I have a chance to react he backstabs me and kills me with a single attack. The backstab attack is that powerful because it is so difficult to get directly behind a player. I was astounded at how perfect his sequence of moves was. As he was fading away to return to his world, he turned towards my corpse and bowed. I wish the battle had been recorded - it would have been fun to be able to watch it again.