The tag has no wiki summary.

learn more… | top users | synonyms

-2
votes
0answers
90 views

Pi in combinatorial game theory [closed]

Here, on slide 27, it says that $\pi = \{3, 25/8, 201/64, ... | 4, 7/2, 13/4, ... \}$ The largest number on the left will be $3 + 1/8 + 1/64 + \dots$ which I evaluated as \begin{align} 2 + (1 + 1/8 ...
6
votes
3answers
254 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
505 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
89 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
198 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
115 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
197 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
214 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 ...
11
votes
0answers
235 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
145 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
359 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
155 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
178 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
352 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
614 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 ...
36
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
535 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
309 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
324 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
232 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
682 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
103 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
170 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
109 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
603 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
245 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
373 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
634 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
342 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
482 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
609 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
355 views

Game on undirected graphs

One of my friends suggested the following 2-player game. ...
2
votes
3answers
794 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
512 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
283 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 ...
109
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
134 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
942 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
811 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
315 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 ...
-1
votes
4answers
527 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
617 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
349 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
881 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
520 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. ...
13
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 ...