Skip to main content

Questions tagged [minimax]

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

Filter by
Sorted by
Tagged with
1 vote
1 answer
690 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 ...
0 votes
1 answer
47 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
1 answer
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 ...
4 votes
1 answer
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?
1 vote
0 answers
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 (...
0 votes
0 answers
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 ...
5 votes
1 answer
243 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 ...
0 votes
0 answers
86 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 ...
3 votes
1 answer
375 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 ...
0 votes
1 answer
183 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 =...
0 votes
1 answer
4k 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 vote
2 answers
683 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?...
2 votes
1 answer
432 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 ...
1 vote
0 answers
372 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 ...
1 vote
0 answers
373 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 ...
3 votes
2 answers
5k views

How to make minimax optimal?

By optimal I mean that: If max has a winning strategy then minimax will return the strategy for max with the fewest number of moves to win. If min has a winning strategy then minimax will return the ...
3 votes
1 answer
1k 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, ...
1 vote
0 answers
197 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 ...
2 votes
2 answers
404 views

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?

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-...
1 vote
1 answer
309 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 ...
2 votes
0 answers
473 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 ...
1 vote
2 answers
108 views

What's the name of the value that you add or subtract from a minimax tree node?

I am coding a tic-tac-toe program that demonstrates reinforcement learning. The program uses minimax trees to decide its moves. Whenever it wins, all the nodes on the tree that were involved in the ...
3 votes
1 answer
701 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 : ...
4 votes
1 answer
518 views

How do I use a genetic algorithm to generate the scores of an evaluation function for alpha-beta pruning?

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 evaluation function of the Alpha-Beta algorithm. When it ...
5 votes
1 answer
322 views

Why do zero-sum perfect information games satisfy the conditions of Von Neumann's theorem?

The Von Neumann's Minimax theorem gives the conditions that make the max-min inequality an equality. I understand the max-min inequality, basically ...
2 votes
1 answer
125 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 ...
1 vote
1 answer
492 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 ...
2 votes
0 answers
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 ...
1 vote
2 answers
1k 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 ...
3 votes
1 answer
5k 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?
4 votes
1 answer
578 views

How do we find the length (depth) of the game tic-tac-toe in adversarial search?

When we perform the tic-tac-toe game using adversarial search, I know how to make a tree. Is there a way to find the depth of the tree, and which level is the last level?
1 vote
0 answers
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, ...
4 votes
2 answers
4k 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
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 ...
1 vote
1 answer
966 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
1 answer
2k 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 ...
0 votes
2 answers
90 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 ...
6 votes
1 answer
5k 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 ...
3 votes
1 answer
400 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 ...
6 votes
1 answer
717 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 ...
1 vote
1 answer
713 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{...
19 votes
3 answers
12k 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,...
0 votes
1 answer
185 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
0 answers
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 ...
10 votes
1 answer
8k 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 ...
3 votes
1 answer
937 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 ...
1 vote
3 answers
1k 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$ ...
5 votes
1 answer
3k 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 ...
1 vote
0 answers
302 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 ...
3 votes
1 answer
1k 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?