Virtual Combinatorial Games Seminar

April 8, 2024
Time: 15:00-16:00 EDT
Type: Research
Speaker: Carlos Pereira dos Santos, Center for Mathematics and Applications (NovaMath), FCT, NOVA University of Lisbon  
Title: Affine Normal Play
Abstract: There are many combinatorial games in which a move can terminate the game, such as a checkmate in chess. These moves give rise to diverse situations that fall outside the scope of the classical normal play structure. To analyze these games, an algebraic extension is necessary, including infinities as elements. In this work, affine normal play, the algebraic structure resulting from that extension, is analyzed. We prove that it is possible to compare two affine games using only their forms. Furthermore, affine games can still be reduced, although the reduced forms are not unique. We establish that the classical normal play is order-embedded in the extended structure, constituting its substructure of invertible elements. Additionally, as in classical theory, affine games born by day n form a lattice with respect to the partial order of games.

March 11, 2024
Time: 15:00-16:00 EDT
Type: Research
Speaker:  Silvia Heubach, California State University
Title: How to Win in Slow Exact k-Nim and Slow Exact Set-Nim – an Update  (joint work with Matthieu Dufour)
Abstract: Slow Exact k-Nim is a variant of the well-known game of Nim. The rules of this variant are that in each move, k of the n stacks are selected and then one token is removed from each of the selected stacks.  The last player to move wins. 

Slow Exact k-Nim has been solved for some small values of n and k and for the two trivial families when k = 1 or k = n. We give new results on the structure of the P-positions for the infinite family of games where play is on all but one of the n stacks. In addition, we generalize the game to Slow Exact Set-Nim SN(n,A), where the possible choices of number of stacks are given by the set A. We give results for A = {n-1, n} and state a conjecture on the P-positions of SN(n, A) for A = {k, k+1,…, n}.

For those in the audience who heard us talk about these two games in the Azores, you will see improved results – we were able to combine the cases of odd and even n, for which we had different patterns for the P-positions. We have also made progress on generalizing the crucial criteria and conditions used for Slow Exact k-Nim to the more general setting of SN(n,A) and will discuss which piece is still missing for the proof of our conjecture.

February 12, 2024
Time: 15:00-16:00 EST
Type: Research
Speaker: Craig Tennenhouse (University of New England)
Title: I'm not touching you! On closeness of Combinatorial Game values.  
Abstract: The study of Combinatorial Games does not often benefit from stochastic methods, in part because there is no obvious distance metric among Combinatorial Games. We propose a few reasonable metrics that can be run in CGSuite, along with a genetic algorithm approach to finding game positions close to given values. Some open problems and shortfalls will be discussed. 

January 22, 2024
Time: 15:00-16:00 EST
Type: Research
Speaker: Tom Maciosowski (Concordia University of Edmonton)
Title: The Temperature of a Snort Position can be Infinitely Larger Than Its Degree
Abstract: Snort is a two-player game played on a simple graph in which players alternately colour a vertex such that they do not colour adjacent to their opponent's vertex. It is known that the temperature of Snort in general is infinite (K_{1,n} has temperature n). We show that the temperature in addition can be infinitely larger than the degree of the board being played on. We do so by constructing a family of positions in which the temperature grows twice as fast as the degree of the board.

This work results from a summer research project supervised by Svenja Huntemann.

(Slides)

December 7, 2023
Time: 14:00-15:00 EST
Type: Coffee Klatsch
Speaker:  Various
Title: N/A

