Scientific analysis of board games, playing strategies and their complexity

learn more… | top users | synonyms

0
votes
1answer
42 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
44 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
2answers
78 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
99 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 ...
3
votes
1answer
84 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 ...
0
votes
0answers
35 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. ...
1
vote
0answers
47 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 ...
2
votes
1answer
111 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
54 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
180 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 ...
8
votes
1answer
192 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
84 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
673 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
647 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 ...
1
vote
1answer
76 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 ...
14
votes
3answers
684 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
177 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 ...
1
vote
1answer
3k 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
2k 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
96 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 ...
4
votes
1answer
246 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, ...
23
votes
2answers
995 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 ...
5
votes
2answers
7k 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 ...
5
votes
1answer
219 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
600 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 ...
2
votes
1answer
196 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
0answers
42 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 ...
0
votes
1answer
756 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 ...
6
votes
1answer
145 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
1answer
249 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 ...
12
votes
2answers
2k 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 ...
15
votes
1answer
456 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 ...