Introduction

During my sophomore year at Stanford, I took CS 221: Artifical Intelligence. For the final project, I teamed up with my roommate Harry Sha to build an AI game player for the game: One Night Ultimate Werewolf.

I am very proud of this project - it was such a unique idea but also was easily scopable to build something meaningful in 6 short weeks. By the project deadline, we made two AI game players: one that tried to find the werewolves by detecting lies, and one that played as a werewolf, trying to tell the best lie to evade capture. By pitting these two game players against each other, we were able to accelerate their learning and replicate the complex social interactions present in the game.

Even after we submitted the final version of this project, I continued to work on the game and AI players in the years after, and has resulted in a polished ccodebase and much potential for new features and gameplay. In future posts, I’ll dive into the specific topics I’ve learned about in architecting this Python version of the game.

Building the Game

The first major decision we made was to build both the game and the AI game player at the same time. This allowed us to test the concept of the game player on a very small scale (e.g. 3 Villagers, 2 Wolves), and ensure that neither the game nor our algorithms had any bugs.

We defined all of the statements a character could say (e.g. Player 1: “I am a Villager”) and denoted what information this translated to (e.g. [1, {‘Villager’, ‘Wolf’}]). We allowed the Wolf players to randomly choose another role’s statements to say. At this stage, we found that the AI player was pretty close to random guessing, since no additional information could be gained from any player’s statements.

However, once we introduced role switching and other character abilities, the game got a lot more interesting. The game was no longer easily solvable by the human eye, and understand the game mechanics became much more ambiguous.

AI Game Players

The biggest challenge we faced was completing this massive project on time. To do so, we carefully defined milestones to ensure the project work would progress smoothly. For example, we started off using only simple scenarios with 5 players and 3 roles, and introduced more game mechanics, players (up to 13), and character roles (up to 10) only after we ensured the foundations we built worked perfectly. This incremental development allowed us to make significant progress early on and helped us more accurately estimate our project’s scope.

MaxSAT Solver

The first feature we implemented was a statement consistency solver. This was essentially a custom MaxSAT clique solver. The problem statement was: given a set of statements and players, what is the maximum number of statements can be true at the same time?

We use the solution to this question as a heuristic to figuring out the possible set of roles for each player. While the problems are not exactly identical (for example, the true set of statements may not be the largest set of consistent ones), it is the most likely, given that there are more Village players on the “good” team than there are Wolves on the “bad” team.

Constraint Satisfaction

Using the output of the MaxSAT solver, we receive a list of possible roles for each player. To form our algorithm’s prediction for who is who, we perform constraint satisfaction on eacch of the possible roles sets. We also tried variants of arc consistency to speed up this step.

The approach we used was essentially a DFS over all assignments of roles. There is a lot of optimization we could do here in the future!

Future

Overall, this project represents my best work of Python. In creating the codebase from scratch, I also gained a deep understanding on how to create an optimal development experience - for example, finding ways to cleanly configure module imports/exports, or introducing linting and type annotations to avoid bugs. This project allowed me to take the many theoretical software engineering principles we learned in class and apply these best practices to our rapidly expanding codebase.

Though we formally presented our project at the end of the quarter, I’m still incredibly thrilled to continue working on this project in the years after. Since last year, I have worked on creating a web adaptation of the game using our agents, creating NLP parsers to convert human remarks into machine logic, adding test cases to ensure output consistency, and continually polishing the codebase to make it easy to add new features.

Overall, I am immensely proud of the many directions we were able to take on a single idea, and am still excited by the directions I hope to take this project in the future!

You can check out my progress on the project on GitHub: WolfBot.