Creating a Chess Engine from Scratch

I am writing this article as a Journal to keep a record of my progress so far in this experimental project.

Backstory and Inspiration

I have been dumb at playing chess since childhood. I never won against a good opponent. even at the easiest level in a mobile game. I found some system design notes and problems. I enjoyed solving LLD (low-level design) problems in my mind and then reading the solution to check the depth of my knowledge. I came across designing a chess board game. And the design was very much what I thought, from creating an abstract class for a Piece, and inheriting other Pieces from it, each class will have its methods to move a piece and calculate the score on moving that Piece. Still, I have many questions unanswered after that like:

• Is chess so simple to design using OOP concepts? Do modern games do it like this?
  • I think it is what they do. What other ways could be there?
• How do they manage levels in a chess game?
  • If I had to guess, they take the top 10 moves with high scores and based on level choose the move to play.
• Is chess AI nothing, only a set of rules to decide a move with a high score?
  • This is something I had to discover, and I found that there is nothing like AI, it's just some advanced algorithms like minimax/negamax, alpha-beta pruning, etc.

Anyway, I decided that I would test myself If I could make a chess game that beats me. I chose Go as the programming language because I have only learned the basics of it, and this would enhance my skills. I chose fyne.io as the GUI framework because It was the only one with some good looking easy documentation.

Finding the best move

I want to keep it simple in the beginning. We will go with only 1 layer, searching for all the next possible moves
I found two cases where I need to calculate the score:

1. A piece shouldn't move
2. A piece should move

I think We eventually have to move a piece. so to simplify it, I came up with the following idea.

• if a piece moves
  • calculate its score
  • calculate other pieces loss if this one moves.
• final score = sum of both scores
• move the piece with the highest score

Scoring mechanism

I searched for scoring in chess and found that Rook is given more importance than the horse and bishop.
I think this choice is different from player to player. from my point of view, I will give my Rook to capture the opponent's Knight or Bishop. so they all should have equal scores.

• a piece gives check to king +20
• a piece captures pawn +20
• a piece captures rook +30
• a piece captures horse +30
• a piece captures bishop +30
• a piece captures queen +40
• a piece captures king +50

• a piece removes check on king +50

• pawn reaches last row +20

• pawn has a threat from someone on reaching a position -30

• Rook, Bishop, Knight has threat on reaching a position -40

• Queen has a threat on reaching a position -40

• King has a threat on reaching a position -50

Giving check to the king is only 20 points because what if your Queen is giving check to the king, but is also in danger. so I kept it minimum.
Initially, I started scoring from 10 points but changed it to 20. I realized that there will be a situation when the Pieces will try to keep their distance from one another, and this will result in a draw. so I will calculate the absolute distance of a piece from its nearest enemy and subtract its score from that distance.
Getting yourself captured is considered a loss, and to minimize it, I increased the loss score by +10
That's simple to start.

March 17, 2024

I decided that I wanted to make a cross-platform application, with a stack that I don't know. so that I will be able to learn it. I spent the whole day creating the board design in Fyne. It's not that simple, the framework is evolving but It doesn't give me what I wanted. I tried to put 64 cells in an 8x8 grid and resize all cells to 50x50 but the resize was not working. I checked many answers on stack overflow related to resizing but nothing worked. Later I found a video on YouTube, the person there did something different from what I was doing (still using the resize function) and it worked. I got super annoyed by it. As you can see I have so much going on in mind related to chess scoring, capturing pieces, and designing with the software principles I learned, and I am stuck on a UI issue. With this, I will not be able to go anywhere.

So I went to look for other options the other day. The next language is Python. I found QT and Tkinter frameworks. I have made a small tik-tak-toe game in Tkinter in the past, and it's good too. But QT is the most advanced and popular, so I went to look at its documentation and It's nothing in comparison to React UI libraries / tkinter / Fyne / Flutter. There is no good visual tutorial, only references to the API, and It's huge. I don't want to go with tkinter because it's very basic, like fyne and I am afraid I will get stuck there too.

The next I know is flutter/dart. I have worked previously on it and it's great. It now supports build for desktops too and has very flexible widgets that you can style as you want. But I need to reinstall and set it for desktop and mobile builds. I can't do that, because it will take a whole day also and I will not be able to put my ideas into code. I needed something fast. So I decided that I would fall to React/JS for making the game and then rewrite the logic on Flutter later.

And I think I made the right choice. Making the game on React was so fast because designing the chess board was very easy due to all the HTML and CSS. I made all chess piece classes, wrote the move and scoring logic for all of them, and made it run. So far, everything in my head is in the code now. Now I can take a sleep.

The game is very nice, playing by the rules. It can beat me at this point, just like any other Chess game out there. For debugging I added the score so when I click on a piece, it shows me the score of that piece if it moves to one of the movable cells.

