Reference number : GC-2017-Q1-02104, amendment number : , agreement type : G, recipient legal name : Milley, Rebecca (Memorial University of Newfoundland), recipient country : CA, recipient province : nan, recipient city : Newfoundland and Labrador|Terre-Neuve-et-Labrador, recipient postal code : nan, program name english : Discovery Grants Program - Individual, program name french : Programme de subventions à la découverte - individuelles, program purpose english : 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 &ldquo;equal&rdquo; (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 &ldquo;win-by-losing&rdquo; 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&ndash;loss but also with a &ldquo;score&rdquo; 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 &ldquo;best&rdquo; 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., program purpose french : 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 &ldquo;equal&rdquo; (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 &ldquo;win-by-losing&rdquo; 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&ndash;loss but also with a &ldquo;score&rdquo; 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 &ldquo;best&rdquo; 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., agreement title english : Combinatorial Games and Graph Optimization: Losing and Scoring, Packing and Walking, agreement title french : Combinatorial Games and Graph Optimization: Losing and Scoring, Packing and Walking, agreement number : RGPIN, agreement value : 64825.0, agreement start date : 2017-05-10, agreement end date : nan, description english : nan, description french : nan, expected results english : nan, expected results french : nan, additional information english : Grant or Award spanning more than one fiscal year. (2017-2018 to 2022-2023), additional information french : Subvention ou bourse octroyée s'appliquant à plus d'un exercice financier. (2017-2018 à 2022-2023), owner organization : nserc-crsng, owner organization title : Natural Sciences and Engineering Research Council of Canada | Conseil de recherches en sciences naturelles et en génie du Canada