Except it is not difficult to prove that you can't win in expectation against a random RPS player. The programming competition is only fun because the players are nonrandom.

Nope, the random player ends up in the middle, on average.

If you'd join a tournament with only random players then your optimal strategy, actually doesn't matter because you're going to randomly win/lose (because your opponents always play random) and on average, end up in the middle rank, just like everybody else.

If there are other non-random players, then you can aim for the middle rank by playing random (and one of the other non-random players will do better than the other, and you will do worse than that one and better than the other). Or you can try to beat the non-random players (while still doing near 50/50 odds on the random ones).

So if you play random, and there is more than one non-random player, you will lose.

Also, check out some of the strategies. There's a couple of really well-performing ones that are incredibly clever, but not all that hard to understand.

One goes like this:

It's based on trying to predict the opponent's strategy and playing against that. But what if the opponent expects that and plays you against that? A-ha but what if you play against your opponent trying to play you?

You'd think that this reasoning can go on forever, but since there are only three moves in RPS, and they circularly defeat eachother, you only need to consider these three steps as the next one brings you to the move of square one.

The algorithm then basically keeps a running score of these three different depths of pre-emptive strategy, and picks the one that works best based on historical moves "what would have won" (and runs random while collecting data).

This algo did extremely well in the first couple of tournaments held many years ago. I don't know what the most popular strategy is currently though.

It just takes one nonrandom player in the pool of players for a more advanced strategy to gain an advantage. Consequently, it is almost certain that, given a tournament of an arbitrary set of RPS players, a very sophisticated RPS player will end up winning, whereas random players will always be relegated to mediocre results.