Skip to main content

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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
21 views

Bingo patterns probability [closed]

I want to calculate the probability of winning a patterns bingo I have some rules. 60 unique numbers on 4 tickets one ticket has a 3x5 (3 rows, 5 colons), I have a patterns one of them is to fill all ...
Volodymyr Yaropud's user avatar
3 votes
0 answers
50 views

Expected number of edges to draw in a bipartite graph until you get a crossing

I was asked by a friend to calculate the number of edge crossings in a $m \times n$ complete bipartite graph: Now play a game where you randomly select an edge with equal probability each turn: what ...
fencer22's user avatar
1 vote
1 answer
70 views

Game - two players take turn moving a marker to an adjacent square in a 9x9 grid

A marker is placed in the centre of a $9$x$9$ grid. Ann and Beth take turns moving the marker to one of the adjacent squares (one sharing a side) provided that this square has never been occupied by a ...
Abhinav Sood's user avatar
0 votes
1 answer
41 views

Even-Nim and Odd-Nim are like Nim in that they are played with piles of stones.

Even-Nim and Odd-Nim are like Nim in that they are played with piles of stones. However, in Even-Nim, a move consists of removing a positive even number of stones from a pile, while in Odd-Nim, a move ...
user avatar
0 votes
0 answers
87 views

Conway's Angel Problem: Strategy for Devil to catch $1-$Angel

I am learning about Conway's Angel Problem, which is in the image below. How can the Devil devise a strategy that will successfully capture the $1$-Angel, or an angel of power $1$, which is also a ...
GSmith's user avatar
  • 150
2 votes
0 answers
17 views

For a given pair of positions in a family of winning sets, how many winning sets contain it?

This is a lot of exposition for what (I think) amounts to be a pretty simple combinatorics question. It's about bounding the Max Pair-Degree from Beck's Combinatorial Games: Tic-Tac-Toe Theory. On ...
weekendwarrior's user avatar
5 votes
0 answers
103 views

$2$-for-$2$ asymmetric Hex

If the game of Hex is played on an asymmetric board (where the hexes are arranged in a $k\times k+1$ parallelogram), the player who wants to connect the closer pair of sides can force a win, ...
volcanrb's user avatar
  • 3,054
3 votes
2 answers
95 views

Game where players remove up to $t$ stones on turn number $t$

Please help me with following problem. There are 100 stones. Two persons play the following game: the first person takes 1 stone. The second takes one or two. Then the first person takes one or two or ...
Fermat's user avatar
  • 5,254
3 votes
1 answer
107 views

A game on a rectangular board

Setup Let there be a board looking like a rectangular table. A piece is placed at any square of the board. Two players play a game. They move the piece in turns. The piece can only be moved to an ...
Aig's user avatar
  • 5,531
0 votes
1 answer
75 views

Game with 2024 chips to remove

Two players play with a pile of 2024 chips placed on a table. Each in turn, a player removes a certain number of chips from the gaming table: at least one chip, but no more than half of the chips ...
mattandmaths's user avatar
1 vote
2 answers
56 views

coin flipping competition

A, B, C are flipping a coin independently until they got a head (same experiment "to get a head" is repeated by these 3 people). Denote X, Y, Z stand for ...
Xu Shan's user avatar
  • 238
2 votes
1 answer
55 views

WWfYMP: Bypassing reversible moves

This question concerns the theory developed in Winning Ways for Your Mathematical Plays. The relevant Volume 1 can be found online here. I'm unclear about the intuition behind the authors' "...
Zerkoff's user avatar
  • 489
6 votes
1 answer
99 views

Combinatorial game played on a grid

Let the grid consist of r rows and k columns. Two players take turns moving a piece to an adjacent square (no diagonal moves). Once a square has been visited it cannot be visited again. The piece ...
elbarto36's user avatar
  • 111
5 votes
1 answer
242 views

Taking stones game beginning with 1 to 4 stones in a 2 player game. If we started with 18 stones, is the a winning strategy for the first player?

