Tuesday, September 25, 2012

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: 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).
Post a Comment