Hot answers tagged

21 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 ...
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, ...
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 ...
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 ...
user avatar
  • 6,067
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 ...
user avatar
  • 6,067
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 ...
user avatar
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 ...
user avatar
  • 5,062
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'...
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 ...
user avatar
  • 164
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 ...
user avatar
9 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 (...
user avatar
  • 9,379
8 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 ...
user avatar
  • 9,379
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 ...
user avatar
  • 9,379
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/...
user avatar
  • 361
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 ...
user avatar
  • 181
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 ...
user avatar
  • 1,390
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 ...
user avatar
  • 779
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 ...
user avatar
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 ...
user avatar
  • 288
6 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 ...
user avatar
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 ...
user avatar
  • 583
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 ...
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 ...
user avatar
  • 151
5 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 ...
user avatar
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 ...
user avatar
5 votes

What are examples of simple problems and applications that can be solved with AI techniques?

This is fairly boilerplate advice, but, since you're brand new to AI, I'd personally suggest writing a classical Tic-Tac-Toe AI, ideally using minimax. I suggest this because minimax is fundamental ...
user avatar
  • 6,067
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 ...
user avatar
  • 9,379
5 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, ...
user avatar
  • 9,379
5 votes

Examples of single player games that use modern ML techniques in the AI?

There is Google Research Football, which is an open-source platform to develop reinforcement learning algorithms to play a game similar to FIFA or PES, although the football simulation is not as ...
user avatar
  • 33.8k
5 votes
Accepted

How is the AI in 3d games implemented?

Overlap between AI and "Game AI" Nowadays, if you search for AI online, you will find a lot of material about machine learning, natural language processing, intelligent agents and neural ...
user avatar

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