The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [combinatorial-games]

Use for games commonly understood as combinatorial (Chess, Checkers, Go, Tic-Tac-Toe, Hex, Domineering, NIM, etc.) or for any games studied for the purpose of **solving** the game. *(Initially reserved for non-chance games of perfect information, the scope of Combinatorial Game Theory expands as mathematics and computability advance. Thus, game involving randomness and hidden information, such as Poker, may be considered combinatorial games.)*

Filter by
Sorted by
Tagged with
0
votes
0answers
44 views

Can AC-3 algorithm solve N-Queens problem?

I am building CSP NQueens solver and apply the AC-3 algorithm.But,the domain reduction doesn't occur and gets more search time.How does it happen?Is it a nature of AC-3 algorithm?
1
vote
1answer
161 views

Adversarial Game playing using RL

I asked a question relating to TicTacToe playing in RL. From the answer it seems to me a lot is dependent on the opponent (rightly so, if we write down the Expectation Equations). My question is (in ...
3
votes
1answer
89 views

How do I solve the problem of positioning 11 pieces into a 8x8 puzzle?

I was trying to figure out how to create a solver to the puzzle of putting 11 pieces in a board (8 x 8). I created the game in http://www.xams.com.br/quebra. It is possible to turn the piece 90 ...
0
votes
0answers
33 views

How to approach the sequential decision-making problem with sub-actions with RL?

I have been trying to solve a sequential decision-making problem that involves taking "sub-actions". I would like to share my experience and really appreciate any suggestions/insights. Suppose we ...
0
votes
1answer
79 views

What will Q-values look like in self-play tic-tac-toe?

This corresponds to Exercise 1.1 of RLBook, and a discussion followed from here. Considering two reward schemes- Win = +1, Draw = 0, Loss = -1 Win = +1, Draw or Loss = 0 Can we say something about ...
1
vote
1answer
232 views

Q-Learning tic tac toe - bad player

I tried to build an Q-learning agent which you can play tic tac toe against after training. Unfortunately the agent performs pretty poorly. He tries to win but does not try to make me 'not winning' ...
0
votes
0answers
41 views

Examples of strong symbolic AI for unsolved, non-trivial combinatorial games?

Looking primarily for research papers, but any info or insights on this subject are welcome. Strength does not have to exceed that of the best human player (such as Kasparov), just skilled human ...
2
votes
0answers
143 views

How to encode Azul game state as NN input

Question to NN practicioners. I'd like to encode Azul board game state as an input to NN, let's focus on 2-player variant for a while. There are 5 round "Factories" on the table (7 on picture, ignore ...
1
vote
1answer
120 views

Historical weakness of GOFAI in relation to partisan combinatorial games?

I was recently perusing the paper Some Studies in Machine Learning Using the Game of Checkers II--Recent Progress (A.L. Samuel, 1967), which is interesting historically. I was looking at this figure, ...
4
votes
1answer
329 views

Algorithms for games with very high branching factors (Connect6)

Connect6 is an example of a game with a very high branching factor. It is about 45 thousand, dwarfing even the impressive Go. What algorithms can you use on games with such high branching factors? I ...
4
votes
3answers
2k views

What else can boost iterative deepening with alpha beta pruning?

I read about minimax, then alpha-beta pruning and then about iterative deepening. Iterative deepening coupled with alpha-beta pruning proves to quite efficient as compared alpha-beta alone. I have ...
0
votes
2answers
90 views

How the AI network can be modeled for AlphaZero?

There is more information recently that AlphaZero has been trained to be the best chess program after 4 hours of learning (in chess). I am wondering how the AI network could have been modeled for this ...
4
votes
1answer
341 views

How would you encode your input vector/matrix from a sequence of moves in game like tasks to train an AI? e.g. Chess AI?

I've seen data sets for classification / regressions tasks in domains such as credit default detection, object identification in an image, stock price prediction etc. All of these data sets could ...
1
vote
0answers
47 views

Mini (local) NN for Mobile?

I'm working on architecture for a game AI where, due to the nature of the game, the classical approach seems likely be sufficient to beat most humans--the endgame is tractable and traditional game-...
4
votes
2answers
647 views

How do I create an ai for a two players board game?

Brief idea I want to create an artificial intelligence to compete against other players in a board game. Game explanation I have a board game similar to 'snakes and ladders'. You have to get to a ...
9
votes
1answer
944 views

Neural networks vs Genetic algorithms in games like Tic Tac Toe?

Currently I'm doing a project that's about creating an AI to play the game Gomoku (It's like tic tac toe, but played on a 15*15 board and requires 5 in a row to win). I have already successfully ...
0
votes
7answers
392 views

Can an AI learn how to play chess without instructions?

Can an AI learn to play chess if you give it nothing but "the goal is to win" as starting criteria? If not, what is the minimum information the AI would need to be "seeded" with in order to learn to ...
4
votes
0answers
2k views

Is this a good way to represent Connect 4 to a Neural Network?

I'm attempting to make a bot for the Connect 4 competition on http://riddles.io My bot isn't horrible, like it's getting up the ladder, but it cannot compete with the winning bots. I'm using a ...
2
votes
2answers
410 views

Evaluation Function for a Go like game

I am trying to find a good evaluation function for a game with: A 7x7 tile board 2 players, given equal number(>=3 currently undetermined) of stones placed randomly on the tiles A turn is consisted ...
9
votes
1answer
1k views

A few doubts regarding the application of reinforcement learning to games like chess

I invented a chess-like board game. I built an engine so that it can play autonomously. The engine is basically a decision tree. It's composed by: A search function that at each node finds all ...
1
vote
2answers
106 views

Trading off “Memory” vs “Optimization”

I've been researching the following topic. Or rather, I would like to but I can't find anything because I'm not sure what to look for. I am interested weather there are some concepts or models that ...
4
votes
2answers
184 views

Determinization step in Information Set Monte Carlo Tree Search

After reading this paper about Monte Carlo methods for imperfect information games with elements of uncertainty, I couldn't understand the application of determinization step in author's ...
19
votes
4answers
5k views

How to handle invalid moves in reinforcement learning?

I want to create an AI which can play five-in-a-row/gomoku. As I mentioned in the title, I want to use reinforcement learning for this. I use policy gradient method, namely REINFORCE, with baseline. ...