Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

Dalhousie University

$28,000.00

Combinatorial game theory for monotone set coloring games

FY 2024-25

Summary
People have played games since the dawn of humanity, and some strategy games, such as Chess and Go, have stood the test of time for centuries or even millenia. But the mathematical study of games is a relatively recent phenomenon. It was only in the 20th century that mathematical ideas from game theory started to be applied to real-life decision making scenarios, for example in economics, computer science, politics, and diplomacy. The goal of this proposal is to develop a new branch of combinatorial game theory. Combinatorial game theory is a formalism for studying sequential two-player games with perfect information. It was introduced by Conway (1976) and Berlekamp, Conway, and Guy (1982). The flavor of combinatorial game theory that this proposal aims to develop is adapted to a class of games called monotone set coloring games. The best-known example of such a game is Hex. The game of Hex was invented in 1942 by the Danish mathematician Piet Hein and later independently discovered by John Nash at Princeton. Hex is played on a parallelogram-shaped board that is made of hexagonal cells. One pair of opposing edges belongs to Black, and the other pair to White. Each player's objective is to connect their two board edges with an unbroken chain of cells of their color. Hex has many interesting mathematical properties. One of these is decisiveness: the game of Hex always ends with a winner, and there are no draws. Another interesting property is that it can be abstractly proven that the first player has a winning strategy, yet no specific such strategy is known. As for the game's complexity, it is known that determining the winner from an arbitrary starting position is a PSPACE-complete problem. PSPACE is a class of computational decision problems that are known to be very hard; in practice, this means that we will never find a perfect strategy for Hex that is efficiently computable. In other words, no matter how good a human or computer player gets at Hex, there can always be another player who is better. In recent work, I introduced a new class of combinatorial games, called "passable games", which are well-adapted to Hex and related games. The goal of the proposed research is to develop the theory of these games, and to use them to answer open questions in Hex. This theory could further result in improved strategies, both for human players and computer players.
Program
Discovery Grants Program - Individual
Location
Nova Scotia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2024-04191
Name nom
Selinger, Peter
Department département
Mathematics and Statistics
Organization id
79
Institution établissement
Dalhousie University
Province en
Nova Scotia
Province fr
Nouvelle-Écosse
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2024
Award amount
28000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1508
Committee name en
Mathematics and Statistics
Committee name fr
Mathématiques et statistique
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
2914
Research subject group en
Pure mathematics
Research subject group fr
Mathématiques pures
Research subject en
Combinatorics
Research subject fr
Combinatoire
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Combinatorial game theory for monotone set coloring games
Keywords
combinatorial game theory; scoring games; set coloring games; hex
Application summary
People have played games since the dawn of humanity, and some strategy games, such as Chess and Go, have stood the test of time for centuries or even millenia. But the mathematical study of games is a relatively recent phenomenon. It was only in the 20th century that mathematical ideas from game theory started to be applied to real-life decision making scenarios, for example in economics, computer science, politics, and diplomacy. The goal of this proposal is to develop a new branch of combinatorial game theory. Combinatorial game theory is a formalism for studying sequential two-player games with perfect information. It was introduced by Conway (1976) and Berlekamp, Conway, and Guy (1982). The flavor of combinatorial game theory that this proposal aims to develop is adapted to a class of games called monotone set coloring games. The best-known example of such a game is Hex. The game of Hex was invented in 1942 by the Danish mathematician Piet Hein and later independently discovered by John Nash at Princeton. Hex is played on a parallelogram-shaped board that is made of hexagonal cells. One pair of opposing edges belongs to Black, and the other pair to White. Each player's objective is to connect their two board edges with an unbroken chain of cells of their color. Hex has many interesting mathematical properties. One of these is decisiveness: the game of Hex always ends with a winner, and there are no draws. Another interesting property is that it can be abstractly proven that the first player has a winning strategy, yet no specific such strategy is known. As for the game's complexity, it is known that determining the winner from an arbitrary starting position is a PSPACE-complete problem. PSPACE is a class of computational decision problems that are known to be very hard; in practice, this means that we will never find a perfect strategy for Hex that is efficiently computable. In other words, no matter how good a human or computer player gets at Hex, there can always be another player who is better. In recent work, I introduced a new class of combinatorial games, called "passable games", which are well-adapted to Hex and related games. The goal of the proposed research is to develop the theory of these games, and to use them to answer open questions in Hex. This theory could further result in improved strategies, both for human players and computer players.
Dalhousie University - $28,000 Grant (2024-25) | Canada Spends