Grants and Contributions:

Title:

Combinatorial Games and Graph Optimization: Losing and Scoring, Packing and Walking

Agreement Number:

RGPIN

Agreement Value:

$64,825.00

Agreement Date:

May 10, 2017 -

Organization:

Natural Sciences and Engineering Research Council of Canada

Location:

Newfoundland and Labrador, CA

Reference Number:

GC-2017-Q1-02104

Agreement Type:

Grant

Report Type:

Grants and Contributions

Additional Information:

Grant or Award spanning more than one fiscal year. (2017-2018 to 2022-2023)

Recipient's Legal Name:

Milley, Rebecca (Memorial University of Newfoundland)

Program:

Discovery Grants Program - Individual

Program Purpose:

COMBINATORIAL GAMES have been played for over five thousand years. These are games like chess and checkers: two players, perfect formation, and no luck. It is a remarkable fact that these games, seemingly born of an innate human desire to play and invent, have a beautiful underlying system of abstract mathematics.

We can add and subtract game positions, and we can say that two positions are “equal” (even if they appear to be different). By considering game positions abstractly, we can even meaningfully compare a position in chess to a position in checkers. Since 1900, this algebraic framework has been used to develop a complete theory for normal play , where the winner of a game is the player who gets the last move.

The primary goal of the proposed research is to advance the theory of the following alternatives to normal play, with emphasis on the first.

Losing : What if we declare that the winner is the player who does not get the last move? This “win-by-losing” mode is called misere play , and it is bafflingly miserable. The mathematical structure of normal play falls apart here, and thus misere analysis was mostly ignored in the 20th century. In 2005, there was a breakthrough: researchers introduced a weakened equality relation, whereby two game positions can be equivalent inside a subset of positions (such as only chess positions), even if they are not equal in general. Equivalence rebuilds some of the structure from normal play, and much progress has been made; but new insights have raised as many questions as they have answered, and a general theory of combinatorial games awaits the solutions to these open problems.

Scoring : Many well-known games end not only with a win–loss but also with a “score” for each player. There has not been a consensus on how to best model such games mathematically. A recent approach is showing promise, but there is much work to be done to determine how standard game properties apply to scoring games.

GRAPH OPTIMIZATION is the process of finding the “best” solution to a problem on a graph (that is, a collection of nodes with various connections). The proposed research includes graph theory as a secondary research area, and will investigate the following optimization problems.

Packing : How can a city choose locations for as many cell towers as possible, without having too many in any one neighbourhood? The proposed research will develop algorithms to solve this vertex packing optimization, and similar problems.

Walking : How can you optimize the patrol of one or more guards walking around a museum? How can we use as few guards as possible, with restrictions on how long a room can go unguarded? How can we minimize unguarded time, with a fixed number of guards? The proposed research will consider variations of the minimum dominating walk problem, which have applications in things like artificial intelligence for video games.