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.

learn more… | top users | synonyms

6
votes
0answers
56 views

Game to maintain distinct number of balls in glasses

There are $n$ glasses, containing $n+1,n+2,\ldots,2n$ balls, respectively. Two players $A$ and $B$ play a game, alternately taking turns with $A$ going first. In each move, the player must choose some ...
7
votes
3answers
292 views

Why are the surreals considered “recreational” mathematics?

One of my college math professors once remarked to me that it was interesting that John Conway's two "biggest" contributions to math were both recreational: the Game of Life and the Surreals. No one, ...
0
votes
0answers
43 views

A combinatorial game theory problem

In details, Let, there are four bishops on a chessboard where every two bishops are in pair ( as there are 4 bishops that means 2 pairs and in each pair they sit in vicinal squares). How many ...
86
votes
0answers
3k views
+50

The Ring Game on $K[x,y,z]$

I recently read about the Ring Game on Mathoverflow, and have been trying to determine winning strategies for each player on various rings. The game has two players and begins with a commutative ...
4
votes
1answer
24 views

Modified parcheesi game

A "modified Parcheesi" game starts with the following position: First $x$ flips a fair coin. If heads he can move two spaces or pass. If tails he can move one space or pass. If he occupies the ...
0
votes
0answers
6 views

Combinatorics- related to poker

In how many ways can a straight flush be dealt ,if two of the cards originally dealt must be discarded and replaced but not if all the 5 cards are clubs ?
3
votes
1answer
73 views

Can the wolves catch the hare?

Say you have 7 positions. 1 Hare and two Wolves in the following starting positions:    H o     o W   W  o   o The hare can take a step of size 2. The ...
4
votes
1answer
437 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 ...
12
votes
0answers
362 views

“Infinito”, a combinatorial game with infinite width game-tree

I recently designed a combinatorial game (sequential game of perfect information) with an infinite branching factor, that is it has a game-tree of infinite width. I'm wondering how is it possible to ...
0
votes
2answers
35 views

Recreational chess questions based on the knights

I basically know whether the following statements are true, but I would like to know how they are proved. A knight kept anywhere on an empty chess board can not reach its adjacent square in exactly ...
17
votes
2answers
432 views

The expected outcome of a random game of chess?

Imagine a game of chess where both players generate a list of legal moves and pick one uniformly at random. Q: What is the expected outcome for white? 1 point for black checkmated, 0.5 for a ...
6
votes
1answer
460 views

Optimal Tic Tac Toe algorithm without lookahead

Is there any algorithm for tic tac toe that does not rely on a lookahead algorithm that is perfect for any sized boards? Edit: For boards larger than $3 \times 3$, we have to find the best move for ...
1
vote
1answer
31 views

A 2 Player Pure Strategy Game

There are two players each has $n$ balls. At the same time they distribute their balls among $m$ boxes. For each box 1 point is given to the player with more balls and zero points to other one (When a ...
0
votes
2answers
38 views

Is this proposition posible? [duplicate]

In a board, you have $13$ White round pieces, $15$ Black round pieces, and $17$ Red round pieces. In each round you can choose two different color pieces and change them with two other pieces of ...
7
votes
2answers
124 views

Winning strategies in multidimensional tic-tac-toe

This question is a result of having too much free time years ago during military service. One of the many pastimes was playing tic-tac-toe in varying grid sizes and dimensions, and it lead me to a ...
4
votes
0answers
37 views

Prime number building game

Players $A$ and $B$ choose digits $(0, \dots , 9)$ turn by turn and build number by concatenating the digit they chose to the end of the number. Player $A$ starts by picking the first (one-digit) ...
1
vote
0answers
36 views

Counting all possible legal board states in Quoridor

Ignoring pawns there are 1,375,968,129,062,134,174,771 possible ways to place 0 to 20 walls on the Quoridor board, as answered here. Ignoring walls there are 81 * 81 = 6410 ways to place the two ...
0
votes
2answers
233 views

traveling salesman with pairs of cities, without return and with given start and end cities

I am looking for the name of the following two problems, and an approach to solve them. Problem#1: given N nodes, find the shortest path starting at a given start node and ending at a given end node, ...
0
votes
2answers
25 views

prove that if $n=k$ then white has a winning strategy in $S_{n,k}$.

Black and white play sequentially the game $S_{n,k}$ with $k,n\in \mathbb N \space 0\leq k\leq n$ the game board consists of all subsets $A\subseteq\{1,2,...,n\}$ such that $1\leq |A|\leq k$. every ...
1
vote
2answers
64 views

Counting problem about pirates and gold coins [duplicate]

Five pirates find a cache of 500 gold coins. They decide that the shortest pirate will serve as the bursar and determine a distribution of the coins however he sees fit, and then they all will vote. ...
2
votes
1answer
28 views

Game removing tokens on number line

A two-player game begins with $k<2^n$ tokens placed at point $0$ on the number line spanning $[0,n]$. Each round, player $A$ chooses two disjoint, non-empty sets of tokens $X,Y$. Player $B$ takes ...
1
vote
2answers
32 views

Combinatorics For $4$ Pool Balls

There lie $4$ pool balls on a pool table: two striped and two plain. Two of the pool balls are selected at the same time, at random. Given that one of the selected balls is striped, what's the ...
3
votes
1answer
26 views

Game picking cards so that sum is divisible by $25$

Adele and Bryce play a game. There are $50$ cards, numbered $1,2,\ldots,50$. They take turns alternately picking a card, with Adele going first. If at the end, the sum of the numbers on Adele's cards ...
3
votes
3answers
67 views

Card Game Probability 13 Card Hand

Me and my friends play a four person poker style card game. Each person is dealt 13 cards, and it is a standard trump card game. Now, as the standard, a five card flush beats a five card straight, but ...
2
votes
2answers
82 views

Gomoku on an infinite big board

I always used to play Gomoku in school on paper, and if we reached the edge of the field, we just put another one at that side. And now I just saw that black can always win on 1 15x15 board. But what ...
7
votes
2answers
174 views

Converting a Gomoku winning strategy from a small board to a winning strategy on a larger board

Gomoku is the game where Black and White take turns placing stones of their own color, and the winner is the player who first gets five of their own stones in a row. Black moves first. In Gomoku on ...
0
votes
1answer
22 views

Proof sprague-grundy value is 0 if and only if it is losing position

So, i take this game theory module this summer, and i encountered this exercise problem, i tried to do this by induction by have terminal position (grundy-value = 0) as base case, but can't figure out ...
8
votes
1answer
82 views

Game replacing two numbers by mean

Alicia and Bart plays a game. Alicia first writes $100$ real numbers on the board. After that they move alternately; Bart goes first. In every move, the player chooses two numbers, erases them, and ...
0
votes
0answers
26 views

Game placing numbers in increasing order

Let $k\leq m\leq 100$ be positive integers. Aaron and Britney play a game on a $1\times m$ board, using $100$ paper pieces numbered from $1$ to $100$. The game has $k$ turns. In each turn, Aaron ...
1
vote
1answer
42 views

Game of polygons

Initially, there is a polygon with N vertices drawn in the plane. The polygon is strictly convex, i.e., each internal angle is strictly smaller than 180 degrees. The vertices of the polygon are ...
1
vote
1answer
165 views

What to do with a random variable when we know its mean and variance but does not know which distribution it is?

Let Y be a random variable with mean μ and variance σ^2 where the support is (0, ∞). Suppose you are offered to play a game where you choose a number z between (0, ∞). If a realization of the random ...
2
votes
1answer
75 views

Commutative Algebra and Game Theory

Is there any relationship between commutative algebra and game theory? For example, have any tools in commutative algebra been applied to game theory? A text or reference would be ideal, but I'd be ...
3
votes
1answer
55 views

Characteristic 3 analogue of nimbers?

Finite nimbers are a way of turning the natural numbers (finite ordinals) into a characteristic 2 field. Addition in this field is found by writing the numbers in binary and adding without carry, ...
1
vote
5answers
101 views

Game Theory - First move vs second move advantage?

This question came up in a lunchtime discussion with coworkers. None of us are professional mathematicians or teachers of math, and we weren't sure how to get the answer. I apologize in advance if my ...
6
votes
2answers
101 views

Eating chocolate game on grid

Given is a chocolate of size $m\times n$. Anne and Birgitte plays a game, with Anne starting. In each turn, the player has to divide the chocolate into two rectangular parts along the lines, and eat ...
2
votes
0answers
69 views

What is the largest value one can get in game 2048 without new tiles appear

This is a simplified version of the famous game 2048. Given a 4x4 grids with some values chosen from {0, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048}. A value of 0 indicates that the position in ...
1
vote
1answer
78 views

Counting all possible board positions in Quoridor

I'm trying to figure out how many possible board positions there are for the game Quoridor. I think sorting out the legal positions from the illegal positions will be difficult, so to start I'm trying ...
0
votes
1answer
60 views

Pigeon-hole principle applied to the game of tic tac toe

In a game of tic tac toe, noughts and crosses are drawn inside an unoccupied cell of a 3 x 3 matrix by two players I, II in alternating moves. Player I draws crosses and Player II draws noughts. The ...
0
votes
1answer
72 views

Nim Sum Game Variant

Suppose there are black and white balls in a box. The initial number of white balls is m and the initial number of black balls is n. This is a two player game. Each player can do the following taking ...
0
votes
1answer
23 views

How to write induction proof of Sprague-Grundy function for subtration game?

So lets say that S={1,2,3} I find the sequence of Sprague-Grundy function. How do I justify my answer using induction?
5
votes
2answers
285 views

Does a finite game that cannot be drawn imply a winning strategy exists?

The author of this page, about a simple game (Chomp) http://plus.maths.org/content/mathematical-mysteries-chomp makes the following statement: "One of the players is sure to have a winning strategy. ...
0
votes
0answers
122 views

N piles games with consecutive piles move

There are 6 piles of stones in a round configuration. In a single move, a player selects 3 consecutive piles, and removes some stones from 1 or more of these piles. (at least 1 stone must be removed ...
30
votes
9answers
65k views

Maximum board position in 2048 game

A game called 2048 is making rounds on social media. I am trying to determine the maximum score attainable for this game. Let's assume WLOG that only 2s are returned (if 4s are possible the max score ...
0
votes
0answers
27 views

Number of ways to shuffle a cardset with fixed top 4 while ignoring the suit

I am interested in the number of possible orders in a standard 52 card deck. There are $52!$ possible orders, if I care for suit and type. If I don't care for the suit / color of the card there are ...
1
vote
1answer
33 views

CGT: value of sum game is sum of values of games

I am involved in a little study about combinatorial game theory. The study makes heavy use of the fact that, at least in a simple combinatorial game called domineering, the value of the sum game is ...
0
votes
1answer
49 views

Relationship between regular Nim and Lasker's Nim

So I'm trying to do qn $6$ (on pg I-13) about staircase Nim in Game Theory by Ferguson Game Theory, Ferguson and it's asking to prove that $(x_1, x_2, \ldots, x_k) \in P $ only if $(x_1, x_3, x_5, ...
6
votes
4answers
296 views

Integral of a function defined in the set of Surreal Numbers

Given ${\{C}\}\ $ the set of all the $Surreal\ numbers$, is it possible to define the integral: $$\int_a^b{dxf(x)}$$where $$a\in{\{C}\},b\in{\{C}\},x\in{\{C}\}$$ Thanks
1
vote
2answers
91 views

Probability that 20 sided die beats 12 sided die with reroll

Alice rolls a 12 sided die (the faces labeled 1 through 12) and Bob rolls a 20 sided die (the faces labeled 1 through 20). After seeing their roll (but not the other person's roll), each person can ...
4
votes
1answer
120 views

Saddle Points on Matrices

Let $n$, $m$ be positive integers. Suppose that $A$ is a $2$ x $n$ or an $m$ x $2$ matrix and that it has a saddle point. Show that among the saddle points of $A$ there exists at least one which ...
14
votes
1answer
486 views

How many possible board states in 2048?

I recently found out about the famous 2048 game. For those of you who don't know how it works, it consists on a 4x4 board on where tiles which are powers of 2 are placed. On every turn, you "swipe" ...