# Tagged Questions

Scientific analysis of board games, playing strategies and their complexity

57 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) ...
327 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 ...
46 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 ...
45 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 ...
88 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 ...
108 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....
89 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 ...
81 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. ...
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 ...
115 views

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 ...
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 ...
98 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 ...
255 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, ...
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 ...
8k 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 ...
222 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 ...
623 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 ...
202 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 ...
43 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 ...
778 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 ...
146 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 ...
263 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 ...