This thesis considers three restricted universes of partizan combinatorial games and finds new results for misere play using the recently-introduced theory of indistinguishability quotients. The universes are defined by imposing three different conditions on game play: alternating, dicot (all-small), and dead-ending. General results are proved for each main universe, which in turn facilitate detailed analysis of specific subuniverses. In this way, misere monoids are constructed for alternating ends, for pairs of day-2 dicots, and for normal-play numbers, as well as for sets of positions that occur in variations of nim, hackenbush, and kayles, which fall into the alternating, dicot, and dead-ending universes, respectively. Special attention is given to equivalency to zero in misere play. With a new sufficiency condition for the invertibility of games in a restricted universe, the thesis succeeds in demonstrating the invertibility (modulo specific universes) of all alternating ends, all but previous-win alternating non-ends, all but one day-2 dicot, over one thousand day-3 dicots, hackenbush ‘sprigs’, dead ends, normal-play numbers, and partizan kayles positions. Connections are drawn between the three universes, including the recurrence of monoids isomorphic to the group of integers under addition, and the similarities of universe-specific outcome determinants. Among the suggestions for future research is the further investigation of a natural and promising subset of dead-ending games called placement games.

This thesis concerns combinatorial games and algorithms that can be used to play them.Basic definitions and results about combinatorial games are covered, and an implementation of the minimax algorithm with alpha-beta pruning is presented.Following this, we give a description and implementation of the common UCT (Upper Confidence bounds applied to Trees) variant of MCTS (Monte-Carlo tree search).Then, a framework for testing the behavior of UCT as first player, at various numbers of iterations (namely 2,7, ... 27), versus minimax as second player, is described.Finally, we present the results obtained by applying this framework to the 2.2 million smallest non-trivial positional games having winning sets of size either 2 or 3.It is seen that on almost all different classifications of the games studied, UCT converges quickly to near-perfect play. / Denna rapport handlar om kombinatoriska spel och algoritmer som kan användas för att spela dessa.Grundläggande definitioner och resultat som berör kombinatoriska spel täcks, och en implementation av minimax-algoritmen med alpha-beta beskärning ges.Detta följs av en beskrivning samt en implementation av UCT varianten av MCTS (Monte-Carlo tree search).Sedan beskrivs ett ramverk för att testa beteendet för UCT som första spelare, vid olika antal iterationer (nämligen 2, 7, ... 27), mot minimax som andra spelare.Till sist beskrivs resultaten vi funnit genom att använda detta ramverk för att spela de 2,2 miljoner minsta icke triviala positionella spelen med vinstmängder av storlek antingen 2 eller 3.Vi finner att, för nästan alla olika klassificeringar av spel vi studerar, så konvergerar UCT snabbt mot nära perfekt spel.

A combinatorial game is a game in which all players have perfect information and there is no element of chance; some well-known examples include othello, checkers, and chess. When people play combinatorial games they develop strategies, which can be viewed as a function which takes as input a game position and returns a move to make from that position. A strategy is winning if it guarantees the player victory despite whatever legal moves any opponent may make in response. The classical complexity of deciding whether a winning strategy exists for a given position in some combinatorial game has been well-studied both in general and for many specific combinatorial games. The vast majority of these problems are, depending on the specific properties of the game or class of games being studied, complete for either PSPACE or EXP. In the parameterized complexity setting, Downey and Fellows initiated a study of "short" (or k-move) winning strategy problems. This can be seen as a generalization of "mate-in-k" chess problems, in which the goal is to find a strategy which checkmates your opponent within k moves regardless of how he responds. In their monograph on parameterized complexity, Downey and Fellows suggested that AW[*] was the "natural home" of short winning strategy problems, but there has been little work in this field since then. In this thesis, we study the parameterized complexity of finding short winning strategies in combinatorial games. We consider both the general and several specific cases. In the general case we show that many short games are as hard classically as their original variants, and that finding a short winning strategy is hard for AW[P] when the rules are implemented as succinct circuits. For specific short games, we show that endgame problems for checkers and othello are in FPT, that alternating hitting set, hex, and the non-endgame problem for othello are in AW[*], and that short chess is AW[*]-complete. We also consider pursuit-evasion parameterized by the number of cops. We show that two variants of pursuit-evasion are AW[*]-hard, and that the short versions of these problems are AW[*]-complete.

In this paper I introduce some background for subtraction games and explore the Sprague-Grundy functions defined on them. I exhibit some subtraction games where the functions are guaranteed to be strictly periodic. I also exhibit a class of subtraction games which have bounded range, and show there are uncountably many of these.

