Peter Norvig

# This is a note for testing purposes # The Devil and the Coin Flip Game If the Devil ever challenges me to a [fiddle contest](https://en.wikipedia.org/wiki/The_Devil_Went_Down_to_Georgia), I'm going down. But here is a contest where I'd have a better chance: > *You're playing a game with the Devil, with your soul at stake. You're sitting at a circular table which has 4 coins, arranged in a diamond, at the 12, 3, 6, and 9 o'clock positions. You are blindfolded, and can never see the coins or the table.* > *Your goal is to get all 4 coins showing heads, by telling the devil the position(s) of some coins to flip. We call this a "move" on your part. The Devil must faithfully perform the requested flips, but may first sneakily rotate the table any number of quarter-turns, so that the coins are in different positions. You keep making moves, and the Devil keeps rotating and flipping, until all 4 coins show heads.* > *Example: You tell the Devil to flip the 12 o'clock and 6 o'clock positions. The devil might rotate the table a quarter turn clockwiae, and then flip the coins that have moved into the 12 o'clock and 6 o'clock positions (which were formerly at 3 o'clock and 9 o'clock). Or the Devil could have made any other rotation before flipping.* > *What is a shortest sequence of moves that is **guaranteed** to win, no matter what the initial state of the coins, and no matter what rotations the Devil applies?* (This same puzzle also appeared in [The Riddler on 21 June 2019](https://fivethirtyeight.com/features/i-would-walk-500-miles-and-i-would-riddle-500-more/), with the role of the devil played by a banker. I'm not sure which is scarier.) # Analysis - We're looking for a "shortest sequence of moves" that reaches a goal. That's a [shortest path search problem](https://en.wikipedia.org/wiki/Shortest_path_problem). I've done that before. - Since the Devil gets to make moves too, you might think that this is a [minimax](https://en.wikipedia.org/wiki/Minimax) problem: that we should choose the move that leads to the shortest path, given that the Devil has the option of making moves that lead to the longest path. - But minimax only works when you know what moves the opponent is making: he did *that*, so I'll do *this*. In this problem the player is blinfolded; that makes it a [partially observable problem](https://en.wikipedia.org/wiki/Partially_observable_system) (in this case, not observable at all, but it is traditional to say "partially"). - In such problems, we don't know for sure the true state of the world before or after any move. So we should represent what *is* known: *the set of states that we believe to be possible*. We call this a *belief state*. At the start of the game, each of the four coins could be either heads or tails, so that's 2⁴ = 16 possibilities in the initial belief state: {HHHH, HHHT, HHTH, HHTT, HTHH, HTHT, HTTH, HTTT, THHH, THHT, THTH, THTT, TTHH, TTHT, TTTH, TTTT} - So we have a single-agent shortest-path search in the space of belief states (not the space of physical states of the coins). We search for a path from the inital belief state to the goal belief state, which is `{HHHH}` (meaning that 4 heads is the only possibility). - A move updates the belief state as follows: for every four-coin sequence in the current belief state, rotate it in every possible way, and then flip the coins specified by the position(s) in the move. Collect all these results together to form the new belief state. The search space is small (just 2¹⁶ possible belief states), so run time will be fast. - I'll [Keep It Simple](https://en.wikipedia.org/wiki/KISS_principle), and not worry about rotational symmetry (although we'll come back to that later). # Basic Data Structures and Functions What data structures will I be dealing with? - `Coins`: a *coin sequence* (four coins, in order, on the table) is represented as a `str` of four characters, such as `'HTTT'`. - `Belief`: a *belief state* is a `frozenset` of `Coins` (frozen so it can be hashed), like `{'HHHT', 'TTTH'}`. - `Position`: an integer index into the coin sequence; position `0` selects the `H` in `'HTTT'`. - `Move`: a set of positions to flip, such as `{0, 2}`. - `Strategy`: an ordered list of moves. A blindfolded player has no feedback, thus there are no decision points in the strategy. I take the coin sequence `'HTTT'` to mean there is an `'H'` at the 12 o'clock position, then 3, , 6, and 9 o'clock in that order are `'T'`.