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.

Final DevLog before First Ship - Boss Battle

I don’t think words can explain what I made so click here to watch a video on my probably final major addition (no pressure)
& also help with a small dilemma I have.

NO!! that does not mean this game will stop development, but i think i finally have enough hours (+10-15 more safety) to get a Framework 12! (and then i will be able to crack on with entrance exams - so i guess development will slow a touch).

Of course I’ll ship once the game is polished enough.

You might see a devlog or two from the “Capital Chaos Website” - follow me ;)

I really hope you guys all enjoy it and now I need to do the readme and stuff. I also realised I was one of the most viewed on Stardance which is honestly amazing and I appreciate all of the support :)

And thank you to all the new friends I’ve made and all the followers and commenters. It’s honestly been insane.

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

Tooltips now show when hovering over items in enderchest UI