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

The tag has no usage guidance.

5
votes
0answers
207 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
249 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 ...
3
votes
1answer
166 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 ...
4
votes
1answer
135 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 ...
6
votes
1answer
120 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 ...
25
votes
2answers
1k 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]$...
11
votes
3answers
301 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 ...
13
votes
0answers
222 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 ...
11
votes
2answers
483 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 ...
8
votes
2answers
225 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 ...
12
votes
1answer
385 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 ...
6
votes
1answer
578 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 ...
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.
-5
votes
1answer
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 ...
2
votes
2answers
498 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 ...
15
votes
2answers
2k 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 ...
0
votes
0answers
382 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 ...
8
votes
5answers
9k 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 ...
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 ...
10
votes
3answers
642 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 ...
3
votes
3answers
975 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?
16
votes
1answer
475 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 ...
25
votes
3answers
1k 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 ...