Advertisement

Alpha-Beta Pruning

Started by March 27, 2010 02:41 PM
4 comments, last by rip-off 14 years, 7 months ago
Soo I'm making a variation of chess called Martian Chess, it's played on half of a chess board and has different rules for how pieces move. When a piece crosses half of the board it changes it's colour and becomes property of the other player. I have everything working so far except for the AI. 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. I've been looking at this code for days now, and googling, trying to explain it to myself, using eclipse debugger but I can't figure it out! I'd be really greatful if someone could look over it for me and tell me if they see any problems (or even just hints). MoveSearch.java

package martianchess;

import java.util.Vector;

public class MoveSearch {
	private Evaluation evaluate = new Evaluation();
	private int blackPlayerScore, whitePlayerScore;
	public MoveContent bestMove;
	
	public MoveSearch(int blackScore, int whiteScore) {
		blackPlayerScore = blackScore;
		whitePlayerScore = whiteScore;
	}
	
	private Vector<Position> EvaluateMoves(Board board) {
		Vector<Position> positions = new Vector<Position>();
		
		for (int i = 0; i < 32; i++) {
			Piece piece = null;
			if (!board.chessBoard.square.isEmpty()) {
				// store the piece
				piece = board.chessBoard.square.firstElement();
			}
			
			// skip empty squares
			if (piece == null) {
				continue;
			}
			// skip the other players pieces
			if (piece.pieceColour != board.whosMove) {
				continue;
			}
			
			// generate valid moves for the piece
			PieceValidMoves validMoves = new PieceValidMoves(board.chessBoard, i, board.whosMove);
			validMoves.generateMoves();
			
			// for each valid move
			for (int j = 0; j < piece.validMoves.size(); j++) {
				// store it as a position
				Position move = new Position();
				move.startPosition = i;
				move.endPosition = piece.validMoves.elementAt(j);
				Piece pieceAttacked = null;
				
				if (!board.chessBoard[move.endPosition].square.isEmpty()) {
					// if the end position is not empty, store the attacked piece
					pieceAttacked = board.chessBoard[move.endPosition].square.firstElement();
				}
				
				// if a piece is attacked
				if (pieceAttacked != null) {
					// append its value to the move score
					move.score += pieceAttacked.pieceValue;
					
					// if the moving pieces value is less than the value of the attacked piece
					if (piece.pieceValue < pieceAttacked.pieceValue) {
						// score extra points
						move.score += pieceAttacked.pieceValue - piece.pieceValue;
					}
				}
				
				// add the move to the set of positions
				positions.add(move);
			}
		}
		return positions;
	} // EvaluateMoves()
	
	private int SideToMoveScore(int score, PieceColour colour) {
		if (colour == PieceColour.Black){
			return -score;
		} else {
			return score;
		}
	}
	
	public int AlphaBeta(Board board, int depth, int alpha, int beta) {
		//int best = -9999;
		
		// if the depth is 0, return the score of the current board
		if (depth <= 0) {
			int boardScore = evaluate.EvaluateBoardScore(board);
			return SideToMoveScore(boardScore, board.whosMove);
		}
		
		// fill the positions with valid moves
		Vector<Position> positions = EvaluateMoves(board);
		
		// if there are no available positions
		if (positions.size() == 0) {
			// and its blacks move
			if (board.whosMove == PieceColour.Black) {
				if (blackPlayerScore > whitePlayerScore) {
					// and they are winning, return a high number
					return 9999;
				} else if (whitePlayerScore == blackPlayerScore) {
					// if its a draw, lower number
					return 500;
				} else {
					// if they are losing, return a very low number
					return -9999;
				}
			}
			if (board.whosMove == PieceColour.White) {
				if (whitePlayerScore > blackPlayerScore) {
					return 9999;
				} else if (blackPlayerScore == whitePlayerScore) {
					return 500;
				} else {
					return -9999;
				}
			}
		}
		
		// for each position
		for (int i = 0; i < positions.size(); i++) {
			// store the position
			Position move = positions.elementAt(i);
			// temporarily copy the board
			Board temp = board.copyBoard(board);
			// make the move
			temp.makeMove(move.startPosition, move.endPosition);
			for (int x = 0; x < 32; x++) {
				if (!temp.chessBoard[x].square.isEmpty()) {
					PieceValidMoves validMoves = new PieceValidMoves(temp.chessBoard, x, temp.whosMove);
					validMoves.generateMoves();
				}
			}
			// repeat the process recursively, decrementing the depth
			int val = -AlphaBeta(temp, depth - 1, -beta, -alpha);
			// if the value returned is better than the current best score, replace it
			if (val >= beta) {
				// beta cut-off
				return beta;
			}
			if (val > alpha) {
				alpha = val;
				bestMove = new MoveContent(alpha, move.startPosition, move.endPosition);
			}
		} 
		// return the best score
		return alpha;
	} // AlphaBeta()
}
And this is my makeMove method:

