Stack Overflow
Stack Overflow

Questions tagged [alpha-beta-pruning]

A search algorithm that seeks to decrease the number of nodes, which are evaluated by the minimax algorithm, in its search tree

For more info see the Alpha-beta pruning wikipedia article.

304 questions
22
votes
8 answers

How to create a good evaluation function for a game?

I write programs to play board game variants sometimes. The basic strategy is standard alpha-beta pruning or similar searches, sometimes augmented by the usual approaches to endgames or openings. I've mostly played around with chess variants, so…
A. Rex
  • 31,633
  • 21
  • 89
  • 96
19
votes
1 answer

Alpha-beta prunning with transposition table, iterative deepening

I'm trying to implement alpha-beta min-max prunning enhanced with transposition tables. I use this pseudocode as reference: http://people.csail.mit.edu/plaat/mtdf.html#abmem function AlphaBetaWithMemory(n : node_type; alpha , beta , d : integer) :…
PanJanek
  • 6,593
  • 2
  • 34
  • 41
18
votes
2 answers

Alpha-beta move ordering

I have a basic implementation of alpha-beta pruning but I have no idea how to improve the move ordering. I have read that it can be done with a shallow search, iterative deepening or storing the bestMoves to transition table. Any suggestions how to…
user1306283
18
votes
5 answers

Java Minimax Alpha-Beta Pruning Recursion Return

I am trying to implement minimax with alpha-beta pruning for a checkers game in Java. My minimax algorithm works perfectly. My code runs with the alpha-beta code in place. Unfortunately, when I play 1000 games vs the standard minimax algorithm, the…
sage88
  • 4,104
  • 4
  • 31
  • 41
15
votes
1 answer

Computing a move score in a Minimax Tree of a certain depth

I've implemented a Chess game in C, with the following structs: move - which represents a move from (a,b) to (c,d) on a char board[8][8] (Chess board) moves - which is a linked list of moves with head and tail. Variables: playing_color is 'W' or…
Evgeny
  • 415
  • 4
  • 17
13
votes
5 answers

Alpha-beta pruning for Minimax

I have spent a whole day trying to implement minimax without really understanding it. Now, , I think I understand how minimax works, but not alpha-beta pruning. This is my understanding of minimax: Generate a list of all possible moves, up until…
apscience
  • 7,033
  • 11
  • 55
  • 89
12
votes
1 answer

How do you derive the time complexity of alpha-beta pruning?

I understand the basics of minimax and alpha-beta pruning. In all the literature, they talk about the time complexity for the best case is O(b^(d/2)) where b = branching factor and d = depth of the tree, and the base case is when all the preferred…
ozstudent
  • 381
  • 1
  • 5
  • 14
11
votes
1 answer

My implementation of the evaluation function and Alpha-beta pruning for Connect Four is not smart enough

I am trying to implement correctly the Connect Four game AI yet not to avail my AI acts stupid: It does not block the opposite player pattern which can lead to failure of the AI, It does not take moves that might lead to AI's victory. My project…
coderodde
  • 1,269
  • 4
  • 17
  • 34
11
votes
2 answers

Chess: Bug in Alpha-Beta

I am implementing a chess engine, and I have written a fairly complex alpha-beta search routine with quiescence search and transposition tables. However, I am observing a strange bug. The evaluation function is using piece-square tables, like this…
dylhunn
  • 989
  • 2
  • 8
  • 25
9
votes
1 answer

Minimax vs Alpha Beta Pruning algorithms

I recently implemented Minimax and Alpha Beta Pruning algorithms and I am 100% sure that(autograder) I implemented them correctly. But when I executed my program they behaved differently. I am 99% sure that the end state of minimax and Alpha beta…
Prethia
  • 1,183
  • 3
  • 11
  • 26
9
votes
2 answers

Chess: high branching factor

I'm trying to develop a simple chess engine, but I'm struggling with its performance. I've implemented Negamax with alpha-beta pruning and iterative deepening (without any additional heuristics), but I'm unable to get reasonable search time beyond…
Matis
  • 503
  • 5
  • 17
8
votes
2 answers

Monte Carlo Tree Search: Tree Policy for two player games

I am a little confused about how the MCTS "Tree Policy" is implemented. Every paper or article I read talks about going down the tree from the current game state(in MCTS teminology: the root for the player about to make a move). My question is how…
CS101
  • 444
  • 1
  • 6
  • 21
8
votes
1 answer

Chess Quiescence Search ist too extensive

I have been creating a simple chess engine in c# over the last month and made some nice progress on it. It is using a simple Alpha-Beta algorithm. In order to correct the Horizon-Effect, I tried to implement the Quiescence Search (and failed several…
xXliolauXx
  • 1,273
  • 1
  • 11
  • 25
8
votes
1 answer

How to display Alpha Beta Pruning algorithm result?

Updates Update 1 I tried this (2nd line): I added changing node color as first instruction in alphabeta function. I am getting this result: Green nodes are visited nodes. It looks like, algorithm is going throw nodes correctly, right? But how to…
Sharikov Vladislav
  • 7,049
  • 9
  • 50
  • 87
7
votes
2 answers

How to implement iterative deepening with alpha beta pruning

I'm writing a program to play Dots and Boxes and I want to increase my time efficiency by ordering the moves I consider in alphaBeta based on their heuristic values in a iterative deepening scheme. Essentially, I want to go into the search tree,…
A. Romer
  • 73
  • 1
  • 1
  • 7
1
2 3
…
20 21