Questions tagged [alpha-beta-pruning]

For questions involving the Alpha-Beta pruning algorithm.

Filter by
Sorted by
Tagged with
2 votes
2 answers
95 views

Can I use Alpha-Beta Pruning for real life game simulation?

I had an idea to use the this algorithm to simulate real life game scenarios where a player could train and retrain their mistake and be ready for when that situation happens again in real life. This ...
Caio Amaral's user avatar
0 votes
0 answers
234 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 ...
numq's user avatar
  • 1
0 votes
1 answer
158 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 =...
maxutil's user avatar
2 votes
1 answer
1k 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 ...
Dimanjan's user avatar
  • 123
1 vote
0 answers
161 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 ...
crass_sandwich's user avatar
3 votes
1 answer
1k 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, ...
Carmellose's user avatar
1 vote
1 answer
254 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 ...
mLstudent33's user avatar
2 votes
0 answers
410 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 ...
Druudik's user avatar
  • 149
2 votes
1 answer
386 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 ...
Gerhardus Carinus's user avatar
1 vote
0 answers
45 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, ...
E. Ginzburg's user avatar
2 votes
3 answers
3k 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 ...
user8714896's user avatar
0 votes
0 answers
378 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 ...
user8714896's user avatar
0 votes
0 answers
631 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 ...
James Urian's user avatar
1 vote
1 answer
431 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 ...
Slowat_Kela's user avatar
0 votes
1 answer
169 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 ...
Paiman Roointan's user avatar
1 vote
0 answers
100 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 ...
SpiderManCity's user avatar
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.
goldilocks's user avatar
10 votes
1 answer
7k 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 ...
R AND B's user avatar
  • 101
2 votes
0 answers
108 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 ...
Zhengliang Chen's user avatar
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 ...
Victor's user avatar
  • 41
3 votes
1 answer
664 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 : ...
user7364588's user avatar
6 votes
1 answer
667 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 ...
TurbulentWinds's user avatar
3 votes
1 answer
813 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 ...
kritika's user avatar
  • 33
3 votes
0 answers
333 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 ...
Mustafa Tufan's user avatar
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 ...
Mr. Eivind's user avatar
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, ...
Mr. Eivind's user avatar
9 votes
2 answers
4k 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 ...
Sunshine 's user avatar
1 vote
2 answers
266 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?
Exprove's user avatar
  • 111
3 votes
1 answer
871 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 ...
josebert's user avatar
3 votes
1 answer
312 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, ...
DukeZhou's user avatar
  • 6,237
7 votes
3 answers
1k 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 ...
Inertial Ignorance's user avatar
2 votes
1 answer
549 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 ...
JoeyB's user avatar
  • 477
3 votes
2 answers
509 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?
JoeyB's user avatar
  • 477
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 ...
JoeyB's user avatar
  • 477
19 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,...
JoeyB's user avatar
  • 477
6 votes
4 answers
6k 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 ...
Suhail Gupta's user avatar
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 ...
po0l's user avatar
  • 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 ...
Conway's user avatar
  • 93
4 votes
1 answer
506 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 ...
Dashadower's user avatar
1 vote
3 answers
952 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$ ...
Peter's user avatar
  • 121