Amy and Beck are playing 'taking the stones game'. There are 18 stones on the table, and the two people take stones in turns. The first move of the starting player can take 1 to 4 stones. For the ...
Jonny Boy1's user avatar
1 vote
0 answers
42 views

A combinatorial game about split chocolate bar [duplicate]

The chocolate bar is a rectangle $m*n$ , divided by a recess into single squares. Two players play the next game in turn. On each turn, it is allowed to pick up one square of chocolate that has not ...
Email's user avatar
  • 61
8 votes
1 answer
163 views

game coloring points rioplatense olympiad 1999

This problem is from the Rioplatense MO 1999/3 L3. The question is the following: Two players $A$ and $B$ play the following game: $A$ chooses a point, with integer coordinates, on the plane and ...
amkpm90's user avatar
  • 352
1 vote
1 answer
29 views

Should the maximal flow through a parted jungle uniquely prescribe its atomic weight?

This paper (pages 19-22) offers an algorithm for deciding which player will win Hackenbush when the position is a parted jungle. The key step seems to be very similar to the Ford-Fulkerson algorithm, ...
user10478's user avatar
  • 1,912
2 votes
1 answer
128 views

Nim multiplication inverse

We have $$\operatorname{mex} S=\min \{n \in \mathbb{N} \mid n \notin S\},a \oplus b=\operatorname{mex}\{a' \oplus b ; a \oplus b', \forall a', b'\in \mathbb{N}: a'<a, b'<b\},$$ and $$a \otimes b=...
Math_fun2006's user avatar
0 votes
0 answers
91 views

Tic-tac-toe possible grids

Let's consider the tic-tac-toe game, with two players and a natural number n of rows and columns (X starts; the winning player is the first who fills up a row, a column, the diagonal or the ...
Amanda Wealth's user avatar
1 vote
1 answer
78 views

Mex function - Lemma 23

We have $\operatorname{mex} S=\min \{n \in \mathbb{N} \mid n \notin S\}$ and $a \oplus b=\operatorname{mex}\{x \oplus b ; a \oplus y, \forall x, y \in \mathbb{N}: x<a, y<b\}$. Prove that $$\...
Math_fun2006's user avatar
1 vote
1 answer
81 views

Mex - minimum excluded value

We have $\operatorname{mex} S= \min \{n \in \mathbb{N}| n \notin S\}$ and $a \oplus b= \operatorname{mex}\{x\oplus b;a \oplus y,\forall x,y \in \mathbb{N}:x<a,y<b\}.$ Let $n,a \in \mathbb{N},a&...
Math_fun2006's user avatar
0 votes
1 answer
99 views

How can I calculate a Blue-Red Hackenbush position value using the Simplest Number Tree?

In this document (pages 5-7), the Simplest Number Tree is used to explain how to assign a value to any arbitrary Blue-Red Hackenbush position. I'm having trouble following its approach. I think I ...
user10478's user avatar
  • 1,912
3 votes
1 answer
262 views

Game of cards and divisors

Ana thinks about some different non-zero natural numbers, and for each of them, she writes on a card every positive divisor. Then, Ana hands all the cards to Maria, who groups them based on the number ...
math.enthusiast9's user avatar
4 votes
3 answers
131 views

Reference for Combinatorial Game Theory [duplicate]

I have become interested in the game of Go and have always loved mathematics. After some reading I have found the subject of combinatorial game theory. I'm looking for a book on the subject with a ...
sean1342's user avatar
1 vote
1 answer
95 views

$n$ piles, $m$ objects. Choose two piles and remove n objects in total from the two piles. Iterate. For which (m,n) is it possible to empty all piles.

Let $m < n$ be positive integers. Start with $n$ piles, each of $m$ objects. Repeatedly carry out the following operation: choose two piles and remove $n$ objects in total from the two piles. For ...
donas konas's user avatar
1 vote
0 answers
35 views

