Tips for King of the Hill challenges

Question

Inspired by this question, what are some tips you guys have for creating king of the hill challenges? What are some things to keep in mind in the planning and implementing of the rules and the controller, and advice on what makes for a good challenge?

Answer 1

Account for turn order advantage

I've come across a number of challenges that would have wildly varying outcomes depending on who went first (or last) in the turn order, such that figuring out who was actually winning was a difficult task.

As a rule of thumb, if each action a player makes has an immediate effect on the game world (as opposed to the results calculated after the round and applied collectively), be sure to account for the advantage that turn order gives. You could run a large number of matches in randomized order and get the average, or randomize turn order per round (if round based), or offer some sort of in-game balance to neutralize the advantage (like what Settlers of Catan does with initial placement).

Alternatively, you can also write the challenge in such a way that turns are handled simultaneously (the same "world state" is given to each player each round), and then between rounds the changes are calculated. This also has the benefit of allowing for parallel/asynchronous calls to bots, which can speed things up.

Answer 2

The Complete How-To KoTH

1. Have an idea

This is the part I can't help you with. If you're looking for ideas, check the sandbox, chat with others, or check your local board game store.

2. Refine your idea

Figure out what mechanics are interesting. This is a refining stage, so remove as much as you can from your idea. For example, if you've got a fighting-based KoTH, consider removing the maze you are putting them in, or even the grid entirely and make it a 1-on-1.

Things to consider:

• Randomness is your enemy. You want there to be as little randomness as possible. Sometimes you need randomness (such as a random turn order), but remove as much as possible. The more randomness in your challenge, the more games you will have to run to ensure you have the right winner.

• Are there winning strategies? What's a feasible strategy that has a chance of winning? Is there a strategy that counters it? Is there a strategy that can't be beaten? Are there interesting strategies (takes more than a couple of lines to write)? Are there a decent amount of easy strategies?. You want to make the entry bar as low as possible to get people's feet wet.

• Is your KoTH a 1-up KoTH? Figure out what you think the best strategy will be. Is it possible to employ the same strategy, but with a slight offset in order to beat the top submission? 1-up strategies are really common in perfect-information games (everybody can see everything), so perhaps try hiding some information from opponents.

• Post it in the sandbox. Be careful about upvotes here. People like king-of-the-hill challenges, and they tend to get a lot of upvotes in the sandbox. You really need as much feedback as you can get, as flaws are not easily fixed later on.

• How are you going to run multiple games? Which players go in which games? How are you going to combine scores across multiple games? Your tournament structure can drastically change strategies, so consider what you really want.

3. Write your controller

This is the fun part. While you are doing this, you'll probably discover that you missed some edge-cases. Make sure to add them to your sandboxed post, and get feedback on how to resolve them.

Things to consider:

• How are you going to run submissions? This decision will have the biggest impact on how fast each game will run.
  • If all submissions extend a class (or is a function call), response times are measured in micro-seconds
  • If submissions are separate processes, but stay alive between method calls, response times are measured in nano-seconds
  • If submissions are separate processes, and you boot it each method call, response times are measured in milli-seconds

I'm not exaggerating here. I've run my fair share of KoTHs, and spent a fair amount of time trying to get cross-language communication as fast as possible. Cross-process communication is orders of magnitude slower.

That said, if you allow more languages, you are likely to get more submissions.

• Write some sample submissions. You need some submissions to test your code and to provide an example of how to write a submission.

• Make your interface as easy as possible. Make it ridiculously easy to write a submission. Not only should the methods be simple, but consider adding helper functions for tasks that will be common in your KoTH (such as pathfinding or tracking other submissions)

• Test your KoTH controller. I cannot tell you how often I see KoTHs posted with ridiculously buggy controllers. I know you are excited, but please, please test your controller.

4. Share and Run your KoTH

KoTHs need lots of submissions, so try to make it as popular as you can:

Your post should:

• Be brain-dead easy to read and understand. KoTHs are complicated beasts, so explaining your challenge well is critically important.
• Contain a complete walk-through of how to write a submission and run your controller
• Have an image. This can help increase the interest of people reading your post.

You should:

• Commit to running and fixing your KoTH at least once a day for the next week, and every 2-4 days after that depending on how many submissions you get.
• Watch the leaderboards. Make sure that the top submissions aren't changing places on each run-through. If so, you need to increase the number of iterations.
• Open a chat room. People are going to get stuck, and helping them through the comment system is sub-optimal.

Answer 3

Read the tag wiki

The wiki for the king-of-the-hill tag contains useful information and tips for creating KOTH challenges. I have copied the material here, but the information is more likely to be up to date on the wiki itself.

---

king-of-the-hill indicates a game where the submissions interact with each other. The game needs to have well defined rules and scoring, and the goal is to write a maximally competitive program.

Make sure you write your test framework / scoring program before posting one of these challenges. In fact, it is strongly recommended that before posting you upload the test framework, one or two simple example bots, and a build script as a public repository on a site such as GitHub. Then competitors can easily download and build the other bots when developing a new one, and might even send you a pull request with their new bot and its build script. See, for example, https://github.com/pjt33/ppcg36515 , which has a make setup that allows building the test framework and the bots in one step.

These challenges are usually a big undertaking for the host of the challenge, so here are a few common practices.

How to communicate with the bots?

There are several options to realize this. Common choices are

• Players implement an abstract class or interface in the language of the controller. All implementations are added to controller's project and can be interacted with directly through function calls. Example: Survival Game - Create Your Wolf
• Players write a script that can be run from the command-line. These scripts are invoked at each turn and given input via arguments, while their output is read from STDOUT. Example: Caveman Duels (or: Me poke you with sharp stick)
• Players write a script that can be run from the command-line. These scripts are invoked once (and the processes kept running), communication is done via STDIN and STDOUT using persistent pipes. Example: Hunger Gaming - Eat or Die