November 9, 2023  (Two talks!)
Time: 14:00-14:30 EST
Type: Research
Speaker:  Carlos Pereira dos Santos, Center for Mathematics and Applications (NovaMath), FCT, NOVA University of Lisbon  
Title: Combinatorial Game Theory monoids: exploring the algebraic structure of different restrictions
Abstract: The classic order relation employed in Combinatorial Game Theory asserts that G>=H when Left can exchange H for G in all contexts without incurring any disadvantage. "Contexts" refer to "disjunctive sums", meaning that Left can accept exchanging H+X for G+X, regardless of the game form X. In the early developments of CGT, X encompassed all possible game forms. Recently, much research has been conducted by restricting the range of X to a subclass of forms F (modulo F). In the case of the misère-play convention, it is possible to obtain monoids with "more structure" than the monoid without any restrictions. Also, in Scoring CGT, interesting monoids can be obtained. Furthermore, Absolute Combinatorial Game Theory has been recently developed as a unifying tool for constructive/local game comparison, giving some general results applicable to any parental restriction. The purpose of this talk is to offer a concise overview of the current advancements in studying these types of structures. The talk will not include any proofs but will focus on delivering an organized exposition that facilitates a general and intuitive understanding of the topic for the audience. 

Time: 14:30-14:50 EST
Type: Research
Speaker: Aaron Siegel   
Title: Invariant Forms of Partizan Games
Abstract: Berlekamp, Conway, and Guy famously showed that every partizan game admits a unique simplest form in normal play, obtained by iteratively eliminating dominated options and bypassing reversible ones. In misere play, the classical construction of simplest forms generalizes well to impartial games and to the full universe of partizan games. Attempts to generalize to more complicated universes encounter difficulties, however, due to the occasional presence of "atomic reversible" options that cannot be bypassed. In this talk I will show that simplest forms in an arbitrary (absolute) misere universe U (as defined by Larsson, Nowakowski, and Santos) can be restored by enlarging U with additional elements that represent "synthetic" analogs of atomic reversible options. These simplest forms can be effectively calculated whenever U admits a computable test for U-strongness (and in particular, whenever U is a computable subuniverse of E). As a proof of concept, I'll give simplest forms of some 2 x N rectangles in misere Domineering, computed in the Domineering universe D(\bar{1}0). 

October 19, 2023
Time: 14:00-15:00 EDT
Type: Research
Speaker: Aaron Siegel
Title: On the General Dead-Ending Universe of Partizan Games Part 2
Abstract: Interest in misere games has a long history, but it is only in the past few decades that meaningful progress has been made in understanding misère play of partizan games. Recent advances due to Duchene, Larsson, Milley, Nowakowski, Santos, and others have opened promising new directions for investigation and raised a number of interesting questions in this area.

This talk is the continuation of a talk that was delivered in the spring 2023 seminar, attempting an investigation of the general universe of misère dead-ending games, i.e., the universal closure D(A), where A is an arbitrary collection of dead-ends. In part 1, I showed that the dead-ends have an unusually rigid ("multiversal") structure that is independent of the universe under consideration; and that there are uncountably many "one-step" extensions of the minimal nondicotic universe D(1). In Part 2, I will show that every misère dead-ending universe admits a computable comparison relation, provided that its generating set of dead-ends is itself computable. I will also suggest a strategy for defining "invariant forms," an analog of canonical forms that works for any dead-ending universe.

September 21, 2023
Time: 14:00-15:00 EDT
Type: Research
Speaker: Matt Ferland (University of Southern California)
Title: Narrowing the Tractability Gap of Adding Games: Sums of Quasi-Nimbers are Hard
Abstract: We address the natural question of "can a sum of simple tepid games in canonical form be intractable.'' Specifically, we use the recent construction of quasi-nimbers, and the classical construction of super-stars by Conway, to illustrate this concept. We prove that disjunctive sums of quasi-nimbers are NP-hard to solve, as well as sums of superstars with a single nimber.  This is striking as quasi-nimbers are only a single move away from nimbers, whose sums can be computed in polynomial time.

This is joint work with Kyle Burke (Florida Southern College), Svenja Huntemann (Mount Saint Vincent University), and Shang-Hua Teng (University of Southern California).

