|home > undergraduate > AI 4211|
ARTIFICIAL INTELLIGENCE (CITS4211)
Quarto!Quarto! is an abstract board game with very simple rules.
Analysis and assistanceThere are 16x16x15x15x14x14x... = (16!)^2 (approx 10^26) distinct games that can be played, and 16! (approx 10^13) arrangements of the 16 pieces on the board. This is too big for an exhaustive search in a reasonable time. Symmetries exist which reduce the complexity of Quarto!, and many games finish without filling the board, but still the numbers are very big.
Generalising the above, if there are x unused pieces, then there are at most (x!)^2 terminal positions to consider. Minimax will be able to give a perfect solution for some values of x. But in other positions, an evaluation function will be required to assess partially-completed games. What features might such a function consider?
I may offer assistance of various kinds at some stages of the project. Such assistance will be announced via help4211, or on this page.
SubmissionYou are required to construct a player for the advanced version of Quarto!. Aim for a system that plays a move (either choosing or placing a piece) in less than five seconds on a standard modern PC.
You must submit two deliverables via cssubmit:
The paper should be about 5-10 pages long: it should describe the structure and design of your program, and include any (experimental or theoretical) analysis that you have performed. If you use or refer to other people's work, make sure that you give all due credit.
AssessmentThe project is designed to be done in pairs. No larger groups will be allowed, but you may do a sole project if you prefer.
You may decide how to distribute the various project tasks (for example programming, testing, collecting empirical data, producing plots, writing, etc) between the group members, but the marks will be divided evenly, so the workload should be roughly equal too.
The project counts for 25% of your mark for CITS4211. Assessment will be based on
You should consult the School's guidelines on plagiarism, available from the unit outline.
DeadlineThe project is due by 4pm on Tuesday 31 May.
Standard penalties will apply for late submission, as specified in the unit outline.