Bots are no stranger for the community. While most would have a negative connotation on them, gaming bots are used to keep up with players. Examples of their vital usage is having an NPC companion in-game. What if I told you that bots can defeat human players in multiplayer hidden-role games?
Well, this is already happening. Beginning of this year, members from the Carnegie Mellon University developed the world’s first bot that can beat professionals in multiplayer poker. There are also bots defeating chess players and other cooperative games, in which the bot knows its opponents and teammates from the start.
Next month, MIT researchers will present DeepRole, the first gaming bot that can win online multiplayer games without information on the players’ roles. This will be held at the Conference on Neural Information Processing Systems.
This is an über-cool paper from those cats @MIT. Using DeepRole they have managed to train a gaming bot to beat human players in the online version of the hidden role game: 'The Resistance: Avalon': https://t.co/v6LAYZoWxG pic.twitter.com/XJYXdC2qg0
— Sam Illingworth (@samillingworth) November 21, 2019
The bot has deductive reasoning added into an AI algorithm commonly used for playing poker. This way, the bot can reason with partially observable actions and determine what side a player might be in. By doing that, it can determine its allies and next moves in order to make the team win.
DeepRole played against humans in more than 4,000 rounds of the online version of The Resistance: Avalon. This popular tabletop game requires a lot of deduction skill as players try to unveil who are their allies and enemies. DeepRole was able to play on either side, and ultimately defeated human players.
More than just gaming bots
While it may seem that the bot was used just to play games, the project’s long-term goal is to create a better model of how humans make socially informed decisions. This could help better robots that understand and work well with humans.
With this in mind, MIT utilized games like Avalon that can test out deductive skills to reflect everyday decision-making. This of course includes finding out who is on your team, and who is not.
The Resistance and the deductive bot
To the uninitiated, The Resistance is essentially a multi-player card game in which three players are randomly and secretly assigned to two teams. The number of rounds would vary according to how many people are playing. Each round pertains a mission that only a few members would participate in. The group must then discuss and vote as to who would take part in the mission.
Each round, it is ideal that the group must send out members of the resistance in order to succeed. However, if a number of spies are able to feign as a resistance member and get into the mix, the mission will fail. That’s where the hard part comes in.
Hidden-role games are a challenge for multi-agent systems since unlike Dota or Quake, players first need to figure out who to cooperate with and who to compete with. We trained our agent (DeepRole) through self-play by enhancing CFR with deductive reasoning about joint beliefs.
— Max Kleiman-Weiner (@maxhkw) June 7, 2019
The main goal for the resistance team is to identify who are spies on or before the end of the game. Meanwhile, the spies must remain unidentifiable until the end. Basically, winning the game is about deducing members of each team, deceiving the other team, and ultimately strategizing to win the game.
This tabletop game became so popular that it spawned different versions, including the Avalon version that DeepRole played with. The program was able to learn how to play the game using a game-planning algorithm called ‘counterfactual regret minimization’ (CFR). This method consists in learning to play a game by repeatedly playing against itself.
With each game, CFR creates a decision ‘game tree’ of lines and nodes which can point out possible future actions of each player at future decision points. The bot looks how each person played at each mission and makes its comparison to the game tree. This way, factors such as inconsistent decisions can help determine the player’s role.
Happy to share what we’ve been working on this year – an agent that can play Avalon at Human-level performance. It can find cooperators in adversarial environments to win the game in a variety of team mixtures. https://t.co/ehPMBu3FnF
— Jack Serrino (@Detry322) June 7, 2019
The algorithm would simulate the game for approximately a billion times to know which actions will lead to victory or defeat. This will also help in analyzing the proper strategy and decisions to make for it to win. It ultimately plans an almost foolproof strategy that the worst thing that can happen is tying up against any opponent.
So far, the program works well for games that have public actions like poker or chess. However, it struggles when the actions deal with what MIT Postdoctoral Fellow Max Kleiman-Weiner calls as “imperfect information”.
Communication within the game
A game like The Resistance relies heavily on communication to strategize. Interestingly enough, the bot didn’t communicate with the other players while playing. “But it turns out our bot was able to work well with a team of other humans while only observing player actions, this is interesting, because one might think games like this require complicated communication strategies.” Kleiman-Weiner says.
For the researchers, language is definitely the next frontier. In the future, they may include some simple texts for bots to communicate during games. They expect that bots to have more complex communication capabilities. This way, the usage of bots can be taken to the next level with language-heavy and social-deduction games, like Werewolf.
Photo credit: The feature image has been taken by Anthony Brolin.
Source: Rob Matheson (MIT News)
