# Tag Info

20

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 should prefer to use some form of heuristic guided search if you can come up with a useful heuristic. Coming up with a useful heuristic usually requires a lot of ...

8

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 minimax algorithm. Given this context, I would recommend starting out with Minimax. Of the three algorithms, Minimax is the easiest to understand. Alpha-Beta, ...

7

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 large, but you can get a decent AI from minimax, game tree pruning, and a good heuristic function (that includes counting half and full 2s,3s,4s,...etc.) as ...

7

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 this is a way to establish better heuristics. My intuition tells me that this is way harder and far more complex. It's not actually that much more complex ...

5

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 state for the current player, that is max or min. So, alpha-beta is a better implementation of minimax. Here are the time complexities of both algorithms ...

4

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? The answer depends on what your goal is. If your goal is to make an interactive agent that will play the game against you, then you are correct: there's no need ...

4

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 (basically would have to know every single tiny detail of your implementation to be able to reproduce). Some things to consider: The size of your transposition table ...

4

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 called Expectiminimax, see https://en.wikipedia.org/wiki/Expectiminimax_tree. At that circles you have to multiply the possibilities on the edges below that ...

3

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-winning moves that help to prune some branches quickly. I've never implemented any Alpha-Beta agents for Gomoku specifically, but I can provide some numbers for our ...

3

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 Search and Minimax Hybrids with Heuristic Evaluation Functions The basic intuition behind such combinations tends to be to use small minimax-like searches inside a ...

3

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 memory rather than working with what's still in the CPU's caches, etc.). Breadth-First Search needs memory to remember "where it was" in all the different ...

3

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 category. For example, you have negamax algorithm which is in a sense the same thing the Monte Carlo Search Tree is to Monte Carlo. Min-max category is game theory ...

2

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 it immediately finds a score of 10 directly to the left of the root node, it can not prune yet, because... maybe there's a score of 20 somewhere else in the ...

2

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 values: A range of values centered around 0 denote estimated values (e.g. -999 to 999). A value less than the smallest heuristic value denotes a loss for max (e....

2

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 +1 without any hint how to progress towards checkmate. In a chess variant without the fifty-move limit, it could play useless turns forever. I guess, this is a rather theoretical ...

2

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 to order the actions from the best to the worst depending on max or min point of view, so the algorithm can quickly realize if the exploration is necessary.

2

I suspect that you'll have to remove this code: if (field.isWinningMove(movePlayed, C4Symbol.BLUE)) { field.playMove(movePlayed, C4Symbol.RED); return new NextMove(BLUE_WIN, movePlayed); } from the max() method, and remove this code: if (field.isWinningMove(movePlayed, C4Symbol.RED)) { field.playMove(movePlayed, ...

2

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 to help grasp the concept. Proving it would be a matter of going through the regular methods of a mathematical proof and would probably be a bit complicated. ...

2

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 already give you some bounds on the game-theoretic value that the player to play in the root node (let's say, the max player) can guarantee by moving into that part ...

2

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 not need to be 100% accurate or complete. It could even be a learned model. However, in the case of applying minimax to classic two player games, such as chess or ...

2

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. It can make meaningful evaluations just from random playouts that reach terminal game states where you can use the loss/draw/win outcome. So if you're faced ...

1

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 sum of the successors, so the probabilities associated with chance nodes must be known. Given that expectiminimax assumes the existence of random events (...

1

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: $$UCT(v_i,v) = \frac{Q(v_i)}{N(v_i)} + cP(v_i, v)\sqrt{\frac{N(v)}{1+N(v_i)}}$$ where P(vi,v) is prior probability of the move (...

1

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 less and less, especially when there's only a few pieces left and quite a bit of "chasing" must occur before a piece is taken, likely more chasing then a depth ...

1

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 useful for domains where you are concerned about an adversary. In finding a customer model, there is no reason to worry about someone coming in and forcing you to ...

1

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 search function and would encourage the continued search of high probability moves that were then simulated by the same NN that now contained the Value Net. The ...

1

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): int Quiesce( int alpha, int beta ) { int stand_pat = Evaluate(); if( stand_pat >= beta ) return beta; if( alpha < stand_pat ) alpha = ...

1

-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 really causes the size of your legal action set to blow up. You have a combinatorial action space here. If each of your pieces has 8 legal moves, then that is: ...

1

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 the Alpha-Beta pruning algorithm. For example, Iterative Deepening is almost the same as Alpha-Beta pruning, but automatically keeps repeating the algorithm ...

1

I believe maximax is what you're looking for: Maximax (economics, computer science, decision theory) A strategy or algorithm that seeks to maximize the maximum possible result (that is, that prefers the alternative with the chance of the best possible outcome, even if its expected outcome and its worst possible outcome are worse than other alternatives); ...

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