Wednesday, May 28, 2014

LINQ - Ordering, Grouping, Joining, and Projections

Intro


In part 1 of our series on LINQ we discussed the very basics of LINQ, pulling a few choice bits of data out of an array based on a simple filtering clause. This week we'll dive a little deeper into LINQ, exploring how to sort the results, group results, join 2 sources together to get a single output, and how to manipulate the structure of the output using projections. Hold onto yer hats (or other similar headgear such as beanies, earmuffs, etc)!

Ordering (orderby)

Everybody needs to sort data at some point in their coding career. To help illustrate my point with many of these LINQ operations, I'm going to compare using T-SQL against a fictional database in a zoo, versus using LINQ queries to pull the same data from C# objects. For starters, let's see a sample T-SQL query for pulling a list of baboons, sorted by aggressiveness:

select * 
from tblAnimals
where AnimalType = 'baboon'
order by Aggressiveness


Now let's see the same thing in LINQ using objects already loaded in memory:

        private dynamic CreateAnimal(string animalType, string name, int aggressiveness)
        {
            dynamic animal = new ExpandoObject();
            animal.AnimalType = animalType;
            animal.Name = name;
            animal.Aggressiveness = aggressiveness;
            return animal;
        }

        private List<dynamic> PopulateAnimalsList()
        {
            var animals = new List<dynamic>();
            animals.Add(CreateAnimal("lion", "Simba", 10));
            animals.Add(CreateAnimal("baboon", "Bobby", 4));
            animals.Add(CreateAnimal("baboon", "Bill", 1));
            animals.Add(CreateAnimal("baboon", "Bjork", 7));
            animals.Add(CreateAnimal("panda", "Pete", 2));
            return animals;
        }

        protected void btnLinqOrdering_Click(object sender, EventArgs e)
        {
            var animals = PopulateAnimalsList();
            var query = from animal in animals
                        where animal.AnimalType.Equals("baboon")
                        orderby animal.Aggressiveness
                        select animal;
            foreach (var val in query)
                Response.Write("<br />" + val.Name + " the " + val.AnimalType + " has aggro val of " + val.Aggressiveness);
        }


The first 2 methods are just setup, putting a list of animals into memory for us to manipulate. The LINQ-ified portion of our code is the 3rd and final method btnLinqOrdering_Click which creates the following output:
Bill the baboon has aggro val of 1
Bobby the baboon has aggro val of 4
Bjork the baboon has aggro val of 7

