public final Move negaMax(final Board chess_board, final Player opponent, final int depth) {
// calculate a decision using the negaMax
final ArrayList<Move> legalMoves = getPlayerLegalMoves();
int highest_seen_value = Integer.MIN_VALUE;
Move best_move = null;
int value = Integer.MIN_VALUE;
System.out.println("PLAYER " + getIdentity() + " SEARCH DEPTH : " + depth);
long path_time = 0;
int i = 1;
for (final Move move : legalMoves) {
try {
final Board b = new Board(chess_board);
final Player c = new Player(this);
final Player o = new Player(opponent);
path_time = System.currentTimeMillis();
System.out.print("\t MOVE " + (i++) + "/" + legalMoves.size() + " -> " + move + " ");
makeMove(b, c, o, move);
if (this.getIdentity() == Piece.WHITE_ALLEGIANCE) {
value = -negaMaxValue(b, o, c, depth - 1, move);
}
else {
value = negaMaxValue(b, o, c, depth - 1, move);
}
if (value > highest_seen_value) {
highest_seen_value = value;
best_move = move;
}
}
catch (final Exception e) {
}
System.out.println(System.currentTimeMillis() - path_time + " ms : SCORE = " + value);
}
return best_move;
}
private static int negaMaxValue(final Board chess_board,
final Player current_player,
final Player opponent_player,
final int depth,
final Move m) {
if (depth == 0 || current_player.isInCheckMate() || opponent_player.isInCheckMate()) {
return Board.evaluateBoard(chess_board, current_player, opponent_player);
}
final ArrayList<Move> legalMoves = current_player.getPlayerLegalMoves();
int highest_seen_value = Integer.MIN_VALUE;
int value = Integer.MIN_VALUE;
for (final Move move : legalMoves) {
try {
final Board b = new Board(chess_board);
final Player c = new Player(current_player);
final Player o = new Player(opponent_player);
makeMove(b, c, o, move);
value = -negaMaxValue(b, o, c, depth - 1, move);
if (value > highest_seen_value) {
highest_seen_value = value;
}
}
catch (final Exception e) {
}
}
return highest_seen_value;
}
Help with adding alpha-beta to my negamax
April 07, 2010 11:19 AM
I've written the code below, and tried several times to modify it to do alpha-beta based on psuedo-code I found on Wikipedia. As it stands, the code works beautifully, but when I tried to do the alpha beta enhancement, it does not seem to work. Can someone show me what I need to do to this code to make it work properly?
[Edited by - amir650 on April 7, 2010 12:13:28 PM]
21,607
April 07, 2010 12:07 PM
Perhaps you can post your attempt, to see what part you are not understanding.
Why are you flipping the sign depending on the side?
EDIT: Oh, and please use [source] tags instead of [code] tags.
Quote:if (this.getIdentity() == Piece.WHITE_ALLEGIANCE) { value = -negaMaxValue(b, o, c, depth - 1, move); } else { value = negaMaxValue(b, o, c, depth - 1, move); }
Why are you flipping the sign depending on the side?
EDIT: Oh, and please use [source] tags instead of [code] tags.
April 07, 2010 12:15 PM
Thanks for your response. I've updated the snippet of code with your suggestion. I will post my attempt shortly. With regards to your question about flipping the sign, it seems like I have to do this in order for the algorithm to work properly. Does that look like a mistake to you?
21,607
April 07, 2010 12:19 PM
Quote: Original post by amir650
[...] With regards to your question about flipping the sign, it seems like I have to do this in order for the algorithm to work properly. Does that look like a mistake to you?
Yes, the call to negaMaxValue should always have the `-' in front of it.
21,607
April 07, 2010 12:26 PM
A few random thoughts about your code:
* You don't need to initialize `value'. Actually, you should declare it inside the loop, right where you assign to it.
* You probably shouldn't be creating new objects to pass around whose turn it is. Can't you just pass the parameters that you were given, without making copies? And why do you need more than a single integer or even a boolean to specify whose turn it is?
* You may want to consider not making copies of the board and instead having an unMakeMove() function.
* I don't understand why you are silently catching all exceptions.
* You don't seem to be handling stalemate.
* You are not using the last parameter `m' in negaMaxValue; you don't need it.
* How does a Player object know if the player is in check mate, or what the legal moves are, if it doesn't know what the board looks like?
* You don't need to initialize `value'. Actually, you should declare it inside the loop, right where you assign to it.
* You probably shouldn't be creating new objects to pass around whose turn it is. Can't you just pass the parameters that you were given, without making copies? And why do you need more than a single integer or even a boolean to specify whose turn it is?
* You may want to consider not making copies of the board and instead having an unMakeMove() function.
* I don't understand why you are silently catching all exceptions.
* You don't seem to be handling stalemate.
* You are not using the last parameter `m' in negaMaxValue; you don't need it.
* How does a Player object know if the player is in check mate, or what the legal moves are, if it doesn't know what the board looks like?
April 07, 2010 12:35 PM
Quote:
A few random thoughts about your code:
* You don't need to initialize `value'. Actually, you should declare it inside the loop, right where you assign to it.
* You probably shouldn't be creating new objects to pass around whose turn it is. Can't you just pass the parameters that you were given, without making copies? And why do you need more than a single integer or even a boolean to specify whose turn it is?
* You may want to consider not making copies of the board and instead having an unMakeMove() function.
* I don't understand why you are silently catching all exceptions.
* You don't seem to be handling stalemate.
* You are not using the last parameter `m' in negaMaxValue; you don't need it.
1) I agree, but this shouldn't cause problems
2) You're right about this. Right now I store state in the Players, and I have copy constructors for everything -- I need to revisit this and optimize it. It shouldn't cause errors though
3) Agreed, see above point
4) The legal move list includes moves that are disputed - and determined to be illegal later -- like castling out of check, or a move that leaves the player in check. If the player attempts to make an illegal move, its an exception.
5) How do you conclude this? I am handling stalemate, not here though.
public void calculatePlayerMated(final Board chess_board, final Player opponent) { for (int i = 0; i < this.playerLegalMoves.size(); i++) { final Move m = this.playerLegalMoves.get(i); if (!movePutsPlayerInCheckFast(chess_board, opponent, m)) { return; } } if (isInCheck()) { setInCheckMate(true); findPlayerKing(chess_board).isCheckMated(true); } else { setInStaleMate(true); } }6) Agreed.
[Edited by - amir650 on April 7, 2010 12:35:17 PM]
21,607
April 07, 2010 12:39 PM
Errr... you quoted 6 points and answered 5. I also added more stuff while you were answering (my bad).
21,607
April 07, 2010 12:41 PM
About the stalemate: I don't see where in the search you stop in case of stalemate. Unless isInCheckMate() has very funny semantics, that is.
April 07, 2010 12:52 PM
I see your point. I just need to add this to the base case of the recursion. Good point.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
