Intro
We're moving right along with this sizable project, a Web API that will tell you the "best" move to make for a given chess position/game. We've created a test page, a Web API for clients to call, and we're still in the middle of calculating valid moves. If you need a refresher, look back through the history of this blog and find parts 1-7; they'll give you the info you need. On to part 8!Can't Put Your Own King in Check
As I mentioned last week, there is still one major restriction we need to code: you cannot make a move that puts your own king in check. Here is an illustration of such an illegal move:
(white's turn)
Normally the white pawn at d2 (the one with the red arrow pointing at it) could move forward/up one square to d3, or two squares to d4. However, because the black bishop on b4 would threaten the king if the pawn moved out of the way, the pawn cannot in fact move from its current location. This is the type of move we are trying to prevent, so let's figure out how to do that.
Logically speaking, the best thing I can come up with is to pretend that the white piece has moved, and then check the valid moves of all the black pieces. If a black piece would be capable of "taking" the white king, then the previous move was invalid. Keep in mind that this invalidity could count for any type of piece; a pawn move can't put your king in danger, a rook move can't, and so on. This means a logical place to put the code would be in AddMoveToList, as it's already called every single time we add a move to, well, the list.
This isn't where we'll start though. We'll first create a method that tells us if the king is in check. We'll be creative and call it IsKingInCheck. Here's the code for it:
protected bool IsKingInCheck(bool colorIsWhite, ChessBoard board)
{
var kingPosition = FindKing(colorIsWhite, board);
return ColorThreatensSquare(!colorIsWhite, board, kingPosition.Item1, kingPosition.Item2);
}
Pretty short and sweet; we find the king, and then return a boolean telling us if the opposite color threatens the square that the king is on. We haven't yet created the FindKing function though, so let's do that now:
protected Tuple<short, short> FindKing(bool colorIsWhite, ChessBoard board)
{
short kingPieceValue = (short)(Constants.King * (colorIsWhite ? Constants.WhiteTransform : Constants.BlackTransform));
for (short row = 0; row < 8; row++)
{
for (short col = 0; col < 8; col++)
{
if (board.Board[row, col] == kingPieceValue)
return new Tuple<short, short>(row, col);
}
}
throw new Exception("King not found");
}
This method determines what the short constant value is for the king based on the color we are looking for, then loops through the board to find the king on it. If there is no king we throw an exception.
It's worth pointing out now that we only need to traverse 1 branch into the tree to check for checks; after all, when you're checking if a piece threatens the king, you don't really care if the piece can actually make the move; you only care if the square is threatened. Because of this we now need to create a new field of class ChessValidMoveCalculator that tells us whether we should allow multi-layer traversal of the tree:
protected bool m_allowCheckSubTrees = true;
If you'll recall, IsKingInCheck calls the pre-existing function ColorThreatensSquare. It is in this function that we calculate the next color's valid moves to see if a square is threatened, so it's in this method that we need to set m_allowCheckSubTrees to false. Here's the updated version of this function:
public bool ColorThreatensSquare(bool colorIsWhite, ChessBoard board, short row, short col)
{
var game = new ChessGame();
var positions = new List<ChessBoard>();
positions.Add(new ChessBoard(true) { Board = (short[,])board.Board.Clone() });
game.Positions = positions.ToList();
game.GameStatus = colorIsWhite ? GameStatus.WhitesTurn : GameStatus.BlacksTurn;
var futureCalculator = new ChessValidMoveCalculator(game);
futureCalculator.m_allowCheckSubTrees = false;
var futurePositions = futureCalculator.CalculateValidMoves();
var colorSign = colorIsWhite ? Constants.WhiteTransform : Constants.BlackTransform;
foreach (var position in futurePositions)
if (Math.Sign(position.Board[row, col]) == colorSign)
return true;
return false;
}
What did we do to this method? We first set the game.GameStatus to the turn of the appropriate color, based on who we are checking using the parameter colorIsWhite. I realized when I opened up this unit that I had never set whose turn it is in this "future" game, so I needed to do that in order to keep things from splodin. I then set futureCalculator.m_allowCheckSubTrees to false, so that we don't check to make sure the piece can actually move to determine if it threatens a square, as we don't want a nigh-infinite traversal of our logic tree.
The last thing we need to do is call our new method IsKingInCheck. As I said a few paragraphs ago, the best place to do this is in AddMoveToList.
protected IList<ChessBoard> AddMoveToList(ChessBoard startingBoard, IList<ChessBoard> boards, short oldRow, short oldCol, short newRow, short newCol)
{
var resultArray = new ChessBoard[boards.Count];
boards.CopyTo(resultArray, 0);
var result = resultArray.ToList();
if (newRow >= 0 && newRow < 8 && newCol >= 0 && newCol < 8)
{
//check the sign (color) of the current square and future square; if same, don't allow the move
var startingPieceSign = Math.Sign(startingBoard.Board[oldRow, oldCol]);
var futurePieceSign = Math.Sign(startingBoard.Board[newRow, newCol]);
if (startingPieceSign != futurePieceSign)
{
var futureBoard = (short[,])startingBoard.Board.Clone();
var piece = futureBoard[oldRow, oldCol];
futureBoard[oldRow, oldCol] = Constants.Empty;
futureBoard[newRow, newCol] = piece;
var newBoard = new ChessBoard(true);
newBoard.Board = futureBoard;
//check if new board and starting board are the same; if so don't add to valid moves list
var equal = futureBoard.Rank == startingBoard.Board.Rank &&
Enumerable.Range(0, futureBoard.Rank).All(dimension => futureBoard.GetLength(dimension) == startingBoard.Board.GetLength(dimension)) &&
futureBoard.Cast<short>().SequenceEqual(startingBoard.Board.Cast<short>());
//make sure the move wouldn't put the current color's king in check
var wouldPutSameColorKingInCheck = false;
if (m_allowCheckSubTrees)
{
var futureBoardContainer = new ChessBoard(true);
futureBoardContainer.Board = futureBoard;
wouldPutSameColorKingInCheck = IsKingInCheck(m_game.GameStatus == GameStatus.BlacksTurn, futureBoardContainer);
}
//add move to list of valid moves
if (!equal && !wouldPutSameColorKingInCheck)
result.Add(newBoard);
}
}
return result;
}
The addition to this function starts with the comment "make sure the move wouldn't put the current color's king in check". Here we first determine if we're supposed to check sub-trees, because if not then we don't care if the move would put the king in check. If we are allowed to check sub-trees we set a local variable wouldPutSameColorKingInCheck to the appropriate value by calling IsKingInCheck, passing in the potential future board. Lastly we add the move to our list of valid moves only if it would not put the king in check.
What's Next?
We're moving right along. Next week we'll create our unit tests. We won't make any actual progress on the "best" move calculation while creating our tests, but we'll give ourselves better confidence that what we've done so far is actually correct and most likely we'll be able to find and fix some bugs.Here's the link to the current source code.
Resources
- Online chess board editor "Apronus"
No comments:
Post a Comment