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.

The game of Subset Take-Away is an impartial combinatorial game posed by David Gale in 1974. The game can be played on various discrete structures, including but not limited to graphs, hypergraphs, polygonal complexes, and partially ordered sets. While a universal winning strategy has yet to be found, results have been found in certain cases. In 2003 R. Riehemann focused on Subset Take-Away on bipartite graphs and produced a complete game analysis by studying nim-values. In this work, we extend the notion of Take-Away on a bipartite graph to Take-Away on particular hypergraphs, namely oddly-uniform hypergraphs and evenly-uniform hypergraphs whose vertices satisfy a particular coloring condition. On both structures we provide a complete game analysis via nim-values. From here, we consider different discrete structures and slight variations of the rules for Take-Away to produce some interesting results. Under certain conditions, polygonal complexes exhibit a sequence of nim-values which are unbounded but have a well-behaved pattern. Under other conditions, the nim-value of a polygonal complex is bounded and predictable based on information about the complex itself. We introduce a Take-Away variant which we call “Take-As-Much-As-You-Want”, and we show that, again, nim-values can grow without bound, but fortunately they are very easily described for a given graph based on the total number of vertices and edges of the graph. Finally we consider Take-Away on a specific type of partially ordered set which we call a rank-complete poset. We have results, again via an analysis of nim-values, for Take-Away on a rank-complete poset for both ordinary play as well as misère play.

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.