Questions tagged [board-games]

Scientific analysis of board games, playing strategies and their complexity

Filter by
Sorted by
Tagged with
26
votes
2answers
2k views

Is Dominosa NP-Hard?

Dominosa is a relatively new puzzle game. It is played on an $(n+1)\times(n+2)$ grid. Before the game begins, the domino bones $\left(0,0\right),\left(0,1\right),\ldots,\left(n,n\right)$ are ...
20
votes
1answer
2k views

distributed alpha beta pruning

I am looking for an efficient algorithm that lets me process the minimax search tree for chess with alpha-beta pruning on a distributed architecture. The algorithms I have found (PVS, YBWC, DTS see ...
19
votes
3answers
2k views

How to use Artificial Intelligence in Computer Chess

In some (historical) papers, chess has been referred to as the drosophila of artificial intelligence. While I suppose that in current research, the mere application of a search algorithm is at best ...
14
votes
2answers
8k views

Machine learning algorithm to play Connect Four

I'm currently reading about machine learning and wondered how to apply it to playing Connect Four. My current attempt is a simple multiclass classificator using a sigmoid function model and the one-...
10
votes
2answers
876 views

Is this classic puzzle book game NP-complete?

There is a classic puzzle book game very similar to a crossword puzzle, except a list of words is given and then a $N \times N$ square board made up of unit squares is given, with some squares blacked ...
7
votes
2answers
456 views

Are there ways to automatically (no human testing) measure a $9 \times 9$ Sudoku puzzle's average hardness for a human to solve?

So most resources providing Sudoku puzzles assign a difficulty category to each puzzle, even some I've seen with 15 or more difficulty categories. But what is a good way to assign these difficulty ...
6
votes
4answers
831 views

Why isn't chess an impartial game?

In Combinatorial Game Theory, a major distinction is drawn between impartial games and partisan games. To be impartial, a game must satisfy these conditions: (1) The game is finite; i.e. there is a ...
6
votes
4answers
7k views

Algorithms for Connect 4?

Im designing a program to play Connect 6, a variation of connect 4. I have narrowed down my options to the following: 1) Minimax with Alpha-Beta Proning 2) A Neural Net 3) Machine Learning My ...
6
votes
2answers
21k views

Trying to improve minimax heuristic function for connect four game in JS

I have made a connect four game in JS and currently have a functioning minimax algorithm. The problem I'm having is that it is very, very easy to beat, even with a large depth. This is leading me to ...
6
votes
1answer
977 views

An Alternative Hanoi Tower problem

We got tower $T_1$ with $n$ odd disks (1,3,5,...) and tower $T_2$ with $n$ even disks (2,4,6,...). Now we want to move all $2n$ disks to tower $T_3$. If $T(p,q)$ is a recurrence relation of minimum ...
6
votes
1answer
831 views

Algorithms to play randomized game

I'm interested in building an AI algorithm to play a board game. This is a sequential two-player game, where they alternate taking turns, so minimax or alpha-beta algorithms sound natural. However, ...
6
votes
1answer
327 views

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

Here, it is well known that the minimal number of givens for a size $9 \times 9$ board of Sudoku requires 17 "givens" in order to be solved (i.e., no puzzle can be solved with $\le 16$ givens). What ...
6
votes
1answer
174 views

Mental poker: proving dealt hand is fair

I have just read mental poker, described in this fascinating paper(PDF) by cryptographic greats Adi Shamir, Ron Rivest, and Leonard Adleman. Assuming I have a website, (TTP) how can I prove to the ...
6
votes
0answers
2k views

Toads and frogs game algorithm

