12 votes
Accepted

Paint a Cube by rolling it (Puzzle Algorithm)

As Dmitry noticed there is very little possible states of the game, so it's relevant to search for solution using BFS traversal. But let's start from some numbers. Staring positions In terms of ...
Michał Stachurski's user avatar
7 votes
Accepted

What complexity class would this version of generalized chess fall?

because the proof would require an exponential amount of steps to show that each branch of the tree eventually leads to a win. Therefore it's not in NP. It is possible that generalized chess is in $...
Tom van der Zanden's user avatar
6 votes

Is this classic puzzle book game NP-complete?

Sorry for answering an old post. I´ve been thinking about it and i think that the problem with a fixed alphabet is NP-complete as well. I´m going to reduce positive 1-in-3 SAT to this word problem ...
rotia's user avatar
  • 749
6 votes
Accepted

Knight on a chessboard

You could use the breadth first search (BFS) algorithm. The knight may move at most to eight cell (from a single position) which means that if each cell is treated as a single node then degree of each ...
fade2black's user avatar
  • 9,817
6 votes

Paint a Cube by rolling it (Puzzle Algorithm)

Of course, but let me show the process on simpler example and then just use same method for calculating final count. Small example We are given $2 \times 2$ square grid and two colors (black and white)...
Michał Stachurski's user avatar
5 votes

Chess Knight minimum moves to destination on an infinite board

The easiest way to solve this problem is to greedily move in the best direction until you get within 100 squares or so, and then A* from there. Figuring out exactly how close you can get before you ...
Matt Timmermans's user avatar
5 votes

Chess Knight minimum moves to destination on an infinite board

There is a closed form solution for finding the minimum number of moves the chess knight needs to move a specified displacement on the infinite chess board. Let $g$ be the requisite displacement ...
Robert Wordar's user avatar
5 votes
Accepted

Find Minimum Transformation Between Multisets of Lists of Cards

I think the variant with sets can be solved using bipartite matching. Build a complete bipartite graph, with one left vertex per set in s0 and one right vertex per set in s1. Also, if there are fewer ...
D.W.'s user avatar
  • 158k
4 votes

Does White never lose in Chess if Chess is solved?

