CODEWITHSUNDEEP
algorithmminimax
TheRapture87
TheRapture87

Reputation: 1423

Minimax Algorithm Advantages / Disadvantages

A disadvantage of the minimax algorithm is that each board state has to be visited twice: one time to find its children and a second time to evaluate the heuristic value.

Are there any other disadvantages or advantages to the minimax algorithm? Say for a game like Chess, would there be any better alternatives? (Of course minimax with alpha-beta pruning but anything else?)

Upvotes: 0

Views: 12234

Answers (1)

Felipe Sulser
Felipe Sulser

Reputation: 1205

Minimax tends to be too slow for games such as chess. For each turn, the player has many choices to decide on, the branching factor of a game of chess is huge and therefore the deeper we go, the slower it gets. On average, the branching factor for chess tends to 30. This is, 30 subtrees per turn are created.

Before giving specific algorithms, they all use what we call alpha beta pruning. Alpha beta reduces the number of nodes to be expanded and therefore we reduce the branching factor.

Keep in mind that there are many different variations of minimax and alpha beta but the most important algorithms are:

  • Negamax: The idea here is that the score for a move for one player is always -ve of the other player but same magnitude that allows you to calculate max(a,b) = -min(-a,-b).

Simple interpretation:

score = -negamax(depth-1,-player)
best = max(score,best)

Windowed search algorithms

The following algorithms use a window in order to reduce the search space. The window would be to assume a value for alpha and beta initially.

  • Principal Variation Method: This method reduces the number of nodes visited by "guessing" the initial alpha and beta. It does so by exploring only one branch and selecting the candidate value. Using this value we prune. If we find a contradiction, this is a value that yields a higher score than the candidate we start again chaning the candidate.

  • MTD(f) Another variation of minimax. Uses Zero-Window Searches. This means, after we find the candidate (say "v"), we assume that the alpha beta values will be (v-1,v) therefore only v is the possible solution. If we find a contradiction, change candidate and repeat.

Also the best and most used algorithm nowadays for chess computer programs is MTD(f) with some variations/heuristics.

Sources:Converting Minimax to Negamax (python)

Upvotes: 3

Related Questions