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

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

Search enhancements All techniques above aimed at reducing the number of nodes to search by better move ordering. There is another class of enhancements with the same goal, but with different means. These enhancements try to exploit the nature of the AlphaBeta algorithm, which has to search fewer nodes when the alpha-beta window is smaller. Note how AlphaBeta receives the parameters alpha and beta which tell it what range the value of the current position should lie. Once a move has returned with a higher value than alpha, this best value is saved in the variable localalpha and used for the next recursive call of AlphaBeta. If the best value is larger than beta, the search terminates immediately - we have found a move which refutes the notion that this position has a value in the range from alpha to beta, and do not need to look for another one. Note how my AlphaBeta function is returning the highest value it found, this can be higher than beta. Some people prefer to return beta instead of the best value on a fail high, that formulation of AlphaBeta is known as fail-hard. My formulation above is called fail-soft. The names come from the fact that in fail hard, the bounds alpha and beta are "hard", the return value cannot be outside the alpha-beta window. It would seem that fail-soft is much more sensible, as it might lead to more cutoffs: If you can return a higher value than beta (or a lower value than alpha), then perhaps you might get a cutoff in a previous instance of AlphBeta at a lower level in the search tree that you wouldn't get otherwise. However, the fail-hard camp says they get less search instabilities when using advanced techniques such as pruning.

See also

http://www.fierz.ch/strategy1.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
--- | --- | ---
|  | AlphaBeta(gamePosition:PositionVO, depth:int = 1, alpha:int, beta:int) The major improvement over MiniMax/NegaMax is the AlphaBeta algorithm: Here you realize that you don't have to go through the whole search tree. | AlphaBeta
|  | applyMove(conductVO:ConductVO):void | SearchingBase
|  | doEvaluation(conductVO:ConductVO, gamePosition:PositionVO):int The evaluation function will return positive values if the position is good for red and negative values. if the position is bad for red in the MinMax formulation. Many things could be said about evaluation functions, for me,the two main objectives in designing a evaluation function are speed and accuracy. The faster your evaluation function is,the better is. and the more accurate its evaluation is,the beeter. Obviously,these two things are somewhat at odds: an accurate evaluation function probably is slower than a 'quick-and-dirty' one. The evaluation function I'm taking about here is a heuristic one -not a exact one. | SearchingBase
|  | 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] | AlphaBeta
|  | 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

AlphaBeta | () | Constructor

`public function AlphaBeta(gamePosition:PositionVO, depth:int = 1, alpha:int, beta:int)`

The major improvement over MiniMax/NegaMax is the AlphaBeta algorithm: Here you realize that you don't have to go through the whole search tree. If you find one winning continuation, you don't have to look at any others. Similarly, if you have found one continuation which will give you the value V you can stop your search along another continuation if you find only one possibility for your opponent which gives you a lower score than V. You don't have to look at all the other possibilities your opponent might have - one refutation is enough! Here is the code for AlphaBeta, extending the earlier NegaMax code: It receives two extra parameters, alpha and beta. They define an interval within which the evaluation has to be. If it isn't, the function will return. Your first call to AlphaBeta will be with an interval -INFINITY...INFINITY; subsequent recursive calls to the function will make the window smaller.

Parameters

| `gamePosition:PositionVO` — the piece's postion in board.
| `depth:int` (default = `1`)`` — the piece's depth in this game tree.
| `alpha:int` (default = `NaN`)`` — INFINITY.
| `beta:int` (default = `NaN`)`` — -INFINITY.

See also

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

run | () | method

`override public function run():void`

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