What would be the most effective self-learning algorithm for a 7 player social deduction game?

Question

There's this 7 player social deduction game called Secret Hitler, and I have been trying to find a self-learning AI algorithm to learn how to play this game for a while. Basically, four players are given a liberal role, two players are given a fascist role, and 1 player is given a hitler role. The liberals and hitler do not know any other roles, and the fascists know everyone's roles. During a turn, a president elects a chancellor based on a yes/no vote and then the government passes a policy (either liberal or fascist) that is drawn from a randomized deck. At certain points in the game, different special abilities come into play, like executing a player or investigating their role. To win the game, the liberals must either enact 5 liberal policies or kill hitler; the fascists must enact 6 fascist policies or get hitler enacted as the chancellor after 3 fascist policies have been enacted.

Now, there are other details that are irrelevant that I didn't mention, but those are the general rules. It seems simple enough to build a visual implementation in a language like Java, but there are so many moving pieces that I would have to account for. I doubt that simply making random moves at first and learning off of the bad/good moves would work, because I need a way for agents to make moves based on which roles they know.

Unfortunately, AlphaZero wouldn't work here, and I'm struggling to find any algorithm that would work for this (or any other social deduction game). Do I have to write my own algorithm? I'm slightly confident that this is a case of supervised learning where I can give weight to the nodes in a neural network that correspond to wins, but please correct me if I'm incorrect.

Answer 1

It is very likely that you want an algorithm like Counterfactual Minimax Regret. This algorithm has several variants, but they differ mostly in their efficiency.

CFR is the algorithm that was used to solve 2-Player Poker, although the solution comes from one of its more advanced versions. The algorithm is highly applicable to other games of incomplete information and games with roles, like Secret Hitler. Essentially, it learns how to act so that the actions it takes leak as little information to the other players as possible about its role (or hand of cards), while also learning about the roles of other players from their actions, and maximizing its chances of winning the game.