Algorithms Explained – minimax and alpha-beta pruning
Why Stack Overflow recommends it
Stack Overflow users link it as the go-to explanation of minimax and alpha-beta when answering or asking about game AI such as chess, Connect 4 and board game bots.
Recommended by 2 people across 3 different months, 2019 to 2022.
What it is
An 11-minute tutorial by Sebastian Lague explaining the minimax search algorithm and how alpha-beta pruning speeds it up, with links to pseudocode for both versions. It uses game-tree examples to show how the algorithm picks moves in two-player games.
What people said
Recommends Irton De Ascencao · 2020-06 · Stack Overflow · on “I have a minimax algorithm but im not sure what to parse into position?”
I'm making a board game similar to mancala. I based my algorithm off this video: [this video] However I'm stuck with variable position and i think i still need to save the move. Its my first time doing AI and this project involved making AI for a unique Game. I think im doing this horribly wrong as i think minimax is supposed to be a tree diagram and i got no tree. public class MiniMax { bool gameOver = false; public float minimax(position, int depth, float alpha, float beta, bool player1) { if (depth == 0 || GameOver()) { float score = Utility(); } if (player1) { float maxVal = float.MaxValue; foreach (var child in postition) { float eval = minimax(postition, depth - 1, alpha, beta, false); maxV
Recommends LittleCoder · 2021-08 · Stack Overflow · on “How to implement a minimax algorithm in a chess-like game?”
MiniMax is good with a recursive implementation. You can find an example in this great video [this video] . Implement Minimax iteratively and write n times the depth 1 function for depth n does not follow the Don't Repeat Yourself (DRY) rule. Implementation in Python : def minimax(pos, depth, alpha, beta, maximizingPlayer) : # maximizingPlayer = True if White2Play and False is Black2Play if depth == 0 or game_is_finished(board) or can_t_move(board) : return evaluate(board) # <- zero ground for recusivity if maximizingPlayer : maxEval = -infinity(or a number smaller than your smallest evaluation) for child in child_of_position(board) : evalu = minimax(child, depth - 1, alpha, beta, False) # recurs
Recommends LittleCoder · 2022-08 · Stack Overflow · on “Issues implementing the Minimax Algorithm”
First of all, do not use the minimax algorithm. It is inefficient compared to alpha-beta [LINK] . You should use Alpha Beta in a NegaMax [LINK] framework for more simplicity. Note with NegaMax : the evaluation function should be relative to the side to move. Then, your evaluation function is only based on material balance, it is not enough to have a decent playing style. Two good (and simple) pages about evaluation : [LINK] [LINK] For more complex/advanced search implementations : the MiniMax and AlphaBeta algorithms are pretty well explained here [this video] transposition tables are well explained here [LINK] and the Zobrist Hashing here [LINK] . The (simplified) idea is to not (wast time to) s
Cites hdw3 · 2019-05 · Stack Overflow · on “Minmax algorithm doesn't return direct child of root (returns illegal move)”
I am trying to create "AI" for Nine Men's Morris but I got hardstuck on minMax algorithm. Summing up, I was trying to find the issue for over 10h but didn't manage to. (debugging this recursion is nasty or I am doing it badly or both) Since I started doubting everything I wrote I decided to post my issue so someone can find anything wrong in my version of minMax. I realise it is really hard task without the whole application so any suggestions where I should triple check my code are also very welcome. Here is link to the video, explaining minMax, on which I based my implementation: [this video] (First video that pops up on yt after searching for minmax - just in case you want to watch the video a
Cites erhuht · 2020-12 · Stack Overflow · on “Alpha-beta pruning makes worse decisions when fully implemented”
I am writing a basic chess AI using a minimax algorithm. I implemented alpha-beta pruning which seemed to work fine. Here's the code: def move(self, board): moves = {} for move in board.legal_moves: board.push(move) moves[move] = self.evaluate_move(board, 1, float("-inf"), float("inf")) board.pop() best_moves = [] for key in moves.keys(): if moves[key] == max(moves.values()): best_moves.append(key) chosen_move = random.choice(best_moves) return chosen_move def evaluate_move(self, board, depth, alpha, beta): if depth % 2: # if depth is odd ie. minimizing player extremepoints = float("inf") else: extremepoints = float("-inf") if depth < self.depth_limit and (not board.is_game_over()): for move
Cites Egi · 2022-02 · Stack Overflow · on “Why my connect4 minimax doesn't work properly?”
Can you please explain to me why my AI can play properly, until player has 3 in a row in sixth or seventh column then my AI refuses to block him. And another problem is in a position when my AI can win in 1 move, but he will rather choose a longer game. Can anyone help me please. Returns a value for a winning move def utility(board): if terminal(board): if winning_move(board, X): return 1000000 elif winning_move(board, O): return -10000 else: return 0 Calculates the score of position when depth = 0 def compute_score(block, board, col, row): score = 0 if block.count(X) == 4 and block.count("-") == 0: score += 100000 elif block.count(X) == 3 and block.count("-") == 1: score += 10 elif block.co
Cites Adrian · 2022-12 · Stack Overflow · on “Minimax algorithm behaving strangely”
@CraigEstey Thanks, there is not really a link with the code. I watched this video [this video] then got inspired by bunch of other codes online.