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,369
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
  • 749
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

Is a good evaluation function as good as any of the extensions of alpha-beta pruning?

To build on Neil's answer a bit, you're right that the better your evaluation function gets, the less work your optimization function will need to perform. If your evaluation function gets good enough,...
user avatar
3 votes
Accepted

More effective way to improve the heuristics of an AI... evolution or testing between thousands of pre-determined sets of heuristics?

Hmmm, I see some issues that are actually present in both of the approaches you propose. It is important to note that the depth level that your Minimax search process manages to reach, and therefore ...
user avatar
  • 9,369
3 votes

Alpha beta pruning - rules for updating alpha/beta value

First, allow me to draw it for better visualization: ...
user avatar
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,369
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,369
3 votes

Can Alpha–Beta be used on symmetric zero sum games?

If the game is not sequential, there would be no game tree and no need for pruning. Alpha-beta is a technique applied to look-ahead search. Alpha-beta has demonstrated utility in algorithms that ...
user avatar
  • 6,067
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 ...
user avatar
  • 9,369
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

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,369
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 ...
user avatar
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,369
2 votes

Is a good evaluation function as good as any of the extensions of alpha-beta pruning?

A perfect evaluation function would mean that you only had to do a local search - i.e. maximise over next set of decisions - in order for an agent to behave optimally in an environment. As such if ...
user avatar
  • 23.8k
2 votes

Combining deep reinforcement learning with alpha-beta pruning

Yes it's possible to to combine AlphaZero with Minimax methods (including alpha-beta pruning). AlphaZero itself is combination of Monte Carlo Tree Search (MCTS) and Deep Network, where MCTS is used ...
user avatar
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,369
1 vote

Does the alpha/beta value of parent nodes change if the alpha beta value of the child node changes?

I couldn't understand your question clearly, however, it think you are making a slim mistake. let's look at the flowing code from "Russell " and do pruning step by step: Assume your are In ...
user avatar
  • 49
1 vote

What is a good way of identifying volatile positions for a checkers game?

When combatting the horizon affect, you want to consider any short term actions that will greatly affect your position evaluation. Thus, in addition to captures, you will also want to include: When ...
user avatar
1 vote

Why is it possible to eliminate this branch with alpha-beta pruning?

You can't prune the nodes that are cross out if we search from left-to-right in the tree using alpha-beta pruning. To do this analysis we can pretend the right branch of the tree doesn't exist. (...
user avatar
  • 361
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,344
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

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,369
1 vote

How do I use a genetic algorithm to generate the scores of an evaluation function for alpha-beta pruning?

Is this a viable replacement to the Fitness function? Sure, the fitness is 1 for the winner and 0 for the loser. You're using some kind of the Tournament selection. It might be better to use more ...
user avatar
1 vote

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

http://inst.eecs.berkeley.edu/~cs61b/fa14/ta-materials/apps/ab_tree_practice/ you can make practice for better understanding the topic. And i also recommend this lecture from MIT https://www....
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.
user avatar
  • 1,380
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 ...
user avatar
  • 11

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