# 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.)*

24 questions
Filter by
Sorted by
Tagged with
20 views

### Hierarchical reinforcement learning for combinatorial complexity

I want to try a hierarchical reinforcement learning (HRL) approach to hard logical problems with combinatorial complexity, i.e. games like chess or Rubik's cube. The majority of HRL papers I have ...
465 views

### Why isn't my Q-Learning agent able to play tic-tac-toe?

I tried to build a 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' ...
288 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 ...
27 views

### Are there any python implementations of GGP games or how to use game logic written in GDL in python?

I'm writing a General Game Playing (GGP) AI in python. I'd like to test it on some GGP games. So are there any python implementations of GGP games? I found in http://games.ggp.org/base games written ...
76 views

### q learning appears to converge but does not always win against random tic tac toe player

q learning is defined as: Here is my implementation of q learning of the tic tac toe problem: ...
77 views

### Can an artificial intelligence be unbeatable at simple games?

There are (two-players, perfect information) combinatorial games for which, at any configuration of the game, a winning move (if there is one) can be quickly computed by a short program. This is the ...
3k 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 ...
1k views

### How do I create an AI for a two-players board game?

Goal 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 final ...
687 views

### How to calculate the optimal placements for settlements in Catan without an ML algorithm?

Is it possible to calculate the best possible placements for settlements in Catan without using an ML algorithm? While it is trivial to simply add up the numbers surrounding the settlement (highest ...
316 views

### How can a neural network learn to play sudoku?

I'm just beginning to understand neural networks and I've performed a couple of successful tests with numerical series where the NN was trained to find the odd one or a missing value. It all works ...
91 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?
112 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 ...
182 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 ...
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 ...
119 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 ...
628 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 ...
336 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 ...
164 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, ...
558 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 ...
466 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 ...
850 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 ...
49 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-...