Pylos

Pylos is an abstract board game with very simple rules. (The description below is for the advanced version of Pylos.)

• The board is 4x4, and is initially empty.
• There are two players, Black and White. Each player has 15 spheres. 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:
     • either they place one of their unused spheres on the pyramid,
     • or if there is a square of four spheres on the board with nothing on top of them and the player has one of their own spheres on an equal or lower level of the board with nothing on top of it, they raise that sphere on top of the square.
  2. If in placing or raising a sphere, the player completes either
     • a square of four of their own spheres on any level of the pyramid, or
     • a (horizontal or vertical) line of four of their own spheres on the bottom level of the pyramid, or
     • a (horizontal or vertical) line of three of their own spheres on the second-bottom level of the pyramid,
     then they must immediately remove one or two of their own spheres from the pyramid. They can only remove spheres which have nothing on top of them, and they can never remove their opponent's spheres.
• 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. Lyndon has a Pylos set available for loan, and you can play online at Board Game Arena. Pylos is marketed by Gigamic.

Analysis and assistance

I may offer assistance of various kinds at some stages of the project. Such assistance will be announced via help3001, or on this page. On the following list, more-recent additions are nearer the top.

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 spheres at a1, a2, & b1, Black has spheres at b3, c2, & c3 (as shown in this picture), and in each move the player places a sphere on b2, and then immediately removes that sphere. Be careful!

Submission

You are required to construct a player for the advanced version of Pylos, described above. Aim for a system that plays a move in less than five seconds on a standard modern PC. 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

The project is designed to be done in pairs. No larger groups will be allowed, but you may do a sole project if you prefer. Make sure that all relevant names are listed clearly on the submission.

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 34% of your mark for CITS3001. 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 us at the time.

Deadline

The project is due by 4pm on Thursday 2 June 2016.

You must submit your project before the submission deadline above. The penalty for late submission is 5% of the maximum mark (i.e. 1.7% of the unit) per day or part thereof. No submissions will be accepted more than seven days late.

You are expected to have read and understood the University's guidelines on academic conduct.