12
\$\begingroup\$

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?

\$\endgroup\$

migrated from codegolf.stackexchange.com Apr 5 '16 at 18:24

This question came from our site for programming puzzle enthusiasts and code golfers.

  • 3
    \$\begingroup\$ There is currently no consensus for questions about challenge writing being on topic on main. I kinda wish they were, but even if so, I think this kind of question is way too broad. If we did have challenges about challenge writing I'd expect them to be more specific like "I've got this idea for a KotH, but I'm worried about the balance of this mechanic. How can I make it work?", or at least something like "What are the dis/advantages of elimination vs. round robin for KotHs?". \$\endgroup\$ – Martin Ender Apr 5 '16 at 17:23
  • \$\begingroup\$ @MartinBüttner I was curious why it hadn't been brought up before, but having seen the one about writing bots, I figured it would be in roughly the same ballpark for type of question, though I see what you mean. Nonetheless, while the actual challenge concepts may be broad, I feel like there is a need of some sort of "guide" of tips to keep in mind when thinking up and writing these sorts of challenges in particular. If this is not the place for it, might there be a better place (perhaps meta)? \$\endgroup\$ – Mwr247 Apr 5 '16 at 17:26
  • \$\begingroup\$ I'm voting to close as off-topic because I think this would be better on meta than main. \$\endgroup\$ – Mego Apr 5 '16 at 17:31
  • 3
    \$\begingroup\$ Could we migrate this to meta if that is the better place for it? \$\endgroup\$ – Blue Apr 5 '16 at 17:31
  • \$\begingroup\$ (I'm not saying that meta IS in fact a better place for it) \$\endgroup\$ – Blue Apr 5 '16 at 17:39
  • \$\begingroup\$ @muddyfish The question Martin Büttner linked to on meta does seem contextually similar, so I would be inclined to think it may at least be a better place. But given that he's writing something up about the issue in general, it probably is best to just wait it out until there's a consensus \$\endgroup\$ – Mwr247 Apr 5 '16 at 17:48
  • \$\begingroup\$ This shouldn't be migrated. The tips on code-golf ones aren't, and this isn't really about the site. \$\endgroup\$ – Rɪᴋᴇʀ Apr 5 '16 at 18:47
11
\$\begingroup\$

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 in 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.

\$\endgroup\$
9
\$\begingroup\$

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.


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 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 ruled 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.
\$\endgroup\$
  • 2
    \$\begingroup\$ About the common pitfalls, which are more loopholes than anything, wouldn't it makes sense to include them in an official meta-post about standard disallowed things in KotH? \$\endgroup\$ – Katenkyo Apr 6 '16 at 6:40
  • \$\begingroup\$ @Katenkyo If there were such a post, then that part of this content would likely be included. For this post, I'm just including the entirety of the tag's wiki. \$\endgroup\$ – mbomb007 Apr 6 '16 at 16:45
  • \$\begingroup\$ Curiously the first KOTH I participated in was specifically for trying to tinker with the other bots. Mind it was done in a sandbox way (no reflection or ASM to work outside the controller) but that each "bot" was actually a series of pointers to submission code methods. And the goal was to inject your "flag" method into other bots (i.e. so that more bots had pointers to your flag-code than other code). It was great fun. \$\endgroup\$ – Draco18s Jun 20 '17 at 17:45
9
\$\begingroup\$

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 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.
\$\endgroup\$
  • 3
    \$\begingroup\$ Or if you can't do cross-language submissions, use a language that's relatively well known, like Java, JS, or Python; something that has a low barrier to downloading a controller and running it. The first KOTH I participated in had a git repo that was just "clone, open in eclipse, run." And be prepared to troubleshoot. Team of the Hill was one KOTH I gave up on because while the controller was available, I was not getting the data I expected from a particular action (an empty array of the area around my bot despite the visualization showing otherwise) and the OP never responded. \$\endgroup\$ – Draco18s Jun 20 '17 at 17:40
  • \$\begingroup\$ This really needs more upvotes \$\endgroup\$ – Redwolf Programs Sep 21 '18 at 3:40
7
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Another solution to this is to have a fixed number of players on each map. If you don't have enough players, duplicate some of them, and if you have too many, then you simply select N of them. \$\endgroup\$ – Nathan Merrill Feb 5 '18 at 22:16
6
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Not disagreeing, but a notable exception: link \$\endgroup\$ – Sp3000 Apr 5 '16 at 17:55
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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

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.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .