Positional evaluation in chess

Chess engine are very good a tactics because it fits their way of approaching a position. To play moves that improve the position without gaining an immediate material advantage or even sacrifice material for a better position is much harder to program. It requires a careful coding of positional chess concepts and a fair amount of chess knowledge in its programmer.

My automated tuner seems to help here a bit. The tuned version is much more willing to give up some material to improve its position then the old "materialistic" version was.

In Jeremy Silman's "The Amateurs Mind" he discussed the following position

1r4k1/5p1p/1p3np1/pR6/P1Pr3P/2R2B2/1P4P1/7K w - -

Fischer - Taimanov, Palma de Mallorca 1970, White to Play

White has the queen side pawn majority and an active bishop targeting the queen side. The black knight wants to relocate to c5. Also Black threatens to take the white pawn at h4 with check.

I gave this position to my original version and it wasn't really understanding the position. At lower depths it tried to save the pawn with g3 and at higher depths it suggested 1. h5 Ne4 2. Bxe4 Rxe4 giving up its strong bishop and its advantage.

The tuned version very quickly found a better move. 1. c5! (1. .. Rxh4+ 2. Kg1 Rb4 3. Rb3 Rxb3 4. Rxb3 Nd7 5. c6). The pawn then queens after a rook sacrifice (Rxb6) which was a tactics my engine still missed so deep down the tree.

But it seems to make a little progress in the area of positional understanding.

Time Trouble (again)

During the tuning process of the engine I realized that some games that were played during the tuning are lost on time. The games are played very fast, e.g. 10 moves within 1 second, so an occasional loss on time is not uncommon. But after I measured it, the rate was between 15% and 20% time losses, which is much to high.

I thought my time management module was working correctly. It should adapt to fast time controls and prevent time losses, but it did not. I decided to have a look at it and spotted the problem almost instantly.

The second line was reading hardLimit = softLimit causing the trouble

The hard limit is the time that the search has to stop no matter what to prevent a time loss. The soft limit is a recommendation for the search but can be extended. There is a final check that the soft limit can never be bigger than the hard limit, but unfortunately I messed up the order. Instead of lowering the soft limit I extended the hard limit.

Stupid me. 

Fixed, tested and the time loss percentage dropped to 0%.

PS.: Another GA run is almost done, so I will soon have enough samples to check how much the whole stuff is worth in terms of ELO points. 

Population Based Incremental Learning (PBIL)

As mentioned earlier I'm using a genetic algorithm to tune my chess evaluation module. I'm not using a classic GA where a good mother and a father is selected and their genes combined to produced the members of the next generation. I'm using a more modern approach called PBIL (Population Based Incremental Learning) and I even used it with some modifications. It is more similar now to "simulated annealing".

During my tests I made the following observations

• The algorithm is able to converge the more important terms rather quickly
• Terms with lesser influence converge very slowly, some none not at all given about 1000 generations
• The choice of the fitness function is very important. Runs with some fast and simple functions failed badly.
• The choice of the GA parameters is rather a second degree influence factor. All runs optimized the gene pool towards the fitness function very good. Some were just faster. But I haven't spent to much time trying to optimize these as a serious run with a complex fitness function takes about a week to complete. 

Here is the evolutionary progress of a run regarding the material weights. Already in generation 9 the values are very good, stable and close to their final values (except maybe for the queen weight).

Convergence data of the material values

Convergence of the Probability Vector after 9, 200, 400 and 1100 generations

As a measurement of increasing strength I checked the ability of the engines to find the best move in a set of positions. After less than 200 generations the engines reached the strength of my manual "tuned" engine. After 1000 generations the engines solved much more. Whether they also play better chess is yet to prove.

  

Chess evaluation evolution

My little chess engine plays correct chess for some time now and also reached a decent strength level. So it is not yet among the worlds top 100 chess engines but the goal is in sight at least (place 117).

So far I haven't spent any time with tuning the evaluation. That does not mean its evaluation is simple. It is not, it possesses already a lot of chess knowledge but it is not able to use that knowledge to its full extend. Besides some basic material knowledge it also understands the concepts of mobility, center control, king safety, basic pawn structure properties, passed pawns or development.

