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 ...
- 9,342
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, ...
- 9,342
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 ...
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 ...
- 6,235
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 ...
- 6,235
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 ...
- 3,847
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 (...
- 10.4k
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 ...
- 5,397
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'...
- 136
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
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 ...
- 10.4k
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 ...
- 9,342
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 ...
- 32.9k
8
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 ...
- 32.9k
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 ...
- 10.4k
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/...
- 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 ...
- 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 ...
- 32.9k
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 ...
- 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 ...
- 823
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 ...
- 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 ...
- 4,272
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 ...
- 603
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 ...
- 10.4k
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, ...
- 10.4k
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 ...
- 9,342
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 ...
- 7,513
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 ...
- 149
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 ...
- 151
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 ...
- 151
Only top scored, non community-wiki answers of a minimum length are eligible