Assignment 3: Hidden Symmetry #

Due date: 09/23/2024

Task: Implement \((n \in \mathbb{N}^{+})\) -sided Tic-Tac-Toe (win in \(n\) ) with a symmetry removal flag. Add symmetry removal for certain cases (probably just the 3x3 magic square case) of Number Scrabble by taking inspiration on their isomorphic Tic-Tac-Toe counterparts, also under a flag argument. Modify solving algorithm to also store remoteness values.

Provided:

• No additional skeleton code.
• Tips on generating symmetric positions for Tic-Tac-Toe cleanly.
• An explanation of the correspondence between TTT and Number Scrabble.
• The binary they installed in Assignment 1 also includes a correct solution for this assignment, and the same testing framework still works.

Metrics: After executing the python program, stdout should match the output of the provided game implementation on arbitrary inputs of \( n \) and \( S \) (within the now extended bounds of an iterative and memoized solution). The specific inputs on which it will be evaluated is not provided. This output should now be a breakdown of the number of winning, losing, and tying positions in the game grouped by remoteness (which they can print via the provided analysis utilities).

Learning objectives:

• Learn the technique of symmetry removal intuitively via TTT’s square board.
• Continue the trend of generic code / parameterization to symmetry removal.
• Get practice for writing state hash functions for physical board games.
• Gain an overall understanding of games as algebraic objects.

Note: This assignment should be very guided. While participants will practice hashing and the implementation of the game interface in this assignment, its purpose is ultimately to get them thinking about the mathematical structure of games, and to use this understanding to motivate something useful (symmetry removal on a game that has no obvious spatial “symmetry”).