Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It only takes a minute to sign up.
Sign up to join this community
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.
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:
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:
For almost every clever strategy there's another strategy that beats it: For example, your opponent might use exactly the same reasoning as you to anticipate your next move and then counteract it. Now you might try to second-guess your opponent again, but it's hard to know when to stop.
Another problem is that a strategy that is good at second-guessing a clever opponent might be far from optimal against more simple opponents.
How can you solve this? You let your bot decide on the fly which strategy to use!
For this, you start off with giving your bot a repertoire of different strategies. Then, before each move, your bot looks at the recorded history of the game so far and evaluates how these different strategies would have fared. It then pics the one that would have been most successful.
Including strategies that are strong in the first place will help to give your bot good options to choose from. But you should also include really simple ones, because they often work better against dumb opponents.
You might consider to put a bias on some strategies, either to avoid overfitting (e.g. trying to beat a pattern where the opponent just acts randomly) or to favor certain strategies in the beginning when there isn't yet much information.
Of course, this approach will only work for certain kinds of king-of-the-hill challenges. It did really well for me in a Rock-Paper-Scissors-Lizard-Spock match. In other games it can be almost impossible to evaluate how a certain strategy would have fared if it was not actually played.
An extreme form of this meta approach (that borders on cheating) would be to include the known behavior of all other bots into your own bot, such that it can perfectly anticipate their moves.
Bots can be written in a variety of languages (and versions of those languages), so it helps everyone out when you:
As a bonus: if you are using a lesser known language, make a link to where people can download the binary/source to run it.
While you can usually write a bot that works solo to complete tasks to help your team, there's a much greater advantage when you coordinate both in and out of the game. A prime example of this can be seen in Red vs. Blue - Pixel Team Battlebots.
During development, teams were able to chat and discuss how to coordinate their bots to function better than alone. While technically the same bot, SphiNotPi3000 was written to work in tandem with another of itself, and was able to move in ways that accounted for the weaknesses it would have faced if it were on its own. The end result was that they were able to almost completely dominate the battlefield, even when it was just the two of them against the entire other team.
So outside the game, plan and coordinate with your teammates on what strategies to cover. Maybe someone has a bot that scans the map diagonally? Have yours scan horizontally (just an example). Inside the game, if the challenge allows for team communication, take advantage of it. In the battlebots game for example, you could send a message to your teammates on the position of bots outside their field of vision, and then encourage them to write their bots in a compatible way to make use of those signals.
Making your bot move somewhat randomly, especially if there are multiple options that seem to be equally good, makes it far harder to predict the behavior of the bots. In some challenges, it's even worth having a probability of making a suboptimal move if other bots are designed to take the optimal move, as it makes it less likely you end up doing the same thing, which is a disadvantage in many challenges.
As a bonus, if hardcoding behavior to go after a specific bot or calculating what moves they will make is allowed, randomness makes it significantly more likely you can put up a fight against them.
