Search

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.

Restricted (s, t)-Wythoff’s game, introduced by Liu et al. in 2014, is an impartial combinatorial game. We define and solve a class of games obtained from Restricted (s, t)-Wythoff’s game by adjoining to it some subsets of its P-positions as additional moves. The results show that under certain conditions they are equivalent to one case in which only one P-position is adjoined as an additional move. Furthermore, two winning strategies of exponential and polynomial are provided for the games.

Letting a = 1 in a- Wythoff’s game introduced by Fraenkel yields Wythoff’s game which is a well-known 2-player impartial combinatorial game introduced by Wythoff in 1907. A method of solving n-player impartial games was presented by Krawec in 2012. In this paper, we employ Krawec’s function to analyze n > 2 players a-Wythoff’s game and obtain game values for all a 1. The results obtained cover n-player Wythoff’s game, a special case 1-Wythoff’s game.

Nim博弈是博弈论中最经典的模型之一，1902年C.L. Bouton给出其完全解。其变形版本的玩法日益受到人们的喜爱，这篇文章介绍了一个Nim博弈的变形玩法，K-L-Nim博弈。其中一个玩家每次不能拿走k个石子(但可拿走多于或者少于k个石子)，而另外一个玩家不能拿走l个石子(但可拿走多于或者少于l个石子)。这篇文章巧妙地借助了Sprague-Grundy定理研究了k=l时的组合解。并用数学归纳法和Bouton定理给出了k≠l时所有组合解。 Perhaps the most famous combinatorial game is Nim, which was completely analyzed by C.L. Bouton in 1902. From then on, the variant of Nim game is getting more and more popular. This paper introduces a new variant of Nim game, K-L-Nim game, one player’s illegal move is to remove k stones from one pile, while the other player’s illegal move is to remove l stones from one pile. This paper gives a complete solution for the game by using Sprague-Grundy Theorem, Bouton Theorem and mathematical induction.

In maths lessons in secondary school, on certain occasions my teacher entertained our class with the following game. Each player starts with an empty 2 × 5 grid, as shown in Figure 1(a). In each round of the game, a die is rolled, and each player has to choose one of the empty boxes in their grid and fill it with the number rolled. For example, after 3 rounds, a player's grid may look like the one in Figure 1(b). After 10 rounds everyone's grid is filled, forming two 5-digit numbers. A player's score is the sum of her/his two 5-digit numbers. Players with the largest sum win the game. We shall call this the ‘dice-and-numbers game’. It is easy to think of other variants. Any child who is comfortable with column addition and understands how place value affects the size of numbers will develop a reasonable strategy for the game.

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.

For card games of the Beggar-My-Neighbor type, we prove finiteness of the mathematical expectation of the game duration under the conditions that a player to play the first card is chosen randomly and that cards in a pile are shuffled before being placed to the deck. The result is also valid for general-type modifications of the game rules. In other words, we show that the graph of the Markov chain for the Beggar-My-Neighbor game is absorbing; i.e., from any vertex there is at least one path leading to the end of the game.

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.

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.

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).

A Nim-type computer game of strategy on plane is described in this paper. It is demonstrated that winning strategies of this two-person game are determined by a system of equations with two unknown integer sequences. Properties of winning points/states are discussed and an O(loglogn) algorithm for the winning states is provided. Two varieties of the Game are also introduced and their winning strategies are analyzed.

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.

Consider a three-person game that occurs in stages. The state of the game is given by the integral amounts of chips that the players have, say x=(x1, x2, x3) with M=x1+x2+x3 fixed. At a stage of the game, player i places ai chips in the pot, an integer between 1 and xi. (Player i is already eliminated from the game if xi=0.) The winner of the pot is then immediately chosen in such a way that player i wins the pot with probability proportional to the index wiai for i with xi>0. The idea is that if player i bets more, then he is more likely to win, but this is modified by weights that parameterize the players’ abilities.Each player is trying to maximize his probability of taking all the chips (i.e., reaching xi=M). In the two-person game, it is known that a Nash equilibrium is for each player to adopt strategy σ of playing timidly (ai=1) or boldly (ai=xi) according to whether the game is in his favor or not (assuming the other also plays σ). In this article, we investigate whether this also is the form of a Nash equilibrium in a three-person game when the weights are of the form (w1, w2, w3)=(w, w, 1−2w) with 01/3 and M≥8.

We define a two-player combinatorial game in which players take alternate turns; each turn consists on deleting a vertex of a graph, together with all the edges containing such vertex. If any vertex became isolated by a player's move then it would also be deleted. A player wins the game when the other player has no moves available. We study this game under various viewpoints: by finding specific strategies for certain families of graphs, through using properties of a graph's automorphism group, by writing a program to look at Sprague-Grundy numbers, and by studying the game when played on random graphs. When analyzing Grim played on paths, using the Sprague-Grundy function, we find a connection to a standing open question about Octal games., 13 pages, 0 figures

