I would have easily won that game (and maybe made a quip about free will when asked how...). All you need is some memorized secret randomness. For example, a randomly generated password that you've memorized, but you'd have to figure out how to convert it to bits on the fly.

Personally I'd recommend going to random.org, generating a few hexadecimal bytes (which are pretty easy to convert to both bits and numbers in any desired range), memorizing them, and keeping them secret. Then you'll always be able to act unpredictably.

Well, unpredictably to a computer program. If you want to be able to be unpredictable to someone who's good at reading your next move from your face, you would need some way to not know your next move before making it. One way would be to run something like an algorithm that generates the binary expansion of pi in your head, and delaying calculating the next bit until the best moment. Of course, you wouldn't actually choose pi, but something less well-known and preferably easier to calculate. I don't know any such algorithms, and I guess if anyone knows a good one, they're not likely to share. But if it was something like a pseudorandom bitstream generator that takes a seed, it could be shared, as long as you didn't share your seed. If anyone's thought about this in more depth and is willing to share, I'm interested.