How related are the magnitude of surreal number combinatorial game values and the propensity to win in spite of potential mistakes?

Surreal numbers are used to represent values of positions in partizan games with perfect information and discrete outcomes (win/lose or win/draw/lose). The primary example is Blue-Red Hackenbush, but ...
user10478's user avatar
  • 1,912
12 votes
2 answers
653 views

Placing kings on a 6x6 board - who wins?

Two players alternate placing kings on a $6\times6$ chessboard, such that no two kings are allowed to attack each other (not even two kings placed by the same player). The last person who can place a ...
Akiva Weinberger's user avatar
2 votes
1 answer
50 views

What are the arguments for/against interpreting the magnitude of the value of Blue-Red Hackenbush as an objective function?

There appears to be a common assumption in Blue-Red Hackenbush that the Blue player should make whichever move will maximize the position value of the game, and the Red player should make whichever ...
user10478's user avatar
  • 1,912
2 votes
1 answer
98 views

Connection between combinatorial game theory and game theory in optimization

As far as I know, there are researches about "combinatorial game theory" and "game theory in optimization" which are generally "unrelated" branches. Is there any ...
Hưng Trần Nguyễn Nam's user avatar
4 votes
1 answer
253 views

Restricted Nim with one pile

Found this game in a tiktok filter, tried to solve it and got stuck. Consider a game of nim, with a single pile of N stones. On their turn, each player can remove either one or two stones. The winning ...
0x716's user avatar
  • 43
2 votes
0 answers
55 views

How to identify which move should be made in Green Hackenbush involving general, possibly-cyclic graphs?

In Green Hackenbush, if the goal is merely to find Sprague-Grundy values, the approach is to transform the arbitrary graphs into trees using the fusion principle, then transform the trees into Nim ...
user10478's user avatar
  • 1,912
1 vote
1 answer
77 views

How to prove that the following conclusion is true? [closed]

Consider a set $\mathcal{X}$ with $m$ numbers, and take out $a, b, c, d$ numbers respectively. The number of combinations of $a$ number taken from $\mathcal{X}$ is recorded as $C_{m}^{a}$. The number ...
Kristy's user avatar
  • 21
2 votes
0 answers
56 views

Can there be a Nim j, k which generalizes Nim k?

In Nim, players must remove objects from exactly $1$ heap, and the winning strategy involves converting all heap sizes to base $2$, and removing objects to manipulate to $0$ the digital sum in base $2$...
user10478's user avatar
  • 1,912
7 votes
1 answer
230 views

The taking away k/p marble game

Came up with this game, haven't thought of a catchy name for it, but here it goes: There are $n$ marbles. Two players alternate between taking away $\frac{kn}{p}$ marbles, where $p$ is a prime number (...
math scat's user avatar
  • 197
4 votes
1 answer
110 views

Winning strategy for a nim-esque game (Combinatorial Game Theory)

The rules of the game are as follows: There are two players. The game starts with N number of game pieces arranged side by side in a row. Taking turns, each player removes one game piece. A piece can ...
blueshellplsno's user avatar
4 votes
1 answer
182 views

What cut should be made in a Green Hackenbush game after solving its corresponding Nim game?

Problem: Find the Sprague-Grundy values of the graphs, and find a winning move, if any. Solution: The SG value of the three-leaf clover is 2. The SG value of the girl is 3. The SG value of the ...
user10478's user avatar
  • 1,912
0 votes
0 answers
44 views

How to move marbles between tubes with the least amount of work

Consider the following problem which I give a "physical" marbles/tubes description of -- the formal description is easy to obtain from this "physical" description. Moving marbles ...
user918212's user avatar
4 votes
1 answer
255 views

How can I win Moore's Nim k?

Nim is a game where there are several heaps of pebbles. Players take turns selecting a heap, then removing any nonzero number of pebbles from that heap. Whoever takes the last pebble wins. In Nim, the ...
user10478's user avatar
  • 1,912
0 votes
1 answer
53 views