May 4, 2023
Time: 12:00-13:00 EDT
Type: Research
Speaker: Ted Hwa
Title: When are overheating operators monotonic and linear?
Abstract: In the paper "Blockbusting and Domineering", Berlekamp introduced the operators of heating and overheating. Heating is closer to being an inverse of cooling, but can be difficult to work with because it is not monotonic nor linear. Overheating is a variant of heating that, under certain conditions, is monotonic and linear. We investigate the conditions under which overheating satisfies these properties by relating it to the Norton product, which is well-known to be both monotonic and linear.
(Slides)

April 13, 2023
Time: 12:00-13:00 EDT
Type: Research Talk
Speaker: Dana Ernst (Northern Arizona University)
Title: Morphisms of impartial combinatorial games
Abstract: The aim of this talk is to formalize some folklore from combinatorial game theory and to introduce a few new results concerning morphisms of impartial games, one of which we can think of as the First Isomorphism Theorem for impartial games. This is preliminary work that was initiated at the most recent Combinatorial Game Theory Colloquium in the Azores. This is joint work with Bojan Bašić, Paul Ellis, Danijela Popović, and Nándor Sieben.
(Slides)

March 16, 2023
Time: 12:00-13:00 EDT
Type: Research Talk
Speaker: Aaron Siegel (independent)
Title: On the General Dead-Ending Universe of Partizan Games
Abstract: Interest in misère games has a long history, but it is only in the past few decades that meaningful progress has been made in understanding misère play of partizan games. Recent advances due to Duchene, Larsson, Milley, Nowakowski, Santos, and others have opened promising new directions for investigation and raised a number of interesting questions in this area.

In this talk I will attempt an investigation of the general universe of misere dead-ending games, i.e., the universal closure D(A), where A is an arbitrary collection of dead-ends. I will show that the dead-ends have an unusually rigid ("multiversal") structure that is independent of the universe under consideration; that there are uncountably many "one-step" extensions of the minimal nondicotic universe D(1); and that every misere dead-ending universe admits a computable comparison relation, provided that its generating set of dead-ends is itself computable. I will also suggest a strategy for defining "invariant forms," an analog of canonical forms that works for any dead-ending universe.

February 23, 2023
Time: 12:00-13:00 EST
Type: Coffee Klatsch
Speaker:  Various
Title: N/A

December 8, 2022
Time: 10:00-11:00 EST
Type: Research
Speaker: Nacim Oijid (Université Lyon 1)
Title: Incidence, a Scoring Positional Game on Graphs
Abstract: Positional games have been introduced by Hales and Jewett in 1963 and have been extensively investigated in the literature since then. These games are played on a hypergraph where two players alternately select an unclaimed vertex of it. In the Maker-Breaker convention, if Maker manages to fully take a hyperedge, she wins, otherwise, Breaker is the winner. In the Maker-Maker convention, the first player to take a hyperedge wins. In both cases, the game stops as soon as Maker has taken a hyperedge. By definition, this family of games does not handle scores and cannot represent games in which players want to maximize a quantity.

In this work, we introduce scoring positional games, that consist in playing on a hypergraph until all the vertices are claimed, and by defining the score as the number of hyperedges a player has fully taken. We focus here on Incidence, a scoring positional game played on a 2-uniform hypergraph, i.e. an undirected graph. In this game, two players alternately claim the vertices of a graph and score the number of edges for which they own both end vertices. In the Maker-Breaker version, Maker aims at maximizing the number of edges she owns, while Breaker aims at minimizing it. In the Maker-Maker version, both players try to take more edges than their opponent.

We first give some general results on scoring positional games such that their membership in Milnor's universe and some general bounds on the score. We prove that, surprisingly, computing the score in the Maker-Breaker version of Incidence is PSPACE-complete whereas in the Maker-Maker convention, the relative score can be obtained in polynomial time. In addition, for the Maker-Breaker convention, we give a formula for the score on paths by using some equivalences due to Milnor's universe. This result implies that the score on cycles can also be computed in polynomial time.
(Slides, arXiv Preprint)

November 16, 2022
Time: 10:00-11:00 EST
Type: Research
Speaker:  Thotsaporn "Aek" Thanatipanonda (Mahidol University International College)
Title: The arithmetic-periodicity of CUT for C = {1,2*c}  
Abstract: CUT is a class of partition games played on a finite number of finite piles of tokens. Each version of cut is specified by a cut-set C. A legal move consists of selecting one of the piles and partitioning it into d + 1 nonempty piles, where d in C. No tokens are removed from the game. It turns out that the nim-set for any C = {1,2*c} with c >= 2 is arithmetic-periodic, which answers an open question of Dailly et al. (2020). The key step is to show that there is a correspondence between the nim-sets of CUT for C = {1,6} and the nim-sets of cut for C = {1,2*c}, c >= 4. The result easily extends to the case of C ={1,2*c1,2*c2,2*c3,...}, where c1,c2,... >= 2.
(Slides)

October 20, 2022
Time: 10:00-11:00 EDT
Type: Research
Speaker:  Koki Suetsugu (National Institute of Informatics)
Title: Improving upper and lower bounds of the number of games born by day 4
Abstract: In combinatorial game theory, the lower and upper bounds of the number of games born by day 4 have been recognized as 3.0*10^12 and 10^434, respectively. In this study, we improve the lower bound to 10^28.2 and the upper bound to 4.0*10^184, respectively.
(Slides)

September 21, 2022
Time: 10:00-11:00 EDT
Type: Research
Speaker:  Akshay V. Upasany and Prem Kant (Indian Institute of Technology, Bombay)
Title: Bidding combinatorial games and a constructive comparison approach
Abstract: Combinatorial Game Theory is a branch of mathematics and theoretical computer science that studies sequential 2-player games with perfect information. Normal play is the convention where a player who cannot move loses. Here, we generalize the classical alternating normal play to infinitely many game families by means of discrete Richman auctions (Develin et al. 2010, Larsson et al. 2021, Lazarus et al. 1996). We generalize the notion of a perfect play outcome and find an exact characterization of outcome feasibility. As a vital landmark, we prove the existence of a game form for each such outcome class; then, we describe their lattice structures. Further, by generalizing standard game comparison techniques from alternating normal play, we propose an algorithmic play solution to the problem of game comparison for a class of bidding games that include game forms that are defined numbers. We demonstrate several consequences of this result that, in some cases, generalize the classical results in alternating play (from Winning Ways and On Numbers and Games). We state a couple of conjectures and open problems for readers to dive into this promising path of bidding combinatorial games.

May 16, 2022
Time: 15:30-16:30 EDT
Type: Research
Speaker:  Carlos Pereira dos Santos  (Center for Functional Analysis, Linear Structures and Applications, University of Lisbon & ISEL-IPL)
Title: Some notes on dicotic universe under misère-play convention
Abstract: It is possible to show the failure of the Archimedean property and the nonexistence of infinitesimals in the full misère structure. However, a breakthrough in the study of misère games occurred when Thane Plambeck and Aaron Siegel suggested weakened equality and inequality relations in order to compare games only within a particular universe. Dicot forms have the property that either both players have a move or the game is over, and the misère dicot universe, restricted in the manner of Plambeck & Siegel, has much more structure than the full misère universe. This work focuses on that.

First, we analyse the form {0,*|*} (mup, "misère up"), the simplest positive dicotic form, showing the infinitesimal nature of the powers of mup, as it happens under normal-play convention with powers of up. Regarding that, we use the ruleset SHELVES as a case study, illustrating the occurrence of muptimals.

Second, we discuss the "tame nature'' of some dicotic rulesets under misère-play convention. A dicotic ruleset played under misère-play convention is tame if it is possible to use the Atomic Weight Theory, as under normal-play convention, until very close to the end of the game. As case studies, we mention PARTIZAN STIRLING SHAVE, BYPASS, and HACKENBUSH SPRIGS. 

April 25, 2022
Time: 15:30-16:30 EDT
Type: Coffee Klatsch

