Questions tagged [board-games]

Scientific analysis of board games, playing strategies and their complexity

15 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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 ...
3
votes
0answers
112 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
0answers
51 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
69 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
0answers
31 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
0answers
48 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 ...
1
vote
0answers
182 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
158 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 ...
0
votes
1answer
14 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 <...
0
votes
0answers
35 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
35 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 ...
0
votes
0answers
764 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 ...
0
votes
1answer
1k views

Data structures and algorithms for bridge game play?

In a bridge game, a deck of 52 cards (13 spades , 13 clubs, 13 diamonds, 13 spades) are dealt to 4 players (13 cards each) then game starts.Game session ends after 13 tricks each having 4 cards.There ...