Questions tagged [alpha-beta-pruning]

For questions involving the Alpha-Beta pruning algorithm.

Filter by
Sorted by
Tagged with
0
votes
0answers
26 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 ...
0
votes
0answers
28 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 ...
0
votes
0answers
23 views

How to interpret the output of alpha-beta pruning in terms of which position to play next in a game

I'm trying to understand question 4 of this paper. This is a tree pruned with alpha-beta pruning: I understand technically how this pruning worked (i.e. calculating mix/max/alpha/beta values). My ...
0
votes
1answer
59 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 ...
0
votes
1answer
30 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 ...
1
vote
0answers
23 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 ...
0
votes
0answers
38 views

When is shallow pruning possible in alpha-beta pruning for multi-player games?

I have read up on some research papers that state that shallow pruning is possible when ...
2
votes
2answers
108 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.
6
votes
1answer
743 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 ...
2
votes
0answers
74 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
1answer
247 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 ...
3
votes
1answer
233 views

Minmax algorithm, search time and search depth compromise and acceptability

Currently working on Gomoku AI implementation with minmax + alpha beta implementation. I'm targeting these two rules from 'acceptable implementation' in terms of search time and search depth : ...
6
votes
1answer
161 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
1answer
181 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 ...
3
votes
0answers
104 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
2answers
1k 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 ...
1
vote
3answers
630 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, ...
8
votes
2answers
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 ...
1
vote
2answers
166 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?
3
votes
1answer
282 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 ...
2
votes
1answer
183 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, ...
7
votes
3answers
636 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
1answer
516 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 ...
3
votes
2answers
265 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?
6
votes
1answer
755 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 ...
17
votes
3answers
7k 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,...
6
votes
4answers
3k 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 ...
3
votes
1answer
968 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 ...
9
votes
1answer
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 ...
1
vote
3answers
552 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$ ...