Quote:
I'm using alpha-beta search to generate the best move and it seems to work for depth 1 and 2 but when I get to 3, it returns a move for the opposite player, 4 seems to work fine and when it gets to 5 it returns a completely invalid move.
The solution for case 5 is to make the board validate all moves. It should be impossible for your game logic to even consider making an invalid move. It sounds like your function to generate all moves is flawed. By validating all moves inside the board class, you can catch the case where the move is invalid and trace the logic back until you discover what piece of code thought that move was valid.
I'm looking at the code a little closer, and I see some odd things.
* You loop from i = 0 to 32, why 32?
* Why does a square appear to be a Vector or other container? You've changed the chess rules, but this didn't feature in your description [smile]
* To generate the valid moves, you should only need the current state of the board and either the index of a piece or the piece that knows its position (depending on how your code is set up).
* You should consider using constructor parameters for classes such as position. It should be impossible to create an invalid position instance (that is a good invariant to aim for).
* Position and Piece should be immutable objects. You could also make the board immutable.
* Doesn't "position" really describe a move (a from and to index), rather than a position.
* Your board class could do more than just validate if a move is valid for the piece, it can validate whether the currrent player is allowed move that piece, etc.
* You are using a single index encoded as an integer for your positions. This is ok, but be aware that it makes it much harder to debug, because you have to decode the "real" value. You could make a class to represent positions, which could be implemented using x,y pairs or an encoded index, but an appropriate toString() method will come in handy when viewing it in the debugger.
* I would be worried about how your generateValidMoves appears to be storing state in some object. Could it not simply return a list of Move instances?
Quote:
I'm not really sure what you mean by nested members of the board though! Do you mean that I can directly access and change the chessBoard array, etc instead of using get,set methods?
Kindof. I wasn't taking about get/set functions (these are the opposite of good design).
You shouldn't be accessing deeply nested members, like this:
board.chessBoard[move.endPosition].square.isEmpty()
You want to aim for one member access (a dot) per expression. Two dots is sometimes acceptable, but for such situations you can often move logic into the class in question.
For the given example, your board could have a function Board#isEmpty(Position).
Here is a skeleton of what your code could look like if all objects were immutable and the functions were made stateless (semi-psuedo code):
enum Player { Black, White; Player nextPlayer() { return this == White ? Black : White; }}interface Move { int destination();}interface Board { int squares(); boolean isEmpty(int index); Piece pieceAt(int index); Board makeMove(Move move);}interface Piece { boolean belongsTo(Player player);}class ChessRules { private ChessRules() { } public static List<Move> validMoves(Board board, int index);}class ChessHueristics { private ChessHueristics() { } public static int evaluateScore(Board board, Player player); public static int valueCapture(Piece attacker, Piece victim); public static int evaluateEndGame(Board board, Player player);}class MoveScore { private final Move move; private final int score; public MoveScore(Move move, int score) { this.move = move; this.score = score; } public Move getMove() { return move; } public int getScore() { return score; }}class MoveSearch { private static List<MoveScore> EvaluateMoves(Board board, Player player) { List<MoveScore> moveScores = new ArrayList<MoveScore>(); for (int index = 0; index < board.squares(); index++) { Piece piece = board.pieceAt(index); // skip empty squares if (piece == null) { continue; } // skip the other players pieces if (!piece.belongsTo(player)) { continue; } // generate valid moves for the piece List<Move> moves = ChessRules.validMoves(board, index); // for each valid move for (Move move : moves) { int score = 0; Piece attacked = board.pieceAt(move.destination()); // if a piece is attacked if (attacked != null) { // append its value to the move score score += ChessHueristics.valueCapture(piece, attacked); } // add the move to the set of positions moveScores.add(new MoveScore(move, score)); } } return moveScores; } private static int SideToMoveScore(Player player, Player currentMove, int score) { return player != currentMove ? -score : score; } public static int AlphaBeta(Player scoringPlayer, Player activePlayer, Board board, int depth, int alpha, int beta) { // if the depth is 0, return the score of the current board if (depth <= 0) { int score = ChessHueristics.evaluateScore(board, scoringPlayer); return SideToMoveScore(scoringPlayer, activePlayer, score); } // fill the positions with valid moves List<MoveScore> moveScores = EvaluateMoves(board, activePlayer); // if there are no available positions if (moveScores.isEmpty()) { return ChessHueristics.evaluateEndGame(board, scoringPlayer); } // for each position for (MoveScore moveScore : moveScores) { Move next = moveScore.getMove(); // temporarily copy the board Board copy = board.makeMove(next); // repeat the process recursively, decrementing the depth int result = AlphaBeta(scoringPlayer, activePlayer.nextPlayer(), copy, depth - 1, -beta, -alpha); int score = -result; // if the value returned is better than the current best score, replace it if (score >= beta) { // beta cut-off return beta; } if (score > alpha) { alpha = score; return alpha; } } // return the best score return alpha; } // AlphaBeta()}
Stateless implementations are easier to reason about (but incur a memory overhead, because each state must allocate memory). Much of your state isn't really being used anyway, Alpha beta pruning is stateless - you can calculate the score by examining the current state of the board, rather than recording the score as you go along.
