Skip to main content
Share Your Experience: Take the 2024 Developer Survey
23 votes
Accepted

How do I choose the best algorithm for a board game like checkers?

tl;dr: None of these algorithms are practical for modern work, but they are good places to start pedagogically. You should always prefer to use Alpha-Beta pruning over bare minimax search. You ...
John Doucette's user avatar
16 votes

How do I keep track of already visited states in breadth-first search?

Dennis Soemers' answer is correct: you should use a HashSet or a similar structure to keep track of visited states in BFS Graph Search. However, it doesn't quite answer your question. You're right, ...
John Doucette's user avatar
15 votes
Accepted

How does "Monte-Carlo search" work?

Monte Carlo method is an approach where you generate a large number of random values or simulations and form some sort of conlusions based on the general patterns, such as the means and variances. As ...
Disenchanted Lurker's user avatar
14 votes
Accepted

Is AlphaZero an example of an AGI?

Good question! AlphaZero, though a major milestone, is most definitely not an AGI :) AlphaGo, though strong at the game of Go, is narrowly strong ("strong-narrow AI"), defined as strength in a ...
DukeZhou's user avatar
  • 6,237
10 votes

How to train a neural network for a round based board game?

Great question! NN is very promising for this type of problem: Giraffe Chess. Lai's accomplishment was considered to be a pretty big deal, but unfortunately came just a few months before AlphaGo ...
DukeZhou's user avatar
  • 6,237
10 votes
Accepted

Is the new AlphaGo implementation using Generative Adversarial Networks?

No, GANs are not used. It's reinforcement learning at what it does best. The tree search is an interesting addition and assists with navigating the sheer scale of the game. Although the agent was ...
Jaden Travnik's user avatar
10 votes

Does Monte Carlo tree search qualify as machine learning?

John's answer is correct in that MCTS is traditionally not viewed as a Machine Learning approach, but as a tree search algorithm, and that AlphaZero combines this with Machine Learning techniques (...
Dennis Soemers's user avatar
  • 10.3k
10 votes

What are examples of approaches to create an AI for a fighting robot in an MMO game?

I would set up a list of goals for your bot. These could be 'maintain a minimum level of health', 'knock out human player', 'block way to location X', etc. This obviously depends on the domain of your ...
Oliver Mason's user avatar
  • 5,387
9 votes
Accepted

How much memory does the Deepstack poker program require?

A DeepStack-style algorithm only requires that you have a way of approximating equilibrium counterfactual values for subtrees at the leaves of lookahead trees from each of its decision points. So if I'...
Dustin Morrill's user avatar
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
9 votes

How do I choose the best algorithm for a board game like checkers?

So far, I have considered only three algorithms, namely, minimax, alpha-beta pruning, and Monte Carlo tree search (MCTS). Apparently, both the alpha-beta pruning and MCTS are extensions of the basic ...
Dennis Soemers's user avatar
  • 10.3k
9 votes
Accepted

Does Monte Carlo tree search qualify as machine learning?

Monte Carlo Tree Search is not usually thought of as a machine learning technique, but as a search technique. There are parallels (MCTS does try to learn general patterns from data, in a sense, but ...
John Doucette's user avatar
8 votes
Accepted

How could I use reinforcement learning to solve a chess-like board game?

I would like to use reinforcement learning to make the engine improve by playing against itself. I have been reading about the topic but I am still quite confused. Be warned: Reinforcement learning ...
Neil Slater's user avatar
  • 32.4k
8 votes
Accepted

How do I keep track of already visited states in breadth-first search?

You can use a set (in the mathematical sense of the word, i.e. a collection that cannot contain duplicates) to store states that you have already seen. The ...
Dennis Soemers's user avatar
  • 10.3k
8 votes

How do I keep track of already visited states in breadth-first search?

While the answers given are generally true, a BFS in the 15-puzzle is not only quite feasible, it was done in 2005! The paper that describes the approach can be found here: http://www.aaai.org/Papers/...
Nathan S.'s user avatar
  • 371
8 votes

What are examples of approaches to create an AI for a fighting robot in an MMO game?

Oliver Mason's answer is great for specific methods and tools to use, but I wanted to pull out a more general principle which was mentioned in a comment. The distinction your friend is making is not ...
IMSoP's user avatar
  • 181
8 votes
Accepted

Neural network for game

Neural networks do not directly take actions in games. Instead, some code needs to supply the current state of the game to the neural network, interpret its output and take the action. Typically yet ...
Neil Slater's user avatar
  • 32.4k
7 votes

How to train a neural network for a round based board game?

I'm a chess player and my answer will be only on chess. Training a neural network with reinforcement learning isn't new, it has been done many times in the literature. I'll briefly explain the common ...
SmallChess's user avatar
  • 1,411
7 votes
Accepted

Should I use neural networks or genetic algorithms to solve Gomoku?

For Gomoku, it seems a bit of an overkill to use neural networks or the genetic algorithm as both take a while, and more often than not, don't go how you want it to. The Gomoku game tree is rather ...
sma's user avatar
  • 823
7 votes
Accepted

Why most imperfect information games usually use non machine learning AI?

A heuristic search using MCTS + minimax + alphabeta pruning is a highly efficient AI planning process. What the AI techniques of reinforcement learning (RL) plus neural networks (NNs) typically add to ...
Neil Slater's user avatar
  • 32.4k
7 votes
Accepted

Can this tic tac toe program be considered AI?

This is basically reinforcement learning. The state space contains your moves, and the value function are the value you store at the end. And your rewards are the end results. And you have episodic ...
drerD's user avatar
  • 298
6 votes
Accepted

Why did AlphaGo lose its Go game?

We know what Lee's strategy was during the game, and it seems like the sort of thing that should work. Here's an article explaining it. Short version: yes, we know what went wrong, but probably not ...
Matthew Gray's user avatar
  • 4,262
6 votes
Accepted

How can I apply reinforcement learning to solve this asteroid game?

A closely related question and a minimal implementation written in Python. That program implements the reinforcement learning technique 'Q-Learning'. The idea is for the program to take in an ...
DrMcCleod's user avatar
  • 603
6 votes
Accepted

Can genetic algorithms be used to learn to play multiple games of the same type?

Genetic algorithms and Neural Networks both are "general" methods, in the sense that they are not "domain-specific", they do not rely specifically on any domain knowledge of the game of Mario. So yes, ...
Dennis Soemers's user avatar
  • 10.3k
6 votes

Why didn't champion of the Go game manage to win the last game against AlphaGo, after winning the 4th one?

The technique used by AlphaGo is "Monte Carlo Tree Search", combined with a very well trained neural network. The network's job is to estimate the quality of different board states and moves. This ...
John Doucette's user avatar
5 votes

How can I design and train a neural network to play a card game (similar to Magic: The Gathering)?

Yes. It is feasible. Overview of the Question The design goal of the system seems to be gain a winning strategic advantage by employing one or more artificial networks in conjunction with a card ...
Douglas Daseeco's user avatar
5 votes

What's the difference between Starcraft and Dota from an AI perspective?

Those AI-learning programs may have very similar scheme. We are changing only inputs and possible actions (like "use skill" or "move here"). Starcraft AI must do a lot of actions and control many ...
Adrian Grygutis's user avatar
5 votes

How can I design and train a neural network to play a card game (similar to Magic: The Gathering)?

I think you raise a good question, especially WRT to how the NNs inputs & outputs are mapped onto the mechanics of a card game like MtG where the available actions vary greatly with context. I ...
Ben Hutchison's user avatar
5 votes

How can you represent the state and action spaces for a card game in the case of a variable number of cards and actions?

Instead of having the AI learn what action to take, you can alternatively train it to judge how "good" a position is. In order to determine what move to make, you don't ask the AI "This is the current ...
user12889's user avatar
  • 151
5 votes
Accepted

What is the typical AI approach for solving blackjack?

Blackjack is usually modelled using Monte Carlo (MC) Methods. There is a lot of literature on MC methods which is interesting on its own right but here is a paper describing how MC is applied to ...
Jaden Travnik's user avatar

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