Questions tagged [combinatorial-game-theory]
Combinatorial game theory (abbreviated CGT) is the subfield of combinatorics (not traditional game theory) which deals with games of perfect information such as Nim and Go. It includes topics such as the Sprague-Grundy theorem and is tangentially related to the Surreal Numbers.
967
questions
1
vote
1
answer
30
views
(Combinatorial) Game Theory: Determinacy and Determinism
I am struggling with the concepts of Determinacy and Determinism.
Are the following statements correct(for 2-player, zero-sum games)?
Or am I getting something mixed up in my head?
A game has the ...
- 13
3
votes
0
answers
132
views
Is there a winning strategy in the card removal game?
A and B play a game with blue, red, and green cards. They start with an even number of $n$ blue cards ("stacks"). Player A starts, and the players take turns. Only two moves can be made:
(i) ...
- 53
1
vote
0
answers
51
views
Game theory question on a 2 player game
Paul and Luke are playing a game with stacks of black, red and green tiles.
At the start of the game, there are n stacks of one black tile on the board, where n is any positive integer.
Paul begins. ...
- 79
1
vote
1
answer
84
views
Nim variant with two piles where in each turn the sum of their sizes gets reduced by three
So in this game we have two piles of size n and m respectively. Two players take turns, in each turn the player chooses one pile to reduce its size by 2 and the other gets reduced by 1. For example ...
- 13
2
votes
0
answers
144
views
What is the chance of one player winning a chess tournament?
Person A plays a chess tournament against persons B and C. Person B is a professional, while person C is an amateur. Person A wins the tournament if they achieve at least $k$, $k<n$ consecutive ...
- 41
1
vote
0
answers
57
views
Solving a Certain Combinatorial Game
I've been trying to come up with a combinatorial game even simpler than Hex with non-trivial gameplay and been failing dismally. Currently, my idea is that players sequentially lay pieces on a ...
- 2,246
1
vote
1
answer
86
views
What Hackenbush game represents oof? [closed]
I have been reading about Hackenbush recently and have learned that the surreal numbers can be represented using RGB Hackenbush. I am having a hard time understanding On, Off, and Oof. What Hackenbush ...
- 134
5
votes
1
answer
194
views
When is "do-almost-nothing" a good idea in CHOMP?
Now asked at MO:
The proof by strategy-stealing that CHOMP on a rectangular board is a first-player win involves player 1 taking the top-right square on their first move. Of course given the proof-by-...
- 237k
0
votes
1
answer
24
views
Maximizing Neighboring Count in a Sequential Grid Placement: A Combinatorial Optimization Problem [closed]
Given a 20x20 grid and an initial value of N = 0, we follow a certain strategy to place a piece into each cell of the grid sequentially. Upon each placement of a piece, we calculate the number of ...
- 3
0
votes
0
answers
37
views
A graph coloring game of merging subgraphs
A graph coloring game
This is a 2-player game played by players $A$ and $B$. A random non-trivial planar connected graph $G(V,E)$ is chosen. Player $A$ sets up the game as follows:
Player $A$ ...
- 3,133
0
votes
0
answers
43
views
Jeson Mor chess variant - graph problem equivalent
It is rather a kind of general question, any hints are very pleasant to see :)
There is a chess variant called Jeson Mor: https://en.wikipedia.org/wiki/Jeson_Mor. Briefly speaking, the goal of this ...
- 31
2
votes
1
answer
205
views
4-color coloring game.
Similar to this question.
5-color coloring game.
Let there be two players, $𝐴$ and $𝐵$, and a map.
They now play a game such that:
Player $𝐴$ picks a region and player $𝐵$ colors it such that the ...
- 796
0
votes
1
answer
40
views
Minesweeper sparsity and information processing
I've noticed while playing Minesweeper that when I have too few bombs, I get very easy to play games. In other words, I get games that can be solved with very simple algorithms. When I play games with ...
- 21
3
votes
1
answer
154
views
How come $\omega^3=2$ for infinite nimber $\omega$?
The Details:
I don't know much about nimbers. It is my understanding that their multiplication is different than ordinary numbers. I'm not sure how to multiply infinite nimbers together; it's given ...
- 43k
2
votes
1
answer
61
views
Translate an extensive form game into normal form game
I have the following problem. It is about how to analyze the coin game and finally find its Nash equilibrium.
The coin game: 2 players each get $n$ coins and will play $k$ rounds. Each round each of ...
- 21
1
vote
1
answer
128
views
What are some applications of Surreal Numbers outside of Go endgames?
I've read through Don Knuth's book, a fair amount of "Winning Ways for your Mathematical Plays" and watched a handful of videos, and almost all the material seems to talk about definitions, ...
- 11
2
votes
1
answer
94
views
Why restricted removal Nim games with 1 pile has pattern (cycle in states)?
I working on solution of NIM-like game, where players take from one piece from 1 to k and players can't repeat previous turn (only the opponent's previous move). Total n stones in beginning. Winner is ...
- 21
1
vote
2
answers
59
views
Questions on Sprague-Grundy Theorem
In my current understanding, the idea of Sprague-Grundy is basically:
There is Nim space $N$, and regular game space $G$ (which is a DAG where vertices are states and edges are possible actions)
By ...
- 21
0
votes
0
answers
26
views
Preperiod and Period of the nim-sequence of Octal Games .17 and .117
This refers to a type of impartial game defined as octal games by Berlekamp, Guy and Conway in the first edition of the Winning Ways books.
I noticed that the nim-sequences of $.17$ and $.117$ (first ...
- 1
1
vote
0
answers
85
views
Probability of a draw in the game
There is a basket with $n$ balls, such that $n$ is even. Balls come in $k$ colors. The number of balls of each color is specified by a list of positive integers $c_1,c_2,\dots,c_k$, where $c_1+\dots+...
- 119
3
votes
0
answers
50
views
Can there exist a set $S$ and $F_1, F_2 \in ([5] \times S)^{([5]^S)}$ such that for all $f_1,f_2\in [5]^S$, $F_1(f_1)\in f_2$ or $F_2(f_2)\in f_1$?
Here $[5]:=\{0,1,2,3,4\}$ and for sets $O,I$, $O^I$ denotes the set of functions from $I$ to $O$.
The motivation for this question comes from the following axiom of choice "paradox":
Let $...
- 111
0
votes
1
answer
108
views
Calculating Prize Line Expectation Part 2
Thanks in advance for any help.
Yesterday a very helpful member called @joriki answered my original question on this and that conversation came to a conclusion as a result. I have a second part that ...
- 31
7
votes
4
answers
163
views
Colour $2$ or $3$ numbers that total $15$
So my friend comes up and confidently says that he can defeat me in this game:
The integers $1$ to $14$ are written down on a blackboard (paper in our case).
Players take turns colouring (striking ...
- 2,429
0
votes
0
answers
87
views
Maximize the score of a card game
About the game
This game consist on a deck of 24 cards. Each has a color (there are only 3 colors) and a number (from 1 to 8), and each card is unique.
Every turn you are given cards (randomly) from ...
3
votes
0
answers
197
views
Combinatorial game greater than its left options and smaller than its right options.
A number in combinatorial game theory is a game $x=\{x^L\mid x^R\}$ such that all its options are numbers and there are no $x^L,x^R$ such that $x^L\geq x^R$.
It turns out, after some work, that if $x$ ...
- 1,385
-1
votes
1
answer
110
views
Show that player I can always win a Nim game in which the number of heaps with an odd number of coins is odd
Show that player 1 can always win a Nim game in which the number of heaps with an odd number of coins is odd. This question is provided in Richard A. Brauldi's book on Introductory Combinatorics. I ...
- 1,377
2
votes
0
answers
63
views
Reference Request for Combinatorial Game Theory
Some time ago I found a paper, written I believe by Conway, in which the author describes different operations we may perform on combinatorial partizan games and how these operations can be used in ...
- 1,385
1
vote
1
answer
75
views
TicTacToe on an NxN Board
I am attempting to find a strategy for the second player that leads to a forced draw in the case of a general NxN TicTacToe game where N fields in a row/column or diagonal are required to win the game....
- 73
3
votes
0
answers
100
views
Does "adding rainbows" eventually stabilize in $\ge 4$-color Hackenbush?
EDIT: now generalized and asked at MO.
This is an outgrowth of an earlier MSE question, which itself was motivated by an MO question. An answer to this question is claimed there as well, but the ...
- 237k
5
votes
1
answer
111
views
Tricolor columns-only Hackenbush boards: must adding the "rainbow" board eventually stabilize?
This is a question about "columns-only three-color Hackenbush." Formally, a board is a finite formal sum (or multiset if one prefers) of finite strings from $\{1,2,3\}$. For $i\in\{1,2,3\}$ ...
- 237k
1
vote
0
answers
28
views
Find an optimal strategy to win with highest probability in a hat game [duplicate]
The magician gives each of $2^n - 1$ prisoners a hat, which is colored black or white. Each prisoner's hat color is likely to be white as much as it is likely to be black (each prisoner's hat color is ...
- 2,408
2
votes
1
answer
150
views
Hat guessing game optimality of best strategy
Given the following variant of the hat guessing game: There are n players and two colors, everybody has to guess his hat color. The aim is to find a strategy guaranteeing as many correct guesses as ...
- 623
5
votes
1
answer
67
views
Guessing a triple of digits by knowing if you got at least one of them right
Here is a rephrased version of problem $4$ in BMO $2016$ round $2$. I rephrased to make it clearer and shorter.
Given is a triple of digits $(a,b,c)$, where $a$, $b$, $c\in\{0,1,\dots,9\}$. Each turn ...
user1034536
4
votes
1
answer
127
views
How to calculate multiplication of transfinite nimbers with a Cantor normal form
I failed to calculate nimber multplication in the form of $[\omega^\alpha]*[\omega^\beta]$, according to the "mex" definition.
The cases when $\alpha<3,\beta<3$ are easy, while $[\...
- 53
0
votes
2
answers
55
views
Defining a finite impartial game.
I've been wondering how to abstractly describe a finite impartial game, and if there exists a standard way to do so, similar to how one would define a metric space $(M,d)$.
I've read this related ...
- 349
30
votes
1
answer
1k
views
In the game of Repeat-a-Number, who wins?
I devised a game recently. There is a string of numbers, and each player extends the string by appending a number to the end based on the current last number of the string. The string starts as the ...
- 3,831
1
vote
1
answer
74
views
Two players are trying to figure out the binary code
Two players guess code that is hidden in $2^n$ ($n\geq2$, n $\in$ $\Bbb N$) digits that each contain either 0 or 1 which makes a binary code that consists of zeros and/or ones, for example, '0010' is ...
0
votes
1
answer
70
views
Help determining best strategy to play a game
The game is a simple version of tic tac toe which this YouTuber made
rules of the game are simple
tic-tac-toe like 3 x 3 Grid
p1 can place horizontal marks and p2 can place vertical marks
players ...
- 3
2
votes
0
answers
140
views
Who wins in this simple "factoring game" depending on the starting number?
There is a given $N$ written on a board. Two players, Alice and Bob choose a number from the board and factorize that number to $N=XY$ where $\gcd(X,Y)\neq1$, then erase $N$ and write $X, Y$ on the ...
- 742
3
votes
1
answer
305
views
Does the game Go have an algebraic structure?
What if we considered each arrangement of pieces on the board to be an element in the set of all configurations, and somehow, each new possible move to be sort of a transformation of the current state ...
- 255
2
votes
1
answer
121
views
Two players take turns placing a domino onto a $6\times6$ grid. The first player who can't place a domino loses.
Two powerhouses of history go head to head.
Leonhard Euler starts. Carl Friedrich Gauss plays second.
They have a $6\times 6$ grid. Each turn a player places a domino (a $1\times2$ or $2\times1$ ...
- 21
0
votes
1
answer
493
views
Winning strategy with game of coins
Alice and Bob are playing a game. They
choose a natural number $n$ and build a stack of $n$ coins. Taking turns, they can remove 1,
2 or 3 coins from this stack. The player that takes the last coin ...
- 17
0
votes
1
answer
106
views
Nash equilibria problem [closed]
I have a problem to solve the next exercise.
Two players call a number from 1 to 100. The winnings are distributed as follows: players always receive no more than 100 rubles in total, the most greedy ...
- 19
1
vote
1
answer
124
views
Any tips or idea how to play this combinatorial game?
There is this puzzle called Chomp. You can play and read about it here if you don't know it:
https://www.math.ucla.edu/~tom/Games/chomp.html
It is well-known that Chomp has a winning strategy for the ...
- 5,544
1
vote
0
answers
48
views
Minimax over long term, one player plays first for a long time -> converges to single player game optimum
Suppose there is a game with two players involving probability. There are finitely many game states, and associated with each state is a set of moves available to the current player, and each move ...
- 85
2
votes
0
answers
46
views
Formal definition of decision tree
I am looking for a reference that would provide a formal definition of a decision tree. I am mostly referring to combinatorial games, Markov decision processes and similar fields. It should be ...
- 193
1
vote
0
answers
76
views
Number of nodes in a game tree for a binary choice card game
Say you have a game played with a deck of $M$ cards. Every turn, you draw a card and either choose to add the card to your hand, or decline to add it to your hand. If you take the card, your opponent ...
- 111
0
votes
1
answer
404
views
What is the hardest winnable tic-tac-toe-ish game? [closed]
A tic-tac-toe-ish game is a game on an infinite where the goal is to claim a specific set of cells reflected, rotated, or translated where each player takes turns claiming a cell. A winnable tic-tac-...
- 3,831
1
vote
0
answers
44
views
How many Legal positions of tic tac toe are possible? (Ignoring symmetry) [duplicate]
I wanted to know how many possible legal positions of tic-tac-toe can be found if we ignore symmetry. I have done a little calculation myself but the answers i have found in the internet are way ...
3
votes
1
answer
94
views
An interesting combo question about the lights on-off game
There are n lights, one at each vertex of a regular $n$-gon. Only one light is on at first, each time you can select some vertices to form a regular $m$-gon($m|n$) and change the state of all lights ...
- 135