# 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 ...

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

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, you won't need to search at all. This is not just an academic idea though! It's actually fairly widely used, and has been key to solving several games. The ...

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

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 ...

3

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 also the speed with which it can traverse the tree, is extremely important for the algorithm's performance. Therefore, when evaluating how good or bad a ...

3

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 play combinatorial games. (Even in iterated dilemmas, it doesn't really branch because it's simultaneous, more of a vine than a tree. Decisionmaking would be ...

3

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 this page). Then I'd look into things like the Killer Move Heuristic, and maybe also see if you can simply implement existing parts of your engine more ...

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

-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: ...

2

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 games studied, where game states and token values cannot be precisely quantified? I think the short answer is yes. The real issue is in the last part: ...

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

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 you could somehow create that function, it would make a search with alpha-beta pruning redundant. In practice, evaluation functions for complex environments are ...

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 ...

1

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 the opponent can make a king next move When the current player can make a king next move When the only legal moves left will lead to capture the turn after for ...

1

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. (Branch C from the root.) In the left branch (A) of the root Helen will get 2 or more. In the middle branch (B) from the root after going down the left, Stavros ...

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

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 to get data to train network and network used for tree leafs evaluation (instead of rollout as in classical MCTS). It's possible to combine selection-expansion ...

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

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.youtube.com/watch?v=STjW3eH0Cik&index=6&list=PLUl4u3cNGP63gFHB6xb-kVBiQHYe_4hSi

1

Try cache or transposition table. Without it, your search tree might explode.

1

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 algorithm but it increases the space complexity. I am linking the wiki to it https://en.wikipedia.org/wiki/SSS* I will update the answer as soon as i get a ...

1

Based on your description, I'd maximize the following terms: i -max(f - 10 - (MAX_FIELD_INDEX - i), 0) - assuming consumption of one fuel per field; this becomes negative when you have too much fuel a similar function of p, as spending them gets more important when approaching the goal As having fuel is probably a good thing in the beginning, you could use ...

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