March 28, 2022
Time: 9:00-10:00 EDT
Type: Research
Speaker: Koki Suetsugu  (National Institute of Informatics)
Title: Emperor sum: a new sum of games
Abstract: In this talk, we introduce new sum of impartial games, emperor sum. In emperor sum of games, a player, in their turn, chooses a component and makes arbitrary many moves for the component. Moreover, the player can make at most one move for each other component. We show the way to characterize P-positions of emperor sum of games by using a parameter called P-position length. The P-position length is defined for each P-position and indicates the maximal number of P-positions that one can visit to a terminal position from the current position. We also share some closed formulas which show the P-position lengths of positions in some rulesets like nim, wythoff, moore's nim, and delete nim. 

(Slides)

February 28, 2022
Time: 15:30-16:30 EST
Type: Research
Speaker:  Shang-Hua Teng (University of Southern California)
Title: Nimber-Preserving Reduction: Game Secrets and Homomorphic Sprague-Grundy Theorem
Abstract: Classical Sprague-Grundy theory has two main components: (1) a mathematical reduction from any impartial game to an equivalent single-pile Nim game, and (2) Bouton's theory for transforming the sum of Nim games into a single-pile Nim game. While Bouton's sum is polynomial-time computable, the Grundy value (nimber) is PSPACE-hard intractable. 

In this talk, we consider nimber-preserving reductions among impartial games, which enhance the winnability-preserving reductions in traditional computational characterizations of combinatorial games. We prove that Generalized Geography is complete for the natural class, I^P, of polynomially-short impartial rulesets, under polynomial-time nimber-preserving reductions. We refer to this notion of completeness as Sprague-Grundy-completeness. In contrast, we also show that not every PSPACE-complete ruleset in I^P is Sprague-Grundy-complete for I^P.

By viewing every impartial game as an encoding of its nimber—a succinct game secret richer than its winnability alone—our technical result establishes the following striking cryptography-inspired homomorphic theorem: Despite the PSPACE-completeness of nimber computation for I^P, there exists a polynomial-time algorithm to construct, for any pair of games G1, G2 in I^P, a Generalized Geography game G satisfying: nimber(G) = nimber(G1) ⊕ nimber(G2). Thus, if we substitute single-pile Nim with single-graph Generalized Geography in Sprague-Grundy theory, then both the reduction and summation become polynomial-time computable.

Joint work with Kyle Burke (Plymouth State) and Matt Ferland (USC)

(Slides)

January  31, 2022
Time: 10:30-11:30 EST 
Type: Research
Speakers: Eric Duchene (Lyon 1 University) and  Aline Parreau (CNRS, Lyon 1 University)
Title: Smash and grab: a new scoring game on graphs
Abstract: In this talk, we introduce a new scoring game on graphs called Smash and Grab, that can be seen as a variation of both games 0.6 and String and coins.

Given a graph G, two players take turns removing a vertex of G as well as all of its neighbours that become isolated by this removal. For each player and each of their turns, they score the number of vertices that were removed on their turn. The game ends when there are no more vertices remaining, and the player with the highest final score wins. We denote by s(G) the difference between the first and the second player's final scores in G, assuming both players play optimally.

By definition, this game belongs to Ettinger's universe, aka the universe of dicot scoring games. The first part of the talk will be devoted to classes of graphs for which there is no zugzwang during the game, i.e. s(G)>=0 (or in other words, where the first player never loses). This universe of dicot games with no zugzwang is also called Milnor's universe. We will first show that the class of forests belongs to Milnor's universe. In addition, we will give the exact value of s(G) for union of paths by determining the full set of equivalent classes.

For classes of graphs that have cycles, the game is generally no more in Milnor's universe and the resolution becomes more tricky as players do not have interest to start. The case of cycles and union of cycles will be considered. We will finally present open questions about the equivalence relation for scoring games in Ettinger's universe, and in particular the equivalence class of zero. 

November 18, 2021
Time: 13:00-14:00 EST
Type: Open Research Discussion

