Questions tagged [alpha-beta-pruning]
For questions involving the Alpha-Beta pruning algorithm.
40
questions
0
votes
0
answers
98
views
How do derive the time complexity of alpha beta pruning
I think I understand how the time complexity of minimax was derived, I believe it is basically the same as the uniformed Breadth- first search algorithm which is:
In terms of time and space, imagine ...
- 1
0
votes
1
answer
121
views
Would the node with value 5 in this tree be pruned if doing left-to-right alpha-beta pruning?
I'm trying to understand if the node with value 5 would be pruned if doing left-to-right alpha-beta pruning in a minimax game. I can see two interpretations:
Initialize $\alpha = -\infty$ and $\beta =...
- 3
1
vote
1
answer
915
views
The reason behind using MCTS over Alpha Beta Pruning in Alphazero
I am not really satisfied with the available analysis of why AlphaZero uses MCTS instead of Alpha Beta search.
Some analysis claim that its because MCTS is a lot more humanlike. I disagree because I ...
- 113
0
votes
0
answers
341
views
Utility function vs evaluation function vs heuristic function in terms of minmax + alphabeta
So i am trying to grasp the difference between a utility function, an evaluation function and an heuristic function in terms of the minmax algorithm with alphabeta on top.
So far my understanding is ...
- 11
1
vote
0
answers
128
views
Is there a benefit to starting with MCTS and switching to minimax as the branching factor decreases?
I've invented a deterministic, perfect-information game with a fairly large branching factor (~150) which tapers out dramatically after the midgame (~30 at worst). I need a strong AI. My understanding ...
- 111
2
votes
1
answer
826
views
Should minimax with alpha beta pruning depth be an odd number?
I implemented the minimax algorithm with alpha-beta pruning to see how it works, with application to the connect four game.
My AI works fine, considering the AI is the MAX player (VS human player, ...
- 151
1
vote
1
answer
194
views
Can Deep Reinforcement Learning come up with heuristics for a game it trains on and masters?
I am taking a course where we write minimax, alpha-beta pruning and interative deepening in Python for the game of Isolation.
I am supposed to write heuristics for an evaluation function of the game ...
- 115
2
votes
0
answers
338
views
Minimax evaluation function for games with score instead of loss/draw/win result
I am trying to create minimax evaluation function for the Ms Pacman game. The goal of the player is to maximize score.
I have some idea about the features that I would like to use in my evaluation ...
- 159
2
votes
1
answer
326
views
Alpha beta pruning - rules for updating alpha/beta value
I have been working on a problem to which I've applied alpha-beta pruning. While I got most of the answers right, there is one part I'm not quite getting:
Note that I've only provided a part of the ...
1
vote
0
answers
44
views
Why is the number of examined nodes $ O(b^{3d/4})$ in $\alpha$-$\beta$ pruning?
I'm taking a course 'Introduction to AI' and, in one of the tutorials, it was written that when pruning the game tree using $\alpha$-$\beta$ boundaries, the number of nodes that will be developed, ...
- 131
1
vote
3
answers
2k
views
How to alpha-beta pruning to expectiminimax
I have this problem above and I'm trying to think of how to apply alpha-beta pruning to the above. The algorithm states that on you're opponents turn the (expecti turn) you just return the lowest ...
- 717
0
votes
0
answers
313
views
Beating iterative alpha beta search in Isolation Game
I'm having trouble beating an AI in Isolation game: https://en.wikipedia.org/wiki/Isolation_(board_game) with 3 queens on a 7x7 board. I tried applying alpha beta iteration with a scoring function on ...
- 717
0
votes
0
answers
550
views
How to implement very simple move-ordering for alpha-beta pruning
I've done implementing alpha-beta, and transpositional table on my search tree algorithm so I decided to implement move-ordering next. But once I implemented it, it's way more longer to respond than ...
1
vote
1
answer
326
views
Does the alpha/beta value of parent nodes change if the alpha beta value of the child node changes?
I want to do alpha-beta pruning on this tree:
Consider nodes J and K. K is the max. Therefore, node D has an alpha value of 20, node B has a beta value of 20.
Move to Node E. Pass the beta value of ...
- 297
0
votes
1
answer
157
views
What is a good way of identifying volatile positions for a checkers game?
I am implementing an AI for a mobile checkers game, and have used alpha-beta pruning with Minimax.
Now I have the problem of horizontal effect, and need to do Quiesence search to avoid that.
Any ...
- 101
1
vote
0
answers
96
views
Minimax algorithm with only partial visibility
I'm trying to implement the minimax algorithm with alpha beta pruning on a game that works like this:
Player 1 plays (x1, y1).
Player 2 can only see the x-value (x1) that Player 1 played (and not ...
3
votes
2
answers
3k
views
Should I use minimax or alpha-beta pruning?
Should I use minimax or alpha-beta pruning (or both)? Apparently, alpha-beta pruning prunes some parts of the search tree.
- 53
9
votes
1
answer
6k
views
When should Monte Carlo Tree search be chosen over MiniMax?
I would like to ask whether MCTS is usually chosen when the branching factor for the states that we have available is large and not suitable for Minimax. Also, other than MCTS simluates actions, where ...
- 91
2
votes
0
answers
103
views
How can I apply the alpha-beta pruning algorithm to the "1-2 steal marbles" problem?
I have the following problem called "1-2 steal marbles".
Initially, there are 6 marbles on the board. One of the players can choose to remove 1 or 2 marbles leaving 5 or 4. After that, the other ...
4
votes
1
answer
1k
views
Why is it possible to eliminate this branch with alpha-beta pruning?
Can someone explain to me why it is possible to eliminate the rest of the middle branch in this image for alpha-beta pruning? I am confused because it seems the only information you know is that Helen ...
- 41
3
votes
1
answer
600
views
Could you share with me the tree size, search time and search depth of your implementation of Gomoku with minimax and alpha-beta prunning?
Currently, I am working on a Gomoku AI implementation with minimax + alpha-beta pruning.
I'm targeting these two rules from 'acceptable implementation' in terms of search time and search depth :
...
- 133
6
votes
1
answer
602
views
To deal with infinite loops, should I do a deeper search of the best moves with the same value, in alpha-beta pruning?
I have implemented minimax with alpha-beta pruning to play checkers. As my value heuristic, I am using only the summation of material value on the board regardless of the position.
My main issue lays ...
3
votes
1
answer
704
views
Can alpha-beta pruning be used for applications apart from games?
Can alpha-beta pruning/ minimax be used for systems apart from games? Like for selecting the right customer for a product, etc. (the typical data science problems)? I have seen people do it, but can't ...
- 33
3
votes
0
answers
299
views
How to choose the weights for a linear combination of heuristic functions?
I need to write a minimax algorithm with alpha-beta pruning in limited time for the 2048 game. I know expectimax is better for this work.
Assume I wrote different heuristic functions. If I want to ...
1
vote
2
answers
2k
views
Minimax combined with machine learning to determine if a path should be explored
I have an idea for a new type of AI for two-player games with alternating turns, like chess, checkers, connect four, and so on.
A little background: Traditionally engines for such games have used the ...
- 558
2
votes
3
answers
2k
views
Combining deep reinforcement learning with alpha-beta pruning
I will explain my question in relation to chess, but it should be relevant for other games as well:
In short terms: Is it possible to combine the techniques used by AlphaZero with those used by, say, ...
- 558
7
votes
2
answers
3k
views
Can someone help me to understand the alpha-beta pruning algorithm?
I understand the minimax algorithm, but I am unable to understand deeply the minimax algorithm with alpha-beta pruning, even after having looked up several sources (on the web) and having tried to ...
- 71
1
vote
2
answers
253
views
Can Alpha–Beta be used on symmetric zero sum games?
This question was asked in an AI exam. How would you answer such question?
- 111
3
votes
1
answer
783
views
Is it feasible to use minimax to solve a board game with a large number of moves?
I have to build a KI for a made-up game similar to chess. As I did research for a proper solution, I came upon the MinMax algorithm, but I'm not sure it will work with the given game dynamics.
The ...
- 39
3
votes
1
answer
286
views
Historical weakness of GOFAI in relation to partisan combinatorial games?
I was recently perusing the paper Some Studies in Machine Learning Using the Game of Checkers II--Recent Progress (A.L. Samuel, 1967), which is interesting historically.
I was looking at this figure, ...
- 6,237
7
votes
3
answers
981
views
More effective way to improve the heuristics of an AI... evolution or testing between thousands of pre-determined sets of heuristics?
I'm making a Connect Four game where my engine uses Minimax with Alpha-Beta pruning to search. Since Alpha-Beta pruning is much more effective when it looks at the best moves first (since then it can ...
2
votes
1
answer
546
views
If certain moves are compulsory, will there still be a need for a quiescence search?
Certain games, like checkers, have compulsory moves. In checkers, for instance, if there's a jump available a player must take it over any non-jumping move.
If jumps are compulsory, will there still ...
- 467
3
votes
2
answers
483
views
Is a good evaluation function as good as any of the extensions of alpha-beta pruning?
I would like to know if having a really good evaluation function is as good as using any of the extensions of alpha-beta pruning, such as killer moves or quiescence search?
- 467
6
votes
1
answer
1k
views
Are iterative deepening, principal variation search or quiescence search extensions of alpha-beta pruning?
I know that there are several optimizations for alpha-beta pruning. For example, I have come across iterative deepening, principal variation search, or quiescence search.
However, I am a little bit ...
- 467
18
votes
3
answers
11k
views
How do I choose the best algorithm for a board game like checkers?
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,...
- 467
6
votes
4
answers
5k
views
What else can boost iterative deepening with alpha-beta pruning?
I read about minimax, then alpha-beta pruning, and then about iterative deepening. Iterative deepening coupled with alpha-beta pruning proves to quite efficient as compared to alpha-beta alone.
I have ...
- 161
3
votes
1
answer
1k
views
How do I write a good evaluation function for a board game?
I'm currently writing the Alpha-Beta pruning algorithm for a board game. Now I need to come up with a good evaluation function. The game is a bit like snakes and ladders (you have to finish the race ...
- 119
9
votes
1
answer
2k
views
Should I use neural networks or genetic algorithms to solve Gomoku?
Currently, I'm doing a project that's about creating an AI to play the game Gomoku (it's like tic tac toe, but played on a 1515 board and requires 5 in a row to win). I have already successfully ...
- 93
4
votes
1
answer
481
views
How do I use a genetic algorithm to generate the scores of an evaluation function for alpha-beta pruning?
I have created a Gomoku (5 in a row) AI using Alpha-Beta Pruning. It makes moves on a not-so-stupid level. First, let me vaguely describe the evaluation function of the Alpha-Beta algorithm.
When it ...
- 141
1
vote
3
answers
862
views
Can I prune the tree if alpha-beta pruning finds 10 to the left of the root node?
I have an AI class this semester. For our exam, we also cover alpha-beta pruning.
I found an old example, where I think we can stop already earlier.
Here is a picture of it.
I think, because $X$ ...
- 121