There are a few things left to add to it like:

• adding the castling (king and rook interchange position) move
• detecting a checkmate or draw and stopping the game there
• adding the history of moves and undo functionality
• adding animation for a move
• load the game from a saved file

I realized I am missing 1 thing, which is the motivation to move a pawn. moving it forward will help to promote it, but for the time it needs to be protected well too. That is hard to solve.

March 18, 2024

Last night, my game was almost complete, so now I had the question can It beat any other chess AI out there? Of course not. Now I have two more questions to answer:

1. What do other chess game engines do differently?
2. Is chess AI a real thing or it's just some more better algorithm?

I spent the whole night on Internet looking for answers. I found that other chess engines have different scoring mechanisms than mine and different strategies to decide the moves.

One such implementation is to assign a fixed score to every position for a piece, then for each move calculate the sum of all your scores and your opponent score. subtract them to get your score for that move. I am not going with that idea because I cannot understand the piece square table. As this is a stationary table and pieces can move anywhere on the board.

But this gave me the idea of making my algorithm better.

trial 1: I will try to find all moves, for each move, calculate your and the enemy's total score from all pieces, and subtract them to get the final score.

The Implementation also uses minimax and alpha-beta pruning which I am not going to use until I understand those two completely.

---

I keep looking for AI Chess engine implementation and found about Stockfish, and Leela Chess Zero(LC0). I found that LC0 uses MCTS (Mont-Carlo Tree Search). It's another term I don't want to know about. Because when I hear AI, I want to hear tensorflow/keras in play.

And so I changed the search prompt a little to "Neural Network Based Chess Engine".
I found this repository which has the Journal of the Chess Engine Progress, I liked reading it and decided that I will maintain my journal too. And so I am writing all this stuff.

At first, I wasn't clear about the way he had implemented it. For creating a neural network, what I need is an input layer, output layer, optimizer, and loss function. I was able to get all those from his Journal except the output layer. I was thinking what will be the target we have to predict and what will the output layer give us? How the NN will help us find the best move? Then I found DeepPink

It was a similar implementation as his journal. I found the output is in the form of -1,0,1, where -1 is lose, 0 is draw, and 1 is win.
Still after reading all this. I am not able to completely grab everything, like the evaluation function they used. It's just that I don't understand that level of mathematics.

Also about the dataset, they use PGN format, It's good, but I am not sure how to make my matrix using that format now. For now, I will generate my own data, if I need more data then I will think of visiting PGN again.

---

Here is what I am going to do:

trial 3: The data is going to be generated by keeping a record of all moves of both the players in 8 x 8 x 12 matrix form which tells the position of 12 pieces across an 8x8 board. after the result of the game, there will be three targets assigned to the moves: 'win', 'lose', 'draw'
example: if p1 wins, all moves of p1 will be labelled as win.

I will train it using relu, categorical cross entropy, hidden layers not decided, the output will be dense(3)

For prediction, I will find all 1st-level possible moves from the current state of the board. I am not going deeper to get more moves. I will feed all those moves to my NN. for each prediction output will be three numbers, showing the probability of win, lose, and draw. if a win is available, the highest win probability is selected. else if the draw is available, the highest draw probability move is selected, and else lowest loss probability move is selected.

Before I do that, I want to try other classification algorithms, like decision trees.

trial 2: for that I will convert the data to 2d table, with 1 hot encoding all the dimensions of 8x8x12 and drop 1 column. this will give me 7+7+11 = 25 features

I also had the thought to use the score as a parameter in training, but then the results will be highly biased towards the score. so I am dropping this Idea.

---

March 19, 2024

Woke up this morning with a new Idea. Chess is a sequence of moves, where you can play a certain move only based on the outcomes of all previous moves. so it's like an NLP problem, isn't it? We can represent the chess board in the form of a long sentence and for each move, we will have to predict the next word in that sentence.
For this, I am going to make the data repetitive. like if a game has 10 moves, I will make 10 strings, adding 1 move to the previous one. and then annotate them with a win, lose, or draw based on what player played the move.
The problem now is how can I represent the whole board as a sentence, and if I get the next word in a sentence, how will I convert it back to a move? Was looking on the internet for any such approach and found this article and some other research papers. It's simply a PGN format. However, the format itself is a little ambiguous to me.

trial 4 I will modify the PGN format a little to include the piece type at the beginning of the word. Since training a case-sensitive model is not good enough, I will change the piece type notation from k K to bk wk for representing black king and white king.
A problem that I identified with NLP is what if the predicted word is impossible move? While training, we will add a custom loss function that will increase the loss if the generated move is impossible. and if an impossible move occurs in prediction, we will have to fall back to best best-scoring move. I will not use transfer learning for this, because I think I am feeding a completely different language, one which is not used for communicating.