-
Notifications
You must be signed in to change notification settings - Fork 2
Timeline
Implemented the Ford-Fulkerson Max Flow algorithm only to realize that it doesn't actually handle probability distributions. I probably need one of these algorithms instead: https://stackoverflow.com/questions/16762231/ford-fulkerson-algorithm-with-weighted-edges
Forgot where I left off, but I made a function to print out probability distributions cleanly.
Similar to Tesla's ability to find specific training examples, I think it should be possible via my framework to query for certain games (e.g. games where a Hunter chooses the Wolf, or games where the Insomniac becomes a Wolf). I'm not sure what the best way to implement this would be (maybe tag certain events during one_night?), but I think it will be necessary to progress the game further.
Added the Doppelgänger!
Been a long year, but finally back to work. I refactored a bunch of files, cleaning up const.py, creating new util and enum modules, removing original_roles, and adding a bunch of new tooling. Onto next year!
Preparing adding the Doppelgänger at some point. It's really complex logic, but should be really interesting to develop.
Wrote a rough draft of the relaxed prediction engine. No idea how well it works, so probably need to invest in some more testing infra.
Finally fixed all of the Deepsource bugs by removing the os.system("clear") calls.
Spent this month working on the Workshop and writing an implementation of a Max Flow algorithm. I should be able to import the algorithm and Graph implementation here to use.
Continuing work on the relaxed solver prediction engine.
Created a basic version of the companion prediction engine for the relaxed solver. Mostly Python 3.9 updates this month.
Finally got the relaxed solver working. It returns a list of all solutions instead of taking the most likely one using the largest consistent subset heuristic. The goal is to migrate this heuristic to the prediction engine, which will be able to use probabilities to better assign roles to players.
It is theoretically possible to frame the prediction engine as a Max Flow problem, to solve the bipartite graph question.
On the left side, we have available roles. On the right side, we have the assignments that we need. We create a source and a sink node. The source to the available role has edge weight equal to the number of that role available.
To implement this, I need:
- An efficient graph implementation
- Max flow algorithm
- Foundational rewrite of test cases to test functionality rather than implementation.
Framed the prediction engine as a max flow problem, which seems like it would work in the general case, but not as well in my case, since most of the frozensets only contain 1 role at that point.
Refactored the project to use absolute imports and enabled LRU caching, which helped speed up many simulation iterations, from around 34 sec per run to 13 sec for the multistatement Expectimax Wolf. The caching both type-checks and correctly clears itself during unit testing. I also experimented with using bits instead of frozensets. Migrating was tricky, and for some reason it turned out a lot slower than the original. Switched from role strings to Role enums, which also took a performance hit, but the clarity is quite worth it.
Reworked how random numbers are used in unit testing, such that the same random number is generated every time, which makes it much easier to make changes without breaking all of the test cases. Removed all code that generates random numbers in an infinite loop.
Introduced Deepsource to the project to catch and automatically fix some of the more complex bugs to catch.
Finally got a working version of the interactive mode. Players can choose an action, make a statement, vote on the Wolf, and the game correctly clears the GUI at the right times. Created several new classes, including KnowledgeBase, OneNightLogger, and GUIState. Refactored the Expectimax code in order to integrate with the Player classes more easily, and rearranged the files so that all players have access to the Expectimax algorithm. Added the overrides package to clarify the relationship between methods in the Player class.
Used a priority queue to allow a randomized multistatement ordering.
This month marks the great FrozenSet refactor, which included converting the fields of every Statement fixture in the project and rewriting a lot of tests and classes. The benefits of this change were substantial, as using the same type everywhere allows stricter type-checking, faster runs, and consistency across the project thanks to a few forcibly-made regexes.
Additionally, I finally found better ways to refactor the switching solver to avoid nonlocal variables, and more optimized parameter passing to make it very efficient. Overall, these optimizations converted ~13 seconds into ~2 seconds for 100 games, which I'm very happy with. The entire ecosystem of profiling, type-checking, unit and integration testing, and linting is all working to make this project the best Python code I've ever written.
Made more progress on Interactive Mode, which is helping me see how a human would play the game and what oddities are there in my implementation.
Mostly updated requirements and added additional tooling to make style maintenance easier. Black + isort is my new standard for code formatting, and that has saved me a ton of time instead of getting every little detail perfect in this codebase. I think that was important for my learning early on, but now I'm happy to just let the formatter do its thing. Also added code coverage badges and cleaned up a lot of the testing and flows in the project, particularly around replays.
Moving some directories around, with the goal of making it simple to run WolfBot configs and commands from a single client-facing Python script, and being more intentional about client-facing exports. Added a pre-commit git hook to run unit and integration tests before every commit. Tried the cached solver again, framed as the 0-1 knapsack problem, but ran into two difficulties: I have to use a top-down approach because I cannot enumerate all possible states (I don't have weights), and I have to explore separate cases for when a statement is added vs negated and added. Ultimately a dead end, but I still think there's some optimizations to be done.
Worked with Harry on the solver, and translated into a problem about finding cliques, which we know for sure is NP-hard. Unfortunately, I didn't solve P=NP on this project. But that does give us a lot of approximation algorithms to try!
Experimented with fixtures in other files and randomizing integration tests. I also removed several uses of deepcopy in the project and sped up the runtime immensely. Finally, I added a profiler! This project is the first that every small change results in a big performance boost over millions of simulated games.
Still testing, working on the tail end parts of the game (predictions, encoder, and voting). Redid the role initialization yet again using the class method decorator to follow more Pythonic conventions. I also added docstrings and the static method decorator to all test file methods to finally silence all of those Pylint warnings.
Spent a bunch of time setting up test stubs and preliminary tests for all files in the project. Getting ever so slightly closer to the goal of knowing when parts of this project is broken and being able to better notate the requirements and design decisions behind some of this code.
In writing so many tests, I've already found a bunch of important improvements and bugs; for example, making the Statement and SolverState classes immutable, since when operating with them, I never want to modify an existing state, but rather always return a new one. I made their constructors take lists and sets as input and automatically convert them to tuples or frozen sets, echoing some of the enhanced Redux state design patterns I've seen, thus making constructing a new state easy.
Started working on this project again. The main blocker for adding more functionality is the lack of testing I currently have. Without solid unit/integration tests, it's really easy to break or change existing functionality silently. So, I have decided to begin using Pytest as a framework for writing unit tests for the existing code. The test/ folder is intended to follow the folder structure of src/, and will import accordingly. To accomplish this change, I had to change many of the imports to explicitly start from src/.
Additionally, to aid this effort, I have also decided to introduce type annotations for all function declarations (return-type and parameter-type annotations), which I believe will make the test writing process a lot easier. I decided to use Facebook's Pyre as a fast type checker, which together with Pylint has helped me find and fix a lot of poor design decisions in my code.
Changed all interpolated strings in this project to use f-strings, which are intended to be much more performant and readable, even in logging scenarios.
Tried using a Dynamic Programming or Greedy Algorithm for switching solver, but it wasn't too successful. I'm not 100% sure that the greedy approach to consistent statement selection works all of the time.
New features! Made Multi-Statement semi-stable, but right now all roles just ignore the extra information given before the final statement. Ideas for big integration testing - I could have a fixed accuracy threshold needed to pass each test when certain features like Expectimax Wolf or Multi-Statement are enabled. I would also love to have different confidence levels for each character, like a probability distribution or something.
Interactive Mode and Hunter added! Working on multiple statements next, but I need to plan it out a bit more before I try to implement it. I plan to branch off of master to get a proof-of-concept working first.
Added the Minion and Tanner characters and fully integrated them into the game! I changed a large portion of how voting works and how possible statements are obtained (now, saying you are a Wolf is not necessarily a bad idea). I have a lot more ideas to move forward with as well - for example, drawing out file dependencies and finding better representations, using some unit testing to make sure everything works as expected before expanding the game, and using the new Python 3.7 type-checking. Overall, the game looks like it's in a stable state, and the Werewolf and Tanner teams look like they have the advantage. Time to start thinking of more advanced Village team tactics!
Started the basic framework for the Minion character. Currently working on other projects, so I will return to this project later.
More Wolf updates - I updated the Expectimax algorithm and changed the statements Wolves use. Fully tested all Wolf types and finished Pylint refactoring.
Major refactoring update and Single-Wolf Voting added! The next primary focus will be on getting a conversation between roles - each character has more than one statement and is able to convey different types of information. This will enable us to give varying confidence levels to Wolf accusations, and even allow us to add more evil roles, like the Tanner and Minion. By rough estimate, with 12 roles, there are roughly 250 million different games that can occur (role assignments, and then switching scenarios). This is sufficient reason to develop AI that can face this challenge, and the introduction of multiple statements will only push this number higher.
Presented the final iteration of the project with Harry at the CS 221 Project Fair. Good feedback overall, main points moving forward may be looking into using the minimum expectation for the Wolf players, adding new statements from each player (more than one round of speaking), and adding wildcard characters like Minions and Tanners. More to come!
Much progress has been made after only a week of working on this project.
Our main update was introducing the Wolf AI to the mix. The goal here is to develop the two AI in parallel - every time the Good players get smarter, the Wolves gain more trickery and better plans. Each AI has access to the same solvers, and as such can run their own games and gain their own experience to make better predictions. Entirely possible the AI players get so smart they develop their own game meta that humans cannot logically understand, but that hasn't happened yet, so we're fine.
Harry introduced the Expectimax Wolf player, which after my modification to the set of statements it considers, functions extremely well in avoiding detection, and finishes running with decent efficiency over 1000 iterations.
First thoughts to make an AI that can play a game of One Night Ultimate Werewolf. Developed as part of a project for Stanford's CS 221: Artificial Intelligence course. Main focus for this project is on incremental development, introducing new roles and new game mechanics slowly to ensure all scenarios are covered and interpreted optimally.
First steps were to recreate a simplified version of game in Python. We initially only used 5 characters in the game: Villager (x3), Wolf (x2), and Seer. In one_night.py, we randomly assign roles from const.py, have night fall, and then have each character give a statement about what they did during the night. Emphasis on making code expand naturally, minimizing refactoring.
Next, we made a solver for a set of statements from each player. Majority of the work here goes to Harry for introducing a Consistency verifier for Statements, and creating the Baseline Solver.