Once when I was in grad school I noticed an announcement for a lighthearted programming competition for rock-paper-scissors playing agent. The deadline was barely hours away and I was behind on a report for funding or course work, I can't recall now.
As it always happens with me, a non-serious non-essential task suddenly looks attractive over some work I had been procrastinating on.
With no time available to code up a submission from scratch i I just rigged up the zlib compression library to decide the next play. It considered appending the 3 potential completions of the play so far and compressed the sequence. Whichever appended symbol gave the maximum compression was my agent's next move.
It was just a few lines of code and it did surprisingly well. A universal compression library/algorithm that works better for short strings would have performed better. Zlib is an universal compressor but does not converge to the entropy of a sequence very fast.
The only secret strategy I know only works against my good friends son who literally starts every new round of rock scissors paper with scissors. Play him 10 minutes later he starts with scissors.
We we noticed this so we began to say let's play a round and throw paper and lose. 5 minutes later repeat and lose again. THEN, once our drink was almost finished we would say come on one more game and if I win you have to go get me a can from the fridge. He would agree and we would this time throw rock beating him and winning. It works every single time. Lol
> If we want to have a game where every weapon is a viable option, then we can’t bump RPS’s 3 to 4. We have to jump all the way to 5 choices with the game Rock – Paper – Scissors – Lizard – Spock. Each weapon beats two others and loses to two. The big downside of this game is complexity – I’m not a Trekkie and have no idea how Spock and Lizard are supposed to relate to the others. The upside is that ties are less common. For RPS 1/3 of all games will be a tie, while for RPSLS this drops to 1/5 – good if you want more decisive outcomes.
Really though, the way to do this is to represent each game as a payout matrix A, which for this category of game will be skew-symmetric with -1/0/+1 entries. Then since this is a symmetric zero-sum game, you find the null space of that matrix, impose the constraint that probabilities must sum to 1 and individually be >= 0, and that gives you the endpoints of the Nash Equilibria. The optimal strategies (could be one unique one for odd n!) lie on the convex hull of those points.
Thanks for sharing! My background is in control theory, and I think the links between it and game theory and dynamical systems in general are super fruitful but woefully underexplored. Writing this was a good excuse to brush up on my linear algebra basics again.
Paging sdenton4.
Once when I was in grad school I noticed an announcement for a lighthearted programming competition for rock-paper-scissors playing agent. The deadline was barely hours away and I was behind on a report for funding or course work, I can't recall now.
As it always happens with me, a non-serious non-essential task suddenly looks attractive over some work I had been procrastinating on.
With no time available to code up a submission from scratch i I just rigged up the zlib compression library to decide the next play. It considered appending the 3 potential completions of the play so far and compressed the sequence. Whichever appended symbol gave the maximum compression was my agent's next move.
It was just a few lines of code and it did surprisingly well. A universal compression library/algorithm that works better for short strings would have performed better. Zlib is an universal compressor but does not converge to the entropy of a sequence very fast.
Seems a lot like Normalized Compression Distance (https://en.wikipedia.org/wiki/Normalized_compression_distanc...) and Kolmogorov Complexity.
Good compression, necessarily, requires good "next token" probability estimation. I was essentially using zlib's implicit probability estimator.
The only secret strategy I know only works against my good friends son who literally starts every new round of rock scissors paper with scissors. Play him 10 minutes later he starts with scissors.
We we noticed this so we began to say let's play a round and throw paper and lose. 5 minutes later repeat and lose again. THEN, once our drink was almost finished we would say come on one more game and if I win you have to go get me a can from the fridge. He would agree and we would this time throw rock beating him and winning. It works every single time. Lol
The only real game is Rock-Paper-Scissors-Lizard-Spock
> If we want to have a game where every weapon is a viable option, then we can’t bump RPS’s 3 to 4. We have to jump all the way to 5 choices with the game Rock – Paper – Scissors – Lizard – Spock. Each weapon beats two others and loses to two. The big downside of this game is complexity – I’m not a Trekkie and have no idea how Spock and Lizard are supposed to relate to the others. The upside is that ties are less common. For RPS 1/3 of all games will be a tie, while for RPSLS this drops to 1/5 – good if you want more decisive outcomes.
I wonder how OP calculated the Nash equilibrium for each of those game variants.
I had the computer do it for me :)
Really though, the way to do this is to represent each game as a payout matrix A, which for this category of game will be skew-symmetric with -1/0/+1 entries. Then since this is a symmetric zero-sum game, you find the null space of that matrix, impose the constraint that probabilities must sum to 1 and individually be >= 0, and that gives you the endpoints of the Nash Equilibria. The optimal strategies (could be one unique one for odd n!) lie on the convex hull of those points.
Thanks for writing this. I'm going back to basics on a bunch of this stuff myself as the connections in the AI and ML literature keep heating up. Some stuff from my reading list lately that you might like: https://arxiv.org/abs/2604.27167 https://arxiv.org/pdf/2601.15047 https://arxiv.org/abs/2402.01704
Thanks for sharing! My background is in control theory, and I think the links between it and game theory and dynamical systems in general are super fruitful but woefully underexplored. Writing this was a good excuse to brush up on my linear algebra basics again.