|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectfourwin.FourPlayer
fourwin.fourMiniMax
public class fourMiniMax
Implements the MiniMax algorithm with Alpha-Beta pruning to find the robot's next move based on the current situation. See Maximize() method for details about the algorithm.
FourPlayer
,
Maximize(int, int, PlayingField, int, int)
Field Summary | |
---|---|
private int |
moves
Is used to count the number of precalculated moves |
private byte |
nextMove
Is set by the algorithm to determine the next move to be done. |
private byte |
opponentColorValue
Deprecated. |
private byte |
treeDepth
Sets the maximum depth in the tree of possible moves. |
Fields inherited from class fourwin.FourPlayer |
---|
color, colorValue, opponentID, playerID |
Constructor Summary | |
---|---|
fourMiniMax()
Constructor to create an AI object using Alpha-Beta pruning with default search depth. |
|
fourMiniMax(int treeDepth)
Constructor to create an AI player using Alpha-Beta pruning with specified search depth. |
Method Summary | |
---|---|
private int |
IntSignum(int value)
Deprecated. |
private int |
Maximize(int levelsToGo,
int levels,
PlayingField board,
int alpha,
int beta)
Describes a maximizing node in the tree of possible moves. |
private int |
Minimize(int levelsToGo,
int levels,
PlayingField board,
int alpha,
int beta)
Describes a minimizing node in the tree of possible moves. |
PlayingField |
move(PlayingField board)
|
Methods inherited from class fourwin.FourPlayer |
---|
getColor |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Field Detail |
---|
private byte nextMove
@Deprecated private byte opponentColorValue
private byte treeDepth
private int moves
Constructor Detail |
---|
public fourMiniMax()
public fourMiniMax(int treeDepth)
treeDepth
- Determines the depth of the tree of possible moves.Method Detail |
---|
public PlayingField move(PlayingField board)
move
in class FourPlayer
private int Maximize(int levelsToGo, int levels, PlayingField board, int alpha, int beta)
Describes a maximizing node in the tree of possible moves.
It is the maximizing method of the MiniMax algorithm. It searches the maximum value from the next level in the tree of moves. Alpha-Beta pruning is used to cut the tree if it's branches cannot affect the final result.
If the maximum search depth is reached the method uses the Evaluate() method of PlayingField to get an evaluation value which is higher for better initial situations for the AI player.
The maximum of this value is searched in the tree to perform the best move which is possible. Every second level is an opponent move which means that the evaluated value is minimized in that levels. Because of that the alpha-beta pruning allows to cut needless branches if the higher value would be ignored by a minimizing node.
The method is called alternating with the Minimize method to build the tree of moves. Every call of Maximize() or Minimize() is equivalent to another level in the tree in the current branch.
First the two methods define the possible moves and iterate through them simulating the move by using the insertChip() method of PlayingField. The maximum or minimum of the evaluated value at the end of the tree is searched. After all moves has been simulated, the chips are removed from the board.
levelsToGo
- Remaining search depthlevels
- total search depthboard
- current board situation.alpha
- Is set by the algorithm itself. Use lowest possible value in initial call.beta
- Is set by the algorithm itself. Use highest possible value in initial call.
Minimize(int, int, PlayingField, int, int)
,
PlayingField.Evaluate(int)
,
PlayingField.getPossibleMoves()
private int Minimize(int levelsToGo, int levels, PlayingField board, int alpha, int beta)
Describes a minimizing node in the tree of possible moves.
The documentation of Maximize() describes the whole algorithm including the Minimize method. Please read the Maximize() documentation.
levelsToGo
- Remaining search depthlevels
- total search depthboard
- current board situation.alpha
- beta
-
Maximize(int, int, PlayingField, int, int)
@Deprecated private int IntSignum(int value)
value
-
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |