Search

We study operators that combine combinatorial games. This field was initiated by Sprague-Grundy (1930s), Milnor (1950s) and Berlekamp-Conway-Guy (1970-80s) via the now classical disjunctive sum operator on (abstract) games. The new class consists in operators for rulesets, dubbed the switch-operators. The ordered pair of rulesets (R 1 , R 2) is compatible if, given any position in R 1 , there is a description of how to move in R 2. Given compatible (R 1 , R 2), we build the push-the-button game R 1 R 2 , where players start by playing according to the rules R 1 , but at some point during play, one of the players must switch the rules to R 2 , by pushing the button ". Thus, the game ends according to the terminal condition of ruleset R 2. We study the pairwise combinations of the classical rulesets Nim, Wythoff and Euclid. In addition, we prove that standard periodicity results for Subtraction games transfer to this setting, and we give partial results for a variation of Domineering, where R 1 is the game where the players put the domino tiles horizontally and R 2 the game where they play vertically (thus generalizing the octal game 0.07)., Journal of Theoretical Computer Science (TCS), Elsevier, A Para{\^i}tre

In Guy and Nowakowski’s Unsolved Problems in Combinatorial Games, the following entry is found: “David Gale would like to see an analysis of Nim played with the option of a single pass by either of the players, which may be made at any time up to the penultimate move. It may not be made at the end of the game. Once a player has passed, the game is as in ordinary Nim. The game ends when all heaps have vanished.” This paper investigates the n -person combinatorial game of “Small Nim with Passes”, a variant of Nim, where players must always remove objects from the smallest nonempty pile and are allowed to “pass” their turn for a finite number of times. Let N be the number of piles in the game. When the number of players is greater than N + 1 , we determine all game values for all possible positions. The game values are determined completely when the number of players is equal to N + 1 . We also analyze certain cases of positions when the number of players is smaller than N + 1 , and leave some open problems that could be of interest to future research.

Wythoff’s game is a well-known 2 -player impartial combinatorial game, introduced by W.A. Wythoff in 1907. In recent years, many scholars studied the variants of Wythoff’s game, including mainly extensions and restrictions, with fruitful results achieved. One way of solving n -player impartial games was presented by W.O. Krawec in 2012. We employ Krawec’s function in this paper to analyze n -player Wythoff’s game and its nine restricted versions. The game values are completely determined for all ten n -player impartial games.

In this paper we study a cooperative card game called Hanabi from the viewpoint of algorithmic combinatorial game theory. In Hanabi, each card has one among c colors and a number between 1 and n . The aim is to make, for each color, a pile of cards of that color with all increasing numbers from 1 to n . At each time during the game, each player holds h cards in hand. Cards are drawn sequentially from a deck and the players should decide whether to play, discard or store them for future use. One of the features of the game is that the players can see their partners' cards but not their own and information must be shared through hints. We introduce a single-player, perfect-information model and show that the game is intractable even for this simplified version where we forego both the hidden information and the multiplayer aspect of the game, even when the player can only hold two cards in her hand. On the positive side, we show that the decision version of the problem—to decide whether or not numbers from 1 through n can be played for every color—can be solved in (almost) linear time for some restricted cases.

The game of n -person one-pile bounded Nim with two alliances is investigated: Given an integer m ≥ 1 and a pile of counters, each player is allowed to remove l counters from the pile, where l ∈ { 1 , 2 , … , m } . Suppose that n ≥ 2 players form two alliances and that each player is in exactly one alliance. Also assume that each player will support his alliance’s interests. Under misere play convention, all unsafe positions of two alliances are determined for some structures of two alliances. We also point out that some conclusions given by A.R. Kelly are not correct. Moreover, we present a possible explanation for Kelly’s inaccurate conclusions.

In this paper, we consider some properties about a Wadge-like game called Comparison game. We prove that the Comparison game is coherent with Wadge game on a subclass of Borel ideals. Thus answering some questions from M. Hrusak and D.M. Alcantara.

