Tips for King of the Hill bots What general tips do you have for creating a bot to participate in a King of the Hill challenge? What strategies do you use to go from considering the challenge to creating your bot? What data structures do you find most useful?

Please post one tip per answer.
Finding Nash Equilibria

This is a very important concept when the KOTH involves a relatively simple set of decisions, involves only a few players (typically 2), and is deterministic.  A Nash equilibrium describes a "gridlock" position: if the two players have decided upon their two strategies, then the two players are effectively locked in those positions: either player changing their strategy simply creates additional vulnerabilities.

Examples of games where Nash equilibria are important are:


Rock-Paper-Scissors(-Lizard-Spock), in which an "unbeatable" strategy is random play
Morra, which has a "spectrum" of equilibria. Peter Taylor wrote a good example in his answer here.
Prisoner's Dilemma, a cooperative game notable for having an "everybody loses" gridlock


How to find an equilibrium

Finding an equilibrium actually is actually pretty simple for most simple games, and is often pretty intuitive.  A ton of detail about the various methods can be found on the internet.  The basic concept, which is normally applicable, is to create a list of possible strategies that the two players can use (the options provided by the game).  If one strategy is "dominated" by another, then that strategy can be removed from the list, and the process is repeated. By "domination," I mean that if strategy A always gives an equal-or-better result than strategy B, against all of the remaining opponent strategies, then strategy B can be removed from the list.

Example: Rock-Paper-Scissors

RPS has something called a "mixed" equilibrium, meaning that a distribution is involved.  Rather than playing the same move repeatedly (which will lead to quick defeat), the equilibrium is to play 1/3 rock, 1/3 paper, and 1/3 scissors in a random distribution.  If I play randomly, there is nothing my opponent can do to get an edge on me, period.  If my opponent chooses not to play randomly, then that only creates a vulnerability on his part.

Games with mixed equilibrium are probably the most common on PPCG, since they can take many forms (the only interesting game I can think of with a pure equilibrium is prisoner's dilemma).  I should note that the mixed equilibrium doesn't have to be uniformly random, simply something other than playing the same move every time.

Using this information

The Nash equilibrium of a game often represents the "baseline" from which you should try to operate.  In RPS, playing randomly guarantees a finishing spot around the middle of the pack.  In order to move to the top, you have to start identifying other player's weaknesses.

To do this, you should stick to the equilibrium when unsure of the opponent's weaknesses.  Once those weaknesses have been identified (you have detected that your opponent is not in equilibrium), then you need to gently shift out of equilibrium to take advantage of your opponent.  This action, in turn, creates weaknesses on your own part.  You must then detect when your opponent is changing his strategy, so that you can then stop the attack and resume random play.

Detecting variation from equilibrium

This is pretty difficult, and I am not an expert.  Variations can come in many forms:


Favoring some options above/below others for no reason, like an RPS player that plays rock twice as often as scissors, or one that avoids playing paper.  Some relatively simple statistics can detect this.
Basing a current move off past moves, in some predictable pattern.  This includes copy-cats, "beats what beats your last move" bots, or "cycling" bots.  This takes additional logic to detect, since the overall move distribution can be evenly-distributed, even though the moves aren't random.  You should attempt to take the record of moves and find correlations like "the move I made 2 turns ago and the move my opponent made now" and "the move he made 1 turn ago, and the move he made now", etc.
Bots whose move distribution is based off of yours.  The vulnerability in these bots is often not created (in a measurable quantity) until after you have yourself varied from a random distribution.  Generally, your own bot falls into this category.