This morning someone (you know who you are) said that what I write here is insightful. (Actually, the person wrote it, so I know she didn’t mean “inciteful”.) I apologize deeply. It is not my intention to purvey insight — this is really therapy as much as anything else. I do not usually think much during the day about what to write, but when the time comes round for Cajo Snudehygel to speak, there are many ideas competing to be heard.
This preface is really an excuse for me to write something uninsightful, and today to write about something not of general interest.
I think that, for a couple of years now, I may have been spreading a lie by telling people that TIT-FOR-TAT is always a winning strategy for Rock-Scissors-Paper. I can even remember where I learned that “fact”: in Douglas Hofstadter’s wonderful essays about game theory. (Chapters 28 & 29 in Metamagical Themas — well worth reading.) Tonight I looked it up again and it turns out that I remembered wrong! The game was a repeated run of the Prisoner’s Dilemma, and TIT-FOR-TAT was only the best entry in a particular competition. In fact, Hofstadter explains later in the essay that T-F-T is not optimal, and that there are several enhancements to it.
So, the R-S-P field is still open. Thank goodness. I’m thinking of organizing a little competition, along the lines of Darse Billings’s Roshambo competition. The point would not be to create the ultimate R-S-P player, but simply to have a little fun. I think, or hope at least, that students will find it inspiring. It doesn’t require much programming knowledge and such competitions are quite a lot of fun. For me, at least.
I once wrote a program for a class of RSP-programs. It was a simple bayesian player: it plays at random for a few rounds with “priors” set to 1/3 on all “responses”, that is, if the sequence played by the players is X1Y1X2Y2…XkYk in the k last rounds, what will the opponent play this round, i.e., guess what X(k+1) is going to be, based on simple probabilities.
I toyed with this. The simplest was of course just a table for all (or, like 100 most recent) the games played so far and another for the probablities in the 3^2k possible sequences.
So on each round, the player decides what is the most probable move by the opponent; it looks at what was played in the n previous rounds and looks at that entry in the 3^2k table. (The entry has three numbers: a probability for each of the choises) it picks the most probable – for instance, say it is R – and then decides to play against that (that is, P in our example)
If I remember correctly, when playing by hand against such a program, and trying to play “random”, i.e., without thinkin too much, this simple program with k=2 would beat me 50% of the time in the long run. (33% would be the “average” for a pure random player).