A game starts with the empty graph on n vertices, and two players alternate adding edges to the graph. Only moves which do not create a triangle are valid. The game ends when a maximal triangle-free graph is reached. The goal of one player is to end the game as soon as possible, while the other player is trying to prolong the game. With optimal play, the length of the game (number of edges played) is called the K 3 game saturation number.In this paper we prove an upper bound for this number.

Two classes of new games are investigated. Nim with Pointer Restriction is introduced by putting a pointer restriction on Nim, this pointer designates the pile that the next move must be made from. Nim with Pointer and Modular Restrictions is defined by putting simultaneously a pointer restriction and a modular restriction on Nim, the pointer designates the pile that the next move must be made from, the modular restriction designates the number of tokens that next move can remove from the designated pile.The games defined above are of the form 'comply/constrain' or 'Muller twist'. The sets of all P -positions of these games are given by explicit formulae for any m � 1 piles.

In this paper we develop a method of analyzing n-player impartial combinatorial games where n - 1 players behave optimally while one of the players plays randomly. More specifically, we develop a function g r that maps impartial combinatorial games to n-tuples called game values. A game value of some impartial combinatorial game G describes the probability that any player can win assuming player r plays randomly (i.e. player r chooses games at random without strategy).After devising our game value function g r , we apply it to the analysis of three-player Chomp whereby the second player plays randomly. Our analysis gives game values for single rowed Chomp positions and two rowed Chomp positions where the bottom row has 1 or 2 elements.We next discuss three alternative methods of analysis. First we extend our game value function to support more than just a single random player. Our second extension allows the random player to choose from an arbitrary distribution over games (as opposed to uniform which is assumed in our analysis of Chomp). This second extension also allows us to model a player who makes correct decisions for "simple" games (those that are, for instance, close to an end game) while playing randomly for more complex games. Finally, the third method considers the case where the random player only makes a mistake with probability ? and otherwise plays strategically.We conclude with many open problems and some interesting observations on the behavior of games containing a random player.

This paper introduces a new combinatorial game, named XT Domineering, together with its mathematical analysis. XT Domineering is modified from the Domineering game in which 1x2 or 2x1 dominos are allowed to be placed on empty squares in an mxn board. This new game allows a player to place a 1x1 domino on an empty square s while unable to place a 1x2 or 2x1 domino in the connected group of empty squares that includes s. After modifying the rule, each position in the game becomes an infinitesimal. This paper calculates the game values of all sub-graphs of 3x3 squares and shows that each sub-graph of 3x3 squares is a linear combination of 8 elementary infinitesimals. These pre-stored game values can be viewed as a knowledge base for playing XT Domineering. Instead of searching the whole game trees, a simple rule for determining the optimal outcome of any sum of these positions is presented.

Given non-negative integers a and b, we consider the following game WYT(a,b). Given two piles that consist of x and y matches, and two players having alternate turns; a single move consists of a player choosing x′ matches from one pile and y′ from the other such that 0≤x′≤x,0≤y′≤y,0

Partially-ordered set games, also called poset games, are a class of two-player combinatorial games. The playing field consists of a set of elements, some of which are greater than other elements. Two players take turns removing an element and all elements greater than it, and whoever takes the last element wins. Examples of poset games include Nim and Chomp. We investigate the complexity of computing which player of a poset game has a winning strategy. We give an inductive procedure that modifies poset games to change the nim- value which informally captures the winning strategies in the game. For a generic poset game G, we describe an efficient method for constructing a game not G such that the first player has a winning strategy if and only if the second player has a winning strategy on G. This solves the long-standing problem of whether this construction can be done efficiently. This construction also allows us to reduce the class of Boolean formulas to poset games, establishing a lower bound on the complexity of poset games.

The game of n-player Cutcake is the n-player version of Cutcake, a classical combinatorial game. Even though determining the solution of Cutcake is trivial, solving the n-player variant is challenging because of the identification of queer games, i.e., games where no player has a winning strategy. A classification of the instances of n-player Cutcake is presented.

