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

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

PVS.as class. Principal variation searching Windowing is simple and it is quite good. However, windowing is restricted to the root node. PVS tries to go a bit further by making assumptions on the alpha-beta window at every node. Here's the basic idea: Since we have gone to a lot of trouble with our move ordering schemes above, we can be pretty confident that we will find the best move early on. Therefore, our localalpha will be at its maximal value after the first few moves. PVS tries to exploit this by calling the next recursion of AlphaBeta with different parameters than standard-AlphaBeta. AlphaBeta would use alpha and beta. In PVS however, we already guess that our current localalpha will be better than what we will get with the remaining moves. Therefore we set alpha to localalpha and beta to localalpha+1, that is, we use a call value=-alphabeta(p,d-1,-(localalpha+1),-localalpha); We expect this call to fail low, because we believe that we have already found the best move. If this call does not fail low, we need to revise our assumption and call AlphaBeta again with the normal alpha and beta bounds. PVS is also often called NegaScout. It gets its name from the scout search which a minimal window, which sort of probes the territory to see whether a real search is necessary.

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
--- | --- | ---
|  | PVS(gamePosition:PositionVO, alpha:int, beta:int, depth:int = 2) | PVS
|  | 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] | PVS
|  | 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

PVS | () | Constructor

`public function PVS(gamePosition:PositionVO, alpha:int, beta:int, depth:int = 2)`

Parameters

| `gamePosition:PositionVO`
| `alpha:int` (default = `NaN`)``
| `beta:int` (default = `NaN`)``
| `depth:int` (default = `2`)``

Method Detail

run | () | method

`override public function run():void`

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