If you are a student at MSVU in mathematics and interested in working on a research project with me, please email me. A few possible projects are described below. All of these projects require little to no background, although having taken MATH2225 and/or MATH3333/4333 would be an advantage. Almost all of these projects will involve the use of software and potentially require some coding.
Combinatorial games are 2-player games with perfect information and no chance. Examples of these games include chess, checker, go, and Nim. Battleships would be an example of a game that does not have perfect information as one cannot see the opponents board, while anything involving rolling dice or drawing cards fails the second criterion.
Placement games are a special type of combinatorial games in which pieces are placed on a board and never moved or removed. These are also known as pen-and-paper games since, as the name suggests, they can be played with just a pen and some paper - no eraser needed. Some examples of these games are the following:
Domineering: Played on a checkerboard. One player places dominoes horizontally, while the other plays vertically.
Snort: Played on any finite graph (collection of vertices and edges). One player colours vertices blue, while the other colours red. Two vertices of opposite colours cannot be connected.
Col: Like Snort, but vertices of the same colour cannot be connected.
All three of these games end if the current player cannot place a piece and under the normal play convention this player loses.
Here is a bit more terminology used in the description of projects. Note that all of these definitions are very informal.
Outcome class: who wins the game
Game value: Combinatorial games are split into equivalence classes and the equivalence class a game belongs to is called its value. As the name indicates, it represents what the value of the game (or part of a game) is to the player, i.e. how much of an advantage they have.
Temperature: represents how urgent it is to move in an area of the board
Many placement games have the special property of being in a correspondence with simplicial complexes (abstract mathematical structures that can thought of as a collection of sets or higher-dimensional geometric objects). These games are called strong placement (SP-)games and Domineering, Snort, and Col are all examples. We know that every simplicial complex corresponds to some SP-game, but we do not know much about what structures they have when we restrict to only certain games.
This project will be to pick an SP-game and study the structures of the simplicial complexes when playing on different boards.
Distance games are placement games in which the placement of pieces is only restricted by the distance to already placed pieces. For example, in Snort pieces of opposite colour cannot have distance 1.
This project will pick a distance game (or several) and determine which values are possible.
The normal play convention is that the player who made the last move wins and this is the winning convention we use most. A second winning convention often considered is misère play, where the player who cannot move on their turn wins. Analysis under misère play is usually much more difficult, but placement games have properties that make this easier.
This project will study the game values of Snort (and potentially other games) under misère play.
A long-standing conjecture is that the highest possible temperature in Domineering is 2 (while in general they could be as large as desired). This has been proven to be the case for many types of Domineering positions, but is still open in general. We know of several examples of positions that indeed have temperature 2, but of course no larger temperature has been found.
This project will be looking at positions with temperature equal or close to 2 to try to understand what structures they have in common.
A relatively new topic in combinatorial game theory is counting the number of possible positions in a game. We have a technique that enumerates all possible positions in Domineering that takes advantage of the grid structure. Domineering can be generalized to playing on other boards and this generalization is called Partizan ArcKayles. Since we no longer have the same grid structure of the board, other techniques need to be found to count the positions in Partizan ArcKayles.
This project will work on enumerating positions in Partizan ArcKayles on a variety of types of boards.
Ultimate tic-tac-toe is a variant of tic-tac-toe in which each of the nine squares is replaced by another tic-tac-toe game. When one wins one of the subgames, one gets to place their piece in the larger game. In addition, which square one plays in the subgame determines which subgame the opponent next has to play in. This variant is significantly more interesting (as in more difficult) than tic-tac-toe, both to human and computer players.
A similar "stacking" operation for placement games has been defined. This project is to investigate good strategies and the complexity of the new variants.