What’s a Game and How Do You Beat It?
This came out in a rush tonight, a dreadfully annoying rush that kept me from getting any reasonable amount of sleep. But still, here it is. Dunno if anything here is new ground or interesting to anyone already familiar with game theory, but it was definitely new ground for me this evening. A dizzying spiral of though prompted by some of my Austin friends discussing A.I.’s built to play Rock, Paper, Scissors (Thanks, Jeff Meyerson, Chris Mabry, Tony Ho, and Nick Lavender). As I worked my way through, much of the material seemed applicable to a Magic and maybe I’ll address that in the future. But right now, finally, I think I can sleep. Probably gonna edit this post later too, get it into tighter shape and shit.
A game exists when one or more players believe they can make strategic choices that perform better than random choice long-term. A game ceases to exist when all players no longer believe they can outperform random choice long-term. This is not to say short-term randomness can not be utilized by a player in a game. In fact, short-term randomness is the default position when none of a player’s strategies suggest a non-ambiguous choice. If the player devises a new strategy to resolve the ambiguity, randomness is avoided and the player is still playing. Also, as long as the player believes that their short-term randomness will produce information that yields a strategic choice that player is still playing the game. It should not be assumed that a player is not acting strategically just because they are being outperformed by random choice. As long as a player believes they can and endeavors to outperform random choice, they are playing the game.
A player cannot be unaware that they are choosing to quit playing the game, as playing is a function of intention not success. A closed game is one that a player can fully quit, i.e. the player is able to excuse themselves from future choice-making and continued impact on the game. Most of what we consider games are closed. An open game is one that a player cannot fully quit, i.e. they are unable to excuse themselves from choice-making and continued impact on the game. In some sense, and with a few dramatic exceptions, life is an open game. Instead, if a player wishes to quit an open game, they must consciously decide that their choices will be made randomly without the intent of making a strategic choice in the future based on events taking place while they have de facto quit. Fully extricating ones’ self from a closed game is non-reversable. De facto quitting within a game (closed or open) is reversable; however, if the quit-reversing condition is strategically informed, i.e. if the quitting player was aware of possible conditions upon which he or she would begin playing and choosing strategically again, the player did not quit, but instead made the strategic choice of short-term randomness.
Because a player can quit within a game while continuing to make choices that effect it, and because an unfamiliar strategy can appear sufficiently random, it is possible to be unaware that a player has quit playing. No matter. Whether they recognize that the player has quit or not, as long as the other player(s) within the game still believe they can make strategic choices that outperform randomness, a game still exists. In other words, any player must assume there is a non-random element to the game from which they can make strategic choices. The point of games is that non-random elements are exploitable given sufficient strategic sophistication.
Some games present an exploitable environment. In chess, without either player knowing anything about the other, the player who is more aware of the strategies dictated by being black or white is at an advantage. Similarly, in poker, without any interpersonal information, the person with the best strategic understanding of position, expected value, and the like is at an advantage.
On the other hand, some games present an unexploitable environment. In Rock, Paper, Scissors for example, there are no inherent advantages to any play and no opportunities for exploitable gaps in strategic understanding of the environment. Without acknowledging the other player and parsing them strategically, a player cannot outperform randomness long-term. Many games are mixed and strategic deficits re: parsing the environment or other players can be offset by strategic advantages in the other. Rock, Paper, Scissors is interesting in that while it is a game, i.e. while at least one player still thinks they can win by outperforming randomness, it is singly about parsing the other player’s past choices in an effort to predict their future ones.
Using Our Understanding of Games to Break Rock, Paper, Scissors
Assumptions:
1. If there is no point at which the game necessarily ends, randomness will negate itself over time and does not need to be accounted for.
2. When our strategies do not disambiguate a choice, the choice should be made randomly within the ambiguous set.
3. Given (1), we should assume that if we are winning, our current strategies are sufficient for winning. While winning, we should not look to adopt new strategies unless that is part of our current winning strategy.
4. Given (1), we should assume that if we are not winning, our current strategies are insufficient for winning. While not winning, we should not look to maintain our current strategies unless our new strategies integrate them.
5. A new strategy that provides a less ambiguous next choice is preferable to a new strategy that provides a more ambiguous next choice, as it is closer to providing a non-random, unambiguous choice.
6. A strategy is any process for parsing past events that yields predictive choices, i.e. choices whose value derive from how accurately they predict future events.
7. A new strategy is any strategy which has not previously been used to predict a future event.
8. A strategy, being definitionally non-random long-term, yields predictable choices.
9. Any correctly predicted strategy is easily countered.
10. Our opponent is operating strategically. If they are not and are not unintentionally non-random (thus presenting an exploitable environment), we can not outperform random. This situation is not worth considering.
11. Given (10), any randomness must be short-term. Given (1-4), short-term randomness should not be accounted for.
12. Given (9-10), our strategy must be correctly predicting our opponent’s strategy and countering it.
13. We can only evaluate whether our opponent is using strategies we are already aware of.
14. Given (3, 12), we should assume that if we are winning, our opponent is using a strategy we are already aware of.
15. Given (4, 12), we should assume that if we are not winning, our opponent is using a strategy we are not aware of.
16. Given (12, 14), we should evaluate which of our strategies, if used by our opponent, best accounts for her or his past choices, then counter that strategy next round.
17. Given (12, 15), we should generate a new strategy which provides our opponent the least ambiguous next choice possible, then counter it.
18. A given strategy is more likely to be too complicated or sophisticated for a player to use than to be too simple for a player to use.
19. Given (18), a simpler new strategy is preferable to a more complicated new strategy, as a given player is more likely to be capable of the simpler strategy.
20. In developing new strategies, we are bound only by our ability to parse past information in different ways.
21. A program for playing Rock, Paper, Scissors is bound by its ability to perceive new ways to parse past information.
22. The primary work of developing a program to play Rock, Paper, Scissors is providing it with ways to procederually generate new ways of parsing past information. Once generated, strategies are easily evaluated re: how well they predict an opponent’s choices.
5 Comments »
Leave a Reply
Billy Moreno
I mistakenly read the following post before coming back to read this one. Hm. Are you suggesting there may be an algorithm to predict outcomes in R/P/S that beats a random selection? If you are on to anything here, it would actually be quite groundbreaking. R/P/S is one of the most textbook examples of random-mixed-optimal-strategies. If you could beat a computer who chose randomly, over 1000′s of games, You’d be on to something. That’d come down to teaching a computer that doesn’t select randomly (using some unknown algorithm, or perhaps its job is to find that algorithm), to beat a computer that does select randomly, and simulating as many iterations as your computing system allows.
If the opponent is committed to random selection long-term, i.e. if the opponent does not and does not intend to at some point make strategically-driven non-random plays, then no, I do not think it is possible to outperform that opponent. I also think that the opponent who is opting into complete randomness cannot be said to be playing the game. Such an opponent is interesting only as a test of how well our A.I. can distinguish an opponent who has ceased “playing the game” (while still making random moves) from an opponent executing a sophisticated mixed strategy. A key evaluative metric of our AI might be “what is the most randomness an opponent can present and still be identified as fundamentally strategic by our AI?” Another important metric, assuming we have a way to quantify strategy sophistication, might be “what is the most sophisticated strategy our AI is capable of distinguishing from full randomness.
Pretty interesting stuff. Your assumptions look pretty solid, the only one that really gave me pause, and that doesn’t sound right to me is (19). I assume that we are capable of both (simple/complicated) strategies we are evaluating. Why does it automatically follow that if our opponent is using a simple strategy that a simple strategy is better at countering that strategy than a complicated one?
Skipped over a possibility. Of the strategies we are aware, it might be equally likely based on past history that our opponent is using either. The set of strategies we are aware of is what we use to assess what strategies our opponent is using, but it is not our opponent’s set of strategies. When picking which to put our opponent on, we are not only trying to be right on this next play, but also to harden our information about their strategy set. It is more likely that they have the less sophisticated one in their set (18), and simpler strategies tend to be less resistant to disproof with new information.
Hey, Jelger. It’s been too long. Thanks for stopping by though. First off, our strategy is only ever to identify our opponent’s strategy and +1 (Ok, I lied. When we can’t unambiguously put them on a strategy, we pick randomly to obfuscate.) The reasoning on (19) is this: It is almost certainly true that an opponent trying to win will tend towards the more complicated/sophisticated strategies available to them. By the time we get to (19), the implication is that we are not aware of a strategy that our opponent’s history shows them to be using, i.e. that they are using a strategy we are not yet aware of, so we slide down our list of tie breaks (which I’ve done a much better job of enumerating in the next post (https://billymoreno2.wordpress.com/2011/12/14/managing-your-bag-of-tricks-how-to-decide-between-known-and-unknown-strategies/).
At this point we are probably looking to intelligently generate a new strategy to evaluate, and since the average opponent is more likely to be capable of simpler strategies than complicated ones (otherwise, what would be impressive about game skill), that seems like a sound default position. On top of that, we are capable of exhausting the set of actual simple strategies much sooner than we can exhaust the set of sophisticated strategies.
On a related note, I’ve added a preference for putting your opponent on strategies such that the prediction will yield more rather than less ambiguous information. I think this preference when used to generate new strategies will yield less (if not the least complex) ones.
But you’re right, (19) is not fully satisfactory. I haven’t added it yet, but I’m rolling something like this around: “We are always comparing the strategies we are aware of to a baseline of random break-even. While outperforming that, we should never need to generate new strategies. While underperforming it, the further down we get, we should probabilistically increase the sophistication of our newly generated strategies.” Or something like that.