So ice knows that having a doubled pawn is considered a liability and having control of the center is usually an advantage. So it will try to avoid unnecessarily doubling its pawns and will play moves that improve its influence in the center. But a game of chess consists usually of trade offs, unless your opponent makes a mistake you don't get anything for free. So it might be a good deal in a position to double the pawns if this also leads to more center control and a half open file for the rook, or it might still be bad deal.

Those things to decide are very difficult for an engine. A human will use its intuition for that which comes from experience, but an engine does not have this. It has to use a mathematical approach to decide whether some positional imbalances are good or bad for it.

And here tuning the evaluation features comes into play. With good tuned features an engine will be better in estimating whether the positional concessions in a line of play are worth it or whether this line should be avoided. Unfortunately picking the correct values is very tough and most of the values are connected somehow.

A simple example. Most chess players learn very early that a pawn is worth 1 point, knight and bishop 3, the rook 5 and the queen 9. Those are values that can be used as material values for the pieces. So now you add a bonus for the rook on an open file, this will increase the overall value of the rook, so to keep everything in balance its material value must be lowered. As my evaluation consists of more than a 100 terms that all are somehow connected the task of finding an optimal balanced setting lets the traveling sales man problem look like an easy job.

As I was always fascinated by genetic algorithms to solve optimization problems I decided to give it a try to optimize my evaluation. The general public opinion in the chess community is that it does not work. Of course this can also mean that it does work but the people that were successful with it don't talk about it. Having an effective and working automated evaluation tuner will give them a big competitive advantage against the manual weight pickers, so why give it away. I wanted to try it anyway because at least I learn something with it, even if it fails. And it is much more interesting than boring manual tuning.

I decided not to use some existing GA C libraries but to program the algorithm myself. Over the past month I dedicated a bit of my time to it and slowly an advanced tuning framework evolved. And my new i7 will provide the horse power to run it.

So far I did a few runs with different GA parameter settings and the results look promising. I might not be able to find the perfect weights but I'm surely able to find better weights than I would be able to find manually. So it is at least for me a limited form of success, and maybe more than that.

To find out I have to further test the evolved solutions with different parameters and fitness functions against the former version of ice and also against other engines. This will take some more time. Luckily not mine, everything runs automated and unattended, just my electricity bill will probably get a hit.

Multithreading in Windows

The main purpose of my little chess engine project is to grow my computer science skills by doing stuff I haven't done before. Chess programming is great for that because the such a project is small enough to be handled by a single person but complex enough to keep you busy for a long time.

It touches so many areas. You focus on complex high level algorithms and data structures but also on the assembler code that a certain compiler for a certain target platform creates to check whether your programs runs efficiently.    

Between Christmas and New Year I had a bit of time and decided to look into one area that always scared me so far.


Multi-Threading

It is not a completely new concept to iCE because it already dispatches a 2nd thread when started. But the only purpose of this thread is to listen for potential commands sent to the engine to keep the engine responsive even when doing some heavy calculations. The thread is very simple and most of the time just blocked because there is no input. I had to learn some nasty low level API calls to get a thread dispached like

 hThread = CreateThread( NULL, 0, (LPTHREAD_START_ROUTINE) TInputThread::execute, (LPVOID) this, 0, &dwThreadID );

but I got it working.

The real fun starts when multiple threads work on the same data to speed up the overall execution.I don't want to go there for my chess engine yet. It probably requires some significant design changes but for my tuning efforts I though it might be fun to build a multi-threaded tuning framework where different versions of my engine are tested in parallel.

A version of my engine is characterized by a set of evaluation parameter values. Due to my recent efforts those values can be changed anytime without recompiling the code. The tuning process might now build up a work queue of different parameter sets and test the performance of the engine with one of those sets in certain well defined tasks like solving mate puzzles or playing tons of games. This is a real CPU stress test and to fully utilize my new i7 running the whole stuff on a single core doesn't seem the smartest thing to do.  

So I had a reason to have a deeper look into multi-threading. I know how to start and control independent threads but I had no clue how difficult it is to synchronize threads. The usual way of doing  things just don't work. A simple

 if (myQueue.size() > 0) myQueue.pop();    // remove the first element from a queue

doesn't work any longer, because even if queue.size returns a value > 0 there is no guarantee that there is still an item in the queue if the execution reaches queue.pop. Another thread could have just removed the last item between the two calls.

In order to avoid such race conditions the sensitive parts must be protected with something called a critical section for threads or a mutex for process synchronization. There are tons of publications available how to do that and I had a good reading between the years.

One very clever technique I learned is called RAII (Resource Acquisition is Initialization). It basically means to wrap a C++ class around a critical section resource. The critical section is acquired with the construction of the class and freed when the class is destroyed. As in C++ an object is automatically destroyed when it leaves the scope the danger of not freeing a critical section (because of an exception within the code or a forgotten branch) is greatly reduced.

I now feel now a bit more comfortable about writing multi-threaded code. Maybe in a distant future iCE will use more that a 2nd little input handling thread.

We'll see.

Getting used to some C++ techniques

In the new release of my engine I plan to rewrite its board evaluation (again). This is necessary because the old evaluation uses weights declared as compile time constants.

e.g. const int BISHOP_PAIR_BONUS = 50;

This is easy to maintain and also very fast because the compiler just inserts the value in the evaluation code and no memory access is later required to find out what the bonus for having two bishops is. The problem starts when you want to change that value. It requires a recompilation of the whole program. As I want to be able to change that value at run-time, maybe even while the engine is running using constant values is not an option anymore. I have to replace them with variables even if it might slowdown execution a bit, probably not much because those values are accessed so frequently that they will stay in the L1 cache of the CPU.

But it means that I have to touch everything in my board evaluation code and if I have to touch everything anyway I can just as well clean it up a bit.

One thing that bothered me a bit is code duplication. Every feature is evaluated first for white and then again for black. The implementation of the features is not identical, e.g. white pawns move up black pawns move down, white king is safe at G1, black king is safe at G8. But the source code is very similar anyway and differs only in a few parameters. It also makes the code harder to maintain because every time I change something I must remember to change it in the WHITE and in the BLACK part of the code.

Fortunately C++ offers a language construct called function template. It's main purpose is to uses the same code to work with different types of variables e.g. a sort function that sorts integers uses the same logic as a function that sorts floats, it uses just a different declaration. C++ templates allow the programmer now to write the source code only once and the compiler will create the different code for ints and floats automatically.

This is awesome and just what I need.

While rewriting the evaluation I extract those parts where templates might be helpful and clean up my code.

Instead of a function

void TEvaluator::evaluateThreats()

{

     // do something for white threats against black pieces

     ...

    // now do the same for black threats against white pieces

    ...

}

I have now a template function

template< EColor side > void TEvaluator::evaluateThreats()

{

    const EColor enemySide = (side == WHITE ? BLACK : WHITE);

    // do something for threats of "side" against the pieces of the "enemy side"

    ...

}

which is then called via

evaluateThreats< WHITE >();

evaluateThreats< BLACK >();

This works so well that I might rewrite other parts of the engine as well at some point in the future. The move generator currently duplicates code like hell and could definitely benefit from this technique a lot.

A simultaneous over the board experience

I usually don't play over the board. I find it interesting but I don't have the time for that. I never played in clubs or tournaments. My chess efforts are rather programming related. But today I was visiting a local gaming fair and part of it was IM Cliff Wichmann playing 16 boards simultaneous chess. My wife convinced me to play one of the boards. I did and no surprise I lost but not as badly as I thought.

I played black and had a rather bad opening. White played a Queens Gambit and I actually don't know much theory of it. My chess engine plays openings from its opening database so I did not put much efforts in learning all the variations while programming it. So my little knight was chased around and White had the control of the center after 1. d4 d5 2. c4 Nf6 3. cd Nxd5 4. e4

However I survived the opening without plundering away any material and had a rather strong middle game. Our play led later to this position.

 IM Cliff Wichmann vs. Thomas Petzke

  White to Move

So I had a knight and rook vs. the bishop pair which I considered Ok. I analyzed the position at home with iCE and also stockfish. Both agree that black has a slight advantage of a bit more than a pawn here. But due to my lack of routine I wasn't able to hold that advantage. I had played already 90 minutes and my board was one of only 3 boards that were still played in the tournament. So my thinking time dropped because with only 3 boards left my opponent appeared very rapidly after his move at my board again. 

He stormed with his h and g pawn, I was later forced to trade my rook against a bishop and a pawn and he finally promoted 1 move before I could where I resigned. 

It was quite an interesting experience anyway.