A Chess Project, Part 12

Intro

This week we get into some really interesting stuff, namely our algorithm for picking which move is the "best" out of a list of evaluated resulting positions. Last week we planted the seed; we created a few classes to evaluate a position numerically, letting us decide what a specific position is worth to us. Now we decide what's the best position.

First, here's our updated project code.

 

Basics of our Algorithm

You might think that this week should be easy. We already did the hard part last week right? I mean, how hard is it to create a tree of moves and pick the one that gives us the best outcome? Well that doesn't quite work. If all you do is evaluate a tree of potential board positions multiple levels deep to find the leaf node with the highest value, you're going to be disappointed. Such a path requires your opponent to make the worst possible sequence of moves in order for you to arrive at your best possible outcome, which is unlikely to happen. So what do we do instead? The logic behind the algorithm is this:

• Determine the level of depth you will look ahead of time. For example, if you know you can evaluate 5 moves ahead with relative ease, just pick the #5 outta yer butt.
• Find every single combination of moves for a depth of 5. 
• For each leaf node, evaluate the position. 
• White will be trying to maximize the score on his moves, black will be trying to minimize the score on his turns (remember, a negative positional evaluation equates to an advantage for black). 

Check out this link for a great graphical representation of how the algorithm will work. The algorithm in question is called minimax, and has been used for game AI for some time.

And hey, we can improve on it! Don't worry, I'm not smart enough to improve on it myself. This improved version of minimax is called negamax, and it too has been around for a while. It's basically the same as minimax, except it lets you write the same algorithm as above by just negating values rather than using one algorithm for minimization and one for maximization.

Go ahead and take a look at the pseudocode for negamax. One thing you'll notice quickly if you spend a minute reading it, is that it uses recursion. Through recursion we can avoid using a tree structure to hold all the valid moves in memory. It's tough to visualize I admit, it took me hours to really understand how all this worked. If you have the time to spend, google around and read a few more articles about minimax and negamax. Then come back to the graphical representation from above. If you understand how the algorithms work then you'll get a better feel for how you can improve on them yourself should you so desire.

The Code

And now it's time for our code. Within the BlogChess.AI.Basic1 dll, create a new class called Negamax. Here's the code for it:

using System;
using System.Collections.Generic;
using System.Linq;
using BlogChess.Backend;
using System.Diagnostics;

namespace BlogChess.AI.Basic1
{
    public class Negamax
    {
        public static int NumEvaluations = 0;
        public static Stopwatch MoveCalculationTimer = new Stopwatch();
        public static Stopwatch BoardEvaluationTimer = new Stopwatch();

        public static Tuple<double, ChessGame> Evaluate(ChessGame game, int depth, bool isWhite)
        {
            if (game == null || game.Positions == null || game.Positions.Count() == 0)
                return new Tuple<double, ChessGame>(0, game);
            var moveCalculator = new ChessValidMoveCalculator(game);
            MoveCalculationTimer.Start();
            var availableMoves = moveCalculator.CalculateValidMoves();
            MoveCalculationTimer.Stop();
            var colorSign = isWhite ? Constants.WhiteTransform : Constants.BlackTransform;
            if (depth == 0 || availableMoves.Count == 0)
            {
                NumEvaluations++;
                IPositionEvaluator evaluator = new PositionEvaluator(game, availableMoves, moveCalculator);
                BoardEvaluationTimer.Start();
                var evaluation = evaluator.Evaluate();
                BoardEvaluationTimer.Stop();
                return new Tuple<double, ChessGame>(colorSign * evaluation, game);
            }
            var bestValue = new Tuple<double, ChessGame>(-AIConstants.PieceValues[Constants.King], game);
            foreach (var move in availableMoves)
            {
                ChessGame newGame = new ChessGame();
                var positions = new ChessBoard[((IList<ChessBoard>)game.Positions).Count + 1];
                ((IList<ChessBoard>)game.Positions).CopyTo(positions, 0);
                newGame.GameStatus = game.GameStatus == GameStatus.WhitesTurn ? GameStatus.BlacksTurn : GameStatus.WhitesTurn;
                positions[positions.Length - 1] = move;
                newGame.Positions = positions.ToList();
                var val = Evaluate(newGame, depth - 1, !isWhite);
                if (-val.Item1 > bestValue.Item1)
                    bestValue = new Tuple<double, ChessGame>(-val.Item1, val.Item2);
            }
            return bestValue;
        }
    }
}

First let me explain the Stopwatch and NumEvaluations members. Once I had this thing working at a depth of 1 I tried depth 2 and 3. At depth 3 it got incredibly slow; this currently takes 37s to calculate a fairly simple depth 3 board position with an obvious expected outcome (fork the opposing king and queen with a knight). I dropped in these extra member variables in an effort to optimize the code, and I came to the conclusion that I'd have to completely redo the valid move calculation code in order to get a significant improvement. However, we won't be doing that for the blog, so let's move on to the Evaluate method. (disclaimer: it was actually a 60s process to evaluate a depth of 3 on the first try; I made one small improvement to get it down to 37s, though for the sake of conciseness I won't get into what that improvement was).

Our Evaluate method looks very similar to the pseudocode of Negamax from wikipedia. That's because I started with it and modified it to fit our purposes. The main difference between our implementation and that pseudocode, in my opinion, is that I return a Tuple<double, ChessGame> whereas negamax usually returns just the numeric evaluation value. I decided that this would be a bit more intuitive at the potential sacrifice of a small amount of efficiency. Other than that, we recurse the tree to the expected depth, just like every other negamax implementation. Note that only leaf nodes actually have their position evaluated, as denoted by the line "if (depth == 0 || availableMoves.Count == 0)". This is because we don't care about the board evaluation of branch nodes, as they derive their value from their children.

What's Next

I strongly suggest you review all the updated code, especially the new unit tests I created (but did not discuss in the blog post) in our new class BlogChess.AI.Basic1.Test.NegamaxTests. I've created tests in here that make sure we call the Negamax.Evaluate method  properly and validate its parameters, as well as making sure the algorithm can produce the proper expected move for some canned test positions at a depth of 0-3. And guess what, it actually works!! If you are a true fanatic and are excited at the prospect of testing it out further, I encourage you to make your own unit tests, feeding the algorithm some positions where you know the expected outcome. Or hey, feed it some where you don't know the expected outcome and see what it comes up with! If you really want to go nuts, see what you can do to improve the valid move calculator. I didn't write it with efficiency in mind, and it's the biggest drain on CPU and clock time right now.

As for the next blog post...we should have only 1 remaining blog post for this project, yay! We haven't yet modified our Web API from way back when, and we need to make it call our lovely AI dll in order to calculate the "best" move and return it to the client. Once we get that, we've fulfilled the original project goal and can move on with life. See ya next week!

Resources

Wikipedia - Minimax
Wikipedia - Negamax

A Chess Project, Part 11

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):

1. Is the player's king in check? (looking for false)
2. 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):

1. Is the player's king in check? (looking for true)
2. 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):

1. Evaluate a given board position;
2. Calculate future board positions, and eventually pick the "best" move.
3. 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