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