Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [board-games]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3 votes
0 answers
81 views

Complexity of chess with 50-move rule

It is known that evaluating who wins in $n \times n$ chess positions is EXP-complete (and thus unconditionally not in P), and this effect is due to the game having rich possibilities for exponentially ...
Alexey Slizkov's user avatar
10 votes
0 answers
192 views

Is 4-in-a-row PSPACE-complete?

This paper by Laurens Kuiper shows that axis-parallel k-in-a-row is PSPACE-complete in complexity for k ≥ 5, but leaves the question open for k = 4. Has there been any research progress on this ...
user76284's user avatar
  • 662
5 votes
0 answers
202 views

Generating Where's Waldo?

I want a challenging Where's Waldo type game, where the goal is to find some pattern. But I would want something where you can make your own puzzles, for example by randomly pulling your hand over a ...
domotorp's user avatar
  • 14k
2 votes
0 answers
58 views

Efficient game traversal of a DAG of 3-colorings

Let $X$ be a set of size $n$. Consider a game played on board $X$ by two players black and white. Starting with the empty board, each player chooses an empty spot to place a stone. Black moves ...
Geoffrey Irving's user avatar
5 votes
0 answers
767 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-...
Stella Biderman's user avatar
9 votes
1 answer
363 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 ...
Joseph O'Rourke's user avatar
3 votes
1 answer
192 views

Matrix Coloring under Vertical and Horizontal Constraints

I'm searching for the correct name of the following NP-complete problem. I would also appreciate answers pointing to problems with similar-looking variations. The input consists of A set of ...
Mateus de Oliveira Oliveira's user avatar
4 votes
1 answer
147 views

doubt about two minesweeper gadgets

(Unlike most posts on stackexchange with that word, I really do doubt that they work as described.) In Figure 15 of this paper, the cells two to the right of the leftmost circle and two to the left ...
user avatar
6 votes
1 answer
159 views

Are there PPAD-complete puzzles?

Most puzzles that you can buy are in P, NP-complete (like Sudoku) or PSPACE-complete (like Sokoban), at least if you scale them up. Are there any natural puzzles that are PPAD-complete? What about ...
domotorp's user avatar
  • 14k
27 votes
2 answers
2k views

Complexity of n-queens-completion?

The classical $n$-queens problems asks, given a positive integer $n$, whether there is an array $Q[1..n]$ of integers satisfying the following conditions: $1\le Q[i] \le n$ for all $i$ $Q[i] \ne Q[j]$...
Jeffε's user avatar
  • 23.2k
11 votes
3 answers
364 views

Is there a simple game with asymmetric complexity?

Consider full information two-player combinatorial games that end after a polynomial number of moves, and in an alternating way, the players picks from a finite number of allowed moves. The usual ...
domotorp's user avatar
  • 14k
14 votes
0 answers
245 views

Is it possible to make trapdoor board games?

Motivated partly by this MO question, I am wondering if it's possible to design a board game where there is a simple winning strategy but it's hard to find. For example, the game of picking a random ...
domotorp's user avatar
  • 14k
11 votes
3 answers
924 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 ...
Denis's user avatar
  • 8,893
8 votes
2 answers
244 views

What is the value of this "game" (counters rebalancing)?

This question was posted in CS.SE two weeks ago, but it didn't get a satisfying answer. Suppose you have the following game: There are infinitely many counters $\{c_1,c_2,\ldots\}$, all initialized ...
R B's user avatar
  • 9,458
17 votes
2 answers
1k views

Does this game terminate?

Consider the following card game (known in Italy as "Cavacamicia," which may be translated as "stripshirt"): Two players randomly split in two decks a standard deck of cards. Each player gets one ...
Manu's user avatar
  • 7,669
7 votes
1 answer
1k views

Is it NP-hard to _play_ minesweeper perfectly?

This paper shows that it is NP-hard "to determine if there is some pattern of mines in the blank squares that give rise to the numbers seen." If there is a way to "lead a perfect player into" such ...
user avatar
8 votes
4 answers
284 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.
fkenter's user avatar
  • 181
-5 votes
1 answer
2k views

Developing A Perfect Tic-Tac-Toe Player - AI [closed]

I'm interested in AI as an area to study on in MSc. I don't have much prior knowledge. So, I decided to develop an AI that plays Tic-Tac-Toe perfectly, as an introduction. I've made some progress that ...
oak's user avatar
  • 101
2 votes
2 answers
511 views

Permutations of maximum period: applications to Rubik's cube

Dear Mods: this may be a non-research question, but I am asking it because from my knowledge, the question appears nontrivial. This video claims that a Rubik's cube can be "solved" from any starting ...
Ankur's user avatar
  • 779
17 votes
2 answers
4k views

Can chess simulate a Universal Turing Machine?

I am looking to get a definite answer to title question. Is there a set of rules that translates any program into a configuration of finite pieces on an infinite board, such that if black and white ...
TROLLHUNTER's user avatar
0 votes
0 answers
504 views

How to detect dead ends on a board / in a graph?

Given a (2D) board of quadratic cells (movement allowed between 4-neighbours), many of which are blocked, and given a certain starting position, how can I efficiently detect dead ends, i.e. regions of ...
Michael Borgwardt's user avatar
12 votes
4 answers
16k views

What is the computational complexity of "solving" chess?

The basic idea of backwards induction is to start with all the possible final positions of a game in which player X wins. So for chess, look at all the ways White can checkmate Black. Now work ...
Seamus's user avatar
  • 223
13 votes
3 answers
666 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 ...
Tomek Tarczynski's user avatar
10 votes
3 answers
953 views

Applications of MCTS/UCT

MCTS/UCT is a game tree search method that uses a bandit algorithm to select promising nodes to explore. Games are played to their completion randomly and nodes leading to more wins are explored more ...
mhadley's user avatar
  • 295
2 votes
3 answers
1k views

What games best represent well-known computer science problems?

I heard that Clue is a board game that is related to the NP-complete traveling salesman problem. What are other games that relate to important computational problems?
Albert T. Wong's user avatar
17 votes
1 answer
562 views

Complexity of hex with random turn order.

I've been thinking of a variant of hex, where instead of the two players making moves alternately, each turn a player picked at random makes a move. How hard is it to determine the chances for each ...
Itai Bar-Natan's user avatar
31 votes
3 answers
2k views

Is it NP-hard to play international draughts correctly?

Is the following problem NP-hard? Given a board configuration for $n\times n$ international draughts, find a single legal move. The corresponding problem for $n\times n$ American checkers (aka ...
Jeffε's user avatar
  • 23.2k