Crowning a King: Intro to KOTHs

One of the most popular challenge genres on PPCG is king-of-the-hill. In these competitions, points aren’t awarded for brevity or speed, but from bot-on-bot combat. The challenge author lays down the rules of a multiplayer game, and users compete to write the best “AI” to play against the other submissions in a tournament.

Styles of KOTH

KOTHs come in several styles (which can overlap), the most notable of which are listed here:

• One-on-one round robin: The most common format in which each bot competes against each other bot in 1-v-1 matches. Examples: Samurai Showdown, RPSLS, BattleBots, also many of the KOTHs listed below
• Small group: An extension of one-on-one, but obviously with more players in each match. The number of players in each match is fixed. Example: Four-Man Standoff
• Large group: All bots compete in a single large game at once, and the bot that wins the most games / has the highest average wins the tournament. Examples: Strategic Voting, Cake Cutting, Zombie Apocalypse
• Teams: Users are divided into teams, and all of the bots on a single team work together. Examples: Red vs. Blue
• Abstract Game: No concept of “movement.” Includes board games (chess, etc.), rock-paper-scissors, card games, etc. Examples: Traders to the Death, Prisoner’s Dilemma, Caveman Duels
• Arena: The bots compete on a map, which they must navigate. Typically involves more video-game-like elements. Examples: Hunger Gaming, Create Your Wolf
• Custom Language: Bots must be written in a specific language, which serves as a core gameplay mechanic. The controller typically interprets these custom languages. Examples: the Code Bots series, Nano Core War
• Asymmetrical: The game has two distinct roles, such attacker vs. defender, and each bot is targeted to a specific role. A game is run for each attacker and defender pair. Example: Catch the Cat
• Character Creation: Users not only write their AI, but also have a hand in determining the in-game stats and abilities of their bots. There is typically a wide range of abilities of choose from, leading to a very wide variety of strategies. Examples: Codémon, Battle of the Fellowships, Petri Dish
• Web-Hosted or Stack-Snippet: The controller and bots does not have to be downloaded and compiled/run, but rather the tournament is viewable from a web browser. Examples: Bot Flocks, Spacewar

What is a controller?

The controller is the program responsible for running the tournament. It handles the internal game mechanics, communicates with the entrants, and calculates the overall rankings. The controller is written by the challenge author specifically for a particular challenge. The challenge author is also responsible for downloading/running all of submissions, performing the “official runs” of the controller with those submissions, and periodically updating the challenge with a leaderboard. The KOTH genre is the only one which requires such a close interaction between the contestants and the host.

How to host a KOTH

King-of-the-hill competitions are some of the most labor-intensive to host. Unlike most genres, such as code-golf, there is a high barrier-to-entry for KOTH hosts.

1. Come up with an idea for a KOTH. Board and video games are the primary sources of inspiration, although sometimes challenge authors aim for more exotic types of KOTH. You should attempt to outline the core rules and goal of the game.
2. Sandbox it as soon as you can. KOTHs require a lot of incubation time. In this period of time you should ask for feedback on the core concepts, while also finishing up all of the rules of the game itself. Once you’re done with this step, you should know the rules of each game round, ideally to the point that you could hypothetically play a round in real life.
3. Decide upon your style of implementation. Can bots be written in any language, with the controller communicating via STDIN/OUT? Will bots be written as classes in some common language, using function calls to communicate? Each has pros and cons in terms of speed and accessibility.
4. Begin writing a controller. It is generally helpful to see how previous controllers were written, and/or ask permission to reuse code from a previous KOTH. If you are new to KOTHs, this is a good time to look at inter-process communication, if that’s the route you want to go.
5. While writing a controller, you will finish writing the detailed rules of the competition, including the communication format and how the overall winner is determined. At this time, your challenge spec should look almost complete, minus a link to the finished controller.
6. Once you finish a controller, now is probably the time to review the tournament structure, communication format, and game rules. At this time you should not need to make any major changes.
7. Write several example bots which try out several strategies. Examples include random bots, bots that continuously attempt the same move combo, bots that min-max their stats (if applicable), as well as your attempts at writing smart bots. This will test your controller, but will also let you know what to expect when you run the competition. You should note any strategies that you believe are over-powered, since you still have time to do some balancing.
8. Once the controller is in its final state, publicly upload it to some file-hosting site, GitHub being the most popular choice. Attach a link to the controller in your spec. At this time you should set tentative start/end dates for the competition.
9. Once you have proofread your spec and feel comfortable with it, and are ready to host a competition, you can post the challenge. You should attempt to clarify/edit the spec as soon as any questions arise, as to minimize the amount of editing done once people have already started writing bots. You should also post some example bots as answers to help seed the competition.
10. Your work isn’t over once you post the challenge. It is recommended that you “run the tournament” as often as you can, so that people know their current standings. This period can go on for a couple weeks.
11. Once a couple weeks have passed and the flow of new bots has died down, you can choose to run the final tournament, the winner of which is the overall winner of the tournament. Many KOTHs never have an official “final run.”

