22

${\rm D{\small OMINOSA}}$ is NP-hard Playing the game is an optimization problem; finding a valid domino tiling such that it covers all the squares. The decision version of this problem is: Is there a perfect tiling covering a given a $(n+1) \times (n+2)$ grid with $n$ unique tiles? Obviously, the optimization problem, the problem of actually finding a ...


16

The whole state space for chess is enormous - it can be roughly estimated as 1043 (Shannon number (Shannon, 1950), (Wikipedia)). The idea you present - Reinforcement Learning agents playing with each other to learn the game - was successfully applied to Backgammon - TD-Gammon (Tesauro, 1995), (Chapter in Reinforcement Learning by Sutton&Barto). It also ...


9

Note: This is a continuation and revision of my other answer. Problems with the reduction Recall the decision problem: Is there a perfect tiling covering a given a $(n+1) \times (n+2)$ grid with $n$ unique tiles? So for an $(n+1) \times (n+2)$ grid, we can only use $n$ variables. But: Our reduction requires a lot of unique variables, much more than $\...


8

There are have been many such attempts. Most of them try to derive deduction rules which humans seem to use to solve Sudoku puzzles. My money is on this approach: Mária Ercsey-Ravasz & Zoltán Toroczkai (2012), The Chaos within Sudoku, Scientific Reports 2:75, Nature. The idea is based around the notion of transient chaos in a dynamical system. In ...


8

Just to offer a simpler alternative to reinforcement learning, you can use the basic minimax algorithm to search for good moves, and use machine learning to evaluate board positions. To clarify, minimax builds a game tree where each node is labeled with the outcome from the leaves up (1=player A wins, 0=player B wins), assuming that A chooses the moves that ...


7

Connect Four was solved in 1988. The first solution was given by Allen and, in the same year, Allis coded VICTOR which actually won the computer-game olympiad in the category of connect four. I would suggest you to go to Victor Allis' PhD who graduated in September 1994. You can get a copy of his PhD here. In Section 6.3.2 Connect-Four (page 163) you can ...


7

Chess violates all three conditions, so I don't really understand what there is to ask. (1) The game is not finite. Although the 50-move and threefold repetition rules allow a player to end the game under certain circumstances, they do not oblige the player to do so. (2) The game has draws. (3) As you have observed, the game definition distinguishes ...


7

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 $NP$. We do not have a proof that $NP \not = EXPTIME$ or a proof that a certificate for generalized chess would take an exponential amount of steps. It is highly ...


6

Algorithms for Solving Rubik's Cubes by Demaine et al. shows that an $n\times n\times n$ Rubik's Cube can be solved in $O(\frac{n}{\log n})$ moves and this is (asymptotically) optimal. I am not certain on the complexity of actually computing such a solution but I suspect that (by closely following the steps in the proof) it can be done in polynomial time (...


6

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 Yesterday i was having trouble coming with ideas for solving the problem. I had trouble making each variable different until i looked again at the question and ...


6

Connect 4 is a solved game - under perfect play, white wins. Victor Allis's thesis contains a winning algorithm for white. The game had been solved a few weeks earlier by James D. Allen. Later on, John Tromp came up with a strategy that will win the game from any position, if possible, and thus solved the game strongly.


6

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 node is at most eight and so the number of edges is at most $\frac{8N}{2} = 4N$, where $N = n^2$ is the total number of nodes/cells and $n\times n$ is the size ...


5

Stan has two pure strategies for each type of card. Since there are three types of cards (H, M, L), in total he has $2\times 2\times 2 = 8$ strategies. Here is a list of them: Always stay. Always raise. Stay only if H. Stay only if M. Stay only if L. Raise only if H. Raise only if M. Raise only if L.


5

Disclaimer: I'm assuming your minimax works perfectly and your logic of who wins when and when to apply your heuristic how is sound (mainly because you only gave part of your program and partly because it's been a while since I last implemented one of these, so I won't exactly know what to look for) and thus I'm only commenting on your heuristic. Don't ...


5

Let $T_n$ be the the column of disks $1:2:…:n$. Let's start by the end: $(T_n)()()$ is the final configuration. The only mean to get there is by moving the disk $n-1$ on the stack $(n)$, so the remaining $T_{n-2}$ should be on another stick. So we should get to: $(n)(n-1)(T_{n-2})$ in $2^{n-2}$ steps: first move the $n-1$ disk then use $2^{n-2}-1$ steps ...


5

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 have to switch to A* is an interesting problem, but 100 squares away will surely be fine, and A* from there fits into a reasonable amount of memory. Also note ...


5

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 expressed as a Gaussian integer; the real part of $g$ will be the horizontal displacement, and the imaginary part of $g$ will be the vertical displacement. Then we ...


4

I think the following reduction from Directed Hamiltonian path works: Given a graph $G=(V,E)$ and a two vertices $s,t\in V$, we output the following puzzle: The alphabet is $V\cup \{*\}$, with $*$ being some symbol not in $V$. The words are $v*v$ for every $v\in V$, and $vu$ for every edge $(u,v)\in E$. The board consists of two parts. The first looks ...


4

The text you quoted seems clear as it is. But I'll try to elaborate on step 3, since you asked: Let $S$ denote the set of possible secrets (given responses to moves you've made so far). Given a candidate guess $g$, you run over all possibilities $s \in S$ and calculate the response that you'd get if you guessed $g$ and the secret was $s$ (the number of ...


3

Inside the function Minimax-Value, see the line where it says "the highest Minimax-Value of..."? That is implicitly a recursive call to the Minimax-Value function, i.e., a call to yourself.


3

O1(s) = 3. You missed another diagonal.


3

One candidate approach: for each color $c \in \{\text{green}, \text{blue}, \text{purple}\}$, try to define a distance heuristic $f_c(\cdot)$ that approximates the distance to the specific goal of getting all tiles to be the color $c$. For instance, if $s$ is a state, then $f_\text{green}(s)$ should be an estimate of the distance to the all-green state. ...


3

You are probably supposed to use exhaustive search, that is, recursively try all possible moves. They made it easier by restricting the number of possible moves. One optimization which might be needed is storing board positions and the number of fish obtained from them, so that you don't analyze twice the same sub-position; there might be too many of them to ...


3

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 over distributed clusters/ parallelism. also some of the early distributed computing chess literature predates a lot of basic parallel design patterns and can be ...


3

I am pretty sure that any possible (or weird) method of AI or ML in textbooks has been tried and pretty much failed compared to simple brute force. My personal perspective is that chess per se is of no interest to modern AI any more... Simply, because it is solved: by just using a modern computer and brute force. So, I don't feel that there is a need to ...


3

"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 both players. Chess is partisan because there are black and white pieces, and players can only move their own color. The other two conditions listed are not ...


3

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 whether it leads to a node in your set of nodes. If it doesn't you just found a new node and have to add it to the set. Your programming language of choice ...


3

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 rather than a 'pure MCTS' fashion). The trees are built up out of large amounts of collected data, aggretating success rates in the nodes. Nodes that end up being ...


3

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 then optimal will diverge from the results of optimal play. For example see what happened with some famous chess positions when endgame tables where developed (...


3

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 jokers and all tiles are distinct. We'll extend this into the general case afterwards. Given are four lists $a_1,a_2,\ldots, a_A ; b_1,b_2,\ldots, b_B ; c_1,c_2,\...


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