October 21, 2021
Time: 13:00-14:00 EDT
Type: Research
Speaker: Lexi Nash (Concordia University of Edmonton)
Title: The Polynomial Profile of Distance Games on Paths and Cycles  
Abstract: Distance games are a subclass of combinatorial games played on graphs. They consist of the players colouring vertices/placing tokens without later moving or removing them and the placement of new pieces is dependent on the distance from previously played pieces. It was found that the independence polynomial of some graph, related to the game board, is a representation of the number of positions for that game on that board. Recent work enumerated the positions of three distances games (Snort, Col, and Cis) on paths by computing their generating functions. We extend this work to give bivariate polynomials enumerating the same games on new families of graphs. We also take a look at some new distance games on paths.  
(Slides)

September 23, 2021
Time: 13:00-14:00 EDT
Type: Research
Speaker: Carlos Pereira dos Santos  (Center for Functional Analysis, Linear Structures and Applications, University of Lisbon & ISEL-IPL)
Title: Infinitely many absolute universes  
Abstract: A universe of combinatorial games is absolute if it is parental, that is, if each pair of non-empty sets of forms of the universe make a form of the universe. If a universe is absolute, often we have constructive ways to compare two forms, that is, we have ways to avoid the definition of order, comparing the games just with their literal forms. 

Regarding the misère play convention, we prove that there is an infinite number of absolute universes, by recursively expanding the dicot universe with non dicotic elements. On the other hand, regarding the normal play convention, we prove there are two absolute universes, namely the full space, and the universe of all-small games. 

(Slides)

May 14, 2021
Time: 12:00-13:00 EDT
Type: Research
Speaker: Carlos Santos (University of Lisbon & ISEL-IPL)
Title: Some notes on disjunctive short sum: Polychromatic Nim  
Abstract: Polychromatic Nim is a version of the classic game Nim, played with colored stones, in which each pile has stones of a single color, and the player who successfully extinguishes a color wins the game. This game is closely related to the concept of short rule, the ending condition that states that a disjunctive sum ends as soon as any one of the components ends. Here, we discuss that rule, namely when applied to impartial games, and show that the Grundy-values of Polychromatic Nim present an arithmetic-periodic behavior.

Joint work with Alda Carvalho.
(Slides)

April 16, 2021
Time: 12:00-13:00 EDT
Type: Research
Speaker: Peter Selinger (Dalhousie University)
Title: On the combinatorial value of Hex positions
Abstract:  Hex is a strategic perfect information game for two players, invented in 1942 by Piet Hein and later independently discovered by John Nash. Hex is attractive because its rules are extremely simple, yet the game possesses a surprising amount of strategic depth and is actually fun to play. Although several authors, such as Van Rijswijck, Henderson, Hayward, and others, have applied the spirit of combinatorial game theory to the analysis of Hex positions, until recently, no specific formulation of combinatorial game theory had been given that works for Hex "strictly speaking". I will report on such a theory, and give some examples of how it can be applied to solve previously unsolved problems.
(Slides)

March 19, 2021
Time: 12:00-13:00 EDT
Type: Research
Speaker: Aaron Siegel (San Francisco, CA)
Title: The Structure of Misère Impartial Games
Abstract: Combinatorial games in misère play have been the subject of increasing interest in recent years, yet much still remains unknown about the structure of misère impartial games under classical (Conway) equality. In this talk, I will discuss the historical development of misère impartial games, present an overview of what is known about their structure, and discuss some new results. In particular: I will show how to calculate the number of games born by day 7; and I will prove that the group of fractions of the (canonical) monoid $\mathcal{M}$ of misère games is "almost" torsion-free.

Some of the work presented in this talk was joint work with John Conway and Dan Hoey.
(Slides)

February 19, 2021
Time: 12:00-13:00 EST
Type: Research
Speaker: Kyle Burke (Plymouth State University)
Title: Quantum Combinatorial Games: Structures and Computational Complexity
Abstract:  Following on Dorbec and Mhalla's work on Quantum Combinatorial Games, we took a deep dive into one of their quantum flavors, "D", where players can make Quantum or Classical moves whenever available.  This talk will focus on the ramifications (especially with respect to computational complexity) for Nim and both Directed and Undirected Geography.  Additional topics will include reachability of positions, and how quantum play highlights the difference between computing the winnability from any position and maintaining winnability from an initial position.  
(Slides)

