GODPAPER | All Packages | All Classes | Index | Frames No Frames |
NegaMax

Package | com.lookbackon.AI.searching
Class | public class NegaMax
Inheritance | NegaMax SearchingBase AbstractProcess Object

The normal MiniMax code is a bit clumsy, since one side is trying to maximize the value and the other is trying to minimize - therefore, with MiniMax we always have to check if we are the side trying to maximize or the side trying to minimize. A neat way to get rid of this and to have a simpler function is NegaMax. With the NegaMax algorithm both sides try to maximize all the time. NegaMax is identical to MiniMax, it's just a nicer formulation. You can see that the NegaMax algorithm is shorter and simpler than the MiniMax algorithm. At first sight, NegaMax is a bit harder to understand than MiniMax, but it's in fact much easier to use. The side to move is always trying to maximize the value. NegaMax is no better or worse than MiniMax - it's identical. It's just a better framework to use.

See also

http://www.fierz.ch/strategy.htm

Public Properties
Hide Inherited Public Properties
Show Inherited Public Properties

| Property | Defined By
--- | --- | ---
|  | captures : Vector.<ConductVO> [read-only] This function generates all possible captures and stores them in the vector. It returns the vector of the legal captures for Quiescene searching. | SearchingBase
|  | evaluation : IEvaluation | SearchingBase
|  | isSelfManaging : Boolean | AbstractProcess
|  | moves : Vector.<ConductVO> [read-only] | SearchingBase
|  | orderingMoves : Vector.<ConductVO> Ordering Moves To Speed Up Search As we will see next time, search efficiency depends on the order in which moves are searched. The gains and losses related to good or poor move ordering are not trivial: a good ordering, defined as one which will cause a large number of cutoffs, will result in a search tree about the square root of the size of the tree associated with the worst possible ordering! Unfortunately, it turns out that the best possible ordering is simply defined by trying the best move first. | SearchingBase
|  | percentage : Number [override] [read-only] inheritDoc | SearchingBase
|  | processDone : Boolean | SearchingBase

Protected Properties
Hide Inherited Protected Properties
Show Inherited Protected Properties

| Property | Defined By
--- | --- | ---
|  | alpha : int | SearchingBase
|  | bestMove : ConductVO | SearchingBase
|  | bestValue : int | SearchingBase
|  | beta : int | SearchingBase
|  | chessBoardModel : ChessBoardModel | SearchingBase
|  | chessGasketsModel : ChessGasketsModel | SearchingBase
|  | chessPiecesModel : ChessPiecesModel | SearchingBase
|  | depth : int | SearchingBase
|  | gamePosition : PositionVO | SearchingBase
|  | generatedMoves : Vector.<ConductVO> | SearchingBase
|  | _isSelfManaging : Boolean | AbstractProcess
|  | positionEvaluated : int | SearchingBase
|  | tempCapture : ConductVO | SearchingBase
|  | tempMove : ConductVO | SearchingBase
|  | tempValue : int | SearchingBase

Public Methods
Hide Inherited Public Methods
Show Inherited Public Methods

| Method | Defined By
--- | --- | ---
|  | NegaMax(gamePosition:PositionVO, depth:int) | NegaMax
|  | applyMove(conductVO:ConductVO):void | SearchingBase
|  | doEvaluation(conductVO:ConductVO, gamePosition:PositionVO):int [override] The point is that the call value = -negamax(p,d-1); takes care of the signs - or nearly. | NegaMax
|  | generateMoves(pieces:Vector.<ChessPiece>):Vector.<ConductVO> This function generates all possible moves and stores them in the vector. It returns the vector of the legal moves. While is checking,defend moves with high priority. | SearchingBase
|  | makeMove(conductVO:ConductVO):void Obviously,the struct move must contain all information necessary to support this operations. As always,the structures are passed by reference, in this case it is not only a speed question: the position will be modified by this functions. | SearchingBase
|  | noneMove():int | SearchingBase
|  | run():void [override] | NegaMax
|  | runAndManage(allocation:int):void | AbstractProcess
|  | terminate():void | AbstractProcess
|  | unmakeMove(conductVO:ConductVO):void Unmake previous move,for all kinds of searching tree algorithms. | SearchingBase
|  | willNoneMove(gamePosition:PositionVO):Boolean | SearchingBase
|  | yield():void | AbstractProcess

Public Constants
Hide Inherited Public Constants
Show Inherited Public Constants

| Constant | Defined By
--- | --- | ---
|  | MAX_SEARCH_DEPTH : int = 5 | SearchingBase

Constructor Detail

NegaMax | () | Constructor

`public function NegaMax(gamePosition:PositionVO, depth:int)`

Parameters

| `gamePosition:PositionVO`
| `depth:int`

Method Detail

doEvaluation | () | method

`override public function doEvaluation(conductVO:ConductVO, gamePosition:PositionVO):int`

The point is that the call value = -negamax(p,d-1); takes care of the signs - or nearly. There is one further modification we must make for this code to work: The evaluation function must be sensitive to the side to move - for a position with red to move it must return its normal evaluation, for a position with blue to move it must return -evaluation.

Parameters

| `conductVO:ConductVO`
| `gamePosition:PositionVO`

Returns

| `int` — evaluation result

run | () | method |

`override public function run():void`

Thu Jan 16 2014, 01:11 PM +08:00