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
8
votes
3answers
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, ...
7
votes
2answers
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 ...
6
votes
4answers
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 ...
6
votes
2answers
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 ...
4
votes
1answer
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 ...
4
votes
1answer
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 ...
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 ...
3
votes
3answers
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 ...
3
votes
2answers
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 ...
3
votes
1answer
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 ...
3
votes
0answers
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 ...
2
votes
1answer
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: ...
2
votes
1answer
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 ...
2
votes
1answer
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, ...
2
votes
1answer
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 ...
1
vote
2answers
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 ...
1
vote
1answer
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' ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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?
1
vote
0answers
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-...
0
votes
5answers
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 ...
0
votes
0answers
24 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 ...
0
votes
0answers
34 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 ...