-
Notifications
You must be signed in to change notification settings - Fork 0
Research
Investigating Approaches to AI for Trust-Based, Multi-Agent Board Games with Imperfect Information with Don Eskridge's "The Resistance"
This paper was the recommended reading for the project. Its 91 pages!
This paper provides:
- an overview of the game
- reasons why its mechanics are interesting
- a review of related games and AI techniques
- descriptive analysis of existing agent implementations
- original investigation into analysis of "suspicion inaccuracies" and opponent modelling techniques.
- suggests directions for future research
This will just have research into 5 player games (2 spies, 3 resistance). Mission sizes are 2,3,2,3,3. Five failed votes results in the games being lost.
There is a strong focus on the other players rather than the mechanics. The game requires logical deduction of players identities. There is no random elements like a card draw or dice roll but the actions of the other players create uncertainty.
Observant resistance members improve their chances of victory by identifying their enemies.
There is a disconnect from the actions that we know must have happened, and who took those actions. The person that played the fail card could be anyone one the mission team.
In games like warewolf and mafia there are no teams so the treachery is almost completely unobserved so you just rely on social ques.
Playing strength in one role gives no indication to playing strength in another role
number of phases in a game = (x+(2v)) m
m - number of missions v - number of attempts to pick a team x - execution phase (always one per mission
Modern board games have complications over classic board games:
- variable initial setup
- non-deterministic elements (this is the only one not in The Resistance)
- imperfect info
- more than one opponent
These complications prevent typical tree searches or just playing the same set of opening moves each time.
Monte-Carlo Tree Search is a technique which constructs and learns to exploit a game tree during play wih random exploration weighted by past successes and failures had been applied to Catan. Go was the first place to implement it. Also the only AI which was competitive against human opponents.
Poker is interesting because of the Opponent Modelling, which uses statistical information to identify opponents' strategies and even predict their hands.
Categorises approaches and algorithms which can be used to obtain estimations and predictions for scientific and mathematical problems that may be infeasible, or even impossible to solve analytically or exhaustively.
Their defining feature is the use of repeated random sampling of a distribution, which may be, for example, a probability distribution, the domain of a function, or some more abstract representation of data such as a two dimensional graph.
It do look like the monte carlo tree search is going to be the way to go.