我一直在为 Connect Four 游戏编写 alpha-beta 修剪代码，但我似乎无法做到正确。我以为我一开始就正确地实现了它，但是算法每次都会返回第 1 列。我有两个intvalnodeVal用于确定我的 alpha 和 beta 值。当我在alphaBetaPruning()算法中将它们实例化为 0 时，该alphaBetaSearch()方法返回的列始终为 1。如果我在算法之外实例化这些值alphaBetaPruning()，alphaBetaSearch()算法会产生Null Pointer Exception
.
注意：ConnectFourBoard班级拥有董事会州最好的孩子。
任何帮助，将不胜感激！
public class ConnectFourPlayer
{
private final int columns = 7;
private char currentPlayer;
private char computer = 'C';
private char opponent = 'P';
private int depth = 8;
//private int val = 0;
//private int nodeVal = 0;
private int minMax;
/**
* Constructor method creates the computer
* player.
*/
public ConnectFourPlayer()
{
}
/**
* Method returns the number of children
* given a board state.
*/
public int numberOfChildren(ConnectFourBoard board)
{
int count = 0;
//count number of columns with empty slots
for (int col = 0; col < columns; col++)
{
for (int row = 0; row < 6; row++)
{
if ( board.board[row][col] == ' ')
{
count++;
break;
}
}
}
return count;
}
/**
* Method generates the children of a given
* board state and stores them in the array
* boardChildren[]. The array boardChildren
* is the size of the number of possible
* children.
*/
public void generateChildren(ConnectFourBoard board)
{
board.boardChildren = new ConnectFourBoard[this.numberOfChildren(board)];
int childNumber = 0;
for (int boardCol = 0; boardCol < columns; boardCol++)
{
for (int boardRow = 0; boardRow < 6; boardRow++)
{
if ( board.board[boardRow][boardCol] == ' ' )
{
ConnectFourBoard childBoard = new ConnectFourBoard();
for(int row = 0; row < 6; row++)
{
for(int col = 0; col < columns; col++)
{
childBoard.board[row][col] = board.board[row][col];
}
}
childBoard.row = boardRow;
childBoard.column = boardCol;
childBoard.board[boardRow][boardCol] = currentPlayer;
board.boardChildren[childNumber] = childBoard;
childNumber++;
break;
}
}
}
}
/**
* Method implements the alphaBetaPruning algorithm.
* Returns the column that corresponds to that
* column with the highest alphaBetaPruning value.
*/
public int alphaBetaSearch(ConnectFourBoard board)
{
minMax = 1;
currentPlayer = computer;
alphaBetaPruning(board, this.depth, Integer.MIN_VALUE, Integer.MAX_VALUE);
return board.best.column;
}
/**
* Method returns the static evaluation function value of the
* best possible move that will maximize the computer player's
* move value and also minimize the opponent's move value,
* given a depth limit.
*/
public int alphaBetaPruning(ConnectFourBoard board, int depth, int alpha, int beta)
{
//create StaticEvaluationFunction object to evaluate each possible move
StaticEvaluationFunction evaluator = new StaticEvaluationFunction();
int val = 0;
int nodeVal = 0;
//check if the computer is in a goal state
if(board.gameOver() == 'C')
{
board.best = null;
return evaluator.evaluate(board, this.currentPlayer);
}
//check if depth limit was reached
if(depth == 0)
{
board.best = null;
return evaluator.evaluate(board, this.currentPlayer);
}
//fill the boardChildren[] array with all children of the current board
this.generateChildren(board);
int width = this.numberOfChildren(board);
//check if the current board state has any children
if(width == 0)
{
board.best = null;
return evaluator.evaluate(board, this.currentPlayer);
}
else
{
int i = 0;
boolean prune = false;
while((!prune) && (i < width))
{
//recursive call to alphaBetaPruning()
val = alphaBetaPruning(board.boardChildren[i], (depth - 1), alpha, beta);
if(i == 0)
nodeVal = val;
//check if current board is a minNode
if(minNode(board))
{
//check current child < smallest child so far
if(val < nodeVal)
{
//set nodeVal to smaller child
nodeVal = val;
//set best to this child board
board.best = board.boardChildren[i];
}
//check current child < smallest child so far (local)
if(val < beta)
//set beta to smaller child
beta = val;
}
//check if current board is a maxNode
if(maxNode(board))
{
//check current child > biggest child so far
if(val > nodeVal)
{
//set nodeVal to bigger child
nodeVal = val;
//set best to this child board
board.best = board.boardChildren[i];
}
//check current child > biggest child so far (local)
if(val > alpha)
//set alpha to bigger child
alpha = val;
}
//check max so far > min so far
if(alpha > beta)
{
//prune
prune = true;
return nodeVal;
}
else i++;
}//end while
}
return nodeVal;
}
/**
* Method returns true if the given board state is
* a max node.
*/
public boolean maxNode(ConnectFourBoard board)
{
if(minMax == 1)
{
minMax = 0;
currentPlayer = opponent;
return true;
}
return false;
}
/**
* Method returns true if the given board state is
* a min node.
*/
public boolean minNode(ConnectFourBoard board)
{
if(minMax == 0)
{
minMax = 1;
currentPlayer = computer;
return true;
}
return false;
}
}
/**Holds the state of the board*/
public class ConnectFourBoard
{
public final int rows = 6;
public final int columns = 7;
public char board[][] = new char[rows][columns];
public ConnectFourBoard boardChildren[];
public ConnectFourBoard best;
public int column;
public int row;
...
/**
* Method makes the computer player's move. First,
* checks if a move is allowed. If it is, that
* slot is set to the computer player's character.
* Returns true is a move is made and false
* otherwise.
*/
public int generateComputerPlayerMove(ConnectFourPlayer computer)
{
int column = computer.alphaBetaSearch(this);
//update grid
for(int row = 0; row < board.length; row++)
{
if(board[row][column] == ' ')
{
board[row][column] = 'C';
break;
}
}
return column;
}
}