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

25 questions
Filter by
Sorted by
Tagged with
2k views

### How to represent Tic-Tac-Toe vs Checkers or Chess for a Neural Network

I've been reading a lot about TD-Gammon recently as I'm exploring options for AI in a video-game I'm making. The video game is a turn-based positional sort of game, i.e. a "units", or game piece's, ...
2k 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 ...
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 to alpha-beta alone. I have ...
337 views

### In this implementation of the Information Set Monte Carlo Tree Search, why can't the players see the cards of each other?

After reading this paper about Monte Carlo methods for imperfect information games with elements of uncertainty, I couldn't understand the application of the determinization step in the author's ...
655 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 ...
556 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 ...
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 ...
1k 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 ...
453 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 ...
123 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 ...
357 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 ...
83 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: ...
82 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 ...
186 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, ...
135 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 ...
110 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 ...
510 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' ...
186 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 ...
928 views

### How to design a good 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 an equal number(>=3 currently undetermined) of stones placed randomly on the tiles A turn is ...
20 views

### What are some strong algorithms for Perfect Information, Deterministic Multiplayer Games?

I have a series of games with the following properties: 3 or more players, but purely non-cooperative (i.e., no coalition forming); sequential moves; perfect information; deterministic state ...
109 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?
51 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-...
831 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 ...