Competitive Coup Bot
Coup is a relatively well known social deduction card game where players must attempt to eliminate the other players by lying and call bluffs until one player remains.
The lying aspect makes it hard for humans, but even harder for computers to play as you can't simply brute force search all possible future game states as a chess engine might.
In 2022, SYNCS (the USyd CS society) worked with SIG to host a bot battle competition for Coup. I teamed up with James to participate in the bot battle (and we won 🎉).
Our bot "Alpha Coup" won 70% of games, each a battle between 5 different teams.
Overview of Strategy
The development of our strategy was split into two distinct parts that were designed to be non-overlapping, but heavily dependent on each other.
Firstly, James built an engine of the entire Coup game that allowed us to simulate games between bots locally.
It was then my job to use the Coup engine to develop and compare a number of strategies by implementing a generic Bot interface that James has exposed.
For a detailed explanation of the strategy, check out our GitHub repo (which also contains the source code).
Bot Science
Creating a bot is more than software
Having participated in a few bot battles now, I find them to be quite a different beast compared to regular software development.
Typically, when working at a company, there are a list of features that mysteriously end up on your lap and it is your job to implement them. Implementation tradeoffs need to be considered, but many hard decisions have typically already been made by the time you hear about it.
At somewhere like a hackathon, you additionally need to be part of the team that decides which features to implement. A typical strategy is to plan and execute an MVP, with a list of stretch goals to be attempted during any remaining time.
When building a competitive bot however, not only do you need to decide which features to make and how, but you also have no idea what features will actually work until after they are developed. Also, testing a feature in the real world will expose it to your competition, at which point copying you becomes fair game.
If you could figure out which strategy was best from just thinking, you would just spend an hour writing up the code and submit it right near the end. Unfortunately, this is never the case.
Evaluation-driven development
Given these extra complexities, evaluation speed and accuracy should become a priority.
If the bot battle does not provide a local environment to test your bots, one of the best ways to achieve fast evaluation is to write a simulation of the game environment that will allow you to compare bots locally. While a simulation provides you with a huge evaluation speed advantage (often 100x), accuracy is sacrificed in the process.
For this reason, the first step after a building local simulation should be to develop a number of feasible simulated competitors that your testing framework can randomly sample from. You should aim to think of strategies that are likely to be common among your competitors, such that any bot which defeats them is likely to defeat the real competition. Overfitting is always a concern here.
After this, your goal is now to do science.
- Develop hypotheses (theories about which strategies would beat others)
- Build experiments (write the bot)
- Measure results (evaluate the bot using the simulation)
- Repeat with your new learnings.
Many hypotheses will produce null results, but occasionally you will gain a percent of win-rate. Over time, these percents will stack up and your competitors all playing on the public leaderboard will be none-the-wiser.
One important technique I will mention here is to occasionally throw in historical versions of your bots to the simulated competitor bot pool. It will reduce your simulated win-rate, but reduces overfitting and creates more realistic competitors. This is similar to self-play that was used to create AlphaGo.
A number of techniques like this are discussed in our strategy write-up. Ultimately, the key takeaway here should be that bot writing is equally a science as it is (software) engineering, and it should be treated as such.