Interesting Stuff

Today at work we bandied about an interesting logic puzzle, and understanding the answer totally blew my mind. It goes like this:

All dragons have either red eyes or green eyes. If a dragon ever knows its own eye color, it will die on the next stroke of midnight. Moreover, dragons, like all mythical beasts, are perfect logicians. That is to say, if it is possible to infer a fact from what is already known, dragons cannot help but make this deduction.

There is a town in which n dragons live, where n is small enough that every day, every dragon interacts with every other dragon. One day, an oracle, renowned for always speaking the truth, comes to the town. She gathers together all the dragons, looks at each one, and then loudly proclaims, “At least one dragon here has red eyes!”

1. What happens in the town?
2. Suppose that at least three dragons have red eyes. Now, not only does every dragon already know that at least one dragon has red eyes, they also know that every other dragon knows this, too. What information does the oracle add that the dragons didn’t have already?

I think that I’m going to give up trying to solve the Hat Problem, though I’ve come pretty far (for background, see my original description and its follow-up post). I’ve now solved the N=5 version (with surprising results!), and gotten a pretty good framework around the problem: My final analysis of the Hat Problem, including a reduction to the Minimum Dominating Set problem, source code for a better program to search for solutions, and an optimal strategy for N=5 →

Yesterday, I wrote about the Hat Problem. I figured out some more late last night, but haven’t had a chance to post until now. I cancelled my brute-force program because I figured out the solution to the 4-person version: have 1 person pass all the time, and have the other 3 people pretend it’s the 3-person problem. I know this because I got an upper bound on the best strategy: with N people, you can never do better than winning N out of N+1 times (so the solutions based on Hamming codes are always optimal). If you add up all the non-pass responses over all possible hat configurations, you need an equal number of correct and incorrect answers (otherwise, the chances that your own hat is red are not independent of the colors of everyone else’s hat, and probability is broken). The best you can bunch up the wrong answers is to have everyone guess wrong at the same time, and the best you can spread out the right answers is to have each right answer in its own hat configuration. So, for every time the group loses, you can have at most N wins, and the best chances you can ever get are N in N+1.

How does this help in the N=4 situation? We now know that best you can do is win 80% of the time. Moreover, there are 16 distinct hat configurations. Winning 13 of them would be more than 80%, so we must win fewer than that many. However, we can win 12 of them by reducing ourselves to the N=3 version, so we know that’s the optimal solution. For N=5, there are 32 distinct hat combinations, and the optimal strategy will win at least 24 and at most 26 of them (but I don’t know the exact answer). For N=6, the optimal strategy will win at least 48 and at most 54 of the 64 possible configurations. The brute-force method won’t finish within our lifetimes for N>4, so I can’t try that again. Any other ideas on how to progress? FWIW, I’ve found a second way to get 75% success when N=6.

(Edit: see part 3 for more on the problem)

I recently learned about The Hat Puzzle, which is a surprisingly tough little conundrum that goes like this:

N people walk into a room and a hat is placed on each person’s head. Each hat is either red or blue, and the chances that any given hat is red are 1 in 2. Each person can see the colours of everyone else’s hat, but not the colour of their own. While in the room with the hats, no one is allowed to communicate with each other in any way at all. Everyone is then lead into separate rooms, and asked the colour of his or her own hat. Each person can choose to answer or to pass. If at least one person answers correctly and no one answers incorrectly, the whole group wins. How do you maximize your chances of winning?

The naive solution (before entering the room, pick one person who will guess Red and have everyone else pass; chances of winning are 50%) seems easy enough, but there are more complicated solutions that do better. For instance, with 3 people, you can win 75% of the time: if your comrades have the same colour hat on, guess the other colour. If they have different colour hats, pass. The only time you lose is when everyone has the same colour hat. Note that a person who chooses to guess the colour of their hat is still wrong half the time (i.e. probability isn’t broken), but we’ve spread out the occurrences of correct answers and bunched all the wrong answers on top of each other. Apparently you can use Hamming Codes to win with odds N out of N+1 when N is 1 less than a power of 2, but I haven’t seen an explanation of how that works yet.

Apparently, this is an unsolved problem for all other N, though. I have written a Java program to use a brute force method to find the solutions, and it easily verified that the best you can do when N=3 is 75% (using the strategy described above). The problem with this brute force solution is that its running time is O(2^n * 3^(n*2^n)), which makes it rather unwieldy. I’ve started running the program to solve the N=4 case, and I hope it will finish by tomorrow afternoon. edit: I dramastically misunderestimated the time needed to run this program. It will hopefully be done by Thursday. I will not use it to find the solution for N=5.

As usual for subtle and tricky topics, the Wikipedia page is wrong in subtle and tricky ways (at least, it was when I wrote this), so don’t bother looking for more information there.

(Edit: I continue working on this in part 2)

