Questions tagged [board-games]
Scientific analysis of board games, playing strategies and their complexity
78
questions
0
votes
1answer
13 views
Detecting and correcting collisions in (Zorbist) hashing to avoid errors in transposition table
Context
Say I have a transposition table that uses keys produced by (e.g. Zorbist) hashing game positions.
The table has a finite recycled memory (key % p is the <...
2
votes
2answers
96 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 ...
1
vote
1answer
50 views
How to remove an ordering requirement from a board game simulation?
The Problem:
I'm trying to simulate part of the game tantrix which is a board game played with hexagonal tiles. Each tile has 3 lines of different colors that each start at one side of the hexagon ...
0
votes
0answers
34 views
How to reduce Checkers to P and NP-complete?
NxN Checkers where both players are playing to win is EXPTIME complete.
If we fix NxN to be 8x8 and prepare a very large lookup table then it can be solved in constant time and space.
How to formulate ...
0
votes
0answers
30 views
Questions on AlphaZero Implementation
So I've been implementing AlphaZero for Chess from scratch and there were a few things the papers mentioned that I'm not sure how to implement. I'll reference both the original AlphaGoZero paper and ...
1
vote
0answers
30 views
Rummy Card Game Bot
in my beginner’s computer science class, we are asked to create an bot for a variant of rummy. It has to make logical moves as it needs to beat other very simple bots. I wanted to know how you would ...
1
vote
2answers
53 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 ...
3
votes
0answers
106 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 ...
1
vote
1answer
67 views
Are tiny point-symmetric grids of two Pentominos impossible to solve?
The game of Pentomino is a tiling puzzle game played on a grid. A Pentomino piece is a two dimensional shape of five non-diagonally connected tiles. There are exactly 12 unique pieces (ignoring ...
1
vote
1answer
68 views
How many snakes there can be in the “snakes and ladders” game?
How to calculate the maximum allowed number of snakes in the game of "snakes and ladders" from mathematical/algorithmic point of view assuming that there is a nxn board?
UPD: My thoughts are simple, ...
1
vote
0answers
39 views
Is this a valid heuristic for Dots and Boxes to reduce the branching factor of the search tree?
I am implementing an AI based on the MiniMax algorithm that plays the game Dots and Boxes. I would like to reduce the branching factor of the search tree, by introducing a heuristic rule that limits ...
1
vote
0answers
48 views
Is Dots and Boxes complementary to the game of Go?
I've read that La Pipopipette is known to be NP-hard. I have not yet found analysis specifying an exact complexity class for Dots and Boxes, or for some variations in the analysis of Go.
Here's a ...
3
votes
3answers
278 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?
1
vote
1answer
394 views
Pandemic board game - find all possible next 4 actions
I hope I am asking this on the right community.
I am building an Artificial Intelligence to play the board game Pandemic. The AI uses a Monte Carlo algorithm. After implementing the game rules and ...
2
votes
0answers
187 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
2answers
33 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 ...
0
votes
2answers
88 views
Assuming an infinite amount of computing resources, would the minmax algorithm always win in chess?
The minmax algorithm is a popular strategy used to design chess engines. Usually, since the state-space of chess is huge, we choose a fixed depth and evaluate the game tree down to that level, and ...
0
votes
1answer
116 views
Efficient search for solving a Jigsaw Puzzle?
I believe that solving a Jigsaw puzzle is in general NP-complete based on the two questions linked below. However, I'd like to implement a heuristic algorithm that works well in practice.
Let's ...
3
votes
1answer
175 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, ...
1
vote
1answer
276 views
Two Minimax AIs playing against each other
I am trying to have my Minimax AI chess players play against each other.
I was a bit confused about an implementation detail.
Let's call black my first minimax AI ...
2
votes
0answers
50 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 < ...
0
votes
1answer
398 views
Nim game tree minimax [duplicate]
Problem : Two players have in front of them a single pile of objects, say a stack of 7 pennies. The first player divides the original stack into two stacks that must be unequal. Each player ...
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 ...
5
votes
2answers
226 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 ...
4
votes
2answers
39 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 ...
2
votes
1answer
58 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 ...
3
votes
1answer
193 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 ...
0
votes
1answer
354 views
Utilization of static evaluation functions in chess
Disclaimer: I'm very new to computer science & game programming
I'm having trouble with understanding how to implement a static evaluation function in chess. The logic seems simple like just ...
2
votes
2answers
352 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 ...
0
votes
0answers
751 views
Board Game algorithms
I have to find an evaluation function in which we evaluate the state of the game in each round.
The game is like " roborally " , it is 2 player-Game in which there are a board and cards ...
3
votes
1answer
492 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 ...
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 ...
1
vote
3answers
521 views
Is there a way to make chess an absolutely fair game? [closed]
Chess is usually considered a mostly "fair game" between White and Black because the opening position of pieces has mirror symmetry (between players). In practice it also appears to be a fair game ...
1
vote
0answers
177 views
Generating all legal starbattle grids
I am trying to generate a type of logic puzzle called starbattles. The puzzles consist of an nxn grid that is divided into n distinct regions. The rules of the puzzle are to place stars in the grid ...
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 ...
5
votes
1answer
278 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 ...
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)$ ...
3
votes
2answers
697 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 ...
5
votes
1answer
146 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 ...
2
votes
1answer
174 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 ...
1
vote
1answer
973 views
Representation of 8-Puzzle for (A*) Search Algorithm in C
I am trying to complete CS50's hacker edition pset3, where you have to make a program that will solve the game of eight or fifteen from its current state, this must be written in C.
https://en....
1
vote
1answer
931 views
How does MCTS handle games with large numbers of poor moves?
I am trying to understand how pure Monte Carlo tree search (https://en.wikipedia.org/wiki/Monte_Carlo_tree_search) handles games where random playout will likely result in a loss easily avoided by ...
0
votes
1answer
417 views
A nim game variant with pass move
This variant is almost similar to the normal nim game which states -
Two players take turns to remove one or more items from a single, non-empty pile. The player who removes the last item from the ...
3
votes
1answer
671 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
...
0
votes
2answers
118 views
Describe an algorithm for painting cards in the following game
It's my first question out here, so please don't judge me too strictly.
I heard of the following game: there's set of cards with different set of objects (but the same number of them on every card) ...
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 ...
0
votes
1answer
210 views
Checking whether a node is expandable
I'm making a program to play the board game Quoridor. I build a move tree using Monte Carlo Tree Search (MCTS). MCTS requires me to test whether a node is expandable. A node is said to be expandable ...
2
votes
1answer
105 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
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 ...
5
votes
1answer
604 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....
