The combinatorial-game-theory tag has no wiki summary.
7
votes
3answers
331 views
Decidability of the winning-position problem in an infinity chess with a finite number of short-range pieces only
Definitions
Long-range pieces: queens, rooks, bishops.
Short-range pieces: pawns, knights, kings.
We can extend the definition of short-range pieces to include also fairy pieces like: Berolina ...
15
votes
1answer
543 views
Paul Erdős: Determine or estimate the number of maximal triangle-free graphs on n vertices
Among the collections of the open problems of Paul Erdős on the website of
Professor Fan Chung, there is one called "number of triangle-free graphs".
...
4
votes
1answer
120 views
Nash Equilibrium in general graphical game
Any one has any ideas about how to compute the Nash Equilibrium in general graphical game? Especially, when the graph structure is not a tree.
3
votes
0answers
246 views
How many combinations does Android pattern have? [closed]
Rules-
1) At-least 4 and at-max 9 dots must be connected.
2) There can be no jumps
3) Once a dot is crossed, you can jump over it.
1
vote
1answer
122 views
The original proof of Wythoff's game
I am looking for the original proof of Wythoff's game. Wythoff provided the first full analysis of this game in "A modication of the game of nim, Nieuw Archief door Wiskunde, 199{202, 1907". However, ...
2
votes
1answer
223 views
efficient arithmetic with (short) Conway games?
We consider "games" in the sense of ONAG. Conway's definition of a game $G$ as a pair $G = \{L \mid R \}$ of sets of games, together with the definitions of inequality and the arithmetic operations ...
7
votes
1answer
217 views
Infinite-dimensional hex
Suppose $n$ players take turns selecting vertices of the grid $[k]^n = \left\{0, 1, 2, \ldots, k-1\right\}^n$. Each player is assigned a pair of opposite faces of the grid, and wins the game if they ...
16
votes
1answer
449 views
A Ramsey avoidance game
Consider the following game: Given $K_n$ the complete graph on $n$ vertices, two players take turns coloring its edges. Initially no edges are colored. At his turn a player can color a prevoiusly not ...
0
votes
1answer
155 views
What is a description of winning strategies in this tile game?
I'm hoping someone can help me figure out how to describe all winning strategies for "Player 1" in the following game:
Consider a board with $n$ tiles arranged in a row. Player 1 and Player 2 each ...
0
votes
1answer
428 views
Calculate the probability of winning for a selected tic-tac-toe player
I am not a mathematician, I am a programmer. Sorry, if formulation of the problem is inexact.
I want to calculate the probability of winning for a selected tic-tac-toe player.
I have a directed graph ...
1
vote
3answers
176 views
Simulating Mixed Nash Equilibria
I have a $N$ person game where each person has a set of $M$ discrete strategies. I know from the theory that at least one mixed strategy Nash Equilibrium exists.
Can someone please tell me how do I ...
1
vote
1answer
186 views
Infinite board games: sentences about
As a unified approach if we have an ( read any) infinite board game described as $\mathcal{G}$ using a particular axiom set A..
can a sentence be devised in A which automatically answers the basic ...
1
vote
4answers
1k views
How many possible ways are there to win in Quoridor?
Quoridor is a board game in which the objective is to move a piece across to the other side. A player can put up fences to block other players from advancing forward. How many possible ways are there ...
9
votes
1answer
373 views
The infinite X in Conway's game of life
In Conway's game of life, take the initial position to be two infinite diagonal lines of live cells, with a single cell in common. Does this thing converge to a stable configuration? I.e., is the ...
24
votes
2answers
631 views
Is there any superstable configuration in the game of life?
This question spins off of Gil Kalai's recent question on Conway's game of life for a random initial configuration.
There are numerous configurations in the game of life that are known to be ...
37
votes
7answers
3k views
Conway's game of life for random initial position
What is the behavior of Conway's game of life when the initial position is random? -- We can ask this question on an infinite grid or on an $n$ by $n$ table (planar or on a torus). Specifically ...
8
votes
3answers
572 views
Mathematical model for Hanoi Towers
The strategy for the Hanoi Tower puzzle is quite simple. It is based on parity only. In an $n$-pieces puzzle, $2^n-1$ moves are sufficient to carry the whole pile from one pole to another one. My ...
4
votes
0answers
323 views
Number of Configurations in the optimal Hanoi tower
There is a unique strategy how to move $n$ disks from the first rod to the second optimally and it takes $2^n-1$ steps, solution is obtained by simple recursion. I am interested into the following ...
30
votes
4answers
2k views
Verifying the correctness of a Sudoku solution
A Sudoku is solved correctly, if all columns, all rows and all 9 subsquares are filled with the numbers 1 to 9 without repetition. Hence, in order to verify if a (correct) solution is correct, one has ...
3
votes
3answers
363 views
Motivation and Intuition for Sprague-Grundy Theorem
I have read about Sprague Grundy Theorem and understand the proof of its correctness. However, I am unable to see the motivation behind the definitions. How do Sprague and Grundy know that they should ...
-1
votes
2answers
255 views
Generalized Sprague-Grundy Theorem
Hey,
I know what is Sprague-Grundy theorem, but I want to know about generalized Sprague-Grundy (GSG) theorem ( which is used for games with cycles ). Apparently there seems to be very less ...
14
votes
1answer
699 views
Principal maximal ideals in Z[x]/(F)
Is there some irreducible $F \in \mathbb{Z}[x]$ such that $\mathbb{Z}[x]/(F)$ has no principal maximal ideal? Equivalently, is it possible that the $1$-dimensional integral domain $\mathbb{Z}[x]/(F)$ ...
2
votes
0answers
104 views
Open games formed by pasting together infinitely many clopen games
Throughout, I think of games and their underlying trees as the same: so a "clopen game" and a "well-founded tree" mean the same thing.
Fix a sequence of clopen games $\lbrace T_i: i\in\omega\rbrace$. ...
0
votes
1answer
185 views
Equilibrium of random zero-sum game,
Hi,
How to find, or at least express, the equilibrium of a zero-sum game with an $n*n$ payoff matrix (each player has $n$ strategies) and the payoff of the entry $(i,j)$ is $u(i,j)$. $u$ a random ...
1
vote
0answers
111 views
What is known about infinite diminished disjunctive compounds of loopfree partizan combinatorial games?
Background
Basic theories of loopy (normal-play) games which may go on forever under the usual disjunctive sum (the game ends when there are no moves available for you in any component on your turn) ...
20
votes
1answer
631 views
Sane bound on number of moves for Maker-Breaker game on $\mathbb R^2$ for $\{0,1,2,3,4\}$
The description below comes from
József Beck. Combinatorial games. Tic-tac-toe theory, Encyclopedia of Mathematics and its Applications, 114. Cambridge University Press, Cambridge, 2008, MR2402857 ...
0
votes
1answer
247 views
a question on game of chess [closed]
In the game of chess,it is a proven fact that either of the three conditions hold:
1)white has a winning strategy
2) black has a winning strategy or
3)either of them can at least force a draw.
It is ...
0
votes
0answers
388 views
Calculating the Shapley value in a weighted voting game.
Given a special case of WVG (Weighted Voting Game) of $a$ 1s and $b$ 2s and a quota q, $ [q:1,1,1,1..1,2,2,..2] $. I need help with calculating the Shapley value of a player with a weight of $2$ and a ...
3
votes
3answers
650 views
Generalized tic-tac-toe
We begin with $2n+1$ cards, each with a distinct number from $-n$ to $+n$ on it, face up in between the two players of the game. The players take turns selecting a card and keeping it. The first ...
5
votes
1answer
347 views
Resources-Aware Combinatorial Game Theory
First of all, I preemptively apologize if my question happens to be naive, I am no expert of CGT (or general game theory, for that matter).
Now the question:
**is there such a thing as the study of ...
3
votes
2answers
495 views
The game of removing two vertices in a graph
Consider the following impartial combinatorial game played with finite graphs: A move removes two adjacent vertices; and of course all edges connected with them. The game then continues with the new ...
10
votes
1answer
615 views
Sliding blocks puzzle
Consider a 'game' played on a subset $S$ of an $n^2$ square grid as follows. There are 3 types of pieces, each occupying a square of $S$, 1 green, some red and the rest are blue, a move consists of ...
2
votes
2answers
375 views
2
votes
3answers
832 views
Motivation for the Sprague-Grundy theorem
The Sprague-Grundy theorem states that every impartial combinatorial game under the normal play convention is equivalent to a (unique) nimber.
What does the equivalence relation thus defined tell us ...
3
votes
3answers
519 views
Chomp! without the law of the excluded middle
Consider the following impartial combinatorial game, a generalization of Chomp! as mentioned in the paper by David Gale: At each step, we have a finite partially ordered set $S$. Player I or II ...
1
vote
1answer
290 views
A modified divisor game
Consider a two player game. There are N balls marked 1 to N. A move consists of removing a ball n and all other balls which are divisors of n (including 1). The players alternate the moves. The one ...
111
votes
3answers
5k views
A Game on Noetherian Rings
A friend suggested the following combinatorial game. At any time, the state of the game is a (commutative) Noetherian ring $\neq 0$. On a player's turn, that player chooses a nonzero non-unit element ...
2
votes
0answers
135 views
Does a generalized Queen split the upper P-positions of Wythoff Nim into two new beams of P-positions?
Wythoff Nim is an impartial game where 2 players take turns in reducing the heights of two finite heaps of tokens. Two types of moves are allowed
(I) Remove any number of tokens from precisely one ...
17
votes
3answers
1k views
Traversing the infinite square grid
Starting somewhere on an infinite square grid, is it possible to visit every square exactly once, if at move $n$, one must jump $a_n$ steps in one of the directions north,south,east or west, and mark ...
11
votes
2answers
952 views
Can anyone analyze this misere game?
Problem
Let $* = \{0\}$ be the one matchstick nim game, let $*2 = \{0,*\}$ be the two matchstick nim game, let $*3 = \{0,*,*2\} = *2+*$ be the three matchstick nim game, let $g = \{0, *2+*3, ...
5
votes
3answers
813 views
Has Sid Sackson's “Hold That Line” been analyzed?
In Sid Sackson's classic book A Gamut of Games, he introduces a game that he calls "Hold That Line." Briefly, it is an impartial pencil-and-paper game played on a finite grid of dots. The first ...
4
votes
1answer
326 views
Graph connectivity related game
I was considering the following game on an undirected unweighted graph $G=(V,E)$ (not necessarily simple). Two players, Police and Runaway, take moves in turn. Police can cut an arbitrary subset of ...
0
votes
4answers
548 views
Breaking down an impartial game into Nim equivalent
This is the game:
The playing field consists of permutation of numbers. The players take turns playing the game. Each player removes single number from the sequence. The game is finished when the ...
4
votes
1answer
623 views
Algorithmic war
No, not the war on drugs, but the game of War considered in
Does War have infinite expected length?
As noted in that discussion, the game of war can go on forever, but my question is: can it be ...
5
votes
0answers
352 views
SWAT vs Rioters (cops vs robbers variant)
I thought of this while at the Combinatorial Potlatch at Seattle University, where Peter Winkler gave an excellent talk on Cops vs Drunken Robbers. I'll just open it up to the floor. The problem ...
2
votes
7answers
917 views
Nim-like(?) game winning strategy?
I have the following Nim-like game (at least, it seems Nim-like to me).
There are $2k$ tokens in a row, $k \in \mathbb{N}$.
Each token $a_i$ has a value $ v_i \in \mathbb{N}$
All this information ...
8
votes
4answers
1k views
A “rewiring process” on graphs
I am interested in a discrete process defined as follows. We start with a given graph. At each time step we delete an edge $(i,j)$ and add two edges $e$ and $f$; the edge $e$ is incident with $i$ and ...
4
votes
1answer
552 views
Are there any interesting connections between game theory and engineering?
I am doing a senior project and it must be based off game theory, but I am having trouble finding any connections to engineering, possibly structural, or architectural, maybe even civil or mechanical. ...
14
votes
5answers
2k views
Irreversible chess
Suppose we play a chess-variant, where any finite number of pieces are allowed, and the board is as large as we wish, but only two kings in total. And there is no 50 move-rule, no castling and no ...
6
votes
1answer
2k views
Analysis of Misere Nim?
My friend likes to impress people by playing 3-5-7 which has three piles of counters of sizes 3, 5 and 7. You can remove any number of coins from a single pile, the last player to move loses.
ooo
...