I installed ScummVM this evening and have been playing classic LucasArts games. I’ve verified that Monkey Island and Sam and Max seem to work, and they’re as fun as they ever were. These were created back in the day when games couldn’t depend on their graphics to be entertaining, so they actually had to be witty and humourous. Ah, good times!

Most of my friends know that I really like the roguelike game Linley’s Dungeon Crawl and play it often (it’s similar to NetHack and Angband, if you’re familiar with those). In it, you wander around an (ASCII art) dungeon fighting monsters and getting equipment and treasures. The object of the game is to get the fabled Orb of Zot, which is in the Realm of Zot. You can get there from the dungeon by opening the Portal of Zot using three Runes of Zot (see, there’s a theme here…). It has a wonderfully detailed play structure, and provides hours of entertainment.

The only problem, in my opinion, is that it’s impossibly hard: not only have I never won in my 6 years of playing, but I’ve never gotten a single Rune. There are also a few bugs (most notably, it seems to lock up if you’re controlling your teleport destination). I had thought that development stopped in 2003, but it turns out I was wrong: Linley and his friends stopped developing, but there is a branch called Dungeon Crawl Stone Soup that continues on. It has some really nice extra stuff added in. For instance, if there are no monsters around, you automatically pick up gold, food, potions, and certain other objects that you almost certainly want to get. This turns off if you can see a monster. The targeting for ranged weapons/spells is much more automatic. It now has a path planning algorithm in it so that you can walk to any location in the level (and it automatically stops if you encounter a monster along the way). The morgue files (summaries of your character after you die) are much more detailed. Event messages, stats screens, and your inventory are more detailed. It’s still impossibly hard, but DCSS makes some of the basic mechanics much simpler. This is great!

If you’re interested in a fun, easy-to-learn game that offers literally unlimited play, give DCSS a try.

I had dinner with Michael and Robert yesterday, and somehow Michael mentioned in the conversation that E.T. was made into a video game for the Atari 2600, and is widely considered the worst-selling video game of all time (they apparently buried tens of thousands of cartridges in a landfill because it was the most profitable way of getting rid of them). Well, we actually managed to find a copy of this game and play it, and there’s a reason why it didn’t sell well. Here is a synopsis of the game, as best we could piece together by reading the manual and playing it:

• You control ET. The object of the game is to get ET to collect 3 pieces of telephone and phone home. Telephone pieces are hidden at the bottom of large pits that you can fall in.
• The location of the pits appears to be uncorrelated with anything else on the screen: you can fall into a pit without seeing anything unusual on the screen, and you can step into the differently colored parts and only sometimes fall into a pit.
• You can extend your neck to levitate out of and over the pits. Also, sometimes you can extend your neck to change zones. We’re not sure what a zone is (we think it’s like a mode), but we often cycled through the “eat candy zone” and the “call Elliot zone.” One zone changes the terrain around you, which is confusing as hell. Sometimes you can also change zones by moving in a different direction. We have no clue about this.
• Moving around costs energy, and the amount of energy you have left is displayed at the bottom of the screen. When you run out of energy, Elliot comes by and gives you 1500 more units. This means that the game ends either when you win or when you get bored and stop playing. To the best of our knowledge, you can never lose.
• If the FBI man catches you, he takes you to the Parthenon and steals all your candy.
• If you manage to call Elliot while in “call Elliot zone,” he will come and take your candy. He will then pretend to run off and find a piece of telephone for us. We don’t know why he does this, however, because he never actually returns with one.

Lots of letters can be silent in English, but I’m missing a few. Can anyone help fill in the rest of this table? Proper nouns are cheating. So is “February.”

Edit: words in italics were found by minorninth at this page. To be honest, though, I’d like better ones for Q and Y.

• A – boat
• B – numb
• C – scissors
• D – adjective
• E – made
• F –
• G – gnaw
• H – through
• I – piece
• J –
• K -knew
• L – talk
• M – mnemonic
• N – damn
• O – leopard
• P – psychic
• Q – lacquer
• R –
• S – island
• T – often
• U – fugue
• V –
• W – who
• X – faux
• Y – prayer
• Z – rendezvous

If you’re playing Zelda: Twilight Princess and get the iron boots, you should save to a different save slot. The next part is so awesome that you’ll want to play it over and over. Oh, man. This game is amazing.

Take a classic game that makes heavy use of a simple physics engine (such as Asteroids), and add in general relativity to the physics engine (and set the speed of light so that the game has very noticeable relativistic effects). For the Asteroids example, asteroids traveling at high speeds relative to you would exhibit Lorenz contraction, asteroids coming towards you would be bluish and those going away would be reddish, firing your gun would propel you backwards a little, etc. I’m not sure if accelerating would have different behavior than in the usual version (sure, the asteroids would age faster, but that wouldn’t be noticeable in-game). Stuff displayed on the screen would be what the spaceship pilot would perceive “now.” I suspect it would be an interesting twist on a classic game, and give people a better intuition for relativity (assuming people like it and play it a bunch). I can’t find such a game already created on the internet, but I haven’t looked too hard.

Any thoughts?