I am looking for an algorithm (or hint where to start), for Toads and Frogs Game. What I am interested in is not how to solve the problem (it's NP-hard), but how to plan one player's moves. I.e. how ...
5
votes
2answers
264 views

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

Both AlphaGo and AlphaGo Zero include prior board states as input features (the "Turns Since" planes for AlphaGo, and the repeated 8-step history planes for AlphaGo Zero). What is the purpose of ...
5
votes
1answer
311 views

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

Komi is the additional number of points given to the non-starting player in the game of Go. For 19x19 board, currently it is 6.5 under Japanese rules, 7.5 points under Chinese rules. In the past it ...
5
votes
1answer
649 views

Has connect 4 in 3D been studied in CS?

Connect 4 is a classical game in computer science. Recently I found a web game where one could play the game on a 3d board. One version can be found here https://www.mathsisfun.com/games/connect3d....
5
votes
1answer
947 views

Hanoi tower with forbidden direct move from source to destination

I want to know what is algorithm and time complexity of Hanoi tower with forbidden direct move from source to destination (it means you cannot move disk from source to destination directly and you ...
5
votes
1answer
149 views

Monte Carlo Tree Search in connect 5 tree design

I'm trying to create a mcts ai for connect 5 algorithm. However, I'm confused on designing the tree. Here is a quick description of the algorithm: The initial state, S0 is the board state where the ...
4
votes
2answers
1k views

What complexity class would this version of generalized chess fall?

By now I understand that generalized chess is harder than NP, and is EXPTIME-complete for the decision problem "Given an nxn board with a given position, can white force a win?" because the proof ...
4
votes
2answers
3k views

Knight on a chessboard

This is a Hackerrank challenge $Knight$ is a chess piece that moves in an L shape. We define the possible moves of $Knight(a,b)$ as any movement from some position $(x_1, y_1)$ to $(x_2, y_2)$ ...
4
votes
2answers
40 views

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

A large body of work looks at the computational complexity of games. In particular, identifying a forced win from a given position. Is this problem equivalent under polynomial-time reduction to ...
4
votes
1answer
2k views

Rummikub algorithm

I have just played a few games of Rummikub and the manipulations I made during my turns became more and more complex transactions. A few turns reordered the whole field, so that other players did not ...
3
votes
4answers
4k views

Chess Knight minimum moves to destination on an infinite board

There are tones of solutions for Knights tour or shortest path for Knights movement from source cell to destination cell. most of the solutions are using BFS which seems the best algorithm. Here is ...
3
votes
3answers
304 views

Does White never lose in Chess if Chess is solved?

If the machine has enough memory and speed as to compute all states of the Chess game in a reasonable time, can a player with the white pieces - operated by a machine - lose a game?
3
votes
1answer
283 views

Rubik Cube Algorithm for general n

I am not sure if this is the right place , but: Is there an algorithm for solving $n\times n \times n$ rubik's cube (non-trivial one)? If so how efficent is it? Now say I have a $n \times \ldots \...
3
votes
1answer
6k views

Mastermind (board game) - Five-guess algorithm

The algorithm (from here) - Create a set S of remaining possibilities (at this point there are 1296). The first guess is aabb. Remove all possibilities from S that would not give the same ...
3
votes
1answer
246 views

Finding the shortest path for synchronized pawns in a maze

I have been trying to wrap my head around this problem, and I just can't get it. We have an $a \times b$ matrix where every cell corresponds to either an empty space, denoted with a dot, or a wall, ...
3
votes
1answer
241 views

Algorithm playing modification of "Hey, That's My Fish!" game

Ok, I must admit this a task from my studies but I'm stuck. Rules of the game are on Wikipedia. However, we have a modified version: on input we have a board with x fields, there are y penguins on ...
3
votes
2answers
701 views

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

According to Shannon (in his 1949 paper) the game of chess has too much complexity to be solved by a brute-force search of the game tree: A machine... would require over $10^{90}$ years to ...
3
votes
1answer
215 views

Algorithm for a 2D path-finding puzzle

I am trying to find an algorithm for finding an optimal solution to a puzzle of a given format. The 7 by 6 puzzle board is made out of the following pieces: The tears are as follows: Tears and ...
3
votes
1answer
581 views

How to validate a connect X game (Tick-Tak-Toe,Gomoku,...)?

Currently I am working on a Gomoku AI (or generally Connect-X games). Implementing the search tree was no problem, but then I got to the point where I had to implement the value function and was ...
3
votes
1answer
776 views

N-queens problem objective function

I have read about the N-queens problem and I don't understand the following objective function: $O(board)=N^2/2-L$ $N$ ... number of queens $L$ ... number of pairs of queens that attack each other ...
3
votes
0answers
123 views

Speeding up the Rummikub algorithm - explanation required

Regarding this question: Rummikub algorithm. I was reading the first part of the solution in the posted answer (specifically, when there are no jokers involved, all tiles are distinct and only four ...
3
votes
0answers
1k views

Is Chinese Checkers a solved game

Is there a machine or algorithm available to solve the board game "Chinese checkers"? If there is please let me know about relevant material. I have already searched over internet unfortunately i am ...
2
votes
1answer
262 views

Poker with Bluffing (game theory)

I'm doing a self-study of Game Theory Evolving by Gintis, and am stuck on problem 4.16 "Poker with Bluffing". The first question asks "Show that Ollie has 64 pure strategies and Stan has 8 pure ...
2
votes
1answer
117 views

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

Many games have states that can be reached via multiple paths in their gametree. For concreteness, consider the game of tinychess (with the obvious(I hope) rules inherited from chess), which looks ...
2
votes
1answer
263 views

Solving AlienTiles with an A* heuristic

Hello I am trying to solve the AlienTiles problem described at alientiles.com using the A* algorithm but I cannot find any good heuristic function so far. In AlienTiles you have a board with $N \...
2
votes
1answer
31 views

Building a game tree from a board game

Currently I want to come up with a program able to solve a specific type of board game, where we have a car moving across a randomly generated board, can't move backwards, a gas gauge and a food gauge....
2
votes
2answers
118 views

DAG: When adding an edge that would normally result in a cycle, is there an algorithm to split the graph instead?

Summary I am using a DAG to compress a tree structure with many repeated nodes (the repeated nodes only very seldomly do not also have repeated edges out.) Normally, when attempting to add an edge to ...
2
votes
1answer
178 views

Is the mate-in-n problem of infinite chess with each color using traditional pieces plus one huygens decidable?

I noticed in a paper that the mate-in-n problem of chess, even played on an infinite board is decidable. The mate-in-n problem of infinite chess is decidable I believe the paper assumes only ...
2
votes
3answers
1k views

Is there an algorithm that can solve any two-player game?

Note: this is basically a more precise restatement of this question, which didn't get proper answers because it was vague. Most two-player perfect information games can be represented as a finite ...
2
votes
1answer
91 views

Whats the name of this search game?

I am struggling in finding the name of this game (in order to find research papers related to it in the literature). Given an initial word $X$ and a target word $Y$, what is the minimum number of (...
2
votes
2answers
42 views

Neural network game players and incremental updates

Neural networks in recent years have been successfully used for gameplaying. A difference between games and e.g. image processing is that the game boards get updated incrementally. Do any neural ...
2
votes
1answer
75 views

Can this Arrow-Ring puzzle be encoded as an integer programming problem?

I would like to write a solver for these kind of Arrow-Ring puzzles. However, I can't encode all the constraints correctly. I noticed that Sudoku can be solved using integer programming and I am ...
2
votes
2answers
383 views

How to determine the maximum valued play in Rummikub?

This question is meant as a follow-up this question and my answer here. The question asked multiple questions about algorithms for playing Rummikub and my answer provided an algorithm that, given a ...
2
votes
0answers
214 views

Least constraining value heuristic in Sudoku [closed]

I was trying to implement Least Constraining Value Heuristic in Sudoku but wasn't getting the idea on how to do it. Can someone share their idea for the same ?
2
votes
0answers
52 views

Puzzles like Sokoban?

I am looking for some puzzles like Sokoban or 15-puzzle but more difficult to solve and satisfy the following requirements: The number of possible moves at each step should be limited, let's say < ...
2
votes
0answers
73 views

How does this star1 variation work? (star1 is a stochastic (dice) algorithm for artificial intelligence in adversarial games)

I don't understand how the star1 variation mentioned in the paper is Sparse Sampling for Adversarial different than the usual star1 algorithm? (Taken from the bottom of page 7). This variant can be ...
1
vote
2answers
76 views

Complexity of simulating idle games (pt1)

An idle game (Cookie Clicker is a well-known example) is a game where you set up automatic resource production, and most of reasonable human play is then waiting as resources accumulate. Typical ...