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
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,...
JoeyB's user avatar
  • 477
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 ...
R AND B's user avatar
  • 101
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 ...
Conway's user avatar
  • 93
9 votes
2 answers
5k 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 ...
Sunshine 's user avatar
8 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, ...
Inertial Ignorance's user avatar
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 ...
Alexander Aeons Torn's user avatar
6 votes
1 answer
711 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 ...
TurbulentWinds's user avatar
6 votes
1 answer
1k 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 ...
JoeyB's user avatar
  • 477
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 ...
dato nefaridze's user avatar
5 votes
1 answer
239 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 ...
Terri Erickson's user avatar
5 votes
1 answer
321 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 ...
dontloo's user avatar
  • 167
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.
goldilocks's user avatar
4 votes
1 answer
2k 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 ...
Inertial Ignorance's user avatar
4 votes
1 answer
349 views

What is the variant of the minimax tree with 3 types of nodes called?

I have a task on my class to find all the nodes, calculate their values and choose the best way for the player on the given game graph: Everything is fine, but I have no idea what these dots are. Is ...
Jacob's user avatar
  • 153
4 votes
1 answer
391 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 ...
mason7663's user avatar
  • 613
4 votes
1 answer
2k 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 ...
Victor's user avatar
  • 41
4 votes
1 answer
530 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 ...
Inertial Ignorance's user avatar
4 votes
1 answer
517 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 ...
Dashadower's user avatar
4 votes
1 answer
574 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?
Adil Mustafa's user avatar
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?
Rachael E's user avatar
3 votes
2 answers
4k 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 ...
Aadit M Shah's user avatar
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, ...
Carmellose's user avatar
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?
mason7663's user avatar
  • 613
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?
Alaz Sengul's user avatar
3 votes
1 answer
695 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 : ...
user7364588's user avatar
3 votes
1 answer
935 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 ...
josebert's user avatar
3 votes
1 answer
367 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 ...
Kestina's user avatar
  • 31
3 votes
1 answer
398 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 ...
vesii's user avatar
  • 81
3 votes
1 answer
889 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 ...
kritika's user avatar
  • 33
3 votes
0 answers
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 ...
Mustafa Tufan's user avatar
2 votes
1 answer
552 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 ...
JoeyB's user avatar
  • 477
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 ...
Reifocs's user avatar
  • 123
2 votes
1 answer
428 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 ...
Fraser Gilbert's user avatar
2 votes
1 answer
711 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 ...
zooby's user avatar
  • 2,216
2 votes
2 answers
402 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-...
Bar's user avatar
  • 21
2 votes
0 answers
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 ...
Druudik's user avatar
  • 149
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 ...
Errata's user avatar
  • 21
2 votes
1 answer
218 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). ...
gfdsal's user avatar
  • 171
2 votes
0 answers
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 ...
Zhengliang Chen's user avatar
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 ...
Adam Baranyai's user avatar
2 votes
1 answer
484 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 ...
Agade's user avatar
  • 121
2 votes
0 answers
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 ...
Muhammad Rafique's user avatar
1 vote
1 answer
267 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 ...
JoeyB's user avatar
  • 477
1 vote
1 answer
974 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 ...
wesleyy's user avatar
  • 113
1 vote
3 answers
999 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$ ...
Peter's user avatar
  • 121
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 ...
Mr. Eivind's user avatar
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 ...
maaartinus's user avatar
1 vote
2 answers
676 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?...
steward's user avatar
  • 11
1 vote
1 answer
299 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 ...
mLstudent33's user avatar
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 ...
Michael's user avatar
  • 159