Skip to main content
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 ...
WorldWind's user avatar
  • 164
6 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 ...
Dennis Soemers's user avatar
  • 10.3k
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 ...
Dennis Soemers's user avatar
  • 10.3k
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 ...
thecomplexitytheorist's user avatar
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 ...
Dennis Soemers's user avatar
  • 10.3k
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 ...
John Doucette's user avatar
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 ...
rts's user avatar
  • 31
3 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}$ ...
Dennis Soemers's user avatar
  • 10.3k
2 votes
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 ...
chessprogrammer's user avatar
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 ...
mico's user avatar
  • 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 ...
DukeZhou's user avatar
  • 6,237
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 ...
Adrien Forbu's user avatar
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 ...
DukeZhou's user avatar
  • 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 ...
SmallChess's user avatar
  • 1,411
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 ...
SmallChess's user avatar
  • 1,411
2 votes
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 ...
Eric Platon's user avatar
  • 1,510
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 ...
John Doucette's user avatar
1 vote

What else can boost iterative deepening with alpha-beta pruning?

Try cache or transposition table. Without it, your search tree might explode.
SmallChess's user avatar
  • 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 ...
hermes's user avatar
  • 11
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 ...
Seth Simba's user avatar
  • 1,186
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 ...
Azad İrven's user avatar
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 ...
mirror2image's user avatar
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 ...
John Doucette's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible