Chess Bot

I’ve added FEN strings! FEN strings (Forsyth-Edwards Notation) are a way to store positions of chess games. They are used by many chess engines to allow players to start from different positions or midway through games. Adding these wasn’t too difficult as the strings are formatted in a nice way. I simply split up the FEN string into its 6 parts and set my variables to the value in the FEN string. To test if it worked I inputted the FEN string 4kb1r/p2n1ppp/4q3/4p1B1/4P3/1Q6/PPP2PPP/2KR4 w k - 1 16 which gives the position of the famous opera game directly before the queen sacrifice. I then set the bot colour to white and was glad to see that it immediately found the best move (the queen sacrifice). I also added premoves so that I can choose my move in advance. I did this by just storing the move I make when it is the bot’s turn and playing it as soon as the bot plays. However I can only premove 1 move ahead. Next I will try to allow the user to premove multiple moves ahead.

Quiescent search is amazing! After adding it my bot instantly became better. A quiescent search just means that when evaluating a board state to a certain depth even if you reach that depth you need to evaluate until a quiet move (a move that isn’t a capture). This means that even if the bot reaches the max depth in the middle of a piece trade it won’t just think the move is amazing since all it can see it won a piece. Since I added the bot, when tested against other bots it has made 0 blunders! In fact it beat Li, a bot rated 2000 on chess.com ! I’m really proud of this and think it is really cool to say that my bot has beaten a 2000 rated bot. However, it only beat the bot once and so it could just be lucky. I was going to test it in 2 more games against the same bot but found myself getting bored of manually inputting moves into chess.com and my bot to get them to play each other. Therefore, I’m planning on making my bot able to play other bots on its own. To do this I will need to download the other bots and make my bot give properly formatted inputs and outputs.

Massive improvements in depth! I added 2 changes: null move pruning and late move reduction. Null move pruning is when the bot ‘passes its turn’, when searching for the best move. The bot then evaluates the board at a reduced depth after letting the opponent play twice in a row. If it is still in a winning position then that means it is winning by a lot. This means that it can prune this branch since the opponent wouldn’t let the game get to this state and would make a better decision earlier in the tree. Since the opponent wouldn’t let the game get to this it means that further analysis isn’t necessary. Late move reduction works on the basis that I have good move ordering, which I just worked on so I would hope I do. Late move reduction means that I search the later moves at a reduced depth since the best moves are at the start and so later moves are likely bad. If they turn out to be good after the reduced evaluation depth then they are researched at the full depth. This helps reduce the amount of moves which need to be evaluated by a lot. Together null move pruning and late move reduction have taken my depth from around 6 - 7 in midgame to around depth 7 - 10 in midgame! In endgame this is even more. When I tested it in endgame it got to a depth of 13! My next change is something called quiescent search which will boost the bot’s elo by massive amounts as it should mostly stop the bot from making blunders.

Move ordering improved! I’ve merged my SCRUM-29/move-ordering branch with main and now have my improved move ordering in main. This has let me go from a depth of 5 to almost always a depth of at least 6. I then merged main into SCRUM-42/improve-maintainability so that I could add comments to the code I added from the move ordering branch. Next I am going to add some comments explaining what things do.

I’ve massively improved my organisation! I’m now properly utilising branches which is allowing me to work on multiple changes at the same time. Currently I am working on 2 branches. One is about improving my maintainability by adding comments so that other people can understand what I am doing and why. This also has the added benefit of me being able to make some small improvements and bug fixes as I am reading through all of my code. The second branch is about move ordering which is super important as it makes my alpha beta pruning more effective. Working on these changes on branches is useful because it not only keeps it organised and easy to see what each commit is for but also means that if I decide I don’t want the change anymore it is easy to remove as it isn’t mixed in with all the other changes. To help with this I’ve also created a Jira board which helps me keep my ideas organised. My branches are called SCRUM-NUMBER/NAME. The scrum number is given to me by Jira. As well as improving my organisation I also further improved my zobrist hashing by replacing using modulo on the hash to get the index of the transposition with using an and gate between my hash and the table size - 1 (which is just all 1s and a single 0 on the left most digit since the table size is a power of 2). I also stored my castle rights as a single 4 digit binary digit where each digit represents whether a certain rook has castling rights or not. My logic with this was since the point of bitboards is 12 integer is better than 64 integers, a single 4 digit integer is better than a dictionary of 4 values but I am not actually sure if this is true or not. On the maintainability branch so far I have added comments to all of main.py. On the move ordering branch I have improved my sorting from just sorting by most valuable capture and least valuable attacker which is only good for captures to also scoring promotions very highly. I also instantly push the previous best move to the front of the queue and score moves which cutoff branches in alpha beta pruning highly as well. Next I will try to add comments to one of my other files and improve my move ordering by not using lambda functions.

I’ve improved my endgame condition. When testing the bot I found that during endgame it would sometimes move its king to the corners of the board. I realised that this was because it saw a queen on the board and due to the poor endgame condition it thought this meant that it wasn’t endgame and instead used the early / mid game position bonus table which rewards staying safe in the corners. However in endgame moving the king to the corner isn’t good as it makes checkmates easier for the opponent and means that the king isn’t used to help checkmate the opponent, which is crucial in certain endgames such as a king and queen against just a king. In situations like this the king is necessary in achieving a checkmate. I changed it to being if there is less than (2 black queens and 2 white queens and less than 16 pieces) or if there is less than 5 pieces not including pawns. This is more accurate and ensures the king actually helps win and tries to stop a checkmate on itself. I also improved my zobrist hashing by fully incrementing it. Previously I incremented it for everything except castling and en passant however now these are implemented as well. I also noticed that the bot would walk its king towards the centre of the board during the opening which puzzled me until I read through my code and realised its because I set totalPieces to 0, asked if it was endgame, and afterwards set totalPieces to the true value. This was pretty difficult to find as I couldn’t see it by just seeing if it thought it was endgame at the end of a move. This makes sure I can actually get my hashes in O(1) time. Next I am going to try and make my arrows darker when over each other.

I’ve added a better endgame condition! Now endgame is determined if (there are no queens and less than 16 pieces on the board) or if there is less than 8 pieces on the board. This is better because it means when pawns promote the king doesn’t run to the corners or use the other position bonus table. I also improved my bot’s 3 fold repetition check when searching for moves by using a dictionary with hashes as keys and number of times they have appeared as values. This lets me check if I have been in the position 3 times before in O(1) instead of O(n). I also improved my makeMove() and previousMove() functions by checking if its the bot searching for moves and if it is then only storing the key information instead of everything. To help simplify previousMove() I instead created a seperate function called unmakeMove() (clearly related to makeMove()) to undo moves when the bot is searching. I also changed the time the bot has to move from 3 seconds to 1.5 seconds so that it feels snappier. Probably cos I have 0 patience when I want to test if the bot works :). Next I am going to try and make my bot faster by improving the move ordering so that alpha beta pruning can be more effective.

Iterative deepening! The bot now searches depths in an ascending order instead of descending. This is only possible thanks to my transposition tables but means that I can give the bot a time limit. Once the time limit is reached it just return the best move of the highest depth its fully searched. This means that I can search to different depths in different positions whilst making sure I always play within the time limit. This is good as it means I can have a high depth during the opening and endgame whilst having a medium depth during mid game instead of having a medium depth everywhere to ensure moves at midgame don’t take too long. Midgame usually has a lower depth due to the high number or possible moves that can be played. I can also easily change the time limit with just a single variable. This means I can get my bot to play faster but also worse or take longer but play better. I added incremental evaluation. This means that for each move, instead of looping through all 12 bitboards and recalculating the evaluation score from scratch I instead update it from the current evaluation score. So when I move a piece I subtract its old it’s material value and then add the material value if it still exists. The same happens for the position bonuses. This takes my time complexity from O(n) to O(1) which is a massive upgrade. These changes lets my depth in early game and endgame almost always stay at 7 whilst during midgame hover between depth 6 and depth 7. Currently I determine if I am in endgame if both queens are gone and the total amount of pieces is below 16 however I feel that this isn’t a good measure and I should improve this. Next I will try to improve efficiency by improving my move ordering so that the alpha beta pruning is more efficient.

Transposition tables! I’ve added zobrist hashing so that I can create a dictionary that contains all of the board states I have already evaluated. Since many different moves can lead to the same position it means that I can save computing power by just getting the score of that board state instead of having to re-evaluate the board again. Zobrist hashes are just a way to represent the board in hash. This is useful as I can use them as the keys in my dictionary and quickly see if the current board state has been evaluated yet. I also fixed a bug that let the bot play illegal moves as there wasn’t a legality check after the aspiration window failed. An abort flag was also added that is set to True when the user undos or redos a move. This lets me instantly stop that thread’s search for the best move ensuring it doesn’t use unneccessary computing power. Next I am going to try and implement iterative deepening so that I can force the bot to move within a certain amount of time. This would let me make the bot play different ‘time controls’ by altering how long it has to think about what move it should play.

I tested it against some bots from chess.com and it managed to beat Wally (a 1800 bot) but lost to Li (a 2000 bot)

Improved efficiency! I’ve improved the efficiency of the bot by sorting the possible moves better. This is useful as it means when the alpha beta pruning goes over everything it searches the best trees first. This means that it can prune more branches. I also removed some random integer conversions on my bitboards as they did nothing, since the bitboards are already integers. I also removed a restriction that didn’t let the player do anything on the bot’s turn. Now the player can draw during the bot’s turn. I also went across all of my code and changed it to use (row, column) instead of (column, row). This helps keep things cleaner. I then also changed the bot calculations from from using the fullyLegalMoves() function to the movementLegalMoves function(). fullyLegalMoves() just makes sure that the king isnt in check after the move. If it is then it undoes the move. By insteading doing this in my bot.py it means I can just not undo the move and immediately remove that move. This means that I don’t need to undo the move more times than needed. This is very helful as undoing a move takes up computing power. I also completely replaced the piece names with integers as this would be slightly better and I could use bit operations with integers. As well as this I also added a timer that shows how long the bot took to make its move. By adding all of these changes the bot reduced its time on the first move as white from ~4 seconds (with depth 4) to 3 seconds (with depth 5). This shows that it is much more efficient as, time taken increases exponentially as depth increases. As well as this 3 seconds is the earliest the bot can move and so the true speed is likely much less.

Better arrows! I don’t remember where but there is one place where drawing arrows in a knights movement creates an L shaped arrow instead of just a normal arrow. I love this and so implemented it into my program. I also added aspiration windows. Aspiration windows work on the basis that moves don’t usually swing the score by a lot. This means that when going down paths we can set the lower and upper bounds to previous score ± window size. This helps prune more paths. If we find that the score is actually higher than we expect we search again but without the aspiration window. This helps remove lots of the obviously bad paths which makes the program much more efficient. Next I am going to add zobrist hashing so that I can use transposition tables.

Colour randomisation! The colour you play as is chosen at random at the start of the game. The board is also automatically rotated so that you are at the bottom and the bot is at the top. This also helps to show which colour you are playing as. I also show the last move by making the starting square #97C997 and the ending square #8DCE8D. I did this as when I asked I watched someone play it I noticed that they would often undo the move, to see what the bot just did, then redo the move again. This helps make everything feel more polished. I like the ending square colour ( #8DCE8D ) but I’m not sure if I like the starting square colour ( #97C997 ). These colours are very easy to change though and so I can quickly edit them to test out different colours. I also realised that when I eventually ship the project most people who download it won’t have the font I use ( dynapuff ) installed. I tested it out to see what it is like without it and found that it crashed. To fix this, I implemented a try - except statement which sees if dynapuff exists on the user’s computer. If it does then it uses dynapuff which is how it is supposed to be played but if they don’t have the font it uses arial instead. Due to the strange spacing of dynapuff I used double spaces between the words on the game over messages, but when using arial the double spaces look quite strange. I also tweaked some of the position bonus values to further encourage castling. Next I am going to try to add a file to reward moves which keep keep the king safe.

I’ve added position bonuses! I created a new file which rewards moves which place certain pieces in certain areas. For example pawns are rewarded for controlling the centre and pushing to the 7th rank (so that they can promote). The bot now tries to control squares and this means it now has proper openings. I also completely updated the file structure to split the responsibilities more clearly. I also updated main.py and logic.py and made them classes. Making logic.py a class means that I can use it for both the player actions and bot actions without them interfering. This also makes my previousMove() much cleaner as it means when the bot uses it, it doesn’t interfere with when the player uses it. Due to the new file structure it means that I can easily change the weights of each of the different modules to change how the bot plays easily. Later I will add a slider or at least a setting that lets the player control these modules. As well as this I also changed it so that drawing the same arrow again removes the arrow. Next I am going to try add another module that rewards moves which keep the king safe.

I’ve added a bot! The main point of this was to link the new file I made (bot.py) to main.py. The bot currently just chooses moves based off of what would result in the best material difference between white (player) and black (bot). It calculates these moves with a depth of 4. Since the main point wasn’t to actually make a bot in one go the bot isn’t very good currently. However I still added alpha beta pruning. Alpha beta pruning works by storing the best guaranteed outcome for you (alpha) and the best guaranteed outcome for the opponent (beta). Whenever it finds a path where the opponent can force a move that is worse than the alpha, it immediately stops going down that path. The same happens for beta. I also removed some duplicated code in main.py and fixed the undo and redo move logic as I forgot to check if it still worked properly after switching from tkinter to pygame. Currently you can only tap the buttons and but can’t hold to go back multiple moves. Undoing and redoing moves with a bot was a bit confusing for me and so I decided to make it so that when undoing and redoing there is 3 seconds before the bot moves. During these 3 seconds you can go forwards or backwards to reset the timer. I used threading so that the bot starts to calculate what move it would make at the same time as the 3 seconds are passing. This means that if you decide to stay on the turn you don’t need to wait as long. I also blurred the background of the the promotion GUI so that it is grabs the players attention. Next I am going to try and add a better bot by assigning each possible move a score that is based off of the squares it controls, offensive and defensive opportunities and potentials for forks (when 2 pieces are being attacked by 1 piece so only one piece can move out of danger).

I’ve split my file into 5 now. There is moveGeneration.py which calculates all the legal moves, moveExecution.py which actually moves the pieces, updateBoard.py which updates the board, gui.py which handles graphics (like arrows, promotion page and clicks) and main.py which says what functions should happen when an input is given and has a while loop for while the game is running (as is needed by pygame). Splitting the file makes it much easier to debug, keep track and add features instead of just having one ~1000 line file where everything is jumbled up. Next I am going to start work on the actual bot.

Insufficient material and 50 move rule! These were the last things I needed to add before step 1 was complete. Now the next step is to actually add the bot! I’ve got everything I need down for a game of chess before 2 players. I added insufficient material by creating a new insufficientMaterial(). Inside the function are some if statements that determine whether winning is still possible (not assisted by opponent going into the corner). I also added the 50 move rule by checking moves since last pawn advancement or capture and if it exceeds 50 then end the game. I also made it so that once the game ends you can go undo moves and continue playing instead of just having the game end. Next I am going to try to clean up my code, split the code into multiple files and optimise it.

En passant has been added. I find if it is legal by making sure the pawn capturing is on its fifth rank and the pawn being captured is moved 2 forward. Thats all I need for en passant (also only available for the first go it is there). I also made my program more efficient by ensuring I only rely on an array for finding what piece is on an index and drawing. Everything else uses bitboards which helps me fully utilise bitboards. I now have 2 things left: 50 move rule and Insufficient Material. Both of these end in a draw and are the last things I need for my program to have all the rules of chess! Next I will add the 50 move rule

I was so unimpressed by how my old arrows looked I just completely switched libraries! I now use pygame instead of tkinter. It offers much more graphical customisability and now I can draw arrows (and other shapes) with true transparency instead of just stipples. One of the main downsides of pygame is that it constantly redraws each frame. This takes computing power and drains battery. To stop this I created a redraw boolean which tells my script when to redraw. This means instead of redrawing every single frame I redraw whenever something actually changes. Due to pygame I also customised the arrows so that the tails are rounded. This means that multiple arrows from the same point looks much cleaner. I also get true translucency instead of stipples and I added an icon!