Placement games are a subclass of combinatorial games which are played on graphs. In this thesis, we demonstrate that placement games could be considered as games played on simplicial complexes. These complexes are constructed using square-free monomials. We define new classes of placement games and the notion of Doppelgänger. To aid in exploring the simplicial complex of a game, we introduce the bipartite flip and develop tools to compare known bounds on simplicial complexes (such as the Kruskal-Katona bounds) with bounds on game complexes.

京都大学 / 0048 / 新制・課程博士 / 博士(人間・環境学) / 甲第21863号 / 人博第892号 / 新制||人||213(附属図書館) / 2018||人博||892(吉田南総合図書館) / 京都大学大学院人間・環境学研究科共生人間学専攻 / (主査)教授 立木 秀樹, 教授 日置 尋久, 准教授 櫻川 貴司, 特定講師 DE BRECHT Matthew / 学位規則第4条第1項該当 / Doctor of Human and Environmental Studies / Kyoto University / DGAM

The game of Hex is of interest to the mathematics, algorithms, and artificial intelligence communities. It is a classical PSPACE-complete problem, and its invention is intrinsically tied to the Four Colour Theorem and the well-known strategy-stealing argument. Nash, Shannon, Tarjan, and Berge are among the mathematicians who have researched and published about this game. In this thesis we expand on previous research, further developing the mathematical theory and algorithmic techniques relating to Hex. In particular, we identify new classes of moves that can be pruned from consideration, and devise new algorithms to identify connection strategies efficiently. As a result of these theoretical improvements, we produce an automated solver capable of solving all 8 x 8 Hex openings and most 9 x 9 Hex openings; this marks the first time that computers have solved all Hex openings solved by humans. We also produce the two strongest automated Hex players in the world --- Wolve and MoHex --- and obtain both the gold and silver medals in the 2008 and 2009 International Computer Olympiads.

No description available.

This thesis explores the structure of games, including both the internal structure of various games and also the structure of classes of games as partially ordered sets. Internal structure is explored through consideration of juxtapositions of game positions and how the underlying games interact. We look at ordinal sums and introduce side-sums as a means of understanding this interaction, giving a full solution to a Toppling Dominoes variant through its application. Loopy games in which only one player is allowed a pass move, referred to as Oslo games, are introduced and their game structure explored. The poset of Oslo games is shown to form a distributive lattice. The Oslo forms of Wythoff’s game, Grundy’s game and octal .007 are introduced and full solutions given. Finally, the poset of option-closed games is given up to day 3 and all are shown to form a planar lattice. The option-closed game of Cricket Pitch is also fully analyzed.

