Questions tagged [minimax]
Use for questions involving minimax and variants such as maximin. Applies both to algorithms and the minimax theorem.
55
questions
0
votes
2answers
50 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
...
0
votes
0answers
28 views
MCTS: What if all children of a node are terminal?
If all children Nodes of the selected node are terminal in the selection phase - you obviously run into a problem. So how do I prevent a Node to be selected that only has terminal children?
0
votes
0answers
22 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
57 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 ...
3
votes
1answer
94 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 ...
0
votes
1answer
29 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
22 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
1answer
34 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
vote
1answer
59 views
AI to play a solo card game
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 ...
0
votes
0answers
34 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 ...
0
votes
1answer
109 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 ...
2
votes
2answers
104 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.
1
vote
0answers
73 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 ...
2
votes
1answer
101 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?
3
votes
1answer
345 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 ...
6
votes
1answer
568 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 ...
1
vote
1answer
36 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).
...
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
146 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 ...
4
votes
1answer
207 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
1k 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?
2
votes
1answer
110 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 ...
3
votes
1answer
212 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
143 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
174 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
101 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
1answer
218 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 ...
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
0answers
109 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 ...
4
votes
0answers
53 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 ...
1
vote
0answers
72 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 ...
2
votes
1answer
361 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 ...
1
vote
1answer
518 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 ...
8
votes
2answers
1k 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 ...
3
votes
1answer
270 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 ...
4
votes
1answer
575 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, ...
3
votes
1answer
269 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
186 views
Is there a way of representing the minimax algorithm mathematically?
I have successfully figured out how the minimax algorithm works for a game like chess, where a game tree is used, and you assign a value to the terminal nodes and propagate that value up the tree.
Is ...
4
votes
1answer
495 views
Transposition table is only used for roughly 17% of the nodes - is this expected?
I'm making a Connect Four game using the typical minimax + alpha-beta pruning algorithms. I just implemented a Transposition Table, but my tests tell me the TT only helps 17% of the time. By this I ...
0
votes
1answer
370 views
Connect 4 minimax does not make the best move
I'm trying to implement an algorithm that would choose the optimal next move for the game of Connect 4. As I just want to make sure that the basic minimax works correctly, I am actually testing it ...
2
votes
1answer
512 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 ...
6
votes
1answer
746 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,...
2
votes
0answers
81 views
How do GAN's generator actually work?
I have implemented DCGAN's myself and have been studying GAN's for over a month now. Now I am implementing the pggans but I encountered a sentence
When we measure the distance between
the ...
3
votes
1answer
169 views
Can minimax be used when both players want to increase their score?
If both the players want to increase their score (by selecting the highest or best cost path), can this be done using the minimax algorithm, or are there other algorithms for this purpose?
2
votes
1answer
231 views
Adversarial search in the game '2048'
If we model the game '2048' using a max-min game tree, what is the maximal path from a start state to a terminal state? (Assume the game ends only when the board is full
This is one of the sub-...
6
votes
1answer
4k views
Why most imperfect information games usually use non machine learning AI?
To provide a bit of context, I'm a software engineer & game enthusiast (card games, especially). The thing is I've always been interested in AI oriented to games. In college, I programmed my own ...
2
votes
1answer
702 views
Game AI evaluation function and making progress towards winning
In two-player games, the exact value of the evaluation function doesn't matter, as long as it's bigger for better positions. However, for learning, it's customary when it does change when the best ...
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 ...
4
votes
1answer
313 views
Fitness Function altenatives in Genetic Algorithms for game AI
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 grading function of the Alpha-Beta algorithm.
When it ...
