Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Combinatorial game theory

6
votes
1answer
162 views

Winning strategy in the game of triplets

The game of triplets is defined by a finite set of elements $X$, and a finite multi-set $T$ containing triplets of elements. Two players take turns picking elements from $X$ until all elements are ...
5
votes
0answers
222 views

Games on Turing machines that are AH-hard

I'm interested in proving that finding optimal play in a particular two-player game is harder than the arithmetic hierarchy. I suspect this to be true, because even carrying out a deterministic end-...
7
votes
1answer
252 views

Among an infinite variety of n x n board games, why are some interesting?

Suitably generalized to $n \times n$ boards, Checkers, Chess, and Go are each EXPTIME-Complete. (See the Wikipedia Game Complexity table.) Each of these two-person games of perfect information has a ...
1
vote
0answers
72 views

Nim-game variant - weird ending condition

the game is structured like this: two players the players alternate moves 4 heaps $h_1,h_2,h_3,h_4$ with sizes $n_1,n_2,n_3,n_4$ at each move, the player can either remove one or two elements from ...
4
votes
2answers
697 views

Can generalized twenty questions be solved by a greedy algorithm?

The game of twenty questions can be generalized in the following way. Let $\Omega$ be a finite set and $\mathcal Q$ a collection of subsets of $\Omega$, called the questions. A point $x\in\Omega$ ...
1
vote
1answer
143 views

The logic in derivation of virtual welfare

I am learning algorithmic game theory with the lecture notes posted by Tim Roughgarden. In lecture 5 it is proved that the problem of revenue (or profit) maximization in single-parameter environment ...
6
votes
3answers
820 views

What is the application of combinatorial game theory

I find Combinatorial Game Theory very interesting as my primary interest is mathematics. My question is why do Computer Scientists (who tend to have a more practical approach) study it as well? Are ...
1
vote
0answers
240 views

Finding an equivalent NP-complete instance for this game-theory problem

I apologize if this question is not a good fit for CSTheory. I'm a PhD student who has just started out and I'm working on a game-theory problem in one of my classes. Although my professor hasn't ...
5
votes
0answers
154 views

Applications of Combinatorial Games in Computational Biology

I'm looking for general references in the literature about applications of games algorithmics in computational biology. Q1. What are the notable cases of computational-biology or bioinformatics ...
11
votes
3answers
501 views

Properties expressible in 2-CNF or 2-SAT

How does one show that a certain property cannot be expressed in 2-CNF (2-SAT)? Are there any games, such as pebble games? It seems that the classical black pebble game and the black-white pebble ...
11
votes
2answers
490 views

Implementation of surreal numbers for games

There is a very nice construction by Conway of surreal numbers. They are "numbers" that contain both real numbers and ordinals, are totally ordered, and have all the properties of a field (except they ...
7
votes
1answer
206 views

Is there a gadget that reduces generalized geography to undirected graphs?

The directed Generalized Geography game is well-known to be PSPACE-complete, however, I could not find anything for the undirected version. I saw that in Hans L. Bodlaender, Complexity of path-forming ...
1
vote
0answers
217 views

What is the optimal strategy for this 2 player game?

Let some finite array of integers is given initially. There is a number k which is initially '0'. In a move, a player will select a number from the array arr[i] and change k to gcd(k,arr[i]). Also, ...
16
votes
0answers
303 views

Sylver Coinage Game

A game in which the players alternately name positive integers that are not sums of previously named integers (with repetitions being allowed). The person who names 1 (so ending the game) is the loser....
8
votes
4answers
253 views

Examples of Computer-Found Optimal Strategies in Games

I am looking for examples in games such as Go, Chess, and Backgammon, where the believed-optimal move turned out to be suboptimal as a computer found better strategies.
7
votes
0answers
218 views

Is the complexity of ARC KAYLES still open?

In the problem NODE KAYLES two opposing players take turns playing on an undirected graph. In each turn, a player selects a vertex $u$ and removes $u$ and all its neighbors from the graph. The first ...
11
votes
1answer
423 views

Winning strategy of an “edge or isolated vertex” deletion game

Is this perfect information game played on graphs know/studied? Given a graph $G= (V,E)$, two players alternate picking an edge or an isolated node. If the player picks an edge $e = (u,v)$ the two ...
27
votes
5answers
1k views

Is there a natural problem on the naturals that is NP-complete?

Any natural number can be regarded as a bit sequence, so inputting a natural number is the same as inputting a 0-1 sequence, so NP-complete problems with natural inputs obviously exist. But are there ...
16
votes
2answers
1k views

How hard is Mafia?

Mafia is a popular role-playing game at parties, a detailed description is available at wikipedia http://en.wikipedia.org/wiki/Mafia_%28game%29. Basically, it works as follows: At the beginning, ...
2
votes
1answer
171 views

What is the known complexity of this game? (similar to PushPush-1)

I've been looking at a few entries in http://library.msri.org/books/Book56/files/10demaine.pdf (on combinatorial algorithmic game theory). I didn't see the following game listed there, and I want to ...
20
votes
4answers
2k views

Permutation game redux

This is a restatement of an earlier question. Consider the following impartial perfect information game between two players, Alice and Bob. The players are given a permutation of the integers 1 ...
4
votes
1answer
451 views

Is there a method of solving the game of “war”

I was thinking of determining the game of war. I could write a fairly simple game that takes two "decks" of cards, and plays them against each other but I do not think this is optimal. Because in ...
13
votes
3answers
606 views

The Dracula game

Background This question is motivated by a board game called 'Dracula'. In this game there is one vampire and four hunters, the purpose of the hunters is to catch the vampire. The game takes place in ...