Computers are dumb and Chess is hard

Computers are dumb

Computers have certainly affected our way of life in ways unimaginable a few decades ago and these wonderful machines are embedded almost everywhere and we call them smart-devices. But if you take a closer look they are actually hell'a dumb and they remind me of the comedy sketch from Little Britain - Computer says - no.
Little Britain - Computer says - no

It's been a week since I made my first blog about my bot/engine development. I challenged my friends to play it, played it myself and some lichess community players also gave it a go and even left very nice and constructive analysis. If you want to play my bot send it an unlimited challenge, though currently it moves painfully slow - https://lichess.org/@/likeawizard-bot
You can also find all the code and play around with it yourself from my public GitHub Repository

I'll start of with a checklist of things have changed since then and then I'll dive deeper into more involved topics.

• Various small performance upgrades. All these changes added up to around doubling the performance of move search speed.
• A lot of improvements to the eval function. These improvements of course cost some performance. So the performance gained was again given up for smarter play. The engine now considers more tactical/strategic elements of the position:
  • Bishops are now additionally valued according to what diagonals they occupy.
  • Knights on the rim are dim. Knights are valued less on the edge of the board and more when occupying central squares.
  • Pawns that are advanced become valued more, especially when they are on the 7th rank.
• The engine now has understanding of checkmates and stalemates
  • While I had not defined a checkmate specifically previously, I had put the condition that losing the king would end up with a +/- infinity score. This should theoretically force the engine to avoid losing its king and thus getting mated at all cost but it is a bit obtuse way of dealing with things.
  • Stalemates need to explicitly be defined and dealt with. If stalemate draw conditions are not hard-coded, then most stalemating positions are actually quite desirable in terms of restricting your opponent etc.
• A lot of improvements to code quality and lichess API integration.
• Some major bug with move searching.
  • At its most basic implementation chess engines use a MinMax search. In this search algorithm the engine looks at all available moves. It then picks the best move for white (maximizes the score) then it looks at all the possible responses and looks for the best move for black (minimizes, hence the min-max name). Given that on average each side has 31~35 legal moves in a given chess position this means that if we would look at all the moves at depth four we would end up with about 30 to the power of 4 positions. That's 800'000 positions. At depth five we get 24 million positions. And the number rises exponentially with depth.
  • This naive min-max approach is very safe, easy to understand and robust but it is expensive and slow. Of course a human only analyzes a few candidate moves and quickly disregards bad moves. The same can be done to the min-max algorithm - a modified algorithm called Alpha-Beta pruning. The alpha-beta algorithm is very similar to min-max but it also keeps a track of the best and worst results. So often times we can detect positions where further searches are futile as they can no longer improve on a previously found move sequence and it just gives up without wasting resources on a futile task.
  • This can save a lot of time but currently there seems to be a bug that produces strange lines and it might be that some lines that are considered not worth pursuing leak into and mix with the viable ones. Due to this it is currently running the slower min-max algorithm in favor of the theoretically superior but buggy alpha-beta pruning one.
• Other high priority improvements and fixes that need to be implemented:
  • Allow the engine to ponder on its next move. Say we run our engine at a search depth four. If it is not our turn and we are waiting for the opponent to move we can start looking at moves at depth 5. Once a move has been made we can narrow the search by looking only on the branches based on our opponents last move and now look at depth 4 again with some work already being done during the idle time on the opponents move and thus making the search quicker.
  • Further improvements to the evaluation function
    • Pawn valuation based on structural ideas can be improved - isolated, doubled, protected and passed pawn can easily have their values adjusted.
    • Try to come up with a concept of King safety. As now the engine sees castling as a very low priority goal. This will probably involve having friendly pieces near to the king. The kings distance from the center and the number of opposing pieces targeting squares near our king.

Chess is hard to talk about

When I say it's hard to talk about I don't mean it in the way that you might have to tell your children that Santa isn't real one day. Or having to explain your friends and family why there is an open box of cereal in your bathroom. It is complicated talking about it in a very concrete manner that is necessary to put it into code. When we study chess we hear about principles like piece activity, king safety, space, central control and others. But when asked to put those things into specific rules we often realize that they are very abstract and sometimes at odds with each other. Let's look at a few examples.

Piece activity and quality.

A bishop for example. What makes a good or a bad bishop? It is mostly quite simple:

• Is it on a good diagonal? The a1h8 and a8h1 being the major diagonals and then a2g8, b1h7 and a7g1, b8h2 diagonals are usually where you would want to put your bishops on to have the most scope.
• A bishop is said to be great when it has targets - pieces and pawns are placed on the same color squares as our bishop.

However, what if those great diagonals are blocked? And those pieces are all well protected and our bishop is only being blocked by a powerful pawn chain. Even more subtle question comes up- piece activity and quality are certainly real things. However, how do you put a number on it? If my bishop is beautifully fianchetto'ed and is aiming at my opponent's King etc etc. All the hallmarks of what we call a killer bishop are there but what does it mean? Is this bishop worth 3.3 points instead of the basic 3? Four? Maybe even five?

These are hard questions and those are historically also some of the biggest challenges all competitive chess engines have been struggling with.

What is king safety?

It's of course obvious that when you're in check you're not safe. That's not a very thorough take on the question. Obviously castling is the most common way of getting your King to safety. In my own games I have many times castled only for the opponents pawn rolling down the board with their pieces following up and it all falls apart. The best description of King safety I have heard is - give your opponent a few moves in a row. Can they create with those moves an immediate and real threat? If no the King can be considered safe. Another issue is when does the King have to man-up and step up and enter the endgame as an attacking piece.

Again when we're playing a game we mostly can make a good guess on these factors but could you with confidence put it in concrete rules and numbers that don't contradict each other?

A small selection of games

First is a game against a community member on lichess. While there are certainly some very dubious moves by the engine during the match, some possibly due to the aforementioned bug. I really liked how the engine employed pins to tactically protect its Bishop and it immediately jumped on the blunder of the human player. However, once the middle-game came to an end it could not understand how to make progress and missed some serious chances of winning. The simple human plan of bring your King and push&promote could not be stopped.

Having coded it myself and observing its play I knew how to abuse it - avoid tactics and let it implode over self-inflicted strategic weaknesses. Closing the position and putting my rooks on the only semi-open file staring down on a poorly protected knight and weak backwards pawn was too much for it to handle.

And here's a small redemption for our protagonist the engine. My buddy again being a good sport played a game. The engine had the ugliest looking position and pieces placed in such an awkward way that it was easy for a human to make an obvious blunder and the finish of the game with castling to set up a bishop sacrifice into mate was just cute.