Intro
Last week we wrote some more unit tests and fixed up some bugs as a result. Overall we're making great progress but we've still got 3 conceptual tasks left: Evaluate the board position in a quantifiable manner, write an algorithm that emulates a tree structure so we can pick the best possible future outcome, and call all this sweet sweet awesomeness from our web api.
Stalemate and Checkmate
As part of evaluating a board position, we have to check for the end-of-game conditions: stalemate and checkmate. Stalemate should be pretty easy to check. Here are the conditions (based on whose turn it is):
- Is the player's king in check? (looking for false)
- Does the player have any valid moves available? (looking for false)
If both of these conditions are met, then we're in luck!
And hey, guess what? Checkmate is just as easy. Here are the conditions for checkmate (based on whose turn it is):
- Is the player's king in check? (looking for true)
- Does the player have any valid moves available? (looking for false)
If both of these conditions are met, well you get the picture! And best of all, we already have methods that look for check IsKingInCheck() and any valid moves CalculateValidMoves(), so the code is actually done already. Yay us!
AI - Overview
There is such an incredibly body of work out there regarding chess AI; we could go on for years on the topic. Broadly speaking though, we really need 2 parts to our AI (we're keeping things simple):
- Evaluate a given board position;
- Calculate future board positions, and eventually pick the "best" move.
- Strategy: what's that? I wouldn't know a chess strategy if it mated
me in 5 moves. We'll skip an attempt at strategy for now, and
maybe forever.
We'll start first with evaluating the current board position. Take a couple minutes to think about how you might tackle this and then check back in when you're ready.
...
...
Before we jump into coding, a little background on my level of play. When I play chess, I almost always play against a computer of some sort. My current program of interest is called
Shredder (the iPad version), and it has me ranked as "Casual" in human terms (thanks; BTW i own you Mr. computer, so nyah), with an
Elo rating of 1290. Why do I tell you this? Well it's certainly not to brag about my rating of casual; that would be like bragging that you've already showered this month when it's only the 10th. I merely wish to begin setting your expectations of what we will achieve. I will be extremely excited if we can get our basic AI here playing anywhere near my level of 1290. The current chess world champion has a rating over 2800, and Master candidate+ ratings start around 2200. And no this doesn't mean 1100 is halfway to becoming a chess master :).
Now, with my 1290 Elo rating in the back of your brain, here are the criteria I would like to use to evaluate the board:
- Material: more pieces = better odds of winning. Some pieces are better than others.
- Board control: The more squares you control (threaten), the better your odds are of winning.
- Side note: we're going to keep our algorithm uber-simple. Some algorithms treat middle squares as more valuable than edge and corner squares, and really a pawn doesn't "threaten" a square in front of him just because he can move to it; but hey, we have to start somewhere and this blog is already 11 posts long.
And here are a few more that we'll ignore in order to keep things simple. If you're interested in this topic, I strongly encourage you to branch out on your own and try some of these:
- Initiative: The player with the initiative is the one dictating the direction and pace of the game, and this gives the player an inherent advantage.
- Pressure: see initiative. More important as a psychological tool against humans though.
- Pawn structure:
- Pawns generally work best when not stacked together on a single file/column.
- Pawns work best with the smallest # of "islands". A pawn island is a contiguous section of pawns. For example, at the start of the game you could be considered to have 1 big pawn island. If you lose the pawn on the b-file and the e-file, you now have 3 pawn islands (a, c-d, f-h).
- King protection in early and mid-game: in the early/mid game it's usually better to have your king protected behind a shield of pawns. Thus castling and other king protection options should be favored. Other than tweaking the algorithm for threatened squares, this would probably be my #1 choice of things to add to our algorithm.
- Opening move database: Many of the first 2-10 moves have been mapped out and analyzed quite thoroughly, and all the best chess programs out there use such a database.
- End-game database: There are databases out there for 5-6 pieces on the board where the entire possible game is completely mapped out. What an advantage! A computer with a hookup to these will be able to know the perfect path to checkmate or stalemate, whichever is better for it given the current board situation.
- Some people think having 2 bishops is better than having 2 knights or a knight and a bishop. Is it accurate? I dunno, the jury's out.
- We could get a lot more complicated with things like stacked rooks on a file, rook(s) on the 7th rank, x-rays, forks, etc, but these are also a topic best handled outside the blog.
Board Evaluation - Material
For now we'll use somewhat of a standard in the chess evaluation world.We'll use a numeric evaluation of the board, where a positive number means white has a better position and a negative number means black has a better position. Pawns will count for 1 point, Knights and Bishops 3, Rooks 5, Queen 9, and the King is immeasurable in terms of value.
I've babbled enough, let's do some code! Funny how a coding blog can have over a full page of text before any code is even discussed huh? :P. If you need to download the source code from the
last blog post do so now.
First, it's possible I may want (or you may want) to have multiple algorithms for board evaluation and best move calculation, so I want these driven by interfaces. Start by creating an interface in BlogChess.Backend.dll called IPositionEvaluator.
We'll just have a single property to represent the game, and a single method in there called Evaluate, which accepts no parameters and returns a value of type double.
namespace BlogChess.Backend
{
public interface IPositionEvaluator
{
ChessGame Game { get; set; }
double Evaluate(ChessGame game);
}
}
Now create a new DLL in our solution to hold the AI logic. We'll call it BlogChess.AI.Basic1. Create a class in the DLL called PositionEvaluator. In this new dll add a reference to BlogChess.Backend.dll. Make sure the new class implements the new interface. You should have something like this so far:
using System;
using BlogChess.Backend;
namespace BlogChess.AI.Basic1
{
public class PositionEvaluator : IPositionEvaluator
{
public ChessGame Game { get; set; }
public double Evaluate()
{
throw new NotImplementedException();
}
}
}
I also want, for now, a new constants class here in the AI dll to hold a few things. Go ahead and create it, call it AIConstants.
For starters there won't be much in here, just some piece values. Hearken back to the BlogChess.Backend.Constants class where pieces on the board have a numeric representation of -6 thru +6 and you can see that these piece evaluation values in the below code snippet line up with those numeric representational values as far as indexing is concerned:
namespace BlogChess.AI.Basic1
{
public class AIConstants
{
public static double[] PieceValues =
{
0, //no piece on square
1, //pawn
3, //knight
3, //bishop
5, //rook
9, //queen
100000, //king
};
}
}
As you can see, nothing fancy in here. We're just defining some numeric values to represent how much a piece is worth.
I also wish to create another new class, we'll call this one MaterialEvaluator. Why do I want this separated out from the PositionEvaluator class? It seems like I could just as easily put the different evaluation criteria right there in the Evaluate method. However, there's a catch to putting it all in the same method; it's harder to verify that the code is doing what it should. It will be much easier to unit test this stuff if we separate out the different evaluation criteria into their own classes. I'm all about the unit testing, and I'm the one writing the blog so we're doing it my way! Go ahead and create that MaterialEvaluator class in the BlogChess.AI.Basic1 dll. Make it look like this:
using System;
using System.Linq;
using BlogChess.Backend;
namespace BlogChess.AI.Basic1
{
public class MaterialEvaluator : IPositionEvaluator
{
public ChessGame Game { get; set; }
protected ChessBoard CurrentPosition
{
get { return Game.Positions.Last(); }
}
public MaterialEvaluator(ChessGame game)
{
if (game == null)
throw new ArgumentNullException("The game cannot be null", "game");
if (game.Positions == null || game.Positions.Count() == 0)
throw new ArgumentException("The game must have at least 1 position");
Game = game;
}
public double Evaluate()
{
double result = 0.0;
for (short row = 0; row < 8; row++)
{
for (short col = 0; col < 8; col++)
{
var piece = CurrentPosition.Board[row, col];
result += AIConstants.PieceValues[Math.Abs(piece)] * Math.Sign(piece);
}
}
return result;
}
}
}
As you can see, I went ahead and implemented the IPositionEvaluator interface on this class even though it's not meant to be a top-level evaluator. Why? Well it just made sense really. It needs a reference to a game object and it needs a single Evaluate() method, so it just fit right.We also gave it a constructor that takes a Game parameter, as the class needs to know what it's evaluating. The property CurrentPosition is just a helper property that we can use instead of having to call Game.Positions.Last repeatedly. Within the evaluate method all we do is loop through the squares of the board, and add up the material values contained therein.
We have one more task to do before we get back to the PositionEvaluator class that we created...we are going to evaluate the game based on the # of moves available to each player. For now we'll keep it simple and just value each available move exactly the same based on a constant. Go ahead and add the new constant to AIConstants.cs as below (new const is named AvailableMoveValue).
namespace BlogChess.AI.Basic1
{
public class AIConstants
{
public static double[] PieceValues =
{
0, //no piece on square
1, //pawn
3, //knight
3, //bishop
5, //rook
9, //queen
100000, //king
};
public const double AvailableMoveValue = 0.05;
}
}
And we of course need to use this new constant somewhere. Guess what? Another class :). Create a new class in the AI dll named AvailableMovesEvaluator. This is also a fairly simple class, though it has slightly more meat than the one before. Here's a look-see at the class, I'll explain it after you take a look at the code:
using System;
using System.Collections.Generic;
using System.Linq;
using BlogChess.Backend;
namespace BlogChess.AI.Basic1
{
public class AvailableMovesEvaluator : IPositionEvaluator
{
public ChessGame Game { get; set; }
protected IList<ChessBoard> ValidMoves { get; set; }
protected ChessValidMoveCalculator ValidMoveCalculator { get; set; }
protected ChessBoard CurrentPosition
{
get { return Game.Positions.Last(); }
}
public AvailableMovesEvaluator(ChessGame game, IList<ChessBoard> validMoves, ChessValidMoveCalculator validMoveCalculator)
{
if (game == null)
throw new ArgumentNullException("The game cannot be null", "game");
if (game.Positions == null || game.Positions.Count() == 0)
throw new ArgumentException("The game must have at least 1 position");
if (validMoves == null)
throw new ArgumentNullException("The validMoves cannot be null (it can be empty though)", "validMoves");
if (validMoveCalculator == null)
throw new ArgumentNullException("The validMoveCalculator cannot be null", "validMoveCalculator");
Game = game;
ValidMoves = validMoves;
ValidMoveCalculator = validMoveCalculator;
}
public double Evaluate()
{
double result = 0.0;
var colorMultiplier = Game.GameStatus == GameStatus.WhitesTurn ? Constants.WhiteTransform : Constants.BlackTransform;
result += colorMultiplier * ValidMoves.Count() * AIConstants.AvailableMoveValue;
var originalStatus = Game.GameStatus;
Game.GameStatus = Game.GameStatus == GameStatus.WhitesTurn ? GameStatus.BlacksTurn : GameStatus.WhitesTurn;
var oppositeMoves = ValidMoveCalculator.CalculateValidMoves();
colorMultiplier = Game.GameStatus == GameStatus.WhitesTurn ? Constants.WhiteTransform : Constants.BlackTransform;
result += colorMultiplier * oppositeMoves.Count() * AIConstants.AvailableMoveValue;
Game.GameStatus = originalStatus;
return result;
}
}
}
Again, quite similar to the last class. The only difference really, other than the criteria used for evaluation of course, is that we have 2 more parameters in the constructor. These are here purely for the sake of efficiency. We'll be evaluating potentially millions of board positions in a short amount of time, and rather than creating and calculating extra lists of valid moves and move calculation objects, I would rather pass them in. I need them in the Evaluate method anyways, as you can see in the above code.
Now back to the main evaluation class that we created earlier, PositionEvaluator.We need to check for checkmate and stalemate, then call our other 2 evaluation classes. This code is pretty simple:
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using BlogChess.Backend;
namespace BlogChess.AI.Basic1
{
public class PositionEvaluator : IPositionEvaluator
{
public ChessGame Game { get; set; }
protected ChessBoard CurrentPosition
{
get { return Game.Positions.Last(); }
}
public PositionEvaluator(ChessGame game)
{
if (game == null)
throw new ArgumentNullException("The game cannot be null", "game");
if (game.Positions == null || game.Positions.Count() == 0)
throw new ArgumentException("The game must have at least 1 position");
Game = game;
}
public double Evaluate()
{
//setup some locals for later use
double result = 0.0;
var validMoveCalculator = new ChessValidMoveCalculator(Game);
var validMoves = validMoveCalculator.CalculateValidMoves();
var isKingInCheck = validMoveCalculator.IsKingInCheck(Game.GameStatus == GameStatus.WhitesTurn, CurrentPosition);
//look for checkmate
if (validMoves.Count() == 0 && isKingInCheck)
return (Game.GameStatus == GameStatus.BlacksTurn) ? AIConstants.PieceValues[Constants.King] : -AIConstants.PieceValues[Constants.King];
//look for draw
if (validMoves.Count() == 0 && !isKingInCheck)
return 0;
//evaluate based on non-victory/draw conditions
result += new MaterialEvaluator(Game).Evaluate();
result += new AvailableMovesEvaluator(Game, validMoves, validMoveCalculator).Evaluate();
return result;
}
}
}
Just like I said, simple. We look for victory, draw, and then delegate the rest of our activity to those other 2 classes we created.
What's Next?
Regarding the calculation of future board positions, you can take my
word for it that we will not be able to figure out the best move by
evaluating every possible chess position available. If today's
supercomputers can't do it, we're not going to accomplish it with a
starter web service. We'll go into this final piece of the AI more in-depth next week, but suffice it to say we will barely scratch the surface of chess AI programming with our simple board evaluation and the decision tree next week.
For those of you who wish to play with a copy of the latest code, I've placed a link to it below here. One thing I didn't cover in the blog this week is unit testing of the new code. Take my word for it that I did unit test the new code and it did in fact reveal some bugs that were eradicated before I put them in the blog post. You can find the new unit tests within the source code in a dll named BlogChess.AI.Basic1.Test.
The Code
Resources
Wikipedia -
Computer Chess
Wikipedia -
Elo Rating System
