12
\$\begingroup\$

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.

\$\endgroup\$
  • 16
    \$\begingroup\$ I feel like this depends way too much on the specific problem. \$\endgroup\$ – Fund Monica's Lawsuit Apr 4 '16 at 23:12
  • \$\begingroup\$ @QPaysTaxes I modeled this directly after many of the other tips questions. Is there a way to fix this question to be better? Also, do those older tips questions also need to be fixed? \$\endgroup\$ – mbomb007 Apr 6 '16 at 17:40
  • \$\begingroup\$ The older tips questions are based on languages as far as I can tell, which means that the tips are universal but you might not use them. This question is more analogous to "Tips for Code Golf challenges" – where it depends entirely on the challenge. However, as the answers below prove, there are a few universal things. I'm conflicted. \$\endgroup\$ – Fund Monica's Lawsuit Apr 6 '16 at 18:07
  • 2
    \$\begingroup\$ I think this depends as much on the specific questions as "tips for golfing in (lang)", because you use a lot of different language features in different challenges anyway \$\endgroup\$ – Destructible Lemon Apr 6 '17 at 5:00
4
\$\begingroup\$

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.
\$\endgroup\$
3
\$\begingroup\$

Be specific about the requirements to run your bot

Bots can be written in a variety of languages (and versions of those languages), so it helps everyone out when you:

  1. Test it in the environment the OP specifies (or as close to it as you can).
  2. Test it in a variety of other environments if possible (to help others who want to run it).
  3. Be specific about the language and version you use, and explain how to run your bot.

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.

\$\endgroup\$
2
\$\begingroup\$

If team based, work together with your team

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.

\$\endgroup\$
2
\$\begingroup\$

Use a meta strategy

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.

\$\endgroup\$
  • \$\begingroup\$ including the known behavior of all other bots into your own bot doesn't just border on cheating, it is cheating. I'm fairly certain it's a disallowed loophole. \$\endgroup\$ – mbomb007 Jun 13 '18 at 16:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.