CITS3001 Algorithms, Agents and Artificial Intelligence - Project Resistance
CITS3001 Algorithms, Agents and Artificial Intelligence
Project
The project will be to write agents to play the game, The Resistance (https://boardgamegeek.com/boardgame/41114/resistance)
· Due: 5 pm, Tuesday, October 19
· Submit via cssubmit (https://secure.csse.uwa.edu.au/run/cssubmit?option=26&key=CITS3001Project).
· The project contributes 30% to your final grade, and may be done in pairs.
Resistance
RESISTANCE
For this project you will be able to work alone, or in pairs. You will be required to research, implement and validate agents to play in the game Resistance. You will be provided with some tamplate code to implement and agent in Java or Python, some very basic agents, and a basic class to run a game. We will also provide some scaffolding code to allow Java or Python agents to interact with a webserver to play other agents. These can be found on github (https://github.com/drtnf/resistanceAI) and will be regularly updated. You may use a different programming language, but you will have to implement you own websockets interface.
Submission
You will be required to submit a research report, and source code for one or two agents (pairs must submit two agents, individuals may submit two agents). The marking scheme is:
• Project report (2000-3000 words): 50%
1. Literature review of suitable techniques: 20%
2. Design description and rationale of selected technique: 20% 3. Validation of agent performance: 10%
• Java Implementation: 50%
1. Correctness and code quality (no runtime errors, readable code): 20%
2. Design (effective use of data structures, algorithms): 20%
3. Effectiveness (believable Al, challenging play): 10%
4. Competition (How well it plays in a tournament): 10% bonus
There will be a tournament server set up in the second half of semester, and agents will be evaluated on their performance in the final week of semester. The rules finalised closer to that date. The tournament will involve agents playing muliple games against different agents, with those scoring the highest getting the most marks.
Getting started
Agent-Oriented Architecture
Your agent will need to follow an Agent Oriented architecture. It will have a number of methods that the environment will call. Most of these methods will simply pass parameters to the agent containing information about the environment (e.g. who was on the mission, and how many betrayed the mission). The agent should use these parameters to update their internal state. Some of these methods will require the agent to perform an action (e.g. propose a mission or vote on a mission). The agent should use the information in their internal state to strategically select the best action.
Probabilities
This scenario is an imperfect information game. True resistance members do not know who the spies are. Resistance members typically want to limit their uncertainty whilst spies (who know everything) want to maximise the uncertainty in their opponents. In the worst case there are hundreds of different possibilities to consider. Good agents will need to consider which scenarios are most likely given the observations they have seen so far. Good spies will need to consider what the resistance members consider most likely scenarios and exploit this. Statistical modelling will be important here. Bayes rule, Markov models and Monte Carlo tree search are all potential techniques to try.
Other techniques
Adventurous people may want to consider epistemic logic, logic programming and theorem proving for reasoning agents, or perhaps try genetic algorithms or neural nets to build optimised populations of agents.
Research
You are given a lot of scope to choose your research question. For example, you may choose to focus on opponenet modelling (which would require modifying the test harness), social evolution where population norms may emerge, or identifying optimal strategies in perfect information version fo the games. To write a good resaerch report you should be clear on:
1. What the research question is;
2. Why the question is interesting;
3. How you intend to answer the question;
4. What data you collected; and
5. What the data tells us about the question.
This is not the first time an Al resistance tournament has been held. This paper (./Resistance.pdf) describes a number of different techniques and how well they performed. Note that the rules of the tournament are different and opponenet modelling will be restricted. Use this paper as a starting point to look up extra references and do a thorough literature review. Make sure that you cite all resources you use in full.
