How to Make Your Very Own A.I. Chess Program! Part 1
Invented in India around the 8th Century, the history of chess can be traced back nearly 1500 years! With a wide range of 250-750 million chess players, it’s clear that chess is one of the most played games, in our world today.
Yet, in 1997 the entire method of the way the game of chess was played changed forever. This is because, on May 11, 1997, Deep Blue made history as the first computer to beat a chess world champion in a six-game match under standard time controls.
According to The Conversation, What the match did, was signal the start of a societal shift that is gaining increasing speed and influence today.
In terms of chess, the heavy use of computer analysis has pushed the game itself in new directions. The machine doesn’t care about style or patterns or hundreds of years of established theory. It counts up the values of the chess pieces, analyzes a few billion moves, and counts them up again.
You can learn more, about the history of chess and the impact that A.I. has had on it here!
As I created an article on the Impact that A.I. has had on chess, it really got me thinking.
How difficult is it to create a chess computer that can play at a novice level?
How much coding will it require? Will it be Arduous and Enduring?
As I asked myself these questions, I decided to give it a shot, and try it out myself!
For Part 1 of this article, I will just go through the processes I underwent to create my own chess engine, and detail some of the challenges I faced!
After doing some research, and receiving feedback from peers and colleagues, I decided that it would be best to write my code in K & R, as it allows more compact code, making my job more easier and straightforward.
K & R, also known as Kernighan and Ritchie is the original dialect of the C Programming Language. I really suggest using this language, as it is the best program to develop system applications and operating systems which is exactly what we’re looking for!
Before diving into the processes and the steps I took, I’d like to define the goal I set out for when creating this chess engine. There is some form of misinterpretation over the exact definition of what represents a chess program. In my eyes…
The minimum requirement to qualify as an engine would be the ability to finish most games and play moves randomly chosen that are legal from the current position according to the FIDE rules.
Below, is a really great article that details the inherent processes and steps that the AI computer, Deep Blue had to take to become the best chess player the world has ever seen!
Now that we’ve decided what program fits our needs best, and what we’ve defined as a computer engine, I will now let you know what my step-by-step plan was, and include some of the biggest problems that I faced when creating this engine and what you can do to avoid it!
The Process
I split the entire game of chess, into 6 different subsets. These include…
- Basic Data Representation
- Move Generation
- Transposition Tables
- Search Algorithms
- Evaluation
- The Interface
Basic Data Representation
In terms of Basic Data Representations, pieces are encoded as integers which are eventually formed as bi-patterns. The encoding makes use of the binary representation by assigning a specific meaning to some bits of the integer encoding.
For example, the “8”- bit is set to indicate a white piece, where the “16”- bit indicates a black piece. The three low-order bits can be interpreted as a number 0–7 which indicates the piece type.
One problem to look out for is the fact that Black and White pawns both move in entirely different directions; with White pawns moving upstream and Black pawns heading downstream respectively.
We can use Type 1 to indicate white pawns, and Type 2 to indicate the latter in Black.
The complete list thus is {1,2,3,4,5,6,7} = {P+,P-,N,K,B,R,Q}. Type 0 is not used, so it can indicate empty squares on the board.
I’ll go further in detail, on the exact code that was used in Part 2 of the article, so keep a lookout for that!
Move Generation
In terms of Move Generation, there are four key outputs that we have to keep an eye out for! This includes…
- Basic Moves
- En Passant Capture
- Castling
- Pawn Promotions
Move Generation is induced by using three nested loops, which include…
- Over the Pieces
- Over, all Directions of that Piece
- Over, all Squares in that Direction
Without going too deep into the gritty detail, the overall idea is that the engine will be able to scan the board, recognize the location of its pieces, understand which squares are unoccupied, and play accordingly.
Transposition Tables
One cool feature that I incorporated into my computer engine, was the use of a hash table. In the game of chess, The same position can occur in many places in the search tree.
Not only can positions be reached by the same set of moves played in a different order, but pieces can also reach the same destination square through a different route. This in particular happens early in the opening, or late in the end-game.
The purpose of the hash table is to store useful information about a position so that the computer does not have to search it again if it is encountered a second time. Just this act alone, saved me hours of extra time, as I didn’t have to input additional information.
Search Algorithm
Similar to how Google works with its enhanced search algorithms, the efficiency of the alpha-beta search is incredibly important.
This concept, known as Internal Iterative Deepening works like a charm because instead of doing a full-width search including even the most idiotic moves, iterative deepening trains the engine to immediately find solutions for problems that have trivial solutions.
This is incredibly beneficial, as in deeper searches and more complex positions, the computer is able to calculate much faster and veer off of idiotic variations that make limited sense in the long run.
Evaluation: Mate
In the game of chess, the game is over when the king is in check and has no more moves that evade the threat. This is known as Checkmate. Teaching the engine, how to identify when the king is mated was one of the most difficult processes I had to face.
I decided that the best way to identify when the game was over, was when the king is fully captured. Meaning, instead of identifying that the king has no more spaces to move, the engine will just let it run through and will either win or resign the game when the king is captured.
The Interface: Checking Move Legality
When it comes to checking move legality, there are 3 primary factors that must be taken into account. These include…
- Doing the Moves
- Avoiding Check
- Capturing Pieces
I’ll go much more in-depth in the second part of this article, on how I had to breakdown each part accordingly, to ensure that all the moves which are being played are legal.
Though to break it down, to execute the moves at the game level, be it from user input or from the engine, the same code is used in the tree search. This allows, the computer to easily learn and adapt to making legal, and strong moves.
As of now, I believe that the computer level stands at around 1200 Elo. Which is good enough for it to be an average chess competitor! Making this computer engine was a lot of fun, and I had a great time playing against it in my free time!
Keep a lookout for Part 2 of my article, where I detail the actual code I used, and give a more in-depth explanation of my thought process, and my decisions!