In [3] R. Telgarsky (1975) asked: does the first player have a winning strategy in the game G ( F , X × X ) if the first player has a winning strategy in the game G ( F , X ) ? I give a positive answer to this question and prove that this result is also true for spaces where the first player has a winning strategy in game G ( K , X ) where K = 1 , F , C , for σ C if X is P -space and for DC if X is collectionwise-normal space. The last result is related to the Telgarsky's (1983) conjecture discussed in [1] . These results are not true for infinite product of spaces.

We present a setting in which the search for a proof of B or a refutation of B (i.e., a proof of ¬B) can be carried out simultaneously: in contrast, the usual approach in automated deduction views proving B or proving ¬B as two, possibly unrelated, activities. Our approach to proof and refutation is described as a two-player game in which each player follows the same rules. A winning strategy translates to a proof of the formula and a counter-winning strategy translates to a refutation of the formula. The game is described for multiplicative and additive linear logic (MALL). A game theoretic treatment of the multiplicative connectives is intricate and our approach to it involves two important ingredients. First, labeled graph structures are used to represent positions in a game and, second, the game playing must deal with the failure of a given player and with an appropriate resumption of play. This latter ingredient accounts for the fact that neither player might win (that is, neither B nor ¬B might be provable).

Vacuum insulation panels (VIPs) are regarded as one of the most promising high performance thermal insulation solutions on the market today. Thermal performances three to six times better than still-air are achieved by applying a vacuum to an encapsulated micro-porous material, resulting in a great potential for combining the reduction of energy consumption in buildings with slim constructions. However, thermal bridging due to the panel envelope and degradation of thermal performance through time occurs with current technology. Furthermore, VIPs cannot be cut on site and the panels are fragile towards damaging. These effects have to be taken into account for building applications as they may diminish the overall usability and thermal performance. This paper is as far as the authors know the first comprehensive review on VIPs. Properties, requirements and possibilities of foil encapsulated VIPs for building applications are studied based on available literature, emphasizing thermal bridging and degradation through time. An extension is made towards gas-filled panels and aerogels, showing that other high performance thermal insulation solutions do exist. Combining the technology of these solutions and others may lead to a new leap forward. Feasible paths beyond VIPs are investigated and possibilities such as vacuum insulation materials (VIMs) and nano insulation materials (NIMs) are proposed. This work has been supported by the Research Council of Norway, AF Gruppen, Glava, Hunton Fiber as, Icopal, Isola, Jackon, maxit, Moelven ByggModul, Rambøll, Skanska, Statsbygg and Takprodusentenes forskningsgruppe through the SINTEF/NTNU research project ”Robust Envelope Construction Details for Buildings of the 21st Century” (ROBUST).

In 1905 Bouton gave the complete theory of a two-player combinatorial game: the game of Nim. Two years later, Wythoff defined his game as “a modification” of the game of Nim. In this paper, we give the sets of the losing positions of geometrical extensions of Wythoff’s game, where allowed moves are considered according to a set of vectors (v1,…,vn). When n=3, we present algorithms and algebraic characterizations to determine the losing positions of such games. In the last part, we investigate a bounded version of Wythoff’s game, and give a polynomial way to decide whether a game position is losing or not.

Recently, Gabriel Nivasch got the following remarkable formula for the Sprague-Grundy function of game Euclid: g^+(x,y)[email protected]?|x/y-y/x|@? for all integers x,y>=1. We consider the corresponding misere game and show that its Sprague-Grundy function g^-(x,y) is equal to g^+(x,y) for all positions (x,y), except for the case when (x,y) or (y,x) equals (kF"i,kF"i"+"1), where F"i is the ith Fibonacci number and k is a positive integer. It is easy to see that these exceptional Fibonacci positions are exactly those in which all further moves in the game are forced (unique) and hence, the results of the normal and misere versions are opposite; in other words, for these positions g^+ and g^- take values 0 and 1 so that g^-=1-g^+=(-1)^i^+^1+g^+. Let us note that the good old game of Nim has similar property: if there is at most one bean in each pile then all further moves are forced. Hence, in these forced positions the results of the normal and misere versions are opposite, while for all other positions they are the same, as it was proved by Charles Bouton in 1901. Respectively, in the forced positions g^+ and g^- take values 0 and 1 so that g^-=1-g^+=(-1)^i^+^1+g^+, where i is the number of non-empty piles, while in all other positions g^+=g^-.

