Quarto!

• The board has 16 squares, arranged 4x4. At the start of the game, the board is empty.

• There are 16 distinct pieces, capturing all possible combinations of these four attributes:
  • colour: white or black;
  • height: tall or short;
  • shape: square or round;
  • solidity: solid or hollow.

  So for example one piece is white, tall, square, and hollow: another is black, tall, square, and solid. Each piece is different.

• There are two players, whose roles alternate. In each move, one player chooses one of the unused pieces, and the other player places that piece on a vacant square on the board. So a game starts as follows:
  • Player 1 chooses one of the 16 pieces;
  • Player 2 places that piece;
  • Player 2 chooses one of the remaining 15 pieces;
  • Player 1 places that piece;
  • Player 1 chooses one of the remaining 14 pieces;
  • Player 2 places that piece;
  • etc.

  Thus a game comprises 16 moves, each comprising one choice and one placement.

• A player wins if their placement completes a straight line (horizontal, vertical, or diagonal) of four pieces that share a feature (i.e. all the same colour, or height, or shape, or solidity). There are ten possible winning lines.

• In the advanced version of the game, a player also wins if their placement completes a square of four pieces that share a feature. There are nine possible winning squares.

• If the board is filled without a winning move being made, the game is drawn.

A Wikipedia page exists which discusses Quarto!. I have a Quarto! set available for loan. Quarto! is marketed by Gigamic.

Analysis and assistance

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.

Submission

You must submit two deliverables via cssubmit:

• the code you generate in the project, as a zip archive;
• a paper describing and analysing your work, as a PDF file.

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.

Assessment

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

• how well you have analysed the problem,
• how well you have used the AI algorithms that we have studied,
• how well your program plays Quarto!,
• how well you have analysed your program,
• how well your paper is written,
• and anything else that occurs to me at the time.

You should consult the School's guidelines on plagiarism, available from the unit outline.

Deadline