Questions tagged [alpha-beta-pruning]

For questions involving the Alpha-Beta pruning algorithm.

Filter by
Sorted by
Tagged with
1 vote
0 answers
22 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 ...
user avatar
1 vote
1 answer
124 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, ...
user avatar
1 vote
1 answer
43 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 ...
user avatar
2 votes
0 answers
80 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 ...
user avatar
  • 159
0 votes
0 answers
68 views

How to differentiate left-to-right and right-to-left alpha-beta pruning?

I am new to the alpha-beta pruning algorithm. I was trying to understand the concept between Left-to-Right and Right-to-Left alpha-beta pruning examples. Based on my understanding, according to the ...
user avatar
2 votes
1 answer
121 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 ...
user avatar
1 vote
0 answers
36 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, ...
user avatar
1 vote
2 answers
721 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 ...
user avatar
0 votes
0 answers
52 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 ...
user avatar
0 votes
0 answers
268 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 ...
user avatar
1 vote
1 answer
90 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 ...
user avatar
0 votes
1 answer
53 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 ...
user avatar
1 vote
0 answers
52 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 ...
user avatar
2 votes
2 answers
766 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.
user avatar
8 votes
1 answer
3k 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 ...
user avatar
  • 81
2 votes
0 answers
84 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 ...
user avatar
4 votes
1 answer
619 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 ...
user avatar
  • 41
3 votes
1 answer
390 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 : ...
user avatar
6 votes
1 answer
352 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 ...
user avatar
3 votes
1 answer
357 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 ...
user avatar
  • 33
3 votes
0 answers
177 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 ...
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 ...
user avatar
1 vote
3 answers
1k 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, ...
user avatar
7 votes
2 answers
2k 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 ...
user avatar
1 vote
2 answers
214 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?
user avatar
  • 111
3 votes
1 answer
455 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 ...
user avatar
3 votes
1 answer
230 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, ...
user avatar
  • 6,077
7 votes
3 answers
723 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 ...
user avatar
2 votes
1 answer
527 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 ...
user avatar
  • 457
3 votes
2 answers
348 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?
user avatar
  • 457
6 votes
1 answer
915 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 ...
user avatar
  • 457
17 votes
3 answers
9k 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,...
user avatar
  • 457
6 votes
4 answers
4k 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 ...
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 ...
user avatar
  • 119
9 votes
1 answer
1k 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 ...
user avatar
  • 93
4 votes
1 answer
375 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 ...
user avatar
1 vote
3 answers
615 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$ ...
user avatar
  • 121