FAtiMA, MCTS and Don’t Starve Together
During the last year we have been trying to experiment with using a Search Algorithm over the decisions authored by FAtiMA Toolkit.
The result is the implementation of MCTS over FAtiMA Toolkit that is implemented in an agent in the game Don’t Starve Together.
This is separated across 2 different projects. First the bridge between FAtiMA and Don’t Starve Together was made by Fábio Almeida, which you can find in his Github page. Using the FAtiMA Server.exe you can run agents from FAtiMA when you are playing Don’t Stave Together.
The second project is the MCTS asset within FAtiMA Toolkit. As you know FAtiMA is composed by several different and connected assets, one of them is the MCTS which was created by Ricardo Quinteiro. In order to be successfully run this MCTS asset must be compiled within FAtiMA, its .dll file must be transfered to the FAtiMA server project so that it can then be compiled again. Finally, you will the FAtiMA Server application in the bin/Debug folder of this latter project. You can then have your agents successfully running the MCTS by using its Dynamic Property in its Decision Making Process. Here are the resources to execute all of this:
- Fábio Almeida’s Thesis
- Ricardo Quinteiro’s Report
- FAtiMA Toolkit with an incomplete version of MCTS (looking at you IAJ students), updated 12/12/!9
- FAtiMA Server
Steps to follow:
- Use FAtiMA Toolkit to develop your MCTS algorithm (Assets/MCTS)
- Test the algorithm using the MCTS Tutorial program
- Once you are confident about it compile the project and copy the MCTS.dll file generated (Assets\MCTS\bin\Debug) and put on the FAtiMA Server project (FAtiMA-DST-master – hineios\FAtiMA-toolkit) where all FAtiMA related files are kept.
- Compile the FAtiMA Server Project and then run the generated FAtiMA-Server.exe file (FAtiMA-DST-master – hineios/FAtiMA-DST-master – hineios/FAtiMA-Server/bin/Debug).
- Run Don’t Starve Together and test your implementation, look at both the console and Walter to understand what’s happening.
Please note that the linked FAtiMA Server application is running a proper and working version MCTS algorithm. Once you’ve copied over and changed the MCTS.dll file it will run on your implementation of the Monte Carlo Tree Search.
In order to better understand what exactly is happening, let’s now take a look at exactly what each component shown in the figure above is passing around information. Here is how a simple Environment->Agent->Environment loop works in this case.
The first thing to do it to launch FAtiMA Server.exe, this program loads the scenario and its characters (as in, Walter), once this is completed the server starts listening in on port 8080. Afterwards we need to start a Don’t Starve Together game, with the Walter AI Companion mod activated:
As shown in the image above, in its current state, the FAtiMA Server, for each entity around the Player, let’s say a Pine, stores around 20 different beliefs about it:
||Defines an entity what they are (prefab)|
||Defines how big is the stack (quantity) of a given entity|
||True if the given entity is pickable (collect natural resources). PICK action|
||True if the given entity can cook other entities. COOK action|
||True if the given entity can be cooked. COOK action|
||True if the entity may be eaten by the curent character (it takes into account the character’s diet). EAT action|
||True if the given entity may be equipped. EQUIP action|
||True if the given entity may be used to fuel stuff. FUEL action|
||True if the given entity requires fuel to function. FUEL action|
||True if the given entity can be used to grow seeds. PLANT action|
||True if the given entity is ready to be harvested. HARVEST action|
||True if the given entity is pickable (pick stuff from the ground). PICKUP action|
||True if the given entity can take other entities to cook recipes|
||True if the given entity is workable by an axe. CHOP action|
||True if the given entity is workable by a shovel. DIG action|
||True if the given entity is workable by an hammer. HAMMER action|
||True if the given entity is workable by a pick. MINE action|
||Defines the X coordinate (value) of an entity|
||Defines the Z coordinate (value) of an entity|
Here there is a some room for optimisation. If you take a look at saved characters, you can see just how large their knowledge base is, which is somewhat unnecessary. Taking a look at the FAtiMA Server program and its classes will give you an insight on how this process is done and how to change it.
The Decide() method makes use of the agent’s Decision Making Module. This module uses Decision Rules to compute a list of possible actions and its json file ends with a “.edm” extension.
You can learn more about the Emotional Decision Making Assert here.
I won’t get into much detail but what is important here is that Actions have conditions and that you can “run” functions within those conditions to generate the final action. To use MCTS you have to do this, essentially using a Meta-belief, the Decision Making Asset should only have one decision rule that looks like this:
Action: [a] Target: [t] Layer: Behaviour Conditions: MCTS([a],[t]) = True
Essentially it says that the agents wants to execute action [a] towards the target [t] when the MCTS algorithm returns something. That something is exactly what is the value for variable [a] and [t]. It works similarly to the out parameters in C#
The idea is that the MCTS algorithm goes through all the actions and targets and once it finishes it “spits out” the best possible action: [a] with the target [t]. All of this process is done within FAtiMA Toolkit.
It is up to you to complete the MCTS asset within FAtiMA Toolkit. You can find the asset within the “Assets” folder. Take a look at the classes within its sub-folder “DST”. Here you can find the classes Ricardo worked on, including his representation of the World, some of the actions he programmed and the MCTS algorithm. You can change any of them and hopefully improve them.
The actions you “create” must be compatible Don’t Starve Together, you can go to Fábio’s oficial Github page to see how they should look. Additionally if you make any improvements to the FAtiMA’s Server program feel free to submit it to that same Github repo.
Here is how the whole loop ends:
Is your character is getting stuck?
Are you tired of following it around?
Great, you’re doing something right!
In order to facilitate the debugging and testing process, Fábio made it possible to have only one character loaded in the game whose brain can be turned on and off. If a Don’t Starve Together game only has one character the camera automatically follows it and, in turn, makes the testing process way easier. Additionally, turning the brain on and off might also help when a character gets stuck in its decisions and perceptions.
To do this simply go to the Walter – The AI Companion configuration options and change the number of characters to 0:
Once you load the game with the Mod enabled and after choose your character, only one character will be loaded in, yours. Now we need to activate its brain. You can do this by simply pressing the brain icon, as shown in the image below:
Once you’ve clicked the brain and if you have the FAtiMA Server running the character’s decision making and appraisal will be controlled by FAtiMA, according to the .rpc and .edm files you’ve provided the Server with.
The camera will follow the character automatically, and, if the character gets stuck you can turn off the brain, wait for a bit……, and turn it on again. (the icon won’t change colour but it will stop “pulsating” when its turned off).
Changing the time between Decisions/Perceptions
Is your character having trouble dealing with too many decisions in too short of a time? That’s pretty good, it is actually doing something.
There are several different ways to change the time the agent is taking to make decisions and to collect perceptions. Ideally, the server would handle this part, however, for now, the server is listening to what the mod is telling it to do including making decisions.
The easiest way to change this is to change the mod itself, and that means altering its .lua files. Wait wait don’t quit just yet, this is pretty simple. All you have to do is to open the fatimabrain.lua file, with almost any text editor, and change the value of its variables:
local SEE_DIST = 21 local SEE_RANGE_HELPER = false local PERCEPTION_UPDATE_INTERVAL = 2 local DSTACTION_INTERVAL = 4 local SPEAKACTION_INTERVAL = 10 local SPEAKACTION_PROB = 40 local NUM_SEGS = 16
How easy was that?
Now you need to make sure that you change the correct “fatimabrain.lua” file, the one that Steam is using. Steam stores its games and mods in the folder: “steamapps”, for instance in my case it would be: “Steam\steamapps\common\Don’t Starve Together\mods\workshop-1339264854”
Mods and anything that comes from the workshop is saved with the name “workshop-random11digitnumber”. Once you’ve located the correct mod folder, “fatimabrain.lua” will be under: scripts\brains. Edit that file, save it and run the game with the mod loaded (you might have to start a new server).
What is the baseline?
In order to test if the algorithm is working, for each run of the characters, a new world was dynamically generated with equal sets of constraints for both characters. The characters were then let run for as long as possible until their death.
“Artificial Wilson was created for the original game, Don’t Starve. Therefore it is incompatible with Don’t Starve Together because of the updates made to turn it into a multiplayer game. However, the game mechanics and configurations remain the same. As such, we can use the scenario configurator to generate equivalent worlds.“
We considered the following restrains:
- A world with no enemies: all aggressive monsters have been removed from the game as well as the giants.
- No random meteorological events: apart from raining all other events have been disabled (like meteors, frog rains, lightning storms, and wildfires).
- No resurrection stones: if the NPC dies, it stays dead.
- No mating season for beefalos: during this season these, normally pacific creatures, will attack any character on sight.
- No modifications: apart from the necessary ones for running both characters.
- Only one NPC and no players: while in Don’t Starve this does not apply, in Don’t Starve Together the tests were run locally with no players present in the world.
There are several approaches to this problem, using the constrains we’ve mentioned, here is a small comparison between some of them:
|Name||Agent’s Decision Making Approach||Days survived, on average|
|Artificial Wilson||Behaviour Trees with 70 nodes||8.9 days|
|Walter||19 Decision Rules||1.8 days|
|Revised Walter||19 Decision Rules||3 days|
|MCTS Walter||MCTS Algorithm||3.5 days|