Loading...
6 results
Search Results
Now showing 1 - 6 of 6
- On lattices from combinatorial game theory: infinite casePublication . Carvalho, Alda; Santos, Carlos; Dias, Cátia; Coelho, Francisco; Neto, João P.; Nowakowski, Richard; Vinagre, SandraGiven a set of combinatorial games, the children are all those games that can be generated using as options the games of the original set. It is known that the partial order of the children of all games whose birthday is less than a fxed ordinal is a distributive lattice and also that the children of any set of games form a complete lat tice. We are interested in the converse. In a previous paper, we showed that for any fnite lattice there exists a fnite set of games such that the partial order of the chil dren, minus the top and bottom elements, is isomorphic to the original lattice. Here, the main part of the paper is to extend the result to infnite complete lattices. An original motivating question was to characterize those sets whose children generate distributive lattices. While we do not solve it, we show that if the process of taking children is iterated, eventually the corresponding lattice is distributive.
- Bounding game temperature using confusion intervalsPublication . Huntemann, Svenja; Nowakowski, Richard; Santos, CarlosWe consider bounds for the temperatures of combinatorial games. Our first result gives an upper bound on the temperatures of the positions of a ruleset in terms of the lengths of the confusion intervals of these positions. We give an example to show that this bound is tight. Our second main result is a method to find a bound for the lengths of the confusion intervals. This pair of results constitutes the first general technique to bound temperatures. As examples of the bound and the method, we consider the temperature of subsets of positions in DOMINEERING and SNORT.
- Ordinal sums of impartial gamesPublication . Carvalho, Alda; Neto, João; Santos, CarlosIn an ordinal sum of two combinatorial games G and H, denoted by G : H, a player may move in either G (base) or H (subordinate), with the additional constraint that any move on G completely annihilates the component H. It is well-known that the ordinal sum does not depend on the form of its subordinate, but depends on the form of its base. In this work, we analyze g(G : H) where G and H are impartial forms, observing that the g-values are related to the concept of minimum excluded value of order k. As a case study, we introduce the ruleset OAK, a generalization of GREEN HACKENBUSH. By defining the operation gin sum, it is possible to determine the literal forms of the bases in polynomial time. (C) 2017 Elsevier B.V. All rights reserved.
- Ordinal sums, clockwise hackenbush, and domino shavePublication . Carvalho, Alda; Huggan, Melissa A.; Nowakowski, Richard; Santos, CarlosWe present two rulesets, domino shave and clockwise hackenbush . The first is somehow natural and, as special cases, includes stirling shave and Hetyei’s Bernoulli game. Clockwise hackenbush seems artificial yet it is equivalent to domino shave. From the pictorial form of the game, and a knowledge of hackenbush, the decomposition into ordinal sums is immediate. The values of clockwise blue-red hackenbush are numbers and we provide an explicit formula for the ordinal sum of numbers where the literal form of the base is { x | } or { | x }, and x is a number. That formula generalizes van Roode’s signed binary number method for blue-red hackenbush.
- Three-player nim with podium rulePublication . Nowakowski, Richard; Santos, Carlos; Silva, Alexandre M.If a combinatorial game involves more than two players, the problem of coalitions arises. To avoid the problem, Shuo-Yen Robert Li analyzed three-player NIM with the podium rule, that is, if a player cannot be last, he should try to be last but one. With that simplification, he proved that a disjunctive sum of NIM piles is a P-position if and only if the sum modulo 3 of the binary representations of the piles is equal to zero. In this paper, we extend the result in order to understand the complete characterization of the outcome classes, the possible reductions of the game forms, the equivalence classes under the equality of games and related canonical forms.
- Combinatorics of JENGAPublication . Carvalho, Alda; Neto, João; Santos, CarlosJENGA, a very popular game of physical skill, when played by perfect players, can be seen as a pure combinatorial ruleset. Taking that into account, it is possible to play with more than one tower; a move is made by choosing one of the towers, removing a block from there, that is, a disjunctive sum. JENGA is an impartial combinatorial ruleset, i.e., Left options and Right options are the same for any position and all its followers. In this paper, we illustrate how to determine the Grundy value of a JENGA tower by showing that it may be seen as a bidimensional vector addition game. Also, we propose a class of impartial rulesets, the clock nim games, JENGA being an example of that class.