Implementing the “Vanilla” Alpha Beta

Since I had an amazing number of views on my previous article about my chess engine rewriting and publishing it OS, I decided to extend the discussion a little bit more. Unfortunately, this is not a brand new argument, since there are a lot of good articles on the web, but according to me some missing points exist: if you start reading the code of a fully fledged engine, even in C#, you will probably get lost in a big mesh of heuristics and optimizations without really get what’s really happening. By contrast, if you read the literature you will find a lot of pseudo code but nothing really working, and something that is a detail for the pseudo code, can be really difficult to implement in real life just to see what’s happens. Here we will show how a plain algorithm from the literature behaves in its essence, solving a real chess problem. Of course, this will not work in a real playable engine but it has a big advantage: it is *understandable* and can be the starting point to optimize, so by gradually reaching the fully fledged engine, we eventually get each single step better.

Which algorithm to use? Chess engines use some flavor of an algorithm called MiniMax, with an immediately (even for a simply case) necessary optimization called Alpha Beta Pruning. This is what we will show by example here below. So what exactly is MiniMax? It is an algorithm that works by producing a tree of the possible games in which each node is a possible status and each arc that produces the transaction is the move (the decision) the player can do. At each node, we can weight the result of the player Mini and the player Max, Mini wins if that value is little, and Max wins when the value is high, so Mini wants to *minimize* a score function, and Max wants to maximize it. Since chess is a symmetric game, we can say that a good result for Mini is a bad result for Max and vice-versa. This leads us to a single evaluating function, with sign changed depending on the player. This simplification is referred in literature as Negamax. Let's see an example of a game tree, by starting from a specific chess position (2rr3k/pp3pp1/1nnqbN1p/3pN3/2pP4/2P3Q1/PPB4P/R4RK1 w - - 0 0):

The position is our root node, and a portion of the resulting tree is:

Well it is a portion, it's impossible to draw it all even for just a few play, it is even impossible computationally to enumerate all nodes even for a few play, because of the high branching factor chess has. The branching factor is a measure on how many nodes are generated from a root, in other words, in chess it is an average count of the possible moves a board has. For chess, this number is about 35, and so we have, for each ply an exponentially increasing number of nodes like 35^n, where n is the number of play. Let’s consider too why it is so important to have a correct move generator: just a single wrong move somewhere will mess an enormous amount of nodes.

Average number of nodes per ply in chess:

Of course, this is just average data, it can be even worse in some situations. You can always know the exact count of nodes by using the perfect test contained in the same project, but I suggest you start with a 5/6 ply and see how long it takes before trying 8/9 ;)

So some optimization is necessary since such an exponential explosion can’t be managed with any kind of CPU. The only game I know in which generating all the tree is probably tic-tac-toe, but for chess, this is absolutely not the case. So we introduce alpha beta pruning in our algorithm, but how can we prune some nodes despite the others? Let’s have an example with the same position shown above, and suppose we move the Knight in c6 ( Nxc6), the black can catch it with the rock, or with the pawn, Rxc6 and bxc6 respectively. In an alpha beta pruning scenario, as soon such a move refutes the white move, i.e., the move gives a gain better than the current opponentbetter score, the search stops at that level. This is an enormous gain in term of performance, the only drawback is that we have just a lower bound of the actual score of a position, so we don’t really know if we can do better, but we stay on the fact that we can do enough. How this is achieved by code? Let's see what we need:

1. A way of scoring the position: material balance is more than enough for this sample.
2. An algo that traverses the algo keeping track of the best score for a player (alpha) and for the opponent (beta)
3. A way to sort the move ordered so the “strongest” are seen first, the weak later.

Point 1 is easy, just give some value to each piece type, and sum it considering positive the white if the white is the player or vice-versa. The algorithm we will see soon, but the tricky part is the 3). As you probably guessed, having a good move navigated first, increment the changes of stops the search (the so called beta-cut off) with a dramatic performance increment. So the first real heuristic that will give your engine strength and personality is that function. In the example, we will use a very basic ordering strategy, that puts all promotion and good capture in front, all the “other” moves in the center, and the bad captures at the end. (A good capture is one in which the catcher has less value or equal to the captured).

So let’s show the “Vanilla” algorithm. Why “vanilla”? Because a real chess engine extends a lot of this concept, and adds a lot of other functionality to make the engine responsive, but the one shown does the job and it is (hopefully) as clear to understand as the pseudo code, with the difference that it is working code you can inspect and debug and use for learn:

• https://bitbucket.org/Felice_Pollano/felpo-ii/src/ca300fc8a34f/FelpoII.Core/Search/PlainAlphaBeta.cs?embed=t

The interesting portion is the Search function. I used delegates to extract the non algorithm related code so it appears simple as pseudo code, but it is working. Then I wrote a test case using this search function here:

[TestMethod] public
void TestQg6() { using (var rc
= new RunClock())
{ var engine = new SynchronEngineAdapter(new SimpleVanillaEngine(7), 
		"2rr3k/pp3pp1/1nnqbN1p/3pN3/2pP4/2P3Q1/PPB4P/R4RK1
w - - 1 1" ); Assert.AreEqual("g3g6",
engine.Search()); Console.WriteLine("Elapsed
milliseconds:" + rc.GetElapsedMilliseconds()); } } 

The code of the search is called by the class SimpleVanillaEngine, this is just a wrapper that injects the proper move generation calls and evaluation/ordering functions. That test works in about 40 secs on my laptop, that is unacceptable for a real engine, but satisfying because… even if the code is simple, it reports the correct answer, why can I say so? Because the board I proposed is some sort of standard test for chess engines. Please note that the correct move Qg6 is reported in the test as g3g6 since our engine does not yet support the human algebraic notation, but the move as you can guess is equivalent. This case is important because it shows how an apparently wrong move can lead in a win if we look deep enough.

Well if interest in the project continues as it started, I will blog again on how to move this in a real engine.