Started by May 16 2010 03:57 PM

,
4 replies to this topic

Posted 16 May 2010 - 03:57 PM

I am new to game programming.And I know Artificial Intelligence Algorithm is the most important things in developing games.
As everyone knows, Nagemax is the basic things in AI. It was found by Knuth
and Moore. But I can't understand it clearly. Can anyone recommand some books or papers to me that help me understand it. And the example in internet is obscurity. Can anyone know a example that clearly explain it .
Thanks very much

Posted 16 May 2010 - 09:44 PM

Basically, it's just "what's good for me is bad for my opponent".

Posted 19 May 2010 - 11:43 AM

I don't know any books but I'll give it a go...

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.

http://en.wikipedia.org/wiki/File:Plain_Negamax.gif

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.

http://en.wikipedia.org/wiki/File:Plain_Negamax.gif

Posted 19 May 2010 - 11:57 AM

One of the best resources about chess programming is Bruce Moreland's programming pages. He stopped hosting them a few years ago, but they are still accessible through www.archive.org.

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).

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).