The orderby clause, just under the filtering where clause, is the sauce which produces this little bit of magic. By default, just like T-SQL, the sort order is ascending as you can see in the above output. If you wanted to order descending, you would change the orderby line to "orderby animal.Aggressiveness descending".
(Hey, wondering about dynamic and ExpandoObject? Keep paying attention to my blog, it'll probably make an appearance in a month or so).

Grouping (group)

Let's say you wanted to return a list of the types of animals and the count of each type. This will involve grouping. As with the last section, we'll start things with a sample bit of T-SQL:

select AnimalType, Count(1) as [NumAnimals]
from tblAnimals
group by AnimalType
order by Aggressiveness


Here were are selecting a list of types of animals and the number of each type of animal. How would we accomplish the same thing in LINQ? Here's that bit o' sample code:

        protected void btnLinqGrouping1_Click(object sender, EventArgs e)
        {
            var animals = PopulateAnimalsList();
            var query = from animal in animals
                        group animal by animal.AnimalType into animalGroup
                        select animalGroup;
            foreach (var val in query)
                Response.Write("<br /> there are " + val.Count() + " " + val.Key + "ses");
        }


This isn't the most grammatically correct output ever, but it's correct at least:
there are 1 lionses
there are 3 baboonses
there are 1 pandases

Notice how in our foreach loop where we display the output, we are accessing val.Count() and val.Key? This is because when you use the group clause in LINQ as denoted by group...by...into..., you actually create a list of lists. The outer list is a list of your groups which has a Key property that  in this case AnimalType property (because it's the "by" in the group clause).

While we do get a nice count by group from the above LINQ, we can't tell which animals belong to each group. What could we do in our code to show the contents of the groups/inner lists? the query is already selecting them, so in this case it's just a matter of changing our output. Here's the updated code:

            foreach (var val in query)
            {
                Response.Write("<br /> there are " + val.Count() + " " + val.Key + "ses");
                foreach (var animal in val)
                    Response.Write("<br />    " + animal.Name + " the " + animal.AnimalType + " has aggro val of " + animal.Aggressiveness);
            }


The output is pretty much what you'd expect:
there are 1 lionses
    Simba the lion has aggro val of 10
there are 3 baboonses
    Bobby the baboon has aggro val of 4
    Bill the baboon has aggro val of 1
    Bjork the baboon has aggro val of 7
there are 1 pandases
    Pete the panda has aggro val of 2

As you can see, I didn't lie to you earlier when I said the result of a group'd LINQ statement is a list of lists. The above code loops through the outer and inner lists, producing a combined output of summary and detail data. Spifferiferous!

Joining (join), as well as Projections

Joining lets you combine 2 source data sets into a single output data set. Let's pretend for this example that we want to see a list of which animals are in which shows. The shows are stored in a different table for T-SQL and in a different list for LINQ. Here's what the query might look like in T-SQL:

select tblShows.Name as [ShowName], tblAnimals.Name as [AnimalName]
from tblShows
join tblAnimals
on tblShows.AnimalName = tblAnimals.Name


This is pretty simplified as it assumes that the primary key of the Animal (unique property) is it's name, and it assumes only a single animal can be in any show, but hey you gotta lose realism for simplicity sometimes.

Now let's see what that might look like in LINQ:

        private dynamic CreateShow(string showName, string animalName)
        {
            dynamic show = new ExpandoObject();
            show.Name = showName;
            show.AnimalName = animalName;
            return show;
        }

        private ListPopulateShows()
        {
            var shows = new List<dynamic>();
            shows.Add(CreateShow("Early", "Simba"));
            shows.Add(CreateShow("Lunch", "Bjork"));
            shows.Add(CreateShow("Evening", "Pete"));
            return shows;
        }

        protected void btnLinqJoin_Click(object sender, EventArgs e)
        {
            var animals = PopulateAnimalsList();
            var shows = PopulateShows();
            var query = from animal in animals
                        join show in shows on animal.Name equals show.AnimalName
                        select new { ShowName = show.Name, AnimalName = animal.Name };
            foreach (var val in query)
                Response.Write("<br />the " + val.ShowName + " show has " + val.AnimalName);
        }



As in our first example, the first 2 methods are just setup. They create our lovely new list of shows. The 3rd and awesomerest method is our little bit o special LINQ. You can see we've joined the list "animals" to the list "shows", via the join clause. Notice the weird new "select new..." syntax? This is what's known as a projection. You can see the resource link at the bottom of this post for a full definition, but basically in this query our output is a list of a newly defined type of object that has 2 properties, ShowName and AnimalName. It's a pretty cool concept that you can just us a dynamic object like this for your LINQ output, it makes things very flexible. Other than that, we have what you'll recognize by now as some pretty standard output:
the Early show has Simba
the Lunch show has Bjork
the Evening show has Pete


What's Next?

I hope you enjoyed Part 2 in our series on LINQ. I learned a bit along the way myself. For the next post I'll show you guys how to use a different kind of data source, either SQL server or XML files. I haven't decided which yet. If you've read this far and have a preference, let me know in the comments and I'll take your thoughts into consideration when I make my final decision.

Resources

Basic LINQ Query Operations

Friday, May 16, 2014

LINQ - An Introduction

Intro

LINQ stands for Language Integrated Query. It was introduced with Visual Studio 2008, but it is probably still a new concept for many so I figured it just might be worth a blog on the topic. To me, LINQ is basically an extension of .Net that lets you use sql-like query syntax to retrieve some types of data. Let's say for example you have a list of customers and you want to retrieve all customers who have blue hair. If you were to do this in sql, it might look something like "select * from tblCustomers where HairColor = 'blue'". In C# you'd have to create a temp list, then write a loop where you find all blue-hairs and insert them into your temp list. It's just more work. LINQ however lets you treat some aspects of .Net as though you were using something akin to SQL.

On top of that, LINQ lets you pull data from many different types of sources. You can use LINQ to SQL to use LINQ for querying databases, you can use LINQ to XML to use link for querying XML files, and of course there's just plain old LINQ for querying lists of objects in .Net. By learning LINQ, you learn how to, in some fashion, query many different types of data so it saves you a little bit of code and a little bit of extra brainpower for learning other new things. Neat huh?

Constructing a LINQ Query

A LINQ query is comprised of 3 clauses: from, where, and select. If you're familiar with SQL syntax you'll notice that this isn't quite the same. In SQL, it's select, then from, then where. But hey, if this were the exact same order then life wouldn't be fun at all, and hippos would rule the seas. Or something. The from clause is your data source, the where clause is your filtering, and the select clause is what you're returning. Let's see a quick sample:

        protected void btnLinq1_Click(object sender, EventArgs e)
        {
            var blurbs = new string[] { "fred", "george", "fred rocks", "george doesn't" };
            var query = from blurb in blurbs
                        where blurb.StartsWith("fred")
                        select blurb;
            foreach (var val in query)
                Response.Write(" " + val);
        }


The above sample is a button click event in a webforms project. We first define our data source, which in this case is a simple array of strings named blurbs. We then construct our query object. Our query has a from clause that shows we are pulling data from blurbs, the where clause states that we only want to retrieve those blurbs who start with the word "fred", and the select clause states we are selecting individual blurbs from the list of blurbs. The last 2 lines loop through our query results (tip: the query isn't actually run until its results are used! see Introduction to LINQ Queries for more info) and write them out to the web page. As you can guess, we only retrieve and thus only display the values "fred" and "fred rocks" from the list of blurbs.

What's Next?

Either wait until next week's blog post when I delve a little deeper, or be a suck-up and read some of the resources below for more info.

Resources

LINQ
Introduction to LINQ
Introduction to LINQ Queries
Basic LINQ Query Operations

Thursday, May 8, 2014

A Chess Project, Part 13 (The Final Chapter)

Intro

I can see the light at the end of the tunnel! It's an alternating black and white checkered light, but still, a light nonetheless. How many of you thought it would take 13 blog posts to get here? Well I sure didn't, but I'm glad we're almost done. Here in week 13 we'll be modifying our Web API that we created months ago. We'll make it call into our spiffy chess AI dll in order to determine the best move from a given board position. After all, that's what we were trying to do from the very start!

 

 Code Changes

First, here is the absolute latest code as it stands right now, before today's modifications. It's not the most optimized, and I dare say the AI isn't really all that great, but hey the point of this blog was learning new technologies not to make the perfect chess AI.

Let's get to work. Open up BlogChessController from the BlogChessApi project. That method named PostBestMove is the one we want to do our modifications in. Here's what it looks like currently:

        public HttpResponseMessage PostBestMove(ChessGame game)
        {
            try
            {
                //validate the game
                var validator = new ChessGameValidator(game);
                if (!validator.Validate())
                    return Request.CreateResponse(HttpStatusCode.BadRequest, validator.ValidationIssues);

                //calculate the best move
                IChessValidMoveCalculator moveCalculator = new ChessValidMoveCalculator(game);
                var validMoves = moveCalculator.CalculateValidMoves();

                //return the best move wrapped in an http "ok" result
                return Request.CreateResponse(HttpStatusCode.OK, validMoves);
            }
            catch (Exception ex)
            {
                return Request.CreateErrorResponse(HttpStatusCode.InternalServerError, ex);
            }
        }


You'll notice we don't yet have a call into the AI dll. At the time we originally made this method we had no such AI dll, so I can forgive us. Before we can do the code though, we need to reference BlogChess.AI.Basic1 from the Web API project. Go ahead and do that now (I'm assuming you've seen that enough that no screenshots are necessary). Add a using statement up at the top of the unit while you're at it.

All we really need to do is add in a call to our Negamax evaluation, then add in a little bit of logic to look for win/draw conditions. All of this is just calling methods we've already written. Your newly modified should look like the following:

        public HttpResponseMessage PostBestMove(ChessGame game)
        {
            try
            {
                //validate the game
                var validator = new ChessGameValidator(game);
                if (!validator.Validate())
                    return Request.CreateResponse(HttpStatusCode.BadRequest, validator.ValidationIssues);

                //calculate the best move
                var bestMove = Negamax.Evaluate(game, 2, game.GameStatus == GameStatus.WhitesTurn);
                var responseGame = bestMove.Item2;
                responseGame.CurrentEvaluation = bestMove.Item1;

                //is a win or draw, set game move accordingly
                IChessValidMoveCalculator moveCalculator = new ChessValidMoveCalculator(game);
                var availableMoves = moveCalculator.CalculateValidMoves();
                if (availableMoves.Count == 0)
                {
                    var isKingInCheck = moveCalculator.IsKingInCheck(game.GameStatus == GameStatus.WhitesTurn, ((IList<ChessBoard>)game.Positions)[0]);
                    //look for checkmate
                    if (availableMoves.Count == 0 && isKingInCheck)
                        responseGame.GameStatus = game.GameStatus == GameStatus.WhitesTurn ? GameStatus.WhiteWin : GameStatus.BlackWin;
                    //look for draw
                    else if (availableMoves.Count == 0 && !isKingInCheck)
                        responseGame.GameStatus = GameStatus.Draw;
                }
                else //just the next turn now
                {
                    responseGame.GameStatus = game.GameStatus == GameStatus.BlacksTurn ? GameStatus.WhitesTurn : GameStatus.BlacksTurn;
                }

                //return the best move wrapped in an http "ok" result
                return Request.CreateResponse(HttpStatusCode.OK, responseGame);
            }
            catch (Exception ex)
            {
                return Request.CreateErrorResponse(HttpStatusCode.InternalServerError, ex);
            }
        }



As advertised, just a couple minor additions to call our evaluator and check for end of game.


Testing It

Remember way back when, that web forms project BlogChessApiFlexer? It's right there in the solution, and it's just itching to call the modified web api method. We had already coded a call into the web api (in default.aspx.cs), but prior to now we were just passing in a dummy request and expecting a dummy response. Well now it's time for an appropriate request and response!

        public ChessGame Game
        {
            get
            {
                return Session["Game"] as ChessGame;
            }
            set
            {
                Session["Game"] = value;
            }
        }

        protected void btnServerTest_Click(object sender, EventArgs e)
        {
            //1. Create and setup client object
            using (var client = new HttpClient() { BaseAddress = new Uri("http://localhost:11482/"), Timeout = TimeSpan.FromSeconds(300) })
            {
                client.DefaultRequestHeaders.Accept.Add(new MediaTypeWithQualityHeaderValue("application/json"));
                //2. Create a blank chess game to send up in the post request
                if (Game == null)
                {
                    Game = new ChessGame() { GameStatus = GameStatus.WhitesTurn };
                    var positions = new List<ChessBoard>();
                    var sampleBoard = new ChessBoard(true);
                    sampleBoard.Board = new short[8, 8] { { -4, -2, -3, -5, -6, -3, -2, -4 }, { -1, -1, -1, -1, -1, -1, -1, -1 }, { 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0 }, { 1, 1, 1, 1, 1, 1, 1, 1 }, { 4, 2, 3, 5, 6, 3, 2, 4 } };
                    positions.Add(sampleBoard);
                    Game.Positions = positions;
                }
                int numPositions = ((IList<ChessBoard>)Game.Positions).Count;

                //3. Send the request
                var response = client.PostAsJsonAsync("api/BlogChess/BestMove", Game).Result;
                if (response.IsSuccessStatusCode)
                {
                    //4. Read the result from the response, display the "best move"
                    var result = response.Content.ReadAsStringAsync().Result;
                    var resultObject = JsonConvert.DeserializeObject<ChessGame>(result);
                    Game.GameStatus = resultObject.GameStatus;
                    ((IList<ChessBoard>)Game.Positions).Clear();
                    for (int positionIndex = 0; positionIndex < numPositions + 1; positionIndex++)
                    {
                        if (((IList<ChessBoard>)resultObject.Positions).Count > positionIndex)
                            ((IList<ChessBoard>)Game.Positions).Add(((IList<ChessBoard>)resultObject.Positions)[positionIndex]);
                    }
                    lblResult.Text = "Success! :" + result;
                }
                else //5. Request failed; tell the user what happened
                    lblResult.Text = "Failzor'd!: " + response.StatusCode.ToString() + "::" + response.ReasonPhrase;
            }
        }



Let's start with the easiest part, the propert Game of type ChessGame. If you've done webforms before, this shouldn't require much of an explanation. This is just a handy, type-safe way for me to be able to reference the current game object from the session so I can persist information about a single game in memory. Moving on to the button click event...

And here's the meat. Some of this was already here. As I said above, we were already calling the web api. What's new is we're now creating and serializing a chess game object (the one from our session), and we're passing this game object to the web api. Then we're taking the result of this call and updating the Game property. This means that, if you keep clicking that button, the AI will play itself! How cool is that? Well it's moderately cool, as it's incredibly slow. But hey, baby steps.

Wrapping it Up

Thanks for sticking with this series of articles everybody. As can happen with coding endeavors, it got away from me a bit. I thought this might be a 4 or 5 article series, not 13. I hope you learned a few new things, and maybe even gained a little bit of interest in chess in the process of reading these.

Oh and here's the absolutely final code, all fanciful and whatnot.

What's Next?

There are a few things you could do really. You could load AI dlls dynamically, configurable via database entry or config file. This would make it easier for other people to create AI dlls that plug into your web api, and you could have clients configured to choose a specific AI. You could also optimize the existing AI dll further (or just make your own) to make it much much quicker (hint: bitboard!). Or just go have a beer, or martini, or diet dr pepper. Whatever.


Resources

online chess board editor at Apronus.com
Chess.com, a great site for everything chess related 

Thursday, April 17, 2014

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

Thursday, April 10, 2014

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

Thursday, March 27, 2014

A Chess Project, Part 10

Intro

We got a good start on our unit testing in the Chess Project Part 9 posting last week. We unit tested every possible move for white pieces, created a spiffy new html format for chess boards to ease our unit testing, and we tested many of our helper methods in other classes as well. This time around we will finish up unit testing the current suite of functionality. We have to add unit tests for some of the valid black piece moves (I only deem it worth our time to create tests for moves unique to black; his pawns and king castling moves, make sure black pieces can't put their own king in check) and we have just a few helper methods within ChessValidMoveCalculator to test out. Then we're green to move on to the super-fun part (next week), starting to figure out what the "best" move is for a given chess board!

The Code

Like last week, I think it best to start off by giving you this link to the code. There are too many new unit tests forming too much code to paste it in the blog, so at your leisure please download it from the link, open it up, build it, and take a look at the new unit tests. Then come on back so we can discuss them.

Unit Tests

We'll start with pawn moves. Obviously black's pawns move down the board while white's pawns move up the board, so their move calculations are different. This is why I decided to unit test black pawns separately from white pawns. You can see by looking at the unit test file that I mirrored all the white unit tests with black as far as pawns are concerned, so we should have full coverage.

I'm going to skip unit testing of black Knight, Bishop, Rook, and Queen moves. Why? These pieces move exactly the same whether they are white or black. The only difference is that white pieces can't put the white king in check, and black pieces can't put the black king in check, but I don't have to duplicate all my tests to check 1 situation per color. I did however recreate the majority of the king's unit tests as castling is different (white castles on row 7, black on row 0), so you can see in our unit test code that most but not all of the king testing is duplicated from white to black. I also renamed some of the unit tests to better denote color and direction.

We also added 8 more unit tests (4 each) for ColorThreatensSquare and IsKingInCheck, testing the positive and negative and black/white of each method.

You may have also noticed I had to fix more code. This just reaffirms my love of unit tests. See if you can find the code I had to fix. Here's a hint: it had to do with checking if a move would put the same-color king in check.

What's Next?

That's it for this week folks! We have 1 solution, 4 projects, dozens of classes, 80 unit tests, 1 web API, etc etc. Next week we'll FINALLY get to the whole point of this project, calculating the "best" move. I haven't a clue how long that will take us to do, it could be 1 post or 5, we'll just have to wait and see. 

Thursday, March 20, 2014

A Chess Project, Part 9

Intro

As promised last week in Part 8, this week is all about the unit tests. We've got a pretty sizable chunk of code going in this project and so far we have no way to test any of it. I don't plan on creating a GUI for this solution (at least not in this series of blog posts), so unit testing is the way to go. Please view my unit testing series of blog posts (UT1, UT2, UT3, UT4) for a quick refresher on unit testing if necessary.

The Code

I think it will be easier to understand what's going on if I give you a link to the code at the top of the article this time, so here you go. Once you have it pulled down, extracted and compiled come on back for the remainder of the article.

Unit Tests

As you can see in the screenshot below, I created a new unit test project in the solution named BlogChess.Backend.Test.
This is where all our unit tests for the project are going. As of the time I am writing this, there are 57 unit tests in the solution. That is a bit too many for us to walk through in the blog, so at your leisure please dig through the code and see what's going on. The unit tests at this point cover the vast majority of our functionality from the backend dll. We are testing the validation code, board size, and all the valid moves for white. The only things left to test are the black piece move validation methods, and we'll do that in the next blog post.

As a result of all this unit testing, I found 2 other things necessary. First, I had to fix some bugs. I know what you're thinking: "But Pete, you don't make mistakes!". Well I appreciate the kind words (you were thinking them, admit it!), but yes I actually do make mistakes. I bet I fixed a half-dozen of them thanks to the unit tests. I won't detail all of them (mostly because I don't remember what they were at this point), but suffice it to say they would have made this project rather useless if they had been left to fester. The second thing I found necessary while creating unit tests was to have a way to visualize a chess board so that I could set up specific positions in the unit tests, and validate piece movement. Cue dramatic new bold sub-heading...

New Format, New Formatter/Parser (use of html agility pack)

...So, I created a new chess format. Sure arrays are great for representing a chess board, but which is easier to work with when creating a unit test? This...

{ {-4, -2, -3, -5, -6, -3, -2, -4}, {-1, -1, -1, -1, -1, -1, -1, -1}, {0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0}, {1, 1, 1, 1, 1, 1, 1, 1}, {4, 2, 3, 5, 6, 3, 2, 4} }


or this?

So, I invented a new chess format (it sounds a lot more impressive than it really is) and created a class to import the new format. Believe it or not, the above screenshot is pure html/css. There are no images in that. Well the screenshot itself is an image obviously, but it's showing just html/css.

How did we accomplish this? If you're moderately familiar with html/css, it's easier than you might think. It turns out that unicode defines special characters for each of the chess pieces, so as long as the font you are using supports these values, then you can use plain-old-text to represent the pieces. After that it's just a simple matter of putting a board around the pieces you want, and voila! You can look at some of the many samples I put in the solution, using the screenshot below as a guide to finding the files. The essence of the export format though is much simpler than these files allude to. All you need is elements on the page that have a data-col attribute of "a" through "h", and those same elements should have a data-row attribute of "1" through "8". These of course represent the 64 squares of the chess board. For ease of formatting I've elected to use a table (you could use div's, span's, or whatever other html element you feel like using), a modified sample of which you can see below.

    <table>
        <tbody>
<tr>
            <td>8</td>
            <td data-col="a" data-row="8"></td>
            <td data-col="b" data-row="8"></td>
            <td data-col="c" data-row="8"></td>
            <td data-col="d" data-row="8"></td>
            <td data-col="e" data-row="8">♚</td>
            <td data-col="f" data-row="8"></td>
            <td data-col="g" data-row="8"></td>
            <td data-col="h" data-row="8"></td>
        <tr>
</tbody></table>

For some more thorough and much cleaner looking samples with css to format them nicely, take a look at any of the unit test files in the solution as you see highlighted below. These samples all import perfectly fine using our new formatter object, and are also very easy to use the mark-1 eyeball to see what's going on with the board itself by just viewing the file in any modern web browser. Again the above html table is just a sample; obviously you'd need the other 56 squares to make a full board :)




Now, on to the design and code of the formatter. In the future I can see myself wanting to import and export various other chess formats/notations (there are plenty of them), so let's use an interface to represent any type of formatter. We'll call the interface IChessBoardFormatter. Then, because the format we want right now is html based, we'll just call the class HtmlChessBoardFormatter and have the class implement the new interface.


IChessBoardFormatter defines 4 methods: Import, Export, ExternalPieceToNative, NativePieceToExternal. Import and Export should be pretty self-explanatory. ExternalPieceToNative converts an external representation of a piece (in whatever format) to a native piece (a short value from -6 (black king) to +6 (white king). NativePieceToExternal just goes the other direction.

HtmlChessBoardFormatter is the class we'll use to translate boards between our internal representation(arrays of short) and the new human-friendly format (html). For the moment I didn't implement the capability to export; just import. For now I only need this class in order to read in html files for unit testing. It's too much code to put in this blog post, so open up HtmlChessBoardFormatter and take a look at the Import and ExternalPieceToNative methods; they're where the magic is.

If you've never used the Html Agility Pack I highly recommend it for your HTML parsing needs in .net. I've used it in the Import method of the formatter class in order to find html elements with a data-row and data-col attribute, as they are the elements that contain our chess pieces. Here's a sample of it:

            var document = new HtmlDocument();
            document.LoadHtml(sourceBoard);
            foreach (var node in document.DocumentNode.SelectNodes("//*[@data-row]"))
            {
                var sourceRow = node.Attributes["data-row"].Value;
                var sourceCol = node.Attributes["data-col"].Value;


Spiffy huh? Resilient html parsing made easy in .net.

What's Next?

As you may have guessed, we'll have to hit up the unit tests for black pieces/movement and any other public methods of the valid move calculator next week. I can finally see the light at the end of the space-time continuum though, we're almost ready to start coding our "best move" logic! And, thanks to these unit tests, we'll actually be able to suggest valid moves.

Resources

Wikipedia Chess
Wikipedia en Passant
Wikipedia Chess Symbols in UnicodeHtml Agility Pack