|
Algorithm Development Kit 1.0 |
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectalgs.model.gametree.NegMaxEvaluation
public class NegMaxEvaluation
Represents an Intelligent agent that uses the NegMax algorithm to select a move.
NegMax is a variation on MiniMax developed by Knuth/Moore (1975) that aims to simplify the evaluation of moves. Instead of alternating between MIN and MAX levels, each evaluation is a MAX that conforms to the following logic:
A / \ B C / \ |\ D E F G
At Level A, player aims to maximize the best scores of his children (B and C). A will ultimately select "the Maximum of the negative scores of its children". To make this work, non-terminal positions (i.e., A,B,C) return the maximum of the negative scores of its children as evaluated accordingly by the player. Thus PLAYER evaluates A, while OPPONENT evaluates the boards at B,C. Consider the OPPONENT'S two moves from state B that lead to D and E. These boards are evaluated according to PLAYER. If E is the stronger position (say 12) while D is weaker (say -3) then B "returns the max of the negation of its children's values". Thus B returns "-12". Assume in the subtree of C that position F evaluates to 4 and G evaluates to 7, thus C returns "-7". Now, A is choosing between B and C values, and it does so by selecting the max of the negated values. Thus A evaluates to MAX (-(-12), -(-7)) which results in a score of 12. Thus in position A, PLAYER can ensure a score of 12.
Truth be told, the more convoluted logic only seems to increase the complexity of the algorithm, since the return value is the same as MiniMax. The only true benefit lies in the future extension of NegMax with Alpha/Beta pruning.
The toString method is provided to make it a bit easier to debug.
Constructor Summary | |
---|---|
NegMaxEvaluation(int ply)
Create an evaluator with the given state. |
Method Summary | |
---|---|
IGameMove |
bestMove(IGameState s,
IPlayer player,
IPlayer opponent)
Initiates the NegMax computations by using its ply to determine the number of moves in advance to look. |
MoveEvaluation |
negmax(int ply,
IPlayer player,
IPlayer opponent)
Given the board state, Intelligent player is trying to determine where to make his move. |
java.lang.String |
toString()
Expose board state as string (useful for debugging purposes). |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait |
Constructor Detail |
---|
public NegMaxEvaluation(int ply)
bestMove
is invoked.
ply
- Depth to search.Method Detail |
---|
public IGameMove bestMove(IGameState s, IPlayer player, IPlayer opponent)
If no moves are available to player, then null is returned.
bestMove
in interface IEvaluation
s
- Initial Game Stateplayer
- The player making the next moveopponent
- The player's opponentpublic MoveEvaluation negmax(int ply, IPlayer player, IPlayer opponent)
Since we swap player and opponent each time, we always evaluate the board state to select move that Maximizes the negative score of our opponent.
ply
- the fixed depth to look ahead.player
- the current player.opponent
- the opponent.public java.lang.String toString()
toString
in class java.lang.Object
|
Algorithm Development Kit 1.0 | ||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |