9
votes
How do I create an AI for a two-players board game?
Assuming it is a turn-based game and, for each turn, there's an optimal choice that will lead to the winning state (zero-sum), you can basically simplify the question to "What is the optimal sequences ...
- 164
5
votes
Accepted
q learning appears to converge but does not always win against random tic tac toe player
The primary issue I see is that in the loop through time steps t in every training episode, you select actions for both players (who should have opposing goals to ...
- 9,944
5
votes
Which algorithms can we use on games with high branching factors (e.g. Connect6)?
Typically, Monte-Carlo Tree Search (MCTS) actually is the go-to "solution" for such problems with large branching factors. I can understand that "vanilla" MCTS may still have unsatisfactory ...
- 9,944
3
votes
How to calculate the optimal placements for settlements in Catan without an ML algorithm?
Catan is actually a much more complicated game than the simple rules would suggest, and an exact solution is probably beyond the scope of current AI techniques.
Monte Carlo Tree Search or ...
- 9,147
3
votes
How do I solve the problem of positioning 11 pieces into a 8x8 puzzle?
Using your app, I was able to find a (spoiler alert!) solution manually. At least now you know your puzzle is solvable and you did not waste your money :)
It seems your app has a bug, though. I was ...
- 31
3
votes
Accepted
How can a neural network learn to play sudoku?
I think it is the wrong way to frame sudoku as a regression problem in neural networks.
Firstly, you have to understand what regression is. "Regression" is when you predict a value given certain ...
3
votes
What else can boost iterative deepening with alpha-beta pruning?
First thing you're going to want to add is probably a Transposition Table, as also suggested by SmallChess.
Afterwards, I'd look into Aspiration Search and/or Principal Variation Search (also see ...
- 9,944
2
votes
Accepted
Trading off "Memory" vs "Optimization"
The The Oxford Companion to Chess has entries on only 700 named openings, and lists another 1327 opening variations in the index, and I wouldn't be surprised if someone out there had them all ...
- 6,237
2
votes
Trading off "Memory" vs "Optimization"
If you can remember everything and there's no randomisation in your outcome like chess, there is absolutely no reason not to do that. Anybody who can remember all the possible board configurations in ...
- 1,411
2
votes
Accepted
Why isn't my Q-Learning agent able to play tic-tac-toe?
The $Q$-learning rule that you have implemented updates $Q(S_t, A_t)$ estimates as follows, after executing an action $A_t$ in a state $S_t$, observing a reward $R_t$, and reaching a state $S_{t+1}$ ...
- 9,944
2
votes
Historical weakness of GOFAI in relation to partisan combinatorial games?
Nice question!
I think there are a couple of issues at work here.
Is the historical weakness of GOFAI in relation to non-trivial
combinatorial games partly a function of the structure of the ...
- 9,147
2
votes
How can a neural network learn to play sudoku?
You can take a look at this paper that solving your problem with a neural network. You can use the pytorch implementation of the satnet layer : satnet layer API. In this supervised setup the layer ...
- 251
2
votes
Can an AI learn how to play chess without instructions?
It's possible for an AI to learn chess without even knowing how to move the pieces. Google's AlphaZero didn't do that as their programmers coded the chess rules, but it's possible.
One can learn the ...
- 1,411
2
votes
Can an artificial intelligence be unbeatable at simple games?
There is actually a github project about 'solving' Nim that implements certain type of Q-learning reinforcement algorithm (described in undergraduate thesis of Erik ...
- 927
2
votes
How to calculate the optimal placements for settlements in Catan without an ML algorithm?
Historically, the non-ML approach would be an expert system. This is typically a rules-based decision system, falling under the umbrella of symbolic AI.
These systems can have strong utility in ...
- 6,237
1
vote
Accepted
What is the significance of move 37? (to a non go player)
The significance can be mostly summed up as changing the perspective of people on how creativity can be produced by a computer.
There is a widespread belief, which has been largely true until ...
- 2,225
1
vote
How to design a good evaluation function for a go-like game?
If you have the best combination of distance between the stones, you should choose the best move to win. In this case, you have to be close to where your opponent plays. It is best to do this by ...
- 21
1
vote
What else can boost iterative deepening with alpha-beta pruning?
Try cache or transposition table. Without it, your search tree might explode.
- 1,411
1
vote
What else can boost iterative deepening with alpha-beta pruning?
To make boost iterative deepening with alpha-beta pruning you can use the
SSS* Search algorithm, its a best first strategy algorithm. The SSS* Algorithm can improve the time efficiency of the overall ...
- 11
1
vote
Accepted
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?
The core of the question seems to really be: "how to approach thinking about this", where "this" is the input of an AI player.
Modern attempts at game playing AI players try to replace a human player ...
- 1,490
1
vote
How do I create an AI for a two-players board game?
To make an AI opponent, you'll need to create a sub-routine that considers the current state of the board and chooses a move, just like the player would.
Now, how does this subroutine choose what ...
- 1,176
1
vote
In this implementation of the Information Set Monte Carlo Tree Search, why can't the players see the cards of each other?
MCTS only need to "see" states in respect of reward. All game mechanics is abstarcted away from MCTS and MCTS only access actions and rewards. MCTS player don't access states itself, it's only choose ...
- 695
1
vote
In this implementation of the Information Set Monte Carlo Tree Search, why can't the players see the cards of each other?
All the methods in the GameState class that is used to represent state, are stubs, and without these, the MCTS algorithm won't do anything at all. In particular, the DoMove method just changes who's ...
- 9,147
Only top scored, non community-wiki answers of a minimum length are eligible