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
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,429
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
  • 809
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
  • 24.5k
6 votes
Accepted

Should I use minimax or alpha-beta pruning?

Both algorithms should give the same answer. However, their main difference is that alpha-beta does not explore all paths, like minimax does, but prunes those that are guaranteed not to be an optimal ...
user avatar
  • 889
4 votes

If certain moves are compulsory, will there still be a need for a quiescence search?

I understand your question to be: If some moves are compulsory, and my agent has no choice about which move to make next, do I need to perform a search, or can I just return the compulsory move? ...
user avatar
4 votes
Accepted

Transposition table is only used for roughly 17% of the nodes - is this expected?

I don't think that's necessarily a strange number. It's impossible for anyone to really tell you whether that 17% is "correct" or not without reproducing it, which would require much more info (...
user avatar
  • 9,429
4 votes
Accepted

What is the variant of the minimax tree with 3 types of nodes called?

The triangles pointing up are Max' nodes. We assume it starts. Then follows a random choice of moves at the circles, for instance, with a die. The triangles pointing down are from Min. This variant is ...
user avatar
  • 318
4 votes
Accepted

Any interesting ways to combine Monte Carlo tree search with the minimax algorithm?

There has indeed been some research towards combining MCTS and minimax-like algorithms. For example, the following two publications: Monte-Carlo Tree Search and minimax hybrids Monte-Carlo Tree ...
user avatar
  • 9,429
3 votes

Is there a way of representing the minimax algorithm mathematically?

A simple google search gives plenty of results. If you have a look at the entry in wikipedia for Minimax it has mathematical representations as well as some basic pseudocode and tree representations ...
user avatar
3 votes
Accepted

Why does the adversarial search minimax algorithm use Depth-First Search (DFS) instead of Breadth-First Search (BFS)?

The primary reason is that Breadth-First Search requires much more memory (and this probably also makes it a little bit slower in practice, due to time required to allocate memory, jumping around in ...
user avatar
  • 9,429
3 votes
Accepted

Could you share with me the tree size, search time and search depth of your implementation of Gomoku with minimax and alpha-beta prunning?

Intuitively I kind of doubt expecting a search depth of 10 in half a second is reasonable, especially for the initial game state where there's a rather large branching factor and no immediately-...
user avatar
  • 9,429
3 votes
Accepted

How to make minimax optimal?

Minimax deals with two kinds of values: Estimated values determined by a heuristic function. Actual values determined by a terminal state. Commonly, we use the following denotational semantics for ...
user avatar
3 votes

When should Monte Carlo Tree search be chosen over MiniMax?

Some basic advantages of MCTS over Minimax (and its many extensions, like Alpha-Beta pruning and all the other extensions over that) are: MCTS does not need a heuristic evaluation function for states....
user avatar
  • 9,429
3 votes

In what RL algorithm category is MiniMax?

I think you are looking at it from the wrong direction, min-max is just a planning algorithm, decision strategy, in the sense that you are describing other algorithms/methods it does not have a ...
user avatar
  • 77
2 votes

Game AI evaluation function and making progress towards winning

What I'm missing here is a way to direct the evaluation function to actually winning. For example, a perfect evaluation function for a won position in chess would always return ...
user avatar
  • 9,429
2 votes
Accepted

Can I prune the tree if alpha-beta pruning finds 10 to the left of the root node?

The vanilla Alpha-Beta Pruning algorithm as it has been taught to you in class does not assume any domain knowledge / knowledge about the game / knowledge about the tree it is searching. Therefore, if ...
user avatar
  • 9,429
2 votes

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

If you have to choose between minimax and alpha-beta pruning, you should choose alpha-beta. It is more efficient and fast because it can prune a substantial part of your exploration tree. But you need ...
user avatar
2 votes
Accepted

Connect 4 minimax does not make the best move

I suspect that you'll have to remove this code: ...
user avatar
  • 9,429
2 votes

Is it feasible to use minimax to solve a board game with a large number of moves?

-The player can choose as many pieces to move as he likes. For example none, all of them, or some number inbetween. (Whereas in chess you can only move one) That quote specifically is the part that ...
user avatar
  • 9,429
2 votes

Can someone help me to understand the alpha-beta pruning algorithm?

Suppose that you have already search a part of the complete search tree, for example the complete left half. This may not yet give you the true game-theoretic value for the root node, but it can ...
user avatar
  • 9,429
2 votes
Accepted

Is the minimax algorithm model-based?

Minimax is a planning algorithm, and all planning algorithms need access to a model of the environment in order to look ahead or simulate possible future states and results. Technically this does ...
user avatar
  • 24.5k
1 vote
Accepted

Is there a probabilistic version of minimax?

Yes, there is at least one probabilistic version of minimax, which is called expectiminimax. In expectiminimax, in addition to min and max nodes, there are also chance nodes, which perform a weighted ...
user avatar
  • 34.4k
1 vote

To deal with infinite loops, should I do a deeper search of the best moves with the same value, in alpha-beta pruning?

I think this issue stems from the fact you aren't taking position into account. I would think this because as the game progresses, the number of moves that will result in a piece being taken becomes ...
user avatar
  • 1,246
1 vote
Accepted

Can alpha-beta pruning be used for applications apart from games?

Thinking about this more, the answer is in fact yes, but not for the application you mention. You cannot use alpha-beta pruning to learn a model to predict customer outcomes, because it is only ...
user avatar
1 vote

Minimax combined with machine learning to determine if a path should be explored

The use of of a neural network to push the search algorithm to continually only along a promising path is the same that was described in the AlphaZero paper. In AlphaZero, the NN loop contained the ...
user avatar
1 vote
Accepted

Does quiescence search even improve the minimax algorithm?

Your logic is flawed because you negated "stand-pat" (i.e. do nothing) and alpha-beta. Let's take a look at the pseudocode (https://www.chessprogramming.org/Quiescence_Search#Pseudo_Code): ...
user avatar
  • 1,390
1 vote
Accepted

Why do neural nets and machine learning tend to work well with MCTS, but not with regular Minimax game-playing AI?

It just does. Take a look at this post explaining how MCTS works. In both Alpha Go Lee and Alpha Zero the tree traversal follows the nodes that maximize the following UCT variant: \begin{...
user avatar
1 vote
Accepted

Are iterative deepening, principal variation search or quiescence search extensions of alpha-beta pruning?

Are these algorithms an extension of the alpha-beta algorithm, or Are they completely new algorithms, in that they have got nothing to do the alpha-beta algorithm? Most of them are extensions of ...
user avatar
  • 9,429
1 vote

If we model the game "2048" using a max-min game tree, what is the maximal path from a start state to a terminal state?

To model 2048 (or any problem) for search, you need a only a few pieces of information. Note first though, that 2048 is not suitable for minimax, because there's only one player! Instead, you can ...
user avatar

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