Questions tagged [minimax]
Use for questions involving minimax and variants such as maximin. Applies both to algorithms and the minimax theorem.
70
questions
0
votes
0
answers
22
views
How to guess a card in the game of Cambio with limited information?
I need help with a probability problem in the card game of Cambio. In this game, two players are dealt four cards each from a deck of 52 cards . At the start of the game, the bottom cards of each ...
0
votes
1
answer
27
views
Query regarding the minimax value function of GANs
In the book Generative AI with Python and TensorFlow 2 from Babcock and Bali (page 172), it is stated that the value function of a GAN is the following:
where D(x) is the output of the discriminator ...
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
2
answers
441
views
Why do iterative deepening search start from the root each iteration in the context of the minmax-algorithm?
Consider the graph below for an understanding on how IDS work.
Now my question is:
why do IDS start at the root every iteration, why not start at the previously searched depth in the context of minmax?...
- 11
1
vote
0
answers
246
views
What happens if MIN plays suboptimally and unpredictably?
The following quotes are an extract from AIMA, 3ed.
The definition of optimal play for MAX assumes that MIN also plays optimally—it maximizes the worst-case outcome for MAX. What if MIN does not play ...
- 21
1
vote
0
answers
311
views
How should I choose the depth for minimax if I have a strict time constraint?
I am working on a controller that plays Ms. Pac-Man using a minimax algorithm. The controller has a limited time amount in which it can choose a move on each round, otherwise when the time runs out ...
- 21
3
votes
1
answer
245
views
Can we achieve optimality with minimax using an evaluation function?
The following quote (from AIMA) refers to the situation in which the minimax algorithm computes its values directly from the terminal states.
(The) definition of optimal play for MAX assumes that MIN ...
- 31
0
votes
1
answer
2k
views
Why is depth-limited is preferable to minimax without depth limited
I have read about a question that says the following:
Why is depth-limited minimax preferable to minimax?
One of the wrong answers was:
The depth-limited minimax will achieve the same output as ...
- 1
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
0
answers
170
views
Which heuristic function should I use for the ColorShapeLinks game?
For learning purposes, I am trying to implement the minimax algorithm for the ColorShapeLinks game, which is similar to connect 4, except the fact that it combines both shape and color as the winning ...
- 21
1
vote
2
answers
570
views
How does one handle different player turns in MCTS?
Suppose we have a two player game like Tic Tac Toe where the two players take turns to play their moves. It is my understanding that in the game tree that MCTS builds, consecutive levels in the tree ...
- 159
4
votes
0
answers
190
views
How to handle cycles in minimax algorithm
For example, I am implementing AI for turn based game and have enough computational resources for build full game tree. My problem is the game can be infinite if both players will repeat moves and my ...
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
0
votes
2
answers
88
views
What is the meaning of the terms in this evaluation function for chess?
I'm trying to improve my evaluation and I saw this here
...
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
3
votes
1
answer
377
views
Strategy for playing a board game with Minimax algorithm
I want to build a player for the following game:
You have a board where position 1 is your player, position 2 is the rival ...
- 81
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 ...
1
vote
1
answer
620
views
Optimal mixed strategy in two player zero sum games
I am currently studying game theory based on Peter Norvig's 3rd edition introduction to artificial intelligence book. In chapter 17.5, the two player zero sum game can be solved by using the $\textbf{...
- 1,251
2
votes
1
answer
120
views
How can I improve the performance of my approach to solving a 1-player version of the card game "The Game" by Steffen Benndorf?
I would like to create an AI for the 1 player version of the card game called "The Game" by Steffen Benndorf (rules here: https://nsv.de/wp-content/uploads/2018/05/the-game-english.pdf).
The ...
- 123
2
votes
1
answer
369
views
How does the MCTS tree look like?
I have come across the Monte Carlo tree search (MCTS) algorithm, but I can't find what the tree should look like. For example, does it still represent a minimax process, i.e. player 1 from the root ...
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
1
vote
0
answers
248
views
How do you prove that minimax algorithm outputs a subgame-perfect Nash equilibrium?
At every node, MAX would always move to maximise the minimum payoff while MIN choose to minimise the maximum payoff, hence there is nash equilibrium.
By using backwards induction, at every node, MAX ...
- 53
2
votes
1
answer
954
views
In what RL algorithm category is MiniMax?
Q-learning is a temporal-difference method and Monte Carlo tree search is a Monte Carlo method. In what category is MiniMax?
- 603
5
votes
1
answer
2k
views
What happens if the opponent doesn't play optimally in minimax?
I just read an article about the minimax algorithm. When you design the algorithm, you assume that your opponent is a perfect player, i.e. it plays optimally.
Let's consider the game of chess. What ...
- 862
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
1
answer
175
views
How are the Bellman optimality equations and minimax related?
Is the philosophy between Bellman equations and minimax the same?
Both the algorithms look at the full horizon and take into account potential gains (Bellman) and potential losses (minimax).
...
- 171
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
348
views
Is the minimax algorithm model-based?
Trying to get my head around model-free and model-based algorithms in RL. In my research, I've seen the search trees created via the minimax algorithm. I presume these trees can only be created with a ...
- 603
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
4k
views
Why does the adversarial search minimax algorithm use Depth-First Search (DFS) instead of Breadth-First Search (BFS)?
I understand that the actual algorithm calls for using Depth-First Search, but is there a functionality reason for using it over another search algorithm like Breadth-First Search?
- 33
2
votes
1
answer
469
views
Is there a probabilistic version of minimax?
How would a probabilistic version of minimax work?
For example, we may choose a move that could result in a very bad outcome, but that outcome might just be extremely unlikely so we might think it ...
- 2,186
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
1
answer
594
views
Is this ExpectiMinimax Tree correctly drawn?
I need help with ExpectiMinimax problem:
Start a game.
The first player flips a coin.
The second player flips a coin.
The first player decides if he wants to flip another coin.
The second player ...
- 11
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
1
vote
0
answers
215
views
Understanding alpha-beta pruning for simplified NIM
This is a simple version of NIM: Two players alternately remove one, two or three coins from a stack initially containing 5 coins. The player who picks up the last coin loses.
What does alpha-beta ...
- 11
2
votes
0
answers
63
views
What kind of decision rule algorithm is usable in this situation?
I am trying to write an AI to a game, where there is no real adversary. This means, that only the AI player has choices in which move to perform, his opponent may or may not react to the move the AI ...
- 143
1
vote
0
answers
185
views
Can't grasp MiniMax diagram (no alpha beta pruning)
The image is one of many similar exam questions can anyone pelase help me understand it fully?
'Internal node': This is simply every node except A?
Move choices: His only options are B, C and D for ...
- 11
2
votes
1
answer
470
views
Using the opponent's mixed strategy in estimating the state value in minimax Q learning
In the paper Markov games as a framework for multi-agent reinforcement learning (which introduces the minimax Q Learning algorithm), at the bottom left of page 3, my understanding is that the author ...
- 121
1
vote
1
answer
1k
views
Does quiescence search even improve the minimax algorithm?
Consider this game state:
d5 captures c6
Quiescence search returns about 8.0 as evaluation because after dxc6 and bxc6 Qxd6 would be played (then Qxd6 by black). A normal player would not play this ...
- 239
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
4
votes
1
answer
476
views
Why do neural nets and machine learning tend to work well with MCTS, but not with regular Minimax game-playing AI?
I've often heard MCTS grouped together with neural nets and machine learning. From what I gather, MCTS uses a refined intuition (from maching learning) to evaluate positions. This allows it to better ...
7
votes
1
answer
2k
views
Any interesting ways to combine Monte Carlo tree search with the minimax algorithm?
I've been working on a game-playing engine for about half a year now, and it uses the well known algorithms. These include minimax with alpha-beta pruning, iterative deepening, transposition tables, ...