Bot can beat humans in multiplayer hidden-role games

Using deductive reasoning, the bot identifies friend or foe to ensure victory over humans in certain online games.

Recent breakthroughs in AI for multi-agent games have seen great strides in recent years. Yet, these games failed to address the real-life challenge of cooperation in the presence of unknown and uncertain teammates. This challenge is a crucial game mechanism in hidden role games.

MIT scientists have now devised a bot that can beat human players in tricky online multiplayer games where player roles and motives are kept secret. Dubbed as DeepRole, the bot is a multi-agent reinforcement learning agent equipped with AI.

It is a first gaming bot that can win online multiplayer games in which the participants’ team allegiances are initially unclear. The bot is structured with novel “deductive reasoning’ added into an AI algorithm ordinarily utilized for playing poker. This encourages it to reason about partially observable actions, to decide the likelihood that a given player is a partner or rival. In doing as such, it quickly realizes whom to play with and which moves to make to guarantee its group’s triumph.

First author Jack Serrino ’18, who majored in electrical engineering and computer science at MIT, said, “If you replace a human teammate with a bot, you can expect a higher win rate for your team. Bots are better partners.”

Co-author Max Kleiman-Weiner, a postdoc in the Center for Brains, Minds, and Machines, and the Department of Brain and Cognitive Sciences at MIT, said, “Humans learn from and cooperate with others, and that enables us to achieve together things that none of us can achieve alone. Games like ‘Avalon’ better mimic the dynamic social settings humans experience in everyday life. You have to figure out who’s on your team and will work with you, whether it’s your first day of kindergarten or another day in your office.”

DeepRole utilizes a game-planning algorithm called “counterfactual regret minimization” (CFR) — which figures out how to play a game by repeatedly playing against itself. At each point in a game, CFR looks forward to making a decision “game tree” of lines and nodes describing the potential future actions of every player.”

Game trees represent all possible actions (lines) each player can take at every next decision point. In playing out possibly billions of game simulations, CFR notes which activities had expanded or diminished its odds of winning, and iteratively reconsiders its system to incorporate all the more great decisions. In the long run, it designs an ideal methodology that, even under the least favorable conditions, ties against any opponent.

CFR works well for games like poker, with public actions — such as betting money and folding a hand — but it struggles when actions are secret. The researchers’ CFR combines public actions and consequences of private actions to determine if players are resistance or spy.

The researchers pitted DeepRole against human players in more than 4,000 rounds of the online game “The Resistance: Avalon.” In this game, players try to deduce their peers’ secret roles as the game progresses, while simultaneously hiding their roles. As both a teammate and an opponent, DeepRole consistently outperformed human players.

Scientists are further planning to enable the bot to communicate during games with simple text, such as saying a player is good or bad.

Joining Serrino and Kleiman-Weiner on the paper are David C. Parkes of Harvard and Joshua B. Tenenbaum, a professor of computational cognitive science and a member of MIT’s Computer Science and Artificial Intelligence Laboratory and the Center for Brains, Minds, and Machines.

REFERENCEMIT

See stories of the future in your inbox every morning.

MUST READ