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
0answers
43 views

ExpectiMinimax Tree

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
0answers
139 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
60 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 ...
1
vote
1answer
45 views

Chess Engine for low clock cycle CPU

I'm looking for a simple chess algorithm that works well on a ~132MHz CPU. I know that MiniMax would take too long to go deep in order to find good moves. Is Monte Carlo Tree Search working well on ...
4
votes
1answer
41 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
45 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
196 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 ...
0
votes
1answer
159 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 ...
4
votes
3answers
636 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 ...
2
votes
1answer
107 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 ...
2
votes
1answer
156 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, ...
1
vote
1answer
159 views

Minimax algorithm

I have been successfully figured out how the minimax algorithm works for a game like chess. Were by a game tree is used and you assign a value to the terminal nodes and propagate that value up the ...
3
votes
1answer
114 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
240 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 ...
1
vote
1answer
326 views

Quiescence search

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. My question is, if jumps are compulsory will there ...
3
votes
2answers
151 views

Is an evaluation function as good as an optimization function

I have been so for self-learning basic A.I concepts and would like to know if having a really good evaluation function as good as any of alpha-beta pruning optimization functions such as killer moves, ...
4
votes
1answer
377 views

Alpha-beta pruning algorithms optimizations

I know that they are quite alot of optimizations for alpha-beta pruning but what does it mean exactly: 1) Does it mean that these optimized algorithms are to be integrated into the alpha-beta ...
12
votes
5answers
5k views

How do I choose which algorithm is best for something like a checkers board game?

I am currently new to artificial intelligence but I am very intrigued by it. I am currently researching three algorithms, namely: Minimax, Alpha-beta pruning and Monte Carlo tree search. As you may ...
1
vote
0answers
63 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
131 views

Minimax with only max

If both the players want to increase their score (by selecting the highest/best cost path) can this be done using Minimax Algorithm and not other algorithms?
2
votes
1answer
152 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-...
3
votes
1answer
479 views

How do I write a good evaluation function?

I'm currently writing an Alpha-Beta-Pruning algorithm for a board game. Now I need to come up with a good evaluation function. The game is a bit like snakes and ladders (you have to finish the race ...
4
votes
1answer
224 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 ...
3
votes
2answers
2k 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
1answer
107 views

Minmax - choosing the best player's way

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 ...
1
vote
2answers
73 views

Whats 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 ...
5
votes
1answer
132 views

Illustration of Von Neumann's Minimax theorem in games?

The Von Neumann's Minimax theorem gives the conditions that make the max-min inequality an equality. I understand the max-min inequality, basically ...