# Questions tagged [minimax]

Use for questions involving minimax and variants such as maximin. Applies both to algorithms and the minimax theorem.

21 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
329 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?
344 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 ...
471 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 ...
• 149
189 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
112 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 ...
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 ...
124 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 ...
1 vote
20 views

### Two player grid-based game, minimax not good, what to try?

In this game, a matrix with size N x M is given (10<=N,M<=15). There a three main type of value in the matrix: A integer show how many gold is it Char 'D' show obstacle Char 'S' show shield (...
1 vote
366 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
370 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
1 vote
189 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 ...
1 vote
45 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
1 vote
103 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
298 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 ...
1 vote
672 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
240 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
1 vote
203 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
41 views

### Can MAX ensure maximum minimum gain by using minimax once at game start?

MAX and MIN apply the minimax algorithm each time before making their move, searching to some predefined depth. Imagine, however, that the MAX player applies the minimax algorithm only once, at the ...
45 views

### What algorithm should I use to train an antichess agent?

I will implement an antichess agent and am not sure about which algorithm to use. My current candidates are minimax with alpha-beta pruning, MCTS and proximal policy optimization. Should I consider ...