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
1
vote
0answers
37 views

Game of two players on table $20 \times 20$

Game of two players on table 20X20: Player one is starting the game. Each turn he can put red stone on any point $(i,j)$ such that there isn't another stone on $(i,j)$ and there isn't another red ...
2
votes
1answer
19 views

To find the subgame equilibrium

So I am trying to solve the following question: X and Y are dividing a pie according to the following procedure. First, X proposes a division. If Y agrees then the division is implemented. Otherwise, ...
2
votes
2answers
70 views

How to find winning Strategy for 4 celled animals of Harary's generalized tic tac toe

A polyomino is a structure made of unit squares joined along their sides. A single square is called a monomino. Two make a domino. Three join in two different ways to make two trominoes. Let's call ...
10
votes
1answer
262 views

Optimal strategy for river crossing game

Background: the bridge-and-torch game In this bridge-and-torch game, $n$ people are trying to cross a river on a boat that carries at most two people. Each person takes a different amount of time to ...
4
votes
2answers
126 views

Amidakuji Puzzle and math behind it

Ghost Leg (Chinese: 畫鬼腳), known in Japan as Amidakuji (阿弥陀籤, "Amida lottery", so named because the paper was folded into a fan shape resembling Amida's halo1) or in Korea as Sadaritagi (...
2
votes
1answer
68 views

Standard Tic Tac Toe is -- Impartial or Partisan?

I am currently studying basic game theory (combinatorial) and was introduced to impartial games. The "definition" of impartial games I saw was: "An impartial game is a two-player game ...
0
votes
0answers
32 views

Misere Nim rigurous proof

I know that this is the optimal strategy for misere nim game: When played as a misère game, Nim strategy is different only when the normal play move would leave only heaps of size one. In that case, ...
0
votes
0answers
39 views

Generate all stars and bars Combinations with different capacities per bar

I have m "slots" with indivual capacity c_m. Now I want to distribute a certain amount of integer k to those m slots without exceeding their capacity c_m. Such that every slot has a certain &...
0
votes
0answers
15 views

Handling of infinite utility children when backward inducting into a Nature node of a Expectiminimax game tree

Background I am coding a game playing engine for a (3+, but for now assume) 2 player card game, which has a shuffled (AKA random) & face down (AKA hidden) deck. This game has perfect* and complete ...
4
votes
1answer
90 views

Let $a_n$ be the position of the nth $1$in the string $t_n$. Prove that: $a_n = [\frac{1+\sqrt5}{2} . n]$

Consider the transformation $f$ acting on a binary string: turn every $(0, 1)$ in it into$ (1, 01).$ The notation$ s_n$ is the string produced after acting$ f $on $1$ all n times. Example :$ 1\...
0
votes
1answer
70 views

Numbers 5,7,9 are written on the whiteboard. In one move, we choose two numbers $a,b$ and and add a new number $5a-4b$ to the whiteboard... [closed]

Numbers 5,7,9 are written on the whiteboard. In one move, we choose two numbers $a,b$ and and add a new number $5a-4b$ to the whiteboard. Is it possible to get the number $2021$ on the whiteboard ...
1
vote
0answers
70 views

Do you know the website of the journal Ars Combinatoria?

Do you know the website of the journal Ars Combinatoria? Is this journal still publishing articles? I have a paper accepted in 2018 by this journal, but now I cannot get any news and message from this ...
1
vote
0answers
29 views

"Proportional coalition function" coalitional game with fair splitting

I have a game that has a special form of payoff function of a coalitional game. There is a set $N$ (of $n$ players) and a coalition function $v$ that maps subsets of players to the real numbers: $ v\...
1
vote
1answer
32 views

Weighted Nim with Stacks and each player picks from opposite sides

There n stacks of coins. Each stack contains $k_i$ coins and the coins in a particular stack have distinct values. In each turn, you get to pick one coin from the top of any stack, and your opponent ...
0
votes
1answer
48 views

Number of ways Nim-sum is X

Find the number of ways, four distinct piles of stones can be made with each pile containing at least 1 and not more than 9 stones, such that the nim-sum of the four piles is zero. I could only think ...
0
votes
1answer
53 views

Theoretical Question Basketball

This is kind of a crazy question. I was looking up the expected value of a binomial distribution here the other day. I was looking at it in relation to basketball where it is clear if you took $n$ ...
0
votes
0answers
29 views

Find dominating strategies in a game

Problem Colonel Blotto can send each of his five companies to one of ten locations whose importance is valued at $1, 2, 3, . . . , 10$, respectively. No more than one company can be sent to any one ...
2
votes
2answers
44 views

Intuition to move-optimality in Sokoban

The puzzle game of Sokoban has been fascinating to me since I was a child. It is played on a rectangular grid. Each square may be empty ( ) or contain a wall (...
5
votes
1answer
156 views

Is this conjecture about a stick game correct?

My math teacher described the following game and for a few days I have been thinking about it. Let $A$ and $B$ be two perfect players. Let $n$ be a positive integer and let's consider a stick of ...
0
votes
0answers
38 views

Optimal play in Strings & Coins

Consider the following Position of Strings & Coins: (taken from Albert, Michael H., Richard J. Nowakowski, and David Wolfe. Lessons in play: an introduction to combinatorial game theory. CRC ...
0
votes
1answer
43 views

Why aren't all games impartial games?

We can take any partisan game, like Chess, and make it into an impartial game like so: Take the game tree of moves for both players and make each game state a spot on the board. Now we start the game ...
2
votes
1answer
159 views

Does an unsolvable game exist? (And can you formulate an example?)

Let me first of all be more clear by explaining what a unsolvable game is. An unsolvable game is a game which can never be solved, not even hypothetically, because no strategy can force a win if the ...
5
votes
1answer
67 views

Why do we say Treblecross' octal game notation is .007?

I've recently been reading a lot about game theory and octal games, and in the few sources on it I can find, people seem to agree that Treblecross' value is .007. For reference, the game of ...
2
votes
0answers
36 views

Precise statement of Number Avoidance Theorem in game theory

Background: In the book Winning Ways for Your Mathematical Plays on combinatorial game theory, the Number Avoidance Theorem is stated: DON'T MOVE IN A NUMBER UNLESS THERE'S NOTHING ELSE TO DO! (sic.)...
3
votes
1answer
115 views

Proof that there is a winning strategy for player 1 in Chomp.

This question is regarding the game "Chomp" which can be found here: https://en.wikipedia.org/wiki/Chomp My quesiton is regarding the proof that there is a winning strategy, the proof can be ...
2
votes
2answers
135 views

Two player divisor game

I saw an interesting question in Dynamic Programming (DP) section on Leetcode webpage. Given an integer $n \ge 1$, A and B play the following game. A picks a number $0<k<n$, such that $k | n$ ($...
4
votes
3answers
281 views

If two curves only touch, do they technically "intersect"?

I was playing sprouts with a few friends the other day, and one of them tried to be clever by "squeezing" their line next to another player's line to effectively prevent any passthrough play:...
5
votes
1answer
199 views

n-player survivor game

Came up with a following game recently and after trying to understand the general strategy for hours I have to admit I failed at finding one, so I thought asking here would be a good idea. As a good ...
0
votes
0answers
31 views

Probability problem on a 9x9 chessboard [duplicate]

Each square of a 9x9 checkerboard (see below) is initially slept on by one of 81 students. At noon, each student will wake up and randomly sleepwalk to a valid adjacent square horizontally or ...
0
votes
0answers
28 views

Which person wins the game? Find the person who removes the last balls from the bag.

I have a game. Suppose the ball is in the bag and each person can take 1, 2, 3, or 4 balls out of the bag at each stage. Assuming that each participant (participants A and B) knows how many balls are ...
2
votes
1answer
71 views

Red-Blue Hackenbush is a cold game

Does the following proof make sense to prove that finite Red(Richard)-Blue(Louise) Hackenbush is a cold game? If all edges touching the ground are exclusively red or blue, clearly one of the players ...
0
votes
0answers
37 views

How can I calculate the amount of possible routes someone could take on a grid with a specific size?

I created a simple game, and I want to calculate approximately how many possible moves there are on a board of N x N squares. The rules are as follows: The player starts on the top left corner Every ...
2
votes
1answer
70 views

A square removing game - winning strategy?

Let $N$ be an odd integer. Let us consider a grid from which we cut out a connected shape consisting of $N$ squares. This shape will be our board. By connected, I mean that given any two squares in ...
0
votes
0answers
30 views

Three drawers with socks combination of rb, gb, rg. Minimum expected numbers to find out each drawers combination. which drawers have which.

So it is about devising an optimal strategy to find out which is which with minimum expected number of draws, and calculate the minimum number of draws. This is how I attempted to solve the problem. ...
0
votes
1answer
198 views

Is there a winning strategy for this number game?

Given a composite number $N_0$. Player one subtract from $N_0$ one of its prime factors and get the number $N_1$. The player two do the same with the number $N_1$ and so on. The first player to reach ...
1
vote
1answer
42 views

Periodicity of Nim sequence of Subtraction Games

I have seen this proof for periodicity of Nim sequences of finite Subtraction games: Consider the finite subtraction game subtraction$(a_1, a_2, \dots , a_k)$ and its nim-sequence. From any position ...
0
votes
1answer
42 views

Prove game Hex must have a winner

About 7 years ago I was asked this question. I remembered it right now, and I can't solve it. Prove that no matter how you play, the game Hex will have a winner at the end.
1
vote
1answer
111 views

Are there elements in $𝐍𝐨^𝕯$ that aren't games?

The text bellow is just an explanation of the title, if you understood the title you don't have to read the text. Games are defined by the rule "If L and R are two sets of games, then { L | R } ...
1
vote
1answer
40 views

Probability of winning the 2-player combat from Warlords series

There was an old PC game series Warlords. My question is to determine the chances of winning a combat there. Two players wage a combat with following rules: They have an unbalanced coin with a known ...
2
votes
1answer
35 views

Winning strategy for a combinatorial game

There are $10^7$ stones on the desk. Two people take turns at taking out stones and they can take out any number of stones as long as the number is the format of $P^n$. Here $P$ is any prime number, ...
1
vote
2answers
62 views

Counting the triangles formed by the sides and diagonals of a regular hexagon

In this regular convex Hexagon, how many triangles are possible if we consider the intersection points of the diagonals? I've tried to count the triangles. First, I counted all the vertices of the ...
3
votes
1answer
68 views

Pile of $753$ Coins

I was given this puzzle earlier today by a colleague who in turn heard it from a friend who got the problem from a math professor at UCSB. Suppose Alice has $753$ coins of some denomination. She ...
3
votes
0answers
34 views

Which voting algorithm to use to assign N number of people to G groups based on their ranked choice preference

I've been looking through social choice theory textbooks and videos trying to find the right sort of algorithm for this, but struggling. Basically I have N (say 21) people that I need to assign into G ...
0
votes
2answers
85 views

Why the number of Nim winning positions is not equal to the number of losing positions?

maybe I miss something and I like to know where is my mistake: Lets suppose we play Nim with $n$ piles, and lets say we we limit each pile to be between $0$ to $k$. Now, according to this question: ...
-3
votes
1answer
98 views

General analysis for heap game, arbitrary number of piles

Here is a problem from my textbook: Here is the general analysis for Heaps with an arbitrary number of piles. Let $A$ be the number of $2$-chip piles, and let $B$ be the number of piles with either ...
1
vote
2answers
111 views

Two player football game -- probability.

A friend gave me the following problem to solve. I have been stuck at it for days. With little or no progress. Well, I did get an estimated answer by running a simulation but not the formal solution. ...
4
votes
2answers
384 views

Determining probability of 'thirteen orphans' hand in riichi mahjong

For anyone not familiar with how riichi mahjong is played, it uses 34 unique tiles with 4 duplicates of each tile, adding up to 136 in total. There are numbers 1 to 9 in 3 different suits, as well as ...
8
votes
2answers
206 views

Winning strategy for a game

All positive integers from $1$ to $n$ are written in a row in increasing order. Two players, $A$ and $B$ are playing a game where they each take turns erasing two consecutive numbers from the row and ...
0
votes
1answer
125 views

Winning strategy at "Turning Turtles"

There is a coins games that called "Turning Turtles". I'd like like to know if there is a winning strategy for this game. From the written above I understand how to calculate the Nim-Value ...
2
votes
0answers
87 views

How exactly does the strategy-stealing argument work?

I'm a little confused about the strategy-stealing argument and how exactly it's supposed to work. This question's answer tells us that strategy-stealing works for tic-tac-toe because 'having extra ...

1
2 3 4 5
18