# Tag Info

16

It's taken years but this post inspired us to write a paper which has come out today. The answer is that n Queens Completion is NP-Complete. However for full disclosure should mention we solve a slight variant of the problem. In our case the set of queens doesn't have to be a prefix of the full set. So technically we haven't resolved the exact problem ...

12

The best known example is probably checkers (also known as draughts), which has been solved recently in 2007 (the game is a draw). Other examples are listed in the Wikipedia page on solved games; notable among them are connect four and nine men's morris. Additionally, several chess endgames have been solved. This perhaps doesn't seem like an answer to your ...

10

Regarding Beggar-My-Neighbour Paulhus (1, p.164) wrote in 1999: If $C$ is a full deck of cards, does ${D_{2}}^{'}(C)$ have a cycle? We leave this question unanswered except to say that we have been unable to find one in 3.2 billion randomly chosen deals. But Conway et al. (2, p.892) wrote in 2006: Strip-Jack-Naked, or Beggar-My-Neighbour **1 ...

9

See Tic-Tac-Toe by Randall Munroe.

8

I don't have an answer to your question of whether the theory of Conway games has been used in building game-playing programs, but still you might be interested in the Combinatorial Game Suite, "an open-source program to aid research in combinatorial game theory" (which I first learned about here). It includes an implementation of various standard ...

8

See Wolfe and Berlekamp -- Mathematical Go. Using Conway's theory of games, they show how to analyze certain kinds of Go endgames. Their solutions turn out to be measurably better than the solutions given by top Go players. (Not quite an answer to your problem, as those latter solutions were probably never claimed to be optimal.)

7

Perhaps a fairly natural game is the following: Player 1 is placed in the middle of a maze and must reach the exit in order to win. Player 2 is in the same maze and must collect a set of "components" to build a radio controller that lets him close the exit (and win). Deciding the next move from a winning position is easy for Player 1: just follow the ...

6

(This points to some related results. I initially thought that the related results are very related, but I can't fill the gaps quickly, so maybe they're not so related after all. Perhaps still helpful.) Exercise 118 in the (draft of) section 7.2.2.2 of The Art of Computer Programming looks at a very similar problem. In the solution, Knuth credits an article ...

6

Since the figure is otherwise mostly symmetric, I believe the 3 I mentioned two sentences ago should be replaced with a 1. Indeed, the 3 is obviously a typo. However, even if that is done, I do not see any way to determine the status of the zs even after... Am I missing something here? After $r$ is revealed: If it was a mine, you can reveal the ...

6

I've spent a lot of time on problems related to the computational complexity of (puzzle) games and I think there are many orthogonal aspects that can make a two-players or a one-player (puzzle) game attractive and fun: simple rules; simple "physical elements" needed to play it (e.g. a bounch of stones like in Mancala) ... clearly nowadays this condition is ...

6

Just an extended comment; in Allan Scott, Ulrike Stege, Iris van Rooij, Minesweeper May Not Be NP-Complete but Is Hard Nonetheless the authors face the problem I mentioned in my comment above. From the abstract: In volume 22 of The Mathematical Intelligencer, Richard Kaye published an article entitled "Minesweeper is NP-Complete." We point out an ...

5

Lower bound for question 2: Theorem: After $TM-1$ steps, with the strategy outlined below, you will have at least $(T-1)\log M$ positive counters. Notation: Define time step $1$ to be the beginning of the $TM-1$ steps, and $TM-1$ to be the end. Decrements happen on time step $Tk$, $1 \le k < M$. Define the upper limit to be $M- \lfloor N/T \rfloor$, ...

5

Here is an upper bound for question 2. Theorem: After $TM$ steps, you can have at most $T \log M$ positive counters. Notation: we assign each step a number, ending with the $0$th step, and starting with the $(-TM+1)$th step. Observation: in the optimal strategy, if you increment a counter, you do not let it return to $0$. Proof: Let us assign a value ...

4

Copy/paste from another (slightly different) cstheory question on Rubik's cube: "What is the shortest sequence that scans all cube's configurations", or "does the configuration graph of the cube have a Hamiltonian path?" is a special case of a more general unsolved problem: For an arbitrary permutation group with a given generating set, is its Cayley ...

4

Yesterday I googled around to check the status of this problem and I found this new (2012) result: Dan Brumleve, Joel David Hamkins and Philipp Schlicht, The mate-in-n problem of infinite chess is decidable (2012) So the mate-in-n problem of infinite chess cannot be Turing complete. The decidability of infinite chess with no restrictions on the number ...

4

By your constraints, we also have the stronger opposite relation: if POSITION-COMPLEXITY is in a class $C$, then so is MOVE-COMPLEXITY, since it suffices to test the finite number of available moves. (I assumed by "finite" you meant "constant", if it is arbitrary then the complexity might change). Then it suffices to look at some natural games where ...

3

on some search there do not seem to be much published general implementations of surreal numbers. heres an implementation of surreal numbers in coq. Surreal numbers in coq / Mamane, TYPES'04 Proceedings of the 2004 international conference on Types for Proofs and Programs Surreal Numbers form a totally ordered (commutative) Field, containing copies of ...

3

As for the question of what characteristics make a problem amenable to bandit-based approaches, this paper describes the behaviour of UCT in various search spaces: http://www.cs.cornell.edu/~raghu/Raghuram_Ramanujan_files/mcts11.pdf Regards, Cameron

3

A1) The problem remains NP-complete even for fixed $|\Sigma|=3$ A reduction from planar 1-3-SAT is the following; suppose $\Sigma = \{0,1,2\}$ use a sequence of $M_{ij} = \{0,1\}$ pairs of horizontal/vertical cells as "wire" gadgets to "carry" the truth values ($0=true$, $1,2 = false$) of the variables (the horizontal and vertical rules of the wires forbid ...

2

In the most authoritative reference on PPAD-complete problems, there is no PPAD-complete puzzle mentioned.

2

In fact, in the so-called Picker-Chooser or Chooser-Picker games it is easy to construct examples for which one player's best strategy is a simple pairing strategy, while the other has to solve a 3-SAT on any CNF specified before, that is an NP-complete problem. Say, a Picker-Chooser games is an asymmetric game on an hypergraph H=(V, E): Picker picks two ...

2

This recent survey paper lists the application of MCTS to a number of search and optimisation problems other than games, in Section 7.8: http://pubs.doc.ic.ac.uk/survey-mcts-methods/survey-mcts-methods.pdf http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=6145622 As for domains that are totally resistant to bandit-based methods, I'm not aware of ...

2

You asked whether there exists a finite set of moves which if applied repeatedly from any starting position, yield a solved Rubik's cube. Then you asked a harder question. The former question has a simple solution. Enumerate the group of permutations of the Rubik cube: $G = \{g_1,\ldots,g_{|G|}\}$. Every $g_i$ can be realized as some sequence of moves which ...

1

Here is an implementation of Surreal Numbers in a relatively new language, Julia. https://github.com/mroughan/SurrealNumbers.jl Described at https://www.sciencedirect.com/science/article/pii/S2352711018302152

1

It is not properly a "game strategy", however in 2010 Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge found that all Rubik's cube positions can be solved with a maximum of 20 face turns using a computer-assisted proof [1] ... a nice result. The annotated source code is available at http://cube20.org/src/. The average number of moves ...

1

Chess endgame techniques have been greatly enhanced by the advent of endgame tablebases. Endgame tablebases are lookup tables that solve chess when there are no more than (currently) seven pieces on the board. Here is an online tablebase I've used in the past that works for up to six pieces. Algorithmically, these tablebases are not very interesting; they ...

1

The game you've described looks a lot like the game of k Cops and 1 Robber, as described in this article by Clarke and Macgillivray : http://www.sciencedirect.com/science/article/pii/S0012365X12000064. Basically, it is played by placing k cops and a robber on the vertices of a graph and asking the cops to catch the robber by moving along the edges. The ...

Only top voted, non community-wiki answers of a minimum length are eligible