Derived from the game of Nim, we present well-known Wythoff's game as a special case of two “larger” types of combinatorial games: • The domination game. We explain that lots of combinatorial games can be con sidered as domination games on a specific graph (called the move-graph). • The three-vectors game. It has been constructed as a geometrical extension of Wythoff's game. We give the sets of losing positions of this game in several cases.

We consider a Nim game played on graphs, which was proposed and was named Nim on graphs in [4], and investigate its Grundy number using matchings of graphs. Especially, by virtue of this investigation, we can find the Grundy number of Nim on trees completely. Another result is that the problem of finding the Grundy number of Nim on cycles is resolved into that of Nim on trees. Thus, we find also the Grundy number of Nim on cycles completely.

A four-part partition game on a rectangle S I × S II is a two-person zero-sum game, where the strategy sets S I and S II are intervals and the rectangle is partitioned by three curves into four regions on each of which the payoff function is constant. These games generalize Silverman's game, where the boundary curves are of the form y = Tx , y = x and y = x / T . In this paper it is shown that two increasing nonintersecting curves may be chosen arbitrarily and there is a uniquely determined third increasing curve such that if the payoffs are properly related, the game is isomorphic to Silverman's game.

We define a new game, which is called an edge-removing game of star type. This game is played by two players on a graph G . Each player in turn removes a set of edges which induces a star, and the player who removes the last edge wins. This game is a generalization of the game of classical Nim and classical Kayles since if we play this game on a graph consisting of stars or one consisting of paths, then this game is equivalent to the game of classical Nim or classical Kayles. We give some results on this game.

In this paper we consider the following type of game: two players must color the vertices of a given graph G = ( V , E ), in a prescribed order, in such a way that no two adjacent vertices are colored with the same color. In one variant, the first player which is unable to move loses the game. In another variant, player 1 wins the game, if and only if the game ends with all vertices colored. In this paper, we obtain several results on the complexity of the problem to decide whether there is a winning strategy for player 1 in a given game instance, when G is restricted to split graphs, interval graphs, or bipartite graphs.

We analyse the following (solitaire) game: each node of a graph contains a pile of chips, and a move consists of selecting a node with at least as many chips on it as its degree, and letting it send one chip to each of its neighbors. The game terminates if there is no such node. We show that the finiteness of the game and the terminating configuration are independent of the moves made. If the number of chips is less than the number of edges, the game is always finite. If the number of chips is at least the number of edges, the game can be infinite for an appropriately chosen initial configuration. If the number of chips is more than twice the number of edges minus the number of nodes, then the game is always infinite. The independence of the finiteness and the terminating position follows from simple but powerful ‘exchange properties’ of the sequences of legal moves, and from some general results on ‘antimatroids with repetition’, i.e. languages having these exchange properties. We relate the number of steps in a finite game to the least positive eigenvalue of the Laplace operator of the graph.

A balancing game is a perfect information two-person game. Given a set V⊂Rd, in the ith round Player I picks a vector vi ϵ V, and then Player II picks ϵi = +1 or −1. Player II tries to minimize sup {| Σi=1n ϵivi | : n = 0, 1, 2,…}. In this paper we generalize this game and give necessary and sufficient conditions for the existence of a winning strategy for Player I and Player II in the generalized game. Later we give upper and lower bounds to the value of the original game; the bounds in many cases are equal. Further we present simple strategies for both players.