Let's take alternative chess. The rules are identical to chess, except that White can pass in it's very first move (but Black can't, even if White passed). Now it's obvious that White has a strategy ...
gnasher729's user avatar
  • 29.4k
3 votes

Rummikub algorithm

Note that I'll use slightly different notation for my convenience. First, I'll describe an algorithm to determine whether some collection has a valid arrangement assuming we have 4 colours, no ...
Discrete lizard's user avatar
  • 8,128
3 votes
Accepted

Analysis of komi values for increasing Go board sizes and agents strength

From my experience of solving some other games, usually there is a huge difference between optimal player and an average player or even state-of-the-art engine. I bet the results for any other player ...
kubus's user avatar
  • 46
3 votes
Accepted

How does MCTS handle games with large numbers of poor moves?

Issues like these are essentially solved in the MCTS itself. The principle of the algorithm is that it tries to make the best pick, rather than guaranteeing it (if done in this randomized fashion ...
DeBunkeD's user avatar
  • 332
3 votes
Accepted

Why isn't chess an impartial game?

Yes, I believe your changes turn chess into an impartial game. As you mention, stalemate and three-fold repetition can be dealt with by declaring loss. Your trick decouples players (P1 and P2) from ...
sdcvvc's user avatar
  • 3,491
3 votes

Why isn't chess an impartial game?

"To be impartial, a game must satisfy these three conditions". My understanding is that what makes a game impartial or partisan is purely a function of whether or not the same plays are available to ...
DukeZhou's user avatar
  • 249
3 votes

How do I go about constructing a game tree that does not duplicate any states?

Instead of a tree you use a game graph. You maintain a set of nodes (your game states) and, if you need them, a set of edges you already explored. Each time you want to explore a new edge you check ...
adrianN's user avatar
  • 5,931
3 votes

distributed alpha beta pruning

yes the theory has advanced significantly and somewhat due to both the chess analysis literature and general parallel programming techniques. here are some newer refs on (chess) alpha beta pruning ...
vzn's user avatar
  • 11k
3 votes

Determining the existence of a forced win vs determining the best outcome

They are equivalent under Turing reductions, assuming that the game has finite/polynomial-size branching factor (i.e., only that many moves are possible from each position). I don't know if they are ...
D.W.'s user avatar
  • 158k
3 votes
Accepted

Finding the shortest path for synchronized pawns in a maze

I am going to take a guess that you are having trouble with understanding how BFS will work on this game. First, you may wonder "what is the graph we are searching on?" Let's first start with, you are ...
ryan's user avatar
  • 4,451
3 votes
Accepted

Does White never lose in Chess if Chess is solved?

This is unknown at the time of writing. Further, according to solving chess on Wikipedia, no resolution is expected in the near future.
Juho's user avatar
  • 22.5k
3 votes

Find Minimum Transformation Between Multisets of Lists of Cards

Update (or possible correction) to the answer of D.W.. Since we are given the move operations and not the swap operations, we can compute $\pi$ in polynomial time. The problem is known as the ...
Inuyasha Yagami's user avatar
2 votes

Minimum number of givens for General Sudoku of size $n^2 \times n^2$

The minimum number of clues for a puzzle of $n^2$ x $n^2$ is known for $n = 2$ (4 x 4 Sudoku), of which the minimum clues is 4 (25% of cells filled). There are 13 such non-equivalent puzzles. (based ...
tomoka kazuki's user avatar
2 votes

Has connect 4 in 3D been studied in CS?

I couldn't find anything on that particular game, but I found an analysis of a similar game called qubic in Victor Allis' PhD thesis chapter 4: http://fragrieu.free.fr/SearchingForSolutions.pdf It is ...
Craig Feinstein's user avatar
2 votes
Accepted

Representation of 8-Puzzle for (A*) Search Algorithm in C

First of all, the $N$-puzzle is hard to solve with A$^*$ using the Manhattan distance. Instead, we use IDA$^*$. To see the technical details involved in the design of IDA$^*$ specifically for solving ...
Carlos Linares López's user avatar
2 votes

Is there an algorithm that can solve chess within the span of a human lifetime?

You can't prove that chess can't be solved with less than 100 years time because you don't know what computers will be developed during that time. The only limits on computational speed we know are ...
adrianN's user avatar
  • 5,931
2 votes
Accepted

Utilization of static evaluation functions in chess

There are simple ways to do so but it may not be a very good heuristic. For example going off of current piece valuation is very simple but leads to poor aggressive behavior. There are many other ...
sma's user avatar
  • 166
2 votes

How to determine the maximum valued play in Rummikub?

I will describe a polynomial time algorithm that solves both problem 1 and problem 2. I learned of the algorithm from this paper. I am going to make the following assumptions: No jokers (adding them ...
xdaimon's user avatar
  • 53
2 votes

Why do AlphaGo and AlphaGo Zero include board history in the input features

The primary reason for including a history of states is likely indeed the ko rule. Even if having a long history will often be redundant, it's unlikely to hurt either (except that it might take some ...
Dennis Soemers's user avatar
2 votes
Accepted

Why do AlphaGo and AlphaGo Zero include board history in the input features

"This doesn't seem to be discussed in either of the papers, " Yes, it is discussed in at least one of the papers. Here is an excerpt taken from Mastering the Game of Go without Human Knowledge - ...
John L.'s user avatar
  • 38.8k
2 votes
Accepted

Chess Knight minimum moves to destination on an infinite board

thanks to matt timmermans by his hint I realized for infinite chess boards no search algorithm BFS, DFS, A*, Dijkstra should be used. just calculate diagonal symmetry and imagine that start point as (...
Amir-Mousavi's user avatar

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