A single player strategy game is studied in this paper. We are interested in algorithms which, given integer n, generate the corresponding move sequences to reach the final state of the game with smallest number of steps. In this paper we present an optimal algorithm to generate an optimal move sequence of the game consisting of n black checkers and n white checkers, and finally, we present an explicit solution for the general game of size n.

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 introduce and study a Maker-Breaker type game in which the issue is to create or avoid two disjoint dominating sets in graphs without isolated vertices. We prove that the maker has a winning strategy on all connected graphs if the game is started by the breaker. This implies the same in the $(2:1)$ biased game also in the maker-start game. It remains open to characterize the maker-win graphs in the maker-start non-biased game, and to analyze the $(a:b)$ biased game for $(a:b)\neq (2:1)$. For a more restricted variant of the non-biased game we prove that the maker can win on every graph without isolated vertices., 18 pages

E. Duchene et al investigate games whose sets of allowed moves are subsets of Wythoff's one, and whose set of P-positions is exactly Wythoff's sequence. Their results show that such a game does not exist. In this paper, we find a pair of games, one is the restricted version of the other, such that they have the same set of P-positions. We also find another pair of games, one is the restricted version of the other, such that they do not have the same set of P-positions. This means that the preservation of P-positions between a game and its restricted game depends on the game itself.

We study a combinatorial game named “sankaku-tori” in Japanese, which means “triangle-taking” in English. It is an old pencil-and-paper game for two players played in Western Japan. The game is played on points on the plane in general position. In each turn, a player adds a line segment to join two points, and the game ends when a triangulation of the point set is completed. The player who completes more triangles than the other wins. In this paper, we consider two restricted variants of this game. In the first variant, the first player always wins in a nontrivial way, and the second variant is NP-complete in general.

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.

One of the games routinely played on the TV game show The Price is Right involves spinning a large wheel with the nickel values 5, 10, 15, …, 100 on it. The object of the game is to have the highest total score, from one or two spins, of all of the players in the game without going over a dollar (100). Using conditional probability and a Pascal computer program, the authors derive the optimal stopping times for all three players in the usual game.

In Complex Adaptive Systems, agents co-adapt to each other through interaction. A typical example is game: players learn and adapt to the opponent through game playing. This paper studies the adaptive characteristic of co-adaptation through a combinatorial game “Five-in-a-row” focusing on the evaluation function and game tree. The computer simulations show that a high-level player (with a good evaluation function) will win more if she knows the opponent's next move, but a low-level player (with a relatively worse evaluation function) will lose more if she knows the opponent's next move. We call this phenomenon "knowing more is less". To explore the reason and the generality of this phenomenon, an abstract theoretical model is built on a full k-ary game tree. Analysis and numerical simulations based on this model prove that “knowing more is less” will happen for a player if her evaluation function accuracy rate is below 0.5. This result indicates that during combinatorial game playing, identification of the opponent only is not enough; the player also need to improve her evaluation function for the board in the sense of mini-max solution as well.

A.S. Fraenkel introduces a new a-Wythoff's game which is the generalization of Wythoff's game. Fraenkel determines all P-positions of a-Wythoff's game under normal play convention. In this paper, we introduce two new restricted versions of a-Wythoff's game, Odd-Even Wythoff's Game and Odd-Even a-Wythoff's Game. Both new games are investigated. All its P-positions under normal play convention are given, and the corresponding wining strategies are also presented.

This article concerns the resolution of impartial combinatorial games, and in particular games that can be split in sums of independent positions. We prove that in order to compute the outcome of a sum of independent positions, it is always more efficient to compute separately the nimbers of each independent position than to develop directly the game tree of the sum. The concept of nimber is therefore inevitable to solve impartial games, even when we only try to determinate the winning or losing outcome of a starting position. We also describe algorithms to use nimbers efficiently and finally, we give a review of the results obtained on two impartial games: Sprouts and Cram., 12 pages, 11 figures

A general game player is a system that can play previously unknown games given nothing but their rules. A key to success in this endeavour is the ability to automatically gain knowledge about new games that follows from the rules without being explicitly given. In this paper, we show how a recently developed, theoretical method for automated theorem proving in general game playing can be put into practice. To this end, we extend the method so as to allow a general game player to systematically search and verify multiple temporal game properties at once. We formally prove this extension to be correct, and we report on extensive experiments that show how this improvement helps to significantly enhance the ability of a successful general game player to infer new properties about a previously unknown 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 create a new two-player game on the Sperner Triangle based on Sperner's lemma. Our game has simple rules and several desirable properties. First, the game is always certain to have a winner. Second, like many other interesting games such as Hex and Geography, we prove that deciding whether one can win our game is a PSPACE-complete problem. Third, there is an elegant balance in the game such that neither the first nor the second player always has a decisive advantage. We provide a web-based version of the game, playable at: http://cs-people.bu.edu/paithan/spernerGame/. In addition we propose other games, also based on fixed-point theorems.

