Questions tagged [minimax]
The minimax tag has no usage guidance.
12
questions
3
votes
4
answers
588
views
What does the perfect chess algorithm look like?
Say we have an infinitely powerful computer playing chess. This computer can tell which moves lead to a win/draw/loss with best play. Obviously we want to pick a winning move if available, or a ...
3
votes
0
answers
36
views
Is there an algorithm polynomial in dimension of space and number of points for the Minimum Enclosing Ball?
Let $C_1, ..., C_m \in \mathbb{R}^n$ Is there a polynomial algorithm in $n,m$ which finds the Minimum Enclosing Ball (MEB) for these points?
My research
I see mentions of algorithms like Megido, Waltz ...
- 185
1
vote
0
answers
54
views
How to find optimizers with computer in this kind of minimax problem [closed]
I have a minimax problem of the form $$\max_{\substack{u_1,\dots,u_n \ge 0 \\ u_1+\dots+u_n = 1}} \min_{\substack{v_1,\dots,v_m \ge 0 \\ v_1+\dots+v_m = 1 \\ v_{j_1} \le v_{j_2} \hspace{1mm} \forall (...
- 154
1
vote
1
answer
47
views
Find optimal play by optimizing orders of each player alternatingly
A zero-sum game for two players allows a player to take no action during a turn. Can I reach optimal play (where both players always choose the best possible action in each turn) by the following ...
- 113
1
vote
0
answers
247
views
Equally optimal nodes during minimax with alpha-beta pruning
Alpha-beta pruning is an optimization for minimax that reduces the number of nodes visited without changing the final result. However, both minimax and alpha-beta only return the optimal node value (...
- 111
1
vote
2
answers
333
views
What mathematical guarantees gives alpha-beta pruning?
In the alpha-beta pruning version of the minimax algorithm, when one evaluates a state p with $\alpha$ and $\beta$ cutoff and gets a ...
- 121
1
vote
1
answer
96
views
MCTS how to prevent Selecting a TERMINAL state in TRAVERSAL Phase?
Hello I am currently working on an implementation of MCTS and I ran into the problem that my tree traversal policy selects nodes with terminal game states. Furthermore how do I prevent selecting a ...
- 11
1
vote
0
answers
567
views
Understanding deep cutoff in Alpha–beta pruning algorithm
I am studying the Alpha Beta pruning algorithm here.
...
- 345
0
votes
2
answers
62
views
How to tell if a minimax search tree is computationally feasible using parallel computing
I am trying to apply the minimax algorithm to a game of Pokemon. This is a problem where the search tree is usually around 20 levels deep (number of turns) and each level has 9 or less branches (...
- 135
0
votes
1
answer
50
views
Computing the minimum distance between each pain of points
I am trying to read an algorithm for computing minimum distance between each pair of points from the book: Algorithm Design
Algorithm Design
It considers the points in a line. If the points are in ...
- 251
7
votes
3
answers
523
views
Why does Min-Max algorithm delays a good move indefinitely?
Consider a simple chess example:
Q is white Queen.
K, R is black King and black Rook respectively.
A B
1 . Q
2 . .
3 K .
4 . .
5 . .
6 R .
7 . .
8 . R
1,2......
- 175
0
votes
0
answers
60
views
How do evaluation functions influence the optimal sequence of moves?
Assume you have a game tree and the features $(f_1, f_2, f_3,\ldots,f_n )$ that describe the state of the game at any node. Also assume that you are using depth-limited minimax and always expand up to ...
- 101