MIT scientists have engineered an advanced artificial intelligence system capable of outperforming human participants in challenging online multiplayer games characterized by concealed player identities and hidden motivations.
Numerous gaming algorithms have been designed to compete with human competitors. Just months ago, Carnegie Mellon University researchers pioneered the world's inaugural AI system capable of defeating professional poker players in multiplayer settings. DeepMind's AlphaGo captured global attention in 2016 by triumphing over a world-class Go champion. Various artificial intelligence systems have also been developed to overcome chess grandmasters or collaborate in team-based challenges like online capture the flag. These gaming scenarios, however, provide AI systems with complete knowledge of adversaries and allies from the beginning.
During the upcoming Conference on Neural Information Processing Systems, the research team will unveil DeepRole, the groundbreaking gaming AI capable of conquering online multiplayer scenarios where participants' team affiliations remain initially ambiguous. This innovative system incorporates cutting-edge "deductive reasoning" into traditional AI algorithms typically employed in poker gameplay. This enhancement enables the system to analyze partially observable behaviors, calculating the likelihood that each participant represents either an ally or adversary. Through this process, the AI rapidly identifies optimal partnerships and determines strategic actions necessary to secure victory for its team.
The research team challenged DeepRole against human competitors across 4,000+ rounds of the popular online game "The Resistance: Avalon." This strategic game requires participants to uncover their counterparts' hidden identities throughout gameplay while simultaneously concealing their own roles. When functioning as either teammate or adversary, DeepRole consistently demonstrated superior performance compared to human participants.
"Substituting a human teammate with our AI system significantly increases your team's probability of success. Artificial intelligence systems prove to be more effective collaborators," explains lead researcher Jack Serrino '18, an MIT graduate in electrical engineering and computer science who also serves as an enthusiastic "Avalon" enthusiast.
This research represents a component of an expansive initiative aimed at more accurately modeling human social decision-making processes. Such advancements could facilitate the development of robotic systems with enhanced capabilities for understanding, learning from, and collaborating with human counterparts.
"Human beings acquire knowledge through collaboration with others, enabling collective accomplishments beyond individual capabilities," notes co-author Max Kleiman-Weiner, a postdoctoral researcher affiliated with MIT's Center for Brains, Minds and Machines, the Department of Brain and Cognitive Sciences, and Harvard University. "Strategic games such as 'Avalon' effectively simulate the complex social dynamics humans navigate in daily life. The challenge of identifying potential allies applies universally, whether in educational environments or professional settings."
The research team additionally includes David C. Parkes from Harvard University and Joshua B. Tenenbaum, a computational cognitive science professor affiliated with MIT's Computer Science and Artificial Intelligence Laboratory and the Center for Brains, Minds and Machines.
Advanced Deductive Reasoning System
Within "Avalon," three participants receive confidential assignments to the "resistance" faction while two participants join the "spy" contingent. Spy participants possess knowledge of all players' roles. Each round features one participant nominating a subgroup of two or three players to undertake a mission. All participants concurrently cast public votes to either endorse or reject the proposed team. Upon majority approval, the subgroup secretly determines the mission's outcome. Two "success" selections result in mission accomplishment, while a single "fail" choice leads to mission failure. Resistance participants must invariably select "success," whereas spy participants retain flexibility in their choices. The resistance faction achieves victory following three successful missions, while the spy contingent triumphs after three failed missions.
Victory in this game fundamentally hinges on identifying resistance and spy participants while strategically voting for collaborators. This challenge actually presents greater computational complexity than chess or poker. "This represents a game characterized by imperfect information," Kleiman-Weiner explains. "Participants lack initial knowledge regarding their adversaries, necessitating an additional discovery phase to identify potential cooperation partners."
DeepRole employs a game-planning methodology known as "counterfactual regret minimization" (CFR) — a learning approach involving repeated self-play — enhanced with deductive reasoning capabilities. Throughout gameplay, CFR anticipates future possibilities by constructing a decision "game tree" comprising branches and nodes representing potential future actions by each participant. These game trees encompass all possible actions (branches) available to each player at subsequent decision points. Through billions of simulated game scenarios, CFR identifies actions that enhance or diminish victory probabilities, progressively refining its strategy to incorporate more effective decisions. Ultimately, this process yields an optimal strategy that, at minimum, results in a draw against any opponent.
While CFR demonstrates effectiveness for games featuring public actions — such as monetary betting and hand folding in poker — it encounters challenges when actions remain concealed. The researchers' enhanced CFR methodology integrates public actions with private action consequences to ascertain whether participants belong to the resistance or spy factions.
The AI system undergoes training through self-play scenarios assuming both resistance and spy roles. During actual gameplay, it utilizes its game tree to predict each participant's likely actions. This game tree embodies strategies maximizing each player's victory probability within their designated role. The tree's nodes contain "counterfactual values" — essentially payoff estimations representing the expected outcome when implementing a particular strategy.
During each mission, the AI system evaluates individual gameplay patterns against its game tree predictions. When a participant consistently makes decisions inconsistent with the system's expectations throughout gameplay, that individual likely assumes the opposing role. Ultimately, the AI assigns high probability values to each player's potential role. These probability assessments subsequently inform strategic updates to enhance victory prospects.
Concurrently, the system employs identical methodology to anticipate how neutral observers might interpret its actions. This capability facilitates prediction of other participants' reactions, enabling more intelligent decision-making. "When participating in a failed two-player mission, other participants recognize that one team member represents a spy. The AI system will likely avoid proposing identical team compositions in subsequent missions, as it understands other participants perceive this configuration unfavorably," Serrino explains.
Advanced Communication: The Next Evolutionary Step
Remarkably, the AI system achieved success without engaging in player communication — typically considered essential gameplay element. "Avalon" incorporates text-based chat functionality for participant interaction. "Unexpectedly, our AI system demonstrated effective collaboration within human teams through mere observation of player behaviors," Kleiman-Weiner observes. "This finding proves intriguing, as such games were presumed to require sophisticated communication strategies."
"I experienced tremendous excitement upon reviewing this research publication," remarks Michael Bowling, a University of Alberta professor specializing in computer gaming training methodologies. "Witnessing DeepStack concepts finding expanded applications beyond poker represents truly thrilling development. These methodologies have proven fundamental to artificial intelligence advancements in chess and Go within imperfect information contexts. However, I hadn't anticipated such rapid extension into hidden role games like Avalon. Successfully navigating social deduction scenarios — seemingly intrinsically human capabilities — constitutes a remarkably significant achievement. Substantial research remains necessary, particularly regarding more open-ended social interactions, yet we consistently observe that fundamental self-play learning algorithms demonstrate tremendous potential."
Future research directions may incorporate basic textual communication capabilities, enabling the AI system to evaluate players as beneficial or detrimental. This advancement would involve correlating textual output with probability assessments regarding player roles — information already utilized in the system's decision-making processes. Subsequent developments might implement sophisticated communication functionalities, allowing participation in language-intensive social deduction games — such as the popular "Werewolf" — featuring extended periods of argumentation and persuasion regarding team affiliations.
"Language unquestionably represents the next evolutionary frontier," Serrino concludes. "However, communication-centric games present numerous substantial challenges requiring resolution."