The analysis of the classical game of Nim relies on binary representation of numbers as shown in the books of Berlekamp and Gardener. There is considerable interest in generalizations and modifications of the game. We will consider one-pile misère Nim for more than two players. In the case of three or more players, the impartial game theory results rarely apply. In this note, we analyze the game in a variety of cases where alliances are formed among the players.

We consider a natural generalization of the classical ruin problem to more than two parties. Our "ruin" problem, which we will call the (k, I)-game, starts with k players each having I units as its initial capital. At each round of the game, all remaining k′ players pay 1/k′th unit as game fee, play the game, and one of the players wins and receives the combined game fees of 1 unit. A player who cannot pay the next game fee goes bankrupt, and the game terminates when all players but one are bankrupt.We analyze the length of the game, that is, the number of rounds executed until the game terminates, and give upper and lower bounds for the expected game length.

About fifty years ago Ed Gilbert proposed a guessing game that remains unsolved and has largely been forgotten. The aim of this note is to revive interest in the game. 1. INTRODUCTION. About fifty years ago, Ed Gilbert proposed the following guessing game: Alice thinks of an integer from 1 to n which Bob must repeatedly guess. After each guess, Alice tells him whether his guess is too high or too low or correct. If Bob has guessed the number, then the game ends. If not, then Alice may change her secret number, but her new number must agree with the information that she has passed on to Bob. At the end of the game, Bob pays Alice one dollar for each guess that he has made. The game ends after at most n rounds, and Alice's gain is Bob's loss. This is a finite zero-sum game and by Von Neumann's fundamental theorem of game theory, there is a number V , called the value of the game, which is the fair price that gives Alice the right to play the game. More specifically, Alice has a mixed strategy which guarantees her an average gain of at least V dollars, regardless of Bob's play. Conversely, Bob has a mixed strategy which guarantees him an average loss of no more than V dollars. I assume that the reader is familiar with these concepts. An excellent text on the subject is (2). The guessing game is a recursive game and the value can be computed recursively. If nD 4, then it is not hard to compute that V is equal to 2 11 dollars, but what about general n? Is it possible to compute V asymptotically, as n goes to infinity? This ques- tion has remained open for almost fifty years, despite the fact that guessing games have accumulated a fair amount of theory (see (1, chapter 5)). One should know that Gilbert also considered another game, which is commonly known as Dresher's guessing game (see (2, problem 16)). The guessing game that we consider here seems to have been forgotten.

This is a digital board game designed as an entertaining educational tool. Adapted from “MONOPOLY,” the board appears on the computer screen and the players roll digital dice and their game piece moves appropriately. The space landed on will have a category assigned and produce a question from that category. Correctly answering the question gives ownership of the space and awarding of points. Players subsequently landing on the space must answer another question from the category or lose equivalent points. The game proceeds until one player has circled the board three times or any player reaches preset point total. The game is designed to import questions from a digital question bank that the end-user can edit. The game provides referenced explanation of erroneous choices.

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.

A discrete search game with an immobile hider is posed and solved. The game is a discrete analogue of a known continuous game where the search takes place on three arcs which connect two points. A solution to the continuous game is obtained as a limiting case.

An inspector's game is a non-constant sum 2person game in which one player has promised to perform a certain duty a5d the other player is allowed to occasionally inspect and verify that the duty has indeed been performed. A solution to a variant of such a game is given in this paper, based on the assumption that the inspector can announce his mixed strategy in advance, if he so wishes, whereas the other player, who has already given his promise, cannot threat by explicitly saying that he will not keep his word. (Author)

(3) In this paper, we shall identify two games if there is a one-to-one correspondence between their players identifying their families of winning sets; to name a more definite object one must say, not "the game G", but "the game G with ordered players Pi, * *, P,", or a similar phrase. Beyond this, note that an n-player game (e.g. the 435-player game 'of the House of Representatives) may be converted into an (n + k)-player game by adjoining k "voteless" players or dummies. The phrase "an n-player game G" does not here imply that all n players are non-dummies. (In the first part of the argument we need games with dummies; afterward we shall exclude them.) A majority game is a game for which one can assign numerical weights wl, , wn to the players so that the winning sets are precisely those sets which have more than half the total weight. Some of the wi may be negative or zero; it is easy to see that the corresponding players must be dummies. (Since every superset of a winning set wins, a player can have negative weight wi only if I wi I is so small that it makes no difference.) Given a game G, the question whether G is a majority game is effectively decidable, since it turns on a finite system of linear inequalities. No better method than the obvious ones is known. It is clear that every majority game has non-negative integral weights-even positive integral weights, for any weights may be assigned to the dummies provided the weights of the other players are made large enough. The method described below for enumerating all majority games depends on the determination of the game with ordered players with weights (wo, w1, * , w ) by the systems (woV + wl, w2, ***, wn) and (wo -w1, w2, ***, wa). The choice