Algorithm
Development Kit 1.0

algs.model.gametree
Class NegMaxEvaluation

java.lang.Object
  extended by algs.model.gametree.NegMaxEvaluation
All Implemented Interfaces:
IEvaluation

public class NegMaxEvaluation
extends java.lang.Object
implements IEvaluation

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.

Since:
1.0
Version:
1.0, 6/15/08
Author:
George Heineman

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

NegMaxEvaluation

public NegMaxEvaluation(int ply)
Create an evaluator with the given state. It is important that the same player evaluate the board regardless of MIN and MAX. The player will be known when bestMove is invoked.

Parameters:
ply - Depth to search.
Method Detail

bestMove

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

If no moves are available to player, then null is returned.

Specified by:
bestMove in interface IEvaluation
Parameters:
s - Initial Game State
player - The player making the next move
opponent - The player's opponent

negmax

public MoveEvaluation negmax(int ply,
                             IPlayer player,
                             IPlayer opponent)
Given the board state, Intelligent player is trying to determine where to make his move. The decision will be made based upon trying all possible moves for Intelligent player and determining which one produces maximum getScore() evaluation.

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.

Parameters:
ply - the fixed depth to look ahead.
player - the current player.
opponent - the opponent.

toString

public java.lang.String toString()
Expose board state as string (useful for debugging purposes).

Overrides:
toString in class java.lang.Object

Algorithm Development Kit 1.0

This code supports the Algorithms in a Nutshell book, published by O'Reilly Media, Inc. in November 2008. Please visit the book web page to learn of any changes to the code repository or to record a potential defect.