I wasn't trying to criticize it -- I think it's a great heuristic and I think it touches on a very fundamental, non-obvious aspect of reality. I just want to better understand what kind of exception AMD and your game are.

Here's an old comment thread where I tried to explain how I think about this.

The short version is this: Adding randomness is only useful when you are trying to obfuscate. Otherwise, adding randomness per se is always bad or neutral. However, many cases that are described as "adding randomness" are really about adding some information that turns out to be just what the agent needs, plus some randomness that turns out not to do any harm.

For example, in the AMD problem, the optimal strategy is often described as "exit with probability 1/3rd". Now, what this really means is the following: The agent is given an input channel C, together with the knowledge that the input from C will belong to a set S such that some known set T contains 1/3rd of the elements of S (but no additional information). The agent then implements the deterministic algorithm of exiting iff the input from C belongs to the set T.

People often explain why this agent is able to do better than an agent without a "mixed" strategy by saying, "This agent has a source of randomness." But I think that it's better to say that the agent has an input channel about which it knows something, but not everything. In contrast, the agent employing a "non-mixed" strategy doesn't have this information about the channel. So, naturally, the agent with the "mixed" strategy does better, because it knows more.