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

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

MiniMax.as class. The idea here is that both players will try all possible moves in their position and then choose, respectively, the one which makes the value of the position as high as possible (the white side) or as low as possible (black). I have called one color 'WHITE', this is the side which tries to maximize the value, and the other side tries to minimize the value. You can see that player 'WHITE' starts with a value of -INFINITY, and then goes on to try every move, and always maximizes the best value so far with the value of the current move. The other player, BLACK, will start out with +INFINITY and try to reduce this value. Note how I use a function checkwin(p) to detect a winning position during the tree search. If you only check winning conditions at the end of your variation, you can generate variations where both sides have won, for instance in connect 4 you could generate a variation where first one side connects four, and later the other side does. Also, note the use of handlenomove(p) - that's what you need to do when you have no legal move left. In checkers you will lose, in chess it's a draw. If the (average) number of possible moves at each node is N, you see that you have to search N^D positions to search to depth D. N is called the branching factor. Typical branching factors are 40 for chess, 7 for connect 4, 10 for checkers and 300 for go. The larger the branching factor is, the less far you will be able to search with this technique. This is the main reason that a game like connect 4 has been solved, that checkers programs are better than humans, chess programs are very strong already, but go programs are still playing very poorly - always when compared to humans.

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
--- | --- | ---
|  | MiniMax(gamePosition:PositionVO, depth:int = 5) | MiniMax
|  | 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] | MiniMax
|  | 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

MiniMax | () | Constructor

`public function MiniMax(gamePosition:PositionVO, depth:int = 5)`

Parameters

| `gamePosition:PositionVO`
| `depth:int` (default = `5`)``

Method Detail

run | () | method

`override public function run():void`

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