Hybrid approaches are also an option, which usually increases accessibility of the challenge.

How to handle randomness?

If the scoring program contains (pseudo)-randomness or submissions are allowed to use randomness, this can greatly affect the leaderboard of a single trial. You should either seed your pseudo-random number generator (PRNG) and tell your participants to do the same or you should run a specified number of trials and take the average or median, say, of the individual scores.

Common pitfalls

King-of-the-hill challenges tend to be quite prone to loopholes. Consider including these restrictions to your challenge:

• Any attempt to tinker with the controller, runtime or other submissions will be disqualified. All submissions should only work with the inputs and storage they are given.
• Bots should not be written to beat or support specific other bots. (This might be desirable in rare cases, but if this is not a core concept of the challenge, it's better to rule it out.)
• Reserve the right to disqualify submissions that use too much time or memory to run trials with a reasonable amount of resources.
• A bot must not implement the exact same strategy as an existing one, intentionally or accidentally.

Answer 4

Scale the challenge for the number of players

Many challenges involve a "field" (where the player has a location and may move) or "world" (where the player can interact with and change aspects of the world that affect all players). When incorporating these sorts of play environments, be sure to take into account how the game may change between small and large player counts.

On a field for example, a 100x100 grid might work for 2-10 players, but not so great for 40 players if the challenge gets really popular.

In a world setting, having bots send out commands to change some stat about the world (like killing off "5%" of each enemies forces) might work better at a small scale, but with more players becomes too effective if they all run it at once (20 players * 5% = 100%), in which case, a static value might work better.

One thing to try is making for demo bots to handle a few different play styles, and then cloning them to see how the game changes for larger numbers. Test different situations to find the flaws, then work out the numbers to scale better.

Answer 5

Allow as many bots as possible

Nobody wants to be disallowed from a contest right? Allow as many languages as you can. If someone posts a bot in a language you don't have, try as hard as you can to install it. If you can't? Ask for instructions.

Allow people to post as many bots as they want. This means when they come up with a Super Amazing Idea™ they don't have to worry about changing/removing their other bot from the contest.

Answer 6

Ask for sandbox reviews

I think everybody does that, but it is especially important with KotH. Designing a KotH is like designing a game (in fact, it IS a game), and you might need help to find some flaws in your ruleset or to balance things the right way.

Also, once the controller is written, put the link in the sandbox and try to have some people playing around with it to point-out bugs you may have missed.

Answer 7

FAQs

How big should my map be? As small as possible. There are three solutions here:

• Scaling map. You often see this in the form of "Side length is equal to 5*PlayerCount". Please do not do this. If you want a scaling map, you want X*sqrt(PlayerCount). With the original equation, if there are 100 players, there are 250,000 squares, while only 625 squares with 5 players. The distance between players gets bigger and bigger with more players.
• Fixed size map. I actually really like these. You often combine this with a fixed game size, so this often means that not all players are in all games, or that games will have duplicate players. Both of these usually aren't problems (and may actually increase potential strategy)
• No map at all. Maps are overused. As a comparison to board games, how many games have you played where you are a dude walking around doing stuff? Even games like Risk have a map, but it is drastically different than maps we use in our KotHs.

How do I ensure that games are fast? There are several things you can do:

• Provide fast sample bots
• Provide a fast "helper API" for common actions
• Reduce randomness
• Require same-language submissions
• Place a time limit (submissions must have an average of Xms response time over Y turns)
• Make each turn count
• Cache bot responses. Cache path-finding.

How do I prevent cheating?. Simply mentioning in the post what isn't allowed is all you need.

Who wins?. This is a question people should ask more:

• If A comes in 1st 50 times, and last 50 times, and B comes in 1st 30 times and 2nd 70 times, who wins?
• If A wins 50 times with score of 20, and B wins 30 times with a score of 100, who wins?
• If the top 3 players beat each other in a Rock-Paper-Scissors style, who wins?

How do I get more players?:

• Make the rules as simple as possible
• Add images to your post, especially visualizations of the game in progress
• Make the controller easy to download and run (Remove ALL known bugs beforehand)
• Require all submissions be in the same language (makes it easier to run/modify other submissions)
• Make the post as easy to read as possible.
• Add an easy-to-use helper API
• Add sample bots

I'm having trouble coming up with ideas. Here are some interesting concepts that you can build off of:

• Variable-time turns. Some turns may take longer, allowing other players to do multiple actions.
• Secret-secret knowledge. Your opponents can see some of what you have, but not all of it. You don't know what your opponent can see.
• Alternate roles. Some players have different goals than other players. Those goals can either be opposing, or they can be adjacent (which is often more interesting).
• Multiple pieces. Like in chess, a bot can control more than one "object". This leads to better and more interesting coordination.
• Collaboration. Have certain actions assist other bots. (Consider if people can submit multiple, collaborative bots)
• Real-time bots. Spawn each bot as its own thread, and make the game continuous instead of turn based. (Don't make moves computationally difficult: You don't want people fighting over computer resources)
• Build-a-bot: Allow players to choose characteristics of their bot that persist. (Think Pokemon: Choose stats, or choose abilities, etc)
• Finite resources. Players want different resources, and there aren't enough to go around. Make players choose which resource they really want.

Answer 8

Opponent prediction

In general, a koth is better if there is some level of opponent prediction, rather than perfect info where the result tends to be based on whether someone wrote the ideal bot.

Even if your koth doesn't have perfect info, it can still have an ideal bot. for example, a move with an expected value of 5 is better than one with an expected value of 4. hence there should be opponent variance and simultaneous turns or fog of war, so that you can take the guessing about how your opponent would behave to enrich the metagame.