Pylos

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

• There are two players, Black and White. Each player has 15 pieces, each of which is a sphere. Players move alternately: White always moves first. The basic paradigm is that the players build a pyramid from the 30 spheres: four layers of respectively 4x4 spheres, then 3x3, then 2x2, then 1.

• Each move has (potentially) two phases.

  1. Initially the player does one of the following:
     • they can place one of their unused pieces on the pyramid, or
     • if there is a square of four pieces on the board with nothing on top of them and the player has one of their own pieces on an equal or lower level of the board with nothing on top of it, they can raise that piece on top of the square.

  2. If in placing or raising a piece, the player completes either
     • a square of four of their own pieces on any level of the pyramid, or
     • a (horizontal or vertical) line of four of their own pieces on the bottom level of the pyramid, or
     • a (horizontal or vertical) line of three of their own pieces on the second-bottom level of the pyramid,
     then they immediately remove one or two of their own pieces from the pyramid - but they can only remove pieces which have nothing on top of them. A player can never remove their opponent's pieces.

• The player who places the final sphere on top of the pyramid wins. (Conversely, a player who runs out of spheres loses.)

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

Analysis and assistance

1. Use the following notation when talking about moves. From White's point of view:
   • the bottom tier is squares [a,b,c,d][1-4];
   • the second tier up is squares [e,f,g][1-3];
   • the third tier up is squares [h,i][1-2];
   • the top tier is square j1.

2. Counting only placements (i.e. not raises or removals), and ignoring any symmetries, there are approximately (15!)^2 possible games, i.e. roughly 10e25, and 155,117,520 distinct complete pyramids. Thus an exhaustive search is not possible.

3. Obviously games can cycle, because of the removal rule. One trivial possibility is where White has pieces at a1, a2, & b1, Black has pieces at b3, c2, & c3 (as shown in this picture), and in each move the player places a piece on b2, and then immediately removes that piece. Be careful!

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 Pylos,
• 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