Skip to main content

Questions tagged [board-games]

Scientific analysis of board games, playing strategies and their complexity

Filter by
Sorted by
Tagged with
1 vote
0 answers
19 views

Multiplayer one-round one-move voronoi game on graphs

I'm trying to solve a variant of Voronoi Game. Given a Graph $G=(V, E)$, with uniform distance $d(E)=1$, a subset of the vertices $\hat{V} \subseteq V$ are vertices of interests. $k$ players take ...
z.x.99's user avatar
  • 11
0 votes
0 answers
32 views

How can I know the complexity of my conceptual game and solving it with an algorithm?

I made a really simple card game where you and your opponent have 6 cards and in a turn you can use only one of them and it will be discarded. The cards have a value and an effect. The cards, with ...
michaelprimo's user avatar
0 votes
1 answer
37 views

Calculating the highest possible scoring Scrabble move

Let’s say there are n fixed words permitted in some game of Scrabble, on an m x m squares board. We are assuming an idealized scenario where anyone can write any word on the board. Assume both players ...
Julius Hamilton's user avatar
3 votes
2 answers
422 views

Find Minimum Transformation Between Multisets of Lists of Cards

Brief: I have two configurations, a and b, of the same set of Rummikub tiles (a may not be a ...
xdaimon's user avatar
  • 53
2 votes
0 answers
43 views

Bananagrams decision problem - computational complexity

I've been playing Bananagrams recently, and have begun to wonder about the math behind it from a computational perspective. I've tried to formalize the problem as a decision problem below. Loosely ...
AbsentMynd's user avatar
2 votes
2 answers
216 views

Zero sum game: dp recursion strategy

Trying to solve the zero-sum problem described here, where two opponent players at each turn can choose to collect 1, 2 or 3 stones with different values, with the objective of getting more points at ...
rickyviking's user avatar
2 votes
1 answer
102 views

Checking forbidden moves in Renju

I am trying to detect forbidden moves for black in a game called Renju. First, here is an explanation of how Renju works. Renju is a board game played on a 15x15 Go board. There are two players in the ...
Kyaw Shin Thant's user avatar
3 votes
1 answer
282 views

Why is this proof that CHESS is in EXPTIME correct?

I've been reading the following paper (open) by Fraenkel and Lichtenstein that shows that the Generalized $n \times n$ Chess problem ($\texttt{CHESS}$) is $\texttt{EXPTIME-complete}$. They start by ...
alexland7219's user avatar
1 vote
1 answer
141 views

Optimality of A* algorithm

In the book Artificial Intelligence a Modern Approach 4th edition, the author claims that the A* algorithm is cost-optimal if the heuristic function is ...
user101998's user avatar
1 vote
1 answer
144 views

Distributing cards randomly given constraints

We want to distribute 3*n known cards among 3 players evenly given a set of constraints that prohibits some players from having certain suits. For example: We want to distribute 1H, 2H, 3S, 4S, 5D, 6D ...
SAKO's user avatar
  • 11
3 votes
2 answers
319 views

Paint a Cube by rolling it (Puzzle Algorithm)

I stumbled across this game in Simon Tatham's puzzle app. It's called cube. The description according to the game is: You have a grid of 16 squares, six of which are blue; on one square rests a cube. ...
Zingerella's user avatar
2 votes
1 answer
50 views

Storing game traces (e.g. Chess, Othello) in a minimal number of bits

I am thinking about the problem of storing traces of games like Chess and Othello in an information-theoretic minimal number of bits. My idea was to think of a game as an ordered tree of possible ...
Chris's user avatar
  • 131
1 vote
0 answers
46 views

Long and short memory in reinforcement learning Connect 4 AI

I'm writing an AI based on reinforcement learning to play Connect 4. That's my second bot and attempt to RNN and AI (first was copy a code of snake RNN AI from youtube) and I'm looking for some ...
Saguro's user avatar
  • 11
2 votes
1 answer
165 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....
spurdosparde's user avatar
1 vote
1 answer
546 views

Detecting and correcting collisions in (Zobrist) hashing to avoid errors in transposition table

Context Say I have a transposition table that uses keys produced by (e.g. Zobrist) hashing game positions. The table has a finite recycled memory (key % p is the <...
Vepir's user avatar
  • 117
2 votes
2 answers
399 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 ...
OmnipotentEntity's user avatar
1 vote
1 answer
64 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 ...
BRHSM's user avatar
  • 123
0 votes
0 answers
73 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 ...
Oleg Dats's user avatar
  • 299
1 vote
0 answers
170 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 ...
afwksh's user avatar
  • 11
1 vote
2 answers
406 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 ...
Zachary Vance's user avatar
3 votes
0 answers
312 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 ...
S.T.'s user avatar
  • 131
1 vote
1 answer
98 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 ...
mafu's user avatar
  • 339
1 vote
1 answer
608 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, ...
user37014's user avatar
1 vote
0 answers
255 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 ...
Zyx's user avatar
  • 145
3 votes
3 answers
431 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?
108880's user avatar
  • 27
1 vote
2 answers
589 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 ...
AllirionX's user avatar
  • 113
2 votes
0 answers
390 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 ?
math_coder's user avatar
2 votes
2 answers
44 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 ...
rwallace's user avatar
  • 386
0 votes
2 answers
149 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 ...
olinarr's user avatar
  • 394
1 vote
1 answer
310 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 ...
zzz10n's user avatar
  • 13
3 votes
1 answer
388 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, ...
mander39's user avatar
1 vote
1 answer
538 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 ...
namesake22's user avatar
2 votes
0 answers
64 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 < ...
Math-fort's user avatar
  • 173
0 votes
1 answer
808 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 ...
struggling's user avatar
3 votes
5 answers
5k 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 ...
Amir-Mousavi's user avatar
7 votes
2 answers
429 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 ...
Mankarse's user avatar
  • 183
4 votes
2 answers
44 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 ...
Stella Biderman's user avatar
2 votes
1 answer
88 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 ...
john mangual's user avatar
  • 1,951
3 votes
1 answer
338 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 ...
Sail Patcher's user avatar
0 votes
1 answer
467 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 ...
Andre Fu's user avatar
  • 103
2 votes
2 answers
622 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 ...
Discrete lizard's user avatar
  • 8,303
0 votes
0 answers
872 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 ...
Mohbenay's user avatar
  • 319
3 votes
1 answer
837 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 ...
Miemels's user avatar
  • 131
5 votes
1 answer
5k 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 ...
Martin Ueding's user avatar
1 vote
3 answers
964 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 ...
tomoka kazuki's user avatar
1 vote
0 answers
405 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 ...
Robert's user avatar
  • 131
3 votes
0 answers
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 ...
Hamza Ali Siddiqui's user avatar
6 votes
1 answer
436 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 ...
Adam Stelmaszczyk's user avatar
4 votes
2 answers
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)$ ...
paparazzo's user avatar
  • 431
3 votes
2 answers
727 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 ...
tomoka kazuki's user avatar