Dans cette thèse, nous étudions des problématiques de graphes et de jeux combinatoires. Il existe de nombreux liens entre ces deux domaines : ainsi, les jeux sont un bon moyen de modéliser une opposition dans un problème d'optimisation, et dans l'autre sens plusieurs jeux classiques sont définis sur les graphes. Nous allons étudier deux problèmes de graphes et adapter des jeux combinatoires classiques pour y jouer sur des graphes. Dans un premier temps, nous étudions un problème de criticalité. Un graphe qui vérifie une certaine propriété, mais tel qu'une simple modification (ajout ou suppression d'arête ou de sommet) la lui fait perdre est appelé critique pour cette propriété. Nous nous intéressons au problème des graphes critiques pour la propriété ≪ avoir un diamètre égal à 2 ≫, appelés graphes D2C. La conjecture de Murty-Simon donne une borne supérieure sur le nombre d'arêtes d'un graphe D2C en fonction de son nombre de sommets. Or, des recherches récentes laissent supposer que cette borne peut être améliorée pour les graphes D2C non-bipartis. Nous démontrons donc une borne amoindrie pour une sous-famille de graphes D2C. Dans un deuxième temps, nous considérons un problème d'identification, laquelle consiste à assigner une étiquette à toutes les arêtes ou à tous les sommets d'un graphe, cette assignation devant engendrer une étiquette différente pour chaque sommet. Nous définissons une coloration d'arêtes par des ensembles d'entiers induisant une identification des sommets, et démontrons que cette coloration nécessite au plus un nombre logarithmique d'entiers par rapport à l'ordre du graphe pour l'identifier. Ce résultat est mis en comparaison avec d'autres types de colorations identifiantes, qui nécessitent dans le pire des cas un nombre linéaire d'entiers pour identifier tous les sommets. Dans un troisième temps, nous étudions des jeux de suppression de sommets, qui sont des jeux dans lesquels deux joueurs suppriment d'un graphe des sommets en respectant certaines règles prédéfinies, le premier joueur incapable de jouer perdant la partie. Nous proposons un cadre global pour l'étude de nombreux jeux de suppression de sommets dans les graphes, qui inclut plusieurs jeux classiques comme Arc-Kayles et permet une généralisation des jeux de soustraction et des jeux octaux sur les graphes. Dans leur définition classique, ces jeux ont généralement des comportements réguliers : tous les jeux de soustraction finis sont ultimement périodiques et il est conjecture que c'est également le cas des jeux octaux. Nous étudions plus spécifiquement les jeux de soustraction connexes CSG(S), dans lesquels les joueurs peuvent supprimer k sommets induisant un sous-graphe connexe sans déconnecter le graphe si k ∈ S (avec S fini). Nous démontrons que tous ces jeux sont ultimement périodiques, dans le sens ou pour un graphe et un sommet donnés, un chemin attaché à ce sommet peut être réduit à partir d'un certain rang sans modifier la valeur de Grundy du graphe pour le jeu. Nous trouvons également des résultats de périodicité pure, en particulier sur les étoiles subdivisées : pour certains ensembles S, les chemins des étoiles peuvent être réduits à leur longueur modulo une certaine période sans changer l'issue du jeu. Enfin, nous définissons une variante pondérée de Arc-Kayles, appelée Weighted Arc-Kayles (ou WAK), dans laquelle les joueurs doivent sélectionner une arête pour réduire le poids de ses extrémités, les sommets ayant un poids nul étant supprimés du graphe. Nous montrons une réduction entre WAK et Arc-Kayles, puis que les valeurs de Grundy de WAK sont non-bornées, ce qui répond à une question ouverte sur Arc-Kayles. Nous montrons également que les valeurs de Grundy de WAK sont ultimement périodiques lorsque tous les poids du graphe sauf un sont fixes / In this thesis, we study both graphs and combinatorial games. There are several links betweenthose two domains : games are useful for modeling an opponent in optimization problems on graphs,and in the other direction several classical games are played on graphs. We will study two graphproblems and adapt some classical combinatorial games to be played on graphs.In a first chapter, we study a criticality problem. A graph that verifies some property, and suchthat any modification (vertex or edge addition or deletion) breaks the property is called critical forthis property. We focus on the critical graphs for the property "having diameter 2", called D2Cgraphs. The Murty-Simon conjecture gives an upper bound on the number of edges in a D2C graphwith a given number of vertices. However, recent research suggests that this bound can be improvedfor non-bipartite D2C graphs. We show the validity of this approach by proving a smaller upperbound for a subfamily of non-bipartite D2C graphs.In a second chapter, we consider an identification problem. Identification consists in assigningsome data to every edge or vertex of a graph, such that this assignment induces a label to everyvertex with the added condition that two distinct vertices must have a different label. We definean edge-coloring using sets of integers inducing an identification of the vertices, and prove that thiscoloring requires at most a logarithmic number of integers (with respect to the order of the graph)in order to successfully identify the vertices. This result is compared with other identifying colorings,for which the number of colors required to successfully identify the vertices can be linear with respectto the order of the graph.In order to show the link between graphs and games, we adapt a well-known family of games tobe played on graphs. We propose a general framework for the study of many vertex deletion games(which are games in which the players delete vertices from a graph under predefined rules) such asArc-Kayles. This framework is a generalization of subtraction and octal games on graphs. In theirclassical definition, those games exhibit a high regularity : all finite subtraction games are ultimatelyperiodic, and Guy conjectured that this is also true for all finite octal games.We specifically study the connected subtraction games CSG(S) (with S being a finite set). Inthose games, the players can remove k vertices from a graph if and only if they induce a connectedsubgraph, the graph remains connected after their deletion, and k ∈ S. We prove that those gamesare all ultimately periodic, in the sense that for a given graph and vertex, a path attached to thisvertex can be reduced (after a certain preperiod) without changing the Grundy value of the graph forthe game. We also prove pure periodicity results, mostly on subdivided stars : for some sets S, thepaths of a subdivided star can be reduced to their length modulo a certain period without changingthe outcome of the game.Finally, we define a weighted version of Arc-Kayles, called Weighted Arc-Kayles (WAKfor short). In this game, the players select an edge and reduce the weight of its endpoints. Verticeswith weight 0 are removed from the graph. We show a reduction between WAK and Arc-Kayles,then we prove that the Grundy values of WAK are unbounded, which answers an open question onArc-Kayles. We also prove that the Grundy values of WAK are ultimately periodic if we fix allbut one of the weights in the graph