Negamax Algorithm (I am a beginner to this),
Members - Reputation: 100
Posted 16 May 2010 - 03:57 PM
Members - Reputation: 100
Posted 19 May 2010 - 11:43 AM
A Negamax algorithm is a way of selecting the best possible move/decision from a range of all possible decisions. The algorithm trys to "look into the future" to predict what the opponent is going to do. From all the possible outcomes, the algorithm selects the move that will give it the greatest advantage while giving the opponent the greatest DISadvantage, hence the term Negamax/Minimax.
There are a couple of things that are important to remember:
1) This algorithm only works for a turn-based game that has a finite number of possible decisions (pokemon, blackjack, connect 4, naughts and crosses etc)
2) The algorithm always assumes that the opponent will choose the best possible move (no human error).
3) Before the algorithm is started, you have to decide how far into the future you're going to look. This is quite important because the number of calculations that are required to look one step further into the future increases exponentially. If you look too far into the future the algorithm is going to slow down to a crawl. Too near in the future and the algorithm doesn't make intellegent decisions.
4) You have to create some sort of scoring algorithm to determine how "good" any situation is for the player. This can be as simple as "Have I won?" (for things like naughts and crosses) or you can use some sort of points system (for things like connect-4 or chess ).
After you've worked all of this out, you can begin to evaluate the moves. This is done in pairs of plies and replies. A ply is a set of every single possible move that can occur in your turn (taking into account every move that could have occured last turn as well). A reply is the same thing, but for your opponent. You have to evaluate each situation in its final form, then work backwards from there to find the correct move (this makes the algorithm recursive, as you'll see on the wiki page). with each reply you choose the move that gives you the greatest negative effect (the opponents best move) and with each ply you choose the least negative effect (your best move considering that the opponent will choose the best move for them).
That's a really high-level overview of the algorithm (I really hope I haven't got anything wrong) and it doesn't go into the technical implementation, but hopefully you've gained something from this post.
Wikipedia has a really good gif that goes through the algorithm step by step.
Crossbones+ - Reputation: 19325
Posted 19 May 2010 - 11:57 AM
If you read through his items 1.A, 1.B and 1.C you'll probably understand enough to implement NegaMax with alpha-beta pruning.
By the way, almost everything in the original post is wrong: Knuth and Moore didn't actually invent this algorithm, but they did write a clear paper about it in 1975. Also, the "basic thing in AI" is maximization of expected utility, of which alpha-beta is a special case. And the most important thing in developing games is determining what the players do (the gameplay), not AI. There are some good games that don't have AI at all (e.g., Tetris).