Questions tagged [board-games]
Scientific analysis of board games, playing strategies and their complexity
2
votes
0answers
34 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
0answers
15 views
Algorithm to determine an approximate distribution of leaf node depths in a massive tree
I am conducting some analysis of game trees (often consisting of 10^50 or more nodes). I'd like to determine, in a given game, how deep in the tree the leaf nodes tend to be. That is, how long the ...
0
votes
1answer
49 views
Nim game tree minimax
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 ...
1
vote
3answers
356 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
92 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
31 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
32 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
90 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
0answers
16 views
What is the correct loss fuction for this RL game?
I'm writing an RL algorithm similar to AlphaGo to play a single player game similar to solving a Rubik's cube and I'm trying to come up with a good loss function.
Starting from a random initial ...
0
votes
1answer
147 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 ...
3
votes
0answers
29 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
246 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
77 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
322 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
132 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
50 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 ...
1
vote
0answers
341 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
147 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
2k 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
580 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
98 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
161 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
627 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
377 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
354 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 ...
2
votes
1answer
319 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
107 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
566 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
134 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
72 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 ...
1
vote
3answers
738 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 ...
4
votes
1answer
305 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....
6
votes
4answers
427 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 ...
1
vote
1answer
140 views
Numerical Boardgame — Help with with a pruning method (alpha-beta : minimax)
I'm developing a simple AI to play a boardgame which consists of N x N squares, each with a predefined value.
...
5
votes
1answer
213 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 ...
3
votes
1answer
238 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 \...
2
votes
1answer
75 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 (...
7
votes
2answers
347 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 ...
10
votes
2answers
534 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 ...
1
vote
0answers
133 views
Worst-case recursion depth for guessing numbers in a Sudoku puzzle when certain polynomial-time deduction rules are used
So for an arbitrary $n^2 \times n^2$ Sudoku puzzle, there are rules for inferring values and auxillary information in cells that run in polynomial time, e.g. using the filled in values to check to see ...
1
vote
1answer
2k views
Time complexity of 8-queen, by placeing one by one without attack
I am new to artificial intelligence. I have been trying to analyse the time complexity of 8-queen, by placing one by one without attack.
One approach to achieve goal state is to "add a queen to any ...
-1
votes
1answer
1k views
Where is the recursion, in the minimax-decision algorithm?
The below is from an article titled:
Minimax: Recursive Implementation
To be a recursive function, you need to call yourself.
What part of this pseudo code is calling itself?
How does depth-...
1
vote
1answer
223 views
How do I compute this non terminal positions evaluation, for tic-tac-toe?
Looking at this solution on page 3 but having trouble understanding the evaluation function specifically.
For non terminal positions, we use a linear evaluation function
defined as
Eval (...
18
votes
3answers
1k 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 ...
2
votes
1answer
220 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 \...
3
votes
1answer
5k 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
2answers
3k 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 ...
3
votes
1answer
168 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 ...
5
votes
1answer
581 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, ...
25
votes
2answers
1k 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 ...
