Scientific analysis of board games, playing strategies and their complexity

learn more… | top users | synonyms

1
vote
1answer
71 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
87 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
36 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 ...
13
votes
3answers
56 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
151 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 ...
0
votes
1answer
467 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
397 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
72 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
140 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, ...
20
votes
2answers
665 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 ...
4
votes
2answers
3k 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 ...
4
votes
1answer
164 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 ...
2
votes
1answer
157 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
24 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
437 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
129 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 ...
5
votes
1answer
187 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 ...
11
votes
2answers
789 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 ...
9
votes
0answers
263 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 ...