Need to get your strategies into something you can see? Lines let you do just that. Right clicking and dragging draws a line that follows your cursor around. Right clicking again places the line. The lines are automatically centred so that they snap to the centre of the squares. If you line starts and ends at the same place it creates a circle instead. I also spent lots of time making sure my bitboards are used properly as when I created the array last time I used it for more than I intended and lost most of the arrays of bitboards. I also noticed that the promotion GUI wasn’t properly centred and so fixed that. I don’t really like the lines as they use stipples instead of a solid colour and overall don’t look nice but tkinter doesn’t offer transparency apart from stipples and doesn’t allow lots of customisation of the arrows. Next I will likely try to add en passant.

Finally, promotions! This was the last major part of chess that I didn’t have. I added it by finding the row of the piece when I move something. I hardcoded it so that it knows when the pawn is at the last row. When at the last row, it runs a choosePromotion() function. That function then creates a frame inside of my window. I then loop for each of the choices of the pieces I can choose. For each of these pieces I create a button with the piece (in the correct colour) in the centre. The frame waits until I pick a choice before adding a 1 on that piece’s bitboard at the correct location and removes the 1 on the pawn bitboard. Thats all I need to do to register a promotion! The rest of the time I spent optimising my code and realising that I didn’t have to use just a bitboard or an array, I could use both. Knowing that, I removed my getPiece() function and instead used an array to find the piece at a row and column. This is more efficient as arrays have a lookup time of O(1) whereas the getPiece() function has a lookup time of O(n) in the worst case. This is because my getPiece() function worked by cycling through each bitboard to find what piece was at a certain coordinate. This meant that I could also remove my totalPieces bitboard since this was only used in the getPiece() function to avoid cycling through all 12 bitboards if there was nothing there. Overall I’m really happy with how everything is going as I have all I really need for a proper game of 2 player chess. Next I am going to try and add the small things I am still missing such as En passant and the 50 move rule.

Stalemates and three-fold repetition have now been added. Stalemates are calculated if legalMoves(turnColour) returns none but the king is not in check. I find if there is three-fold repetition by storing a hash of the board every move. This is stored in a dictionary as dictionaries are much better than arrays for lookups. After each move I see if that board state is in the dictionary. If it is I increase its value by 1. If not I set its value to 1. I then see how many times its reached that board state and if it is 3 times I end the game and show bright red text saying ‘Three-fold Repetition! Nobody wins!’. The hash includes piece positions, turn colour and castling rights as these are 3 of the 4 criteria that FIDE use. The fourth is en passant however that has not been added yet. Next I will add pawn promotions as this is the last major thing I don’t have.

Castling! I’ve actually added castling this time. The castling also works with undo / redo move so that it undoes and redoes the move correctly. I’m starting to think my python file is getting a bit big now so I also created a few helper functions to help reduce code duplication. Its 572 lines currently. Luckily I am quite close to finishing the actual board and getting everything ready for a 2 person game of chess. This was my first goal so that the bot just becomes one of the players. Once I’m ready for a 2 person game of chess I’ll try to create another python file for the bot. This will help me keep track of what is doing what. Next I am going to add pawn promotion as that’s one of the biggest things that I don’t have yet. It is essential in late game and so is one of my priorities.

Ever misclick and sell the game? Well not anymore! You can now undo moves by tapping the left arrow on the keybord and also redo those same moves if you change your mind by tapping the right arrow! I did this by adding a saveMove() function which I run after every move I make. This saves the details of the last move to the moveHistory array:

• Piece Moved
• Start Position
• End Position
• Piece Captured (Just “” if None)
• Turn Colour
• Moves so far

In my undoMove() function I remove the last move done and add it to an array called redoHistory. I then set all the details to the last entry in moveHistory. I do the same in my redoMove() function excpet I use the last entry in redoHistory instead. I’ve allowed undos after checkmate so that you can look for what went wrong and try other moves that might’ve stopped it. I also added sound! You’ll be able to see / hear all of this if the video uploads instead of just a screenshot. Next I am going to add castling (for real this time).

The game can now end! I have added a check to see if it is checkmate. When it is checkmate bright red text appears on the screen that says “Checkmate! WINNER wins!” (it says the colour which won not WINNER). I have also changed it so that when a player is in check they are forced to make a move that stops them from being in check. The only circles that come up are ones which would block the check to make it a bit easier for players. I’ve also made it so that my new function blockCheck() takes the calculations made by calculateLegalMoves() and uses it to display and allow only legal moves. As well as this anywhere that used to call calculateLegalMoves() now calls blockCheck instead. By making sure each function does 1 task it makes debugging easier ( not that anything would ever go wrong… ). Next I am going to try and add castling as this is a crucial mechanic that is used often.