public void makeMove(int startPosition, int endPosition) {		
		// quick reference to selected piece and attacked piece
		Piece selectedPiece = null;
		if (!(chessBoard[startPosition].square.isEmpty())) {
			selectedPiece = chessBoard[startPosition].square.firstElement();
		}
		
		Piece attackedPiece = null;
		if (!(chessBoard[endPosition].square.isEmpty())) {
			attackedPiece = chessBoard[endPosition].square.firstElement();
		}
		
		// if a piece is taken, amend score
		if (!(chessBoard[endPosition].square.isEmpty()) && attackedPiece != null) {
			if (attackedPiece.pieceColour == PieceColour.White) {
				blackScore = blackScore + attackedPiece.pieceValue;
			}
			if (attackedPiece.pieceColour == PieceColour.Black) {
				whiteScore = whiteScore + attackedPiece.pieceValue;
			}
		}
		
		// actually move the piece
		chessBoard[endPosition].square.removeAllElements();
		chessBoard[endPosition].addPieceToSquare(selectedPiece);
		chessBoard[startPosition].square.removeAllElements();
		
		// changing piece colour based on position
		if (endPosition > 15) {
			selectedPiece.pieceColour = PieceColour.White;
		}
		if (endPosition <= 15) {
			selectedPiece.pieceColour = PieceColour.Black;
		}
		
		//change to other player
		if (whosMove == PieceColour.Black) whosMove = PieceColour.White;
		else if (whosMove == PieceColour.White) whosMove = PieceColour.Black;
	} // makeMove()
That code is a bit too long for me to read in depth right now, but I would say the following. My gut instincts are the following:
  • Invariants
    • how well does your board class prevent invalid moves?

    • Your code can access nested members of the board. This pretty much makes it impossible to verify any class invariants.


  • Java references
    • How confident are you in your deep copy code for the board?


  • Unit tests
    • If you split your code into smaller functions that can be automatically tested in isolation, then you can determine where the error lies through the process of elimination. Small, simple functions are far easier to verify than longer ones with more state.

Advertisement

Well the board class doesn't actually do any validation on the moves...what I'm doing is generating all of the possible valid moves for the board, then making all of those moves while calculating a score. 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?

And I'm pretty sure the copy code is working fine, the only way I could find to do this was serializing the object then deserializing, I did some testing with this and it did appear to work right!

:::Edit:::

It seems to be working better if at the beta cut-off part I exit out of the loop, however, I'm unsure of how to do this properly I can either break or continue. break; makes the program run ALOT faster but it just doesn't seem right...continue takes ALOT longer but I'm unsure...it just feels like a regular negamax search then :/

[Edited by - beckyj on March 27, 2010 6:10:11 PM]
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.
* You loop from i = 0 to 32, why 32?
The game is a weird variant of chess called Martian Chess that's only played on half of a board lol :/

* Why does a square appear to be a Vector or other container?
the actual chess board is an array of square vectors that hold Pieces (piece is also a class lol, the aim was to make it object oriented :/)

* 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).
When the program is first run it generates a move database consisting of every move for every piece on every square lol, the PieceValidMoves needs the colour of the piece to check that it's not going to capture its own piece or anything

* 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).
I think I worked out what the problem was with it returning an invalid move, the alphabeta method was returning a move too early, before it returned to the 'root move', so the move probably was valid for the board it was concerned with (if that makes sense), i figured this out because when it was white's turn, the computer was trying to move a black piece and vice versa...

* Position and Piece should be immutable objects. You could also make the board immutable.
Piece's change during the course of the game though, the rules of 'Martian Chess' say that if a piece crosses the other half of the board, it's colour inverts and it becomes property of the other player...so piece colour (which is defined in the piece object) changes alot.

* Doesn't "position" really describe a move (a from and to index), rather than a position.
I suppose it does lol, I'll probably change this later!

* 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 have drawn a grid with all the square numbers on it lol! I'm so used to using the 1D indexes now that it'll probably be harder for me to change now.

* 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?
generateMoves() stores the validMoves in the Piece object, but the first thing it does when it's run is removes all moves from the piece...which is probably a bad way to do it but when I started coding this I literally had no idea about anything lol (as you can probably tell...you'd hateee to see my GUI code)

* 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.

I know this is really bad lol, I'll probably change this soon too!

I know that my code is really bad and inefficient but I have to atleast demonstrate this in 4 weeks lol so I've been really rushed to just get everything done. Obviously at the end I'll refine it more for when I actually write my dissertation...and if I manage to finish in less than 4 weeks I'll obviously go over everything and find better ways!

I edited my above post though, I managed to 'fix' the alphabeta method (not sure if I've actually FIXED it or not) by not returning beta, but by breaking out of the loop or continuing. Pseudocode for the algorithm all shows that when alpha >= beta, we break out of the loop, this makes it run ALOT faster, even for the depths of 1 and 2, but it just doesn't seem right to me! I tried using a continue statement which seemed a little more right, but then it takes ALOT longer obviously. I just don't know what the right way to do it would be :/

Thanks ALOT for your posts though, they've been very helpful
Quote:
The game is a weird variant of chess called Martian Chess that's only played on half of a board lol :/

Sure, that makes sense. It is a good idea to make such values into named constants rather than "magic numbers". I considered that the board had a different size, but not that it wasn't square.
Quote:
* Why does a square appear to be a Vector or other container?
the actual chess board is an array of square vectors that hold Pieces (piece is also a class lol, the aim was to make it object oriented :/)

I don't understand, you have 32 squares... but from your code you only seem to use either one or no elements from each vector. You can replace the Vector with just a Piece instance, which is "null" if no piece is present.
Quote:
* 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).
When the program is first run it generates a move database consisting of every move for every piece on every square lol, the PieceValidMoves needs the colour of the piece to check that it's not going to capture its own piece or anything

I wouldn't do that, it would be easy to cause bugs where the valid move database is out of sync with the board. Instead, generate the valid moves "on demand".

Quote:
* Position and Piece should be immutable objects. You could also make the board immutable.
Piece's change during the course of the game though, the rules of 'Martian Chess' say that if a piece crosses the other half of the board, it's colour inverts and it becomes property of the other player...so piece colour (which is defined in the piece object) changes alot.

Just because something is immutable, doesn't mean you cannot track changes! Consider java.lang.String. The string class is immutable, you cannot change one once created. However, you can easily get substrings, or trim a string. All these operations return new, immutable strings.

This is what my board interface does, it says that if you move a piece, you get a new board with that piece moved.

Thus, to implement such a move function, you create a copy of the piece container. You then set the source position to null, and the destination to the new piece, or a new piece with the colour inverted (if across the line). Finally, you return a new Board() using the copied array. If the Piece class is immutable too, you can use a shallow copy of the piece instances.

Quote:
I have drawn a grid with all the square numbers on it lol! I'm so used to using the 1D indexes now that it'll probably be harder for me to change now.

Fair enough :)

Quote:
* 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?
generateMoves() stores the validMoves in the Piece object, but the first thing it does when it's run is removes all moves from the piece...which is probably a bad way to do it but when I started coding this I literally had no idea about anything lol (as you can probably tell...you'd hateee to see my GUI code)

Again, storing such "temporary" state is a recipe for bugs, it is too easy to forget to clear it or use it when the source data has been invalidated (e.g. another move has been made).

Quote:
I know that my code is really bad and inefficient ...

I wouldn't worry about efficiency, your code is ok enough for that. It isn't "bad" either, but because of the way you have set some things up there are opportunities for bugs which simply aren't possible is a codebase which features more stateless functions, more immutable objects and in general smaller functions that can easily be unit tested in isolation. Class invariants are very important - they are pretty much the reason to have access modifiers, so you can establish the invariant at construction time and enforce it in all subsequent method invocations. You might notice in my code that the Board class does not expose its inner storage, hence noone can make moves without using the supplied methods. This means that you can have exactly one place where all possible moves are checked, and once that code works you know that no other code can "break" your Board by putting it into an invalid state.
Quote:
I edited my above post though, I managed to 'fix' the alphabeta method (not sure if I've actually FIXED it or not) by not returning beta, but by breaking out of the loop or continuing. Pseudocode for the algorithm all shows that when alpha >= beta, we break out of the loop, this makes it run ALOT faster, even for the depths of 1 and 2, but it just doesn't seem right to me! I tried using a continue statement which seemed a little more right, but then it takes ALOT longer obviously. I just don't know what the right way to do it would be :/

Sounds like you need to read up more on Alpha/Beta pruning algorithm. If you don't understand how and why it works, it is going to be hard to debug it. I haven't touched the algorithm in a while, so I concentrated on clarifying the structure in my example, not the implementation algorithm.
Quote:
Thanks ALOT for your posts though, they've been very helpful

No problem.

This topic is closed to new replies.

Advertisement