January 22, 2021
Time: 12:00-13:00 EST
Type: Research
Speaker: Alexander Clow (St. Francis Xavier University)
Title: Nimber and Strategy Preserving Reductions on Poset Games
Abstract: Poset Games are a class of Impartial Combinatorial Games. In this talk we examine how all normal play Poset Games can be reduced to an infinite number of other normal play Poset Games by a novel method involving a special class of monotone maps, which we denote as order compressions. We then present our work showing all such reductions preserve the nimber and ideal strategies of a Poset Game. The talk aims to give examples of our results rather than focusing on their proofs. To conclude, we give a conjecture concerning the nimber of any Poset Game played on a lexicographic product of posets where the right factor is a poset whose corresponding Poset Game is a generalization of the canonical form (a weak-canonical form) of $*2^n$ for any $n$ and all options of such a game. This is joint work with Stephen Finbow.
(Slides)

December 3, 2020
Time: 12:00-13:00 EST
Type: Tutorial
Speaker: Kyle Burke (Plymouth State University)
Title: Computational Complexity of Combinatorial Games
Abstract: How long does it take for a computer to perfectly play a combinatorial game?  This talk covers ways computational complexity tries to answer this question.  We'll look at different complexity classes, see where well-known rulesets lie in the complexity "zoo", talk about proof techniques, and list some open problems.  This talk will not require an in-depth understanding of computer science.
(Slides)

November 12, 2020
Time: 12:00-13:00 EST
Type: Research
Speaker: Rebecca Milley (Memorial University of Newfoundland)
Title: Domineering under Misere Play
Abstract: Domineering is a well-studied tiling game in which one player places vertical dominoes and a second places horizontal dominoes, alternating turns until someone cannot place on their turn. Research by Berlekamp (1988) and others (1993 – 2016) has found game values and computationally-determined outcomes for certain rectangular boards under normal play (last move wins); however, nothing has been published about domineering under misere play (last move loses). This talk will present combinatorial arguments to prove that all 2xn boards, n>11, are Right-win under misere play, and will demonstrate instances of misere reversibility, comparability, and invertibility "modulo domineering". This is joint work with Aaron Dwyer and Michael Willette. 

October 15, 2020
Time: 12:00-13:00 EDT
Type: Research Talk
Speaker: Urban Larsson (National University of Singapore)
Title: Absolute CGT
Abstract: We propose a unifying additive theory for standard conventions in  Combinatorial Game Theory, including normal-, misere- and scoring-play, studied by Berlekamp, Conway, Dorbec, Ettinger, Guy, Larsson, Neto, Nowakowski, Milley,  Renault, Santos, Siegel, Sopena, Stewart (1976-2019), and others. A game universe is a set of games that satisfies some standard closure properties. Here, we reveal when the fundamental game comparison problem, "Is G>= H?'', simplifies to a constructive 'local' solution, which generalizes Conway's foundational  result in ONAG (1976) for normal-play games. This happens in a broad and general fashion whenever a given game universe is absolute. An absolute universe of games satisfies an additional property, dubbed parentality: any pair of non-empty finite sets of games is admissible as options. This property implies that a universe is saturated with respect to the outcomes, basically, given a game, any outcome is attainable in a disjunctive sum. Game comparison is at the core of combinatorial game theory, and for example efficiency of potential reduction theorems rely on a local comparison. We distinguish between three levels of game comparison; superordinate (global), basic (semi-constructive) and subordinate (local) comparison. Moreover, in proofs, a sometimes tedious challenge facing a researcher in CGT in order to disprove an inequality, involves finding an explicit distinguishing game. Here, we explain how this job becomes obsolete whenever a universe is absolute. Namely, it suffices to see if a pair of games satisfies a certain Proviso (specific for each universe) together with a Common Normal Part (essentially same for all). This is joint work with Carlos P. Santos and Richard J. Nowakowski. 
(Slides)

September 24, 2020
Time: 12:00-13:00 EDT
Type: Research Talk
Speaker: Richard Nowakowski (Dalhousie University)
Title: Game Value Graphs

Abstract: This talk is an exploration of what the title might mean, arising out of joint work with Melissa Huggan.  There may be other ideas and there will be time to discuss them.

For impartial games, the Grundy colouring, or first-fit colouring, is reasonably well known and somewhat understood. What about partizan games? 

For example, is it true that for any graph G, is there a game S such that the edges of G can be directed to form the game graph (as opposed to game tree) of S? 

Questions arise such as: Can values be repeated? Must the values be in canonical form? Are there are 'real-life' applications/interpretations of game value graphs?

August 27, 2020
Time: 13:00-14:00 EDT
Type: Research talk
Speaker: Melissa Huggan (Ryerson University)
Title: The Cheating Robot
Abstract: Simultaneous move combinatorial games can require the use of methods from economic game theory to analyze even relatively simple game positions. Throughout this talk, we explore a deterministic model as an alternative approach to studying simultaneous play games. We call this the Cheating Robot model. This model forces both players to move at the same time, but one player has extra information about where their opponent is going to move and can react accordingly. We discuss some general theory and explore a case study to get some insight into this model.
Joint work with Richard J. Nowakowski.
(Slides)

August 13, 2020
Time: 13:00-14:00 EDT
Type: Tutorial
Speaker: Rebecca Milley (Memorial University of Newfoundland)
Title: Intro to misere game theory
Abstract: Games under misere play - where the last player to move loses - are much harder to analyze than those under normal play. This talk will discuss the reasons for the difference and the solution of considering games "modulo" a restricted subset (universe) of games, and will present recent results for comparability, inverses, and canonical forms in certain restricted universes. These will be illustrated with the game of domineering under misere play.
(Slides)

July 30, 2020
Time: 13:00-14:00 EDT
Type: Tutorial
Speaker: Ted Hwa
Title: Loopy Games
Abstract: I will give a tutorial on the basic facts about loopy games.  My approach will be a mixture of the ideas found in Winning Ways and in Aaron Siegel's book, which (in my opinion) combines the best of both worlds.
(Slides)

July 16, 2020
Time: 13:00-14:00 EDT
Type: Tutorial
Speaker: Richard Nowakowski (Dalhousie University)
Title: Scoring Games
Abstract: I will use the following two versions of the Cleaning game to illustrate how to work with Scoring games. I'll present some useful lemmas (for humans) and some pitfalls to avoid.
Cleaning Game: Given a graph G, a vertex is primed if it has at least degree-many brushes. When a vertex x is fired, it sends a brush to each adjacent vertex and incident edges are deleted.
Basic game: A move is to choose a vertex v and place a brush on it, now choose a primed vertex and fire it, repeat the firing until there are no more primed vertices. The game finishes when there are no more edges.
I'll give an overview of what we know about two scoring versions of the Cleaning game and some hints as to how the proofs work.
**Note: neither game has been completely solved.
Game 1: A player scores 1 for each vertex they fire. (Huggan, Huntemann, McKay, RJN, Ottaway, A.A. Siegel)
Game 2: A player scores 1 for each edge that is cleaned on their turn.  (Larsson, RJN, Santos)
(Slides)

July 02, 2020
Time: 13:00-14:00 EDT
Type: Research talk
Speaker: Craig Tennenhouse (University of New England)
Title: Genetic Programming for Games
Abstract: Genetic programming is the practice of evolving formulas using crossover and mutation of genes representing functional operations. Motivated by genetic evolution we develop and solve two combinatorial games, and we demonstrate some advantages and pitfalls of using genetic programming to investigate Sprague-Grundy values.
(Slides)