why is the expected number of wins in mosteller's 2nd answer for "successive wins" 2c+f?

The "Successive Wins" problem in Mosteller's book 50 challenging problems in probability has a second answer that is often overlooked. The problem is as follows. To encourage her daughter, ...
PLee's user avatar
  • 75
0 votes
0 answers
34 views

Lessons in Play exercise question

Suppose that you play domineering (or cram) on two 8×8 chessboards. At your turn you can move on either chessboard (but not both!). Show that the second player can win (Is it winning for the second ...
Shash Wemwal's user avatar
0 votes
0 answers
64 views

How do you pronounce $\&$ in combinatorial game theory!

I have watched Owen Maitzen’s video on combinatorial game theory, and I saw this equation: $\bf{hi} + \bf{oof} = \bf{hot} \, \rm{\&} \, \bf{oof}$ Owen Maitzen pronounced it 'hi plus oof equals hot ...
3-1-4-One-Five's user avatar
0 votes
0 answers
50 views

Book Recommendations for CGT

Could someone recommend books on Combinatorial Game Theory suitable for self-study and beginners (the book I am using is Combinatorial Game Theory by Aaron N. Siegel) (I didn't really love the Winning ...
Shash Wemwal's user avatar
0 votes
1 answer
62 views

Is $☽+n=☽$ true for finite & transfinite nimbers?

In Winning Ways Volume 2 (pg. 399) they state that "since ☽ represents the empty set, we have the obvious addition rules": $$☽+*n=☽$$ $$n=0,1,2,...$$ I would think this extends to ...
stargirl's user avatar
  • 325
-1 votes
1 answer
106 views

Is $\circledcirc\equiv * \omega$? Or is $* \omega \in \circledcirc$?

In Winning Ways Volume 2 (pg. 398) : $\circledcirc$ (sunny) is used "instead of $0\star\rightarrow$" as "the collection $0, \star1, \star2, \star3, \star4,...$" eg. $$\circledcirc=\...
stargirl's user avatar
  • 325
1 vote
0 answers
33 views

Strategy to minimize the number of guesses for the correct color and order of hidden balls.

I am trying to find the best strategy for a certain problem/game. Consider that there are 10 boxes. Inside each box, there is always one ball, and the color of the ball is of one of the following ...
Rafa's user avatar
  • 576
1 vote
0 answers
352 views

Are $nimonics$ (nimber mnemonics) a thing?

Note: The context of the follwing is nimbers. I found the following nimber addition mnemonic on the Wikipedia page for Fano planes. Inspired by the Fano plane mnemonic, I decided to see if I could ...
stargirl's user avatar
  • 325
3 votes
1 answer
141 views

Is ☽ a master idempotent? ☽º=☽?

I found this equation in Winning Ways Volume 4: $$☽+0=☽+*1=☽+*2=...=☽+☽=☽$$ From what I understand, this means ☽ is idempotent (I'm currently trying to learn more about loopy games & idempotents). ...
stargirl's user avatar
  • 325
3 votes
0 answers
78 views

Cooling is a homomorphism (Siegel, 5.14)

I am currently reading "Combinatorial Game Theory" by Aaron Siegel. In the section about temperature and cooling, there seem to be some issues in the proof that cooling of games is a group ...
Tzimmo's user avatar
  • 1,354
4 votes
1 answer
187 views

What is the relationship between ∅ & ☽?

In HACKENBUSH: a window to a new world of math Owen says that ☽ (loony) is equal to the set of no nimbers (eg. $☽=\{\}$). That seems to imply $\emptyset = ☽$. Is that the case? Or is $\emptyset || ☽$? ...
stargirl's user avatar
  • 325
5 votes
2 answers
337 views

Can we topple the surreal house of cards?

In Winning Ways for Your Mathematical Plays , Volume 2 , there is a section "The House of Cards" which contains figure 18 "Plumtrees in the Uplands" which shows the game trees for (...
stargirl's user avatar
  • 325

1
2 3 4 5
21