Tips for Writings KOTHs

If you are planning on writing KOTH for PPCG, and haven’t read the tag wiki yet, please do so, since it outlines a couple common pitfalls that challenge authors may fall into. Some of these, and others, are also covered by Standard Loopholes, the existence of which you might want to explicitly mention in your challenge spec.

• You should probably explicitly disallow various forms of tampering with the controller or interacting with other bots.
• You should also probably prohibit strategy-stealing (a user writes a bot by copying the strategy of another), or targeting (a user incorporates knowledge of the other bots into his code, so that his bot can predict/identify its competitors). Back in the early days of PPCG, I used that latter strategy to much avail to sweep a particular KOTH.
• Figure out how randomness is handled. If there is a PRNG involved, strongly consider seeding the generator to ensure replicability. Also run a large number of games (each matchup multiple times), so that each individual random event has a minimal influence on the overall ranking. If you run the tournament twice with different seeds and the rankings are significantly different, then you probably aren’t running enough games to determine the true winner.

A couple tips for challenge hosts are explained in this meta post. The main tips from that thread, paraphrased, are:

• Make sure there the game is neither strongly advantageous nor disadvantageous to players based on their turn order. A bot that moves first can have more influence over the game, while a bot that moves last can have an informational advantage. (link to original tip)
• Try to be as inclusive as possible to new submissions. Ideally people who only have experience in a single language can compete in the language they know. Also, allow people to submit multiple bots with different strategies, as long as there is no teamwork between the entries. Sometimes language and answer-count restrictions are unavoidable, or even a core component of the challenge. (link to original tip)
• Consider your tournament’s scaling. Be prepared for anywhere between 5 submissions and 50. Particularly if you are doing a large-group arena battle, you should ensure that the map density is not too small/large no matter the number of participants. (link to original tip)

Resources for Hosts

By far the best resources are people who’ve already hosted KOTHs. Ask and an answer you shall receive. For controller-writing, consider basing it off of someone else’s controller. One resource to note is Nathan Merrill’s KoTHComm, a framework for KOTHs which allows for a wide variety of maps and tournament structures.

Tips for winning in KOTHs

One thing I recommend for competitors is to run tournaments locally, so that you know how well your bot will perform before you submit it. You can even have a wide number of your bots compete against each other, so you know which one is the strongest one that you should submit to the tournament. Other ideas include:

• Break out the math. If there’s any way to compute “expected values” or determine the Nash equilibrium, then do it, because this knowledge is very useful in finding good strategies.
• Genetic algorithms. If you create a bot whose strategy is determined by some collection of parameters, you can write a genetic algorithm of optimize those parameters.
• Bots that learn. You can use statistics and pattern-recognition to predict the most likely next moves of the opponent. Just be cautious of other bots which will do the same to you.

Some tips for competitors were mentioned in this closed question. In particular, check out my answer regarding the usefulness of Nash Equilibria.

About the Author

PhiNotPi is a long-time member of PPCG and has hosted several KOTHs.