I’ve added better red and green overlays that are translucent so that you can see through them an easily know what piece you are taking. But most importantly, I’ve added check detection. I created a few new functions to do this. The first function I created was the isSquareAttacked(row, column, atkColour) function. It works by cycling through the bitboards and checking if they are atkColour or not. If they are find the type of piece and those pieces could attack the king. I think this will be helpful when I start to actually make the bot. I also created a simple findKing(colour) function to see where the king is so that I can parse that information into the isSquareAttacked() function. I then get a boolean. If it is true (the king is in check) I add the red overlay to the king so that the player easily knows they are in check but I don’t actually force them to block the attack yet. I think the overlay should be different but am not sure what to make it (gimme some ideas). I also created a slidingMoves() function as in my calculateLegalMoves() function I had ~40 lines of almost fully repeated code. Next I am going to force the player to block the check and end the game if it is checkmate.

Finally took the time to change the piece textures so that black has an actual piece colour and you don’t get confused about whose pieces are whose

I’ve added dots to show where you can move when you click on a piece. If the position you want to move the piece to the dot is green but if it has an enemy piece the dot is red. Sadly, tkinter (the library I’m using) doesn’t support transparency. Because of this the dot takes up some of piece you want to capture. I can fix this by instead of drawing a circle drawing a translucent image… but tbh i rly cba. I will eventually do it to make it look better and actually add black pieces but i want to focus on getting things to actually work for now. The reason why this took me so long to implement is because as I was making the function to draw the dots I found that it was doing something very similar to my validMove() function but it was MUCH more efficient. In the old function I went through every square on the board and looked if the piece selected could get there. This is very inefficient and would build up quickly when I call the function 1000s of times per second (when I eventually add the bot). In my new function I look at the selected piece and have an array of each of the places it can move relative to its position. I then add the dots to those places if they are able to move there. This ended up with me just completely removing the old function and knowing its a valid move if there is a dot there. Next I am going to add something to see if the king is in check and maybe add some text when it is checkmate.

I’ve implemented bitboards instead of an array to store my board. At first I didn’t understand why bitboards were so good but after an amazing youtube video (here) I understand them and love them. I use them by having a 64 bit long integer (wow thats long) that represents the 8 by 8 board. Each bit can either be a 0 or 1 and represent whether there is a piece there or not. But you might think then how do you know what type of piece each 1 is? Thats why I use 12 bitboards (technically theres 1 more I added for extra efficiency but I don’t need that). Each of these 12 bitboards represents a type of piece in a specific colour (for example: white pawns and black pawns have 2 different bitboards). Then when I want to move pieces I create a position integer which is just 63 zeroes and a single 1 where the piece should be. I then invert this and use an AND statement so that all of the results for the AND are true where there are pieces apart from where I set the 1 at the start (though it is now a 0).

Added move legality. You can now mostly only make legal moves however I have not added something to checks if the king is in check. I made sure the move was legal by taking the startRow startColumn and endRow endColumn. I then look at what piece is being moved and ensure it is ok. If it isn’t nothing happens when you try to click and you have to make another move. I made sure that the correct colour moves as well. I also haven’t added pawn promotions, castling or en passant (tbh im not 100% certain on the rules of en passant). I couldn’t add castling as I don’t have a move history so would have no way of knowing if the king or rook have moved before. I’m now working on converting my current way of storing the board (a 2D array) into bitboards. After some research I found that bitboards are more than 5 times more efficient than arrays!

I can now move pieces! But there is no legality check yet. I also added a green outline if you select a piece. It works by listening for a click. Then when it gets a click it takes mouseX and mouseY and divides by positionSize to find which row and column it is on. It then checks against the board to see what is on that position. If it is a piece then it creates an outline and sets that as the active square. If it is empty AND active square has a value, it moves the piece.

I’ve finally decided to actually making a chess bot and stick to it! So far I’ve set up the chess board for just visuals. Everything right now is purely visual. I am using python and the tkinter library.