**# Journal

| Date | Title | Details |
|:-:|:-:|:-:|
|23.02|[Valid Move Generator (VMG)](https://github.com/kentaris/Bachelor-Thesis_Single-Player-Chess/blob/main/Bachelorarbeit/Stages/1_First_attempt/valid_moves.py)|I'm reading about PDDL and getting a better idea of how to implement chess in PDDL. I apparently need all possible states as a list in the domain.ppdl file, so I stopped reading and started implementing a python program that lists me all possible valid moves of a piece if only that piece is present on the board. I created a working terminal interface for it and calculated the possible valid moves for every piece to be able to verify my program output. It's now 23:20, and I implemented all pieces. It seems to work correctly and passes all tests. I hope I can use the outputs and don't find out that it was all for nothing. But even then... it still was fun to do.|
|24.02|FEN decoder/encoder|Today I tried to implement the PDDL Knight's tour problem, but I got 0 solutions as an answer after ~10 seconds. I also tried to implement the full chess problem with :types, but not sure how to do it yet. I then realized some things that were missing, which I may need later on and added some more functionality to the .py file I started doing yesterday I also implemented a FEN notation decoder/encoder which takes one of either the FEN code or the board position as input and gives me the other. the FEN.py also has functions to get the full movies, half moves, castling rights, who's turn it is and if en passant availability. I think I should have implemented everything in C++ from the get-go, but not sure if I should switch now or not. I probably should. I should read more of Haslum's chapter 2, so I am ready for my supervisor meeting on Monday. I didn't understand much of it the first time I went through it. I still have 37 pages to go through carefully. I understood and tested most of the first part.|
|25.02|PDDL File Generator|In my valid move generator, I forgot to take into account that the black pawns move in the opposite direction and also that they can jump 2 squares on the first move. I separated the 6 cases and made them callable by calling pawns(color, type) where 'type' can be either 'all' valid moves, only capture moves (sideways) or only forward moves. I may need that in the future for my PDDL file, so I have it ready now. I also wrote a program which saves me time and gives me an overview of the PDDL file by editing a template PDDL file, and the program then automatically inserts the lists of valid moves and so on in the correct spot.|
|26.02|Fixing|Not much noticeable has been coded today. I spent about an hour fixing minor mistakes and cleaning up my code. I also spent some time reading some PDDL instructions on the internet to better understand how to implement the complete chess problem in PDDL. I'm still kind of lost at this point, though.|
|27.02|FEN decoder/encoder integration|Today I integrated the FEN decoder/encoder. I can now give my PDDL File Generator a FEN code, and it will translate it into a series of fitting PDDL statements that are directly inserted into the PDDL file (instead of writing them by hand). This will make it way easier, later on, to define a start position and a goal (end/ mate) position by just giving a FEN Code, and it will automatically generate the PDDL file for me. Boards can now also optionally be printed out in colour and with Unicode chess symbols to make them more appealing to the eye. I also discovered many bugs and potential problems, which were either fixed now or marked as a possible source of errors with a ToDo entry.|
|28.02|Meeting|Today I had the meeting with Augusto. We now have a contract set up which is pending to be signed by everyone.|
|01.03|Knight's-Tour|I completed the knights' problem. It's primarily given in the book.|
|02.03|Two-Knight's-Tour|I worked on the 2-knights problem, but I did get 'ff: goal can be simplified to FALSE. No plan will solve it as an answer. If I comment out the restriction that the two knights can't be on the same square simultaneously, then I get 'Planner found 0 plan(s) in 11.005secs.|
|03.03|Two-Knight's-Walk|I learned a lot about PDDL today, and I will focus on reading from now on (instead of implementing). The Two-Knight's-Tour is now a Two-Knight's-Walk instead. Both knights cannot be in the same spot at the same time, and I got a plan with the help of Augusto ([planning.domain session](http://editor.planning.domains/#edit_session=kfziR44JuoW14XN)).|
|04.03|README cleanup|I didn't feel like continuing on the PDDL file, so I did some unnecessary but fun styling work. I made my ReadMe look nice and tidy for both dark-mode and light mode GitHub users, created a logo for the project because I felt like doing it, and I cleaned up some code in the FEN.py file, so the board is nice and tidy in both dark-mode terminals and bright mode terminals.|
|07.03|Official start of my thesis|The contract has been signed, and today in three months, I'll be finished with my thesis. Obviously, I already did some things before this date because I was excited about it and couldn't wait to get started.|
|09.03|Meeting & Coding|The meeting today with Augusto was productive. I know a lot more about how to continue and how to get it done. I'll be reading chapter 3 of the book for our next meeting. <br> The way the squares are labelled right now is problematic because I cannot differentiate between vertical and horizontal movement. I introduced ranks and files to solve this, which took way longer than I expected, but it now seems to work. I also changed the object hierarchy to be usable for the remaining figures on the board of both colours. I also changed the populate.py and population_generator.py accordingly to reflect this change. I also started encoding the pawn actions.|
|10.03|Pawn Moves|I implemented pawn moves. The planner is given a (FEN) starting position and can determine how to reach a given output position (using only knights and pawns so far). I tested it, and it works. I also realized that I don't need a two-fold hierarchy for location (rows and cols) like I assumed yesterday, so I reversed it.|
|11.03|King Moves|Today I implemented King moves. This was a relatively short task.|
|12.03|Rook, Bishop & Queen Moves|Today I implemented Rook moves, Bishop moves, and Queen moves, and it seems to work in the cases I tested so far. I need to read chapter 3 of the book to be finished in time for the meeting with Augusto on Tuesday, so I'll already assign it to the journal.|
|13.03|Reading|Today I re-read parts of chapter 2 because I only skim read them last time because some parts weren't very relevant and didn't make much sense to me then, but now they do.|
|14.03|reading chapter 3 & implement black pieces|Today I implemented the black pieces. I still have 2 separate moves for black and white pawns, which I don't like but I don' know how to combine them. Each of the six figures extends both the figure category and the colour category. I hope this will make it easier to implement taking turns and also that I can merge the 2 pawn actions into one action, so it is cleaner. At this point, I haven't read chapter 3, but I will do so till the meeting with Augusto tomorrow at 11am.|
|15.03|Meeting|Meeting with Augusto|
|16.03|Fast Downward|Today I started using the state of the art planner called [Fast Downward](https://www.fast-downward.org/ObtainingAndRunningFastDownward) because editor.planning.domains are using a very old planner that does not support PDDL 2.2. and I started using Axioms. I can now use the command `foo@bar:~$ ./fast-downward.py chess-domain.pddl chess-problem.pddl --search "eager_greedy([ff])" ` to execute the planner and generate a plan file. I extended my populate_PDDL.py file so that it does the populating and executing of the plan in one step. This should save me some time and make the workflow more appealing. It also converts the text file plan to a .plan file which can be viewed in the vs code extension. I implemented pawn double moves with the derived predicates to test the water. Pawn capturing will be implemented tomorrow.|
|17.03|Pawns|I tried to implement pawn captures with derived predicates and came across a problem: I cannot label the pawns correctly if they make an en-passant move: for example, if we have 3 pawns on the file n, I cannot tell which of the 3 came from file n-1 and which from file n+1. I asked Augusto, and he wrote: *"That is an interesting problem indeed. It will also occur with the other pieces actually -- e.g., the goal says that some rook should be in a specific position, but which one? One way we could solve it is to have predicates that indicate which piece (or none) is at a given position, instead of representing the specific object."* For now, I just ignore this and go around it. I rewrote my FEN decoder to correctly label PDDL format positions when pawns move: the pawns (and other pieces) are now marked by going through columns of the board instead of rows.|
|18.03|Rook,pawn move & time|I created a module which tells me how long the planner needed to execute and which also tells me how much slower/faster it has executed since the last time it ran. I realized that the program execution time varies even if every file involved stays the same, so I need to consider the average variation when making decisions. I have real-time feedback on my changes and their performance (I measured it to be about 10ms on my laptop). I also implemented the rook and pawn moves with recursive derive predicates so the domain file is more compact and so I don't need multiple problem/domain files for different board sizes.|
|19.03|pawn capture|I tried to implement pawn captures but couldn't correctly identify if the colour of the captured piece is not the colour of the capturer piece. I messed around with it a lot but couldn't get closer to a result, so I commented out the pawn capture for now. I also re-implemented Queen and Bishop movements in the recursive derivatives approach.|
|20.03|fixing|I realized some strange behaviour with rook and bishop moves in specific scenarios, which is now fixed. But one problem remains: bishops don't stay on the same diagonal. I tried to fix this by adding another recursive call in the "diag_reachable" derived predicate. This did fix the problem, but now the bishop can only move one move at a time, so I commented that line out again for now.|
|21.03|en passant, capturing & fixing|I found a relatively easy way to fix my bishop problem by introducing a ned derived predicate "same_diag", which checks if the square (next_file,next_file) is on the same diagonal as the from- and to-squares. I implemented the en passant move for pawns with the help of Augusto. I tried to extract the colour type of a pawn in a rather unnecessarily complicated approach, but Augusto pointed out that I can do it with simple static predicates, which is what I did right now. Pawns can now capture opposite-coloured pieces. This means I can delete the colour type. I realized that the planner runs almost twice as fast as before by doing so! I also finished encoding the capturing of pieces. What is still missing is the condition that my own coloured king can't be checked by moving my piece, which is pinned.|
|22.03|Meeting & Optimizing|Today I had a productive meeting with Augusto. We discussed how to model checks and pins. For the pins: The king will walk in all directions up until the end of the board, and if it finds a piece of the opposite colour that can capture it (bishop on diagonal, for ex.), then the piece between the king and that piece cannot move. The king thereby moves through exactly one own coloured piece. I also came across a problem that I'm unable to fix because I can't identify the source. Pawns can make a double move through a piece that blocks its way. But rooks and other pieces also have that problem if the piece stands exactly in front of them. While trying to locate the problem, I rewrote large parts of the code without success. As a side effect, I did accomplish a speedup in runtime tough (by a factor of 2x on the same problem), which is nice. |
|23.03|castling|Castling action (kingside and queenside) is now implemented. There is one minor problem: I can't correctly identify if the rook I'm castling with is my rook or my opponent's rook. This should only be a problem, though, if the starting position is a position where the rook of the opponent already is checking the king because as soon as a rook moves, it can no longer castle, so an opponent rook can't capture my own rook (for example) and then my king castles with it. Also, As soon as the check is implemented, this is no longer a problem because a king can't castle when he's in check.</br> </br>I wrote the following email to Augusto because I'm stuck at this point:</br>```I've been trying to get a hold of the in-check problem as we discussed, but It is getting very complicated and slow very fast so I think this might not be the best idea. The king needs to check from the position he wants to move to if there is a piece that can capture him by moving into all board directions to look for such a piece. The problem here is: that I need to further distinguish because the king can move diagonally towards a rook since he can only capture horizontally and vertically. The king can also move towards all other pieces (except the opponent king and queen) with some angle, and I need to consider this. I'm wondering if there is a better way to do it. Do you think it's possible to do some kind of virtual overlay? If I can get all pieces to label their paths as a sort of "red zone" for the king into which he can't move, this would be more efficient, I think. Also, I don't need to worry about all the cases mentioned above. The king can then check if he moves into a "red zone" or not. And pieces can check if they have a red zone somewhere around them and if there is a king on the same line to check if they are pinned. I'm not sure if I can get this to work or not, so I thought I'd run it by you first. I need to reset the "red zones" properly every time a piece moves. Maybe I can have "red zones" for all figures separately? This way, I must only reset the red zones for the figure which moves. And maybe I can further distinguish between red zones for black and red zones for white? Do you think this will work?```</br></br>Also, I realized that I can give the solver a "wrong" starting-&end-position combination, and it will still solve it in some cases. For example, the `start_FEN '5/5/Q4/R4/5'` and the `goal_FEN ='5/5/R4/5/5'`. The (formatted) output plan is: `queen_w1: A3->B4` & `rook_w1: A2->A3`, which means that the queen just moves out of the way to make space for the rook. But It stays on a square that I did not define to end up on. If I should allow this behaviour or force the output to be " 'sas_plan' not fount ", which would be more correct since the queen disappears in the input so the planner should not be able to solve this. Do you think I should enforce this by introducing a predicate like "removed", which must be true in the output? Or can I expect the input to be correct?|
|24.03|Reading|Augusto recommended that I read chapters 3,7,10, & 11 of 'Artificial Intelligence, A Modern Approach by Stuart Russell. Today I read chapter 3 since I'm not able to do too much with my code except think about it because I'm waiting for Augusto's thoughts on whether or not he thinks my suggestion works.|
|27.03|Captured|I implemented captured pieces. Before, pieces that weren't mentioned in the FEN goal state could dissappear or stay on the board as they pleased. For example: the planner will give me a solution when given the start_FEN '5/5/Q4/R4/5' and goal FEN '5/5/R4/5/5' which is queen_w1: A3->B4 & rook_w1: A2->A3. This makes sense since the queen just moves out of the way to make space for the rook but the queen is still present in the solution but not in the given goal FEN. This is not the case anymore now and the planner returns "'sas_plan' not fount" now (in the case abouve).|
|28.03|adjusting|I fixed some minor issues that made the input sometimes ununiform, so I had to go and change the problem file by hand. Now only the fen code can be given in all tested scenarios. This mainly concerns the removed pieces I implemented yesterday. I also made the population_generator.py create the colour types for me because I sometimes had to go and change it up by hand, and I like it to be automatic, so testing is easier and more precise. I also started to implement the check of the rook with the red zone approach.|
|29.03|meeting, unit tests|Today I had a meeting with Augusto; he was accommodating and immediately saw some problems in my code, which he pointed out. The rooks are now able to check the king. Also, I implemented unit tests. I realized that while doing changes, some things don't work anymore, and I always catch this too late. I now have a file unit_test.py where I store all unit tests, and they are executed with the command `python3 populate_PDDL.py test`, which will give me a summary at the end of ones that found a solution and which ones did not. The ones who did not find a solution are considered as failed. Maybe I will also implement unit tests that should fail sometime, but I think this is enough for now. Also, I could check if the output plan is correct, but I'm satisfied with the tests. I also found a problem with my numbering system.
My Fen-Code interpreter labels pawns from 1 to n by going column by column from top to bottom. This is a problem when a pawn behind a pawn is captured or if a pawn between two other pawns is captured. The captured pawn is the 2nd pawn `pawn_w2`, and in front of it is the 3rd pawn `pawn_w3`. When the pawn_w2 is missing in the goal state (aka has been captured), the pawns are again labelled column-wise from top to bottom, and since pawn_w2 is missing, my algorithm labels the pawn_w3 as pawn_w2. The planner takes way more time than it's supposed to whenever this happens. For example: this is solved in ~2secs: `[start_FEN='5/1pppp/1R1N1/PPP2/5',goal_FEN ='5/Ppp2/RPpN1/4p/5']` while the following has been going for at least an hour when I aborted it: `[start_FEN='5/1pppp/1R1N1/PPP2/5', goal_FEN ='5/PpP2/R1pN1/4p/5']`. There is just one little change: the additional en-passant move: b3->c4 at the end (white pawn captures black pawn).|
|30.01|fixing & speed up|I discovered quite some problems which were causing wrong outcomes in certain scenarios. I fixed it and added unit tests to check them. Right now, the uni tests only check if a solution is found, but I want to expand it at some point that they check if the solution is correct. The only reason I did not do this at this point is that the output plan changes as I make changes to the PDDL files, so this will be added later. I also discovered a problem where unsolvable :init & :goal states are given, but the planner keeps going for hours without outputting 'plan not found'. Mostly that is because of the problem with the numbering of pieces I mentioned yesterday, but I cannot say that it is the only reason. Also, I implemented checks for pawns. I also realized that I didn't implement en-passant. I just called it that. For en passant, I need to check if the last move has been a double pawn move, and I'm not yet sure how to do that.|
|31.03|pawn check, knight check & fixing|Pawn, rook and knight checks are implemented. I also started with the bishop, but I ran into a weird problem: if 2 bishops were on the board, bizarre behaviour would happen. I had to go through a lot of code until I could narrow down the origin of the mistake. The problem is the same as with the pawns described above somewhere. Since the bishops can't change the square colour and because my Fen decoder automatically adds all the predicates needed in the problem file, the bishops don't match up in some configurations where there are 2 bishops present. I am now changing the structure so that the removed predicate correctly assigns the black and white squared bishop automatically.|
|01.04|fixing, bishop check, queen check|Today I fixed the bishop assignment problem. Now only the pawns will be able to cause mix up issues because I don't know which pawn has been captured, so I can't correctly assign the end state pawns to the tart state pawns.|
|02.04|remove function|Today I was fighting with the removed function because I cannot get the logic right. I still haven't solved the problem.|
|03.04|fixing|I've uncovered some problems with some positions because my remove function is not always working correctly. I now fixed it and even simplified it a lot. My approach to it yesterday was unnecessarily complicated. Instead of just comparing the at predicates in the init and goal state, I add the removed predicates based on that instead of calculating them from the start and goal FEN as I tried in the last 2 days. Most unit tests are now working correctly again. Pawns are still causing problems, and I wrote Augusto a mail. I'm not sure how to fix it. I could just implement a chess solver or use an existing one which checks if the given goal position is possible to reach and, if so, how the pawns can be labelled to achieve it. There are probably many options to get to some pawn positions (we can imagine 3 pawns in a row: we don't know if the n+1'th pawn came from the left and the n-1'th pawn from the right or the other way round, for example, and those are not the only options. The best would be to implement it as a variable in PDDL, but that's not possible in a goal position. I hope Augusto has some input on this.|
|04.04|validation|Tonight I let my program run to see which problems present in my unit tests take how much time. I was surprised by how fast most problems are solved even with king checks in place. Some problems take very long (10-25 minutes), and some don't finish after even a few hours. I now implemented a [validation tool](https://github.com/niklasf/python-chess). This is a great tool which can do many things, but I only used it for one spot of my validator.py code. I directly take the original FEN, translate that FEN-code into an 8x8 board since the tool only accepts 8x8 boards, and then I simulate a step by taking the first instruction line in the .plan file given by the planner and move the piece accordingly. Now I translate the board back into its corresponding FEN code to be able to translate it into a chessboard instance of the python-chess module with the line `board=chess.Board(FEN.board_to_FEN(start_board)+' w KQkq - 0 1')`. I also append the moves that white can perform in the next step: `chess.Move.from_uci(move) inboard.legal_moves`, which checks if the given move (ex: `a4h4` for a horizontal rook movement) is in the set of legal moves which can be taken from the given board position. I do this for every line in the .plan file. If one step fails, the validate method returns False; it returns true. I also print out the result into a .txt file, so I don't lose it when it has run for several hours.|
|05.04|Meeting & taking turns|Today I had the meeting with Augusto. We discussed my progress and that I should get started with the report since it has been almost a month now since I started my thesis. We discussed how to implement pins, and I'm planning topics tomorrow. Today I finished the taking turns, but I commented it out for now, so it doesn't mess up my unit tests since they weren't written with turn-taking in mind, and I'm not sure if they all work out well. I'll have to go through them at some point, but there are more important things to do right now, such as validating the plan itself. I thought it worked yesterday, but it really doesn't. The python-chess module I'm using is not returning all possibilities, nor are the given possibilities all correct. I first thought my code was the problem, but it was not. I'm not sure if this is because the kings are missing in the positions I tested, and the solver can't handle that. I'll try another solver for this. Implementing it by hand would be too much to ask for this thesis, I think, and if I only implement it half-heartedly without the restrictions such as pins and so on, it won't be of much use as a validation.|
|06.04|validator.py|Today I fixed the validator; it's now working correctly.|
|07.04|One month|Today I passed the first month of my thesis, 3 more months to go. I fixed the turn-taking, I thought it was working, but it wasn't: I assumed that an action effect where I set (not(white_s_turn)) would act as a toggle (setting it to its opposite value), but I found out that it only sets it to false where it will stay. This is now solved with an ADL conditional effect. I also implemented a (not(my_king_in_check ?figure)) derived predicate and inserted it at all relevant spots so it should work. I couldn't test it tough because the pawns aren't removed anymore. I thought this would not be a problem, but apparently, it is. I'm getting the wrong positions. Remember when we added the '(white_pawn_at ?file ?rank - location)' predicate? this works great, but since I can't declare that some pawn has been removed since I don't know where that last pawn's location will be, I came up with a different approach where I don't say that a pawn has been removed but how many pawns are present on the board. I tried to do this with the function '(amount_of_pawns)', and then I decreased the amount every time a piece which is a pawn has been captured (in the: effect part of the action). However, the planner is outputting: b'Undeclared predicate: decrease\n' even though I added the ':action costs tag to the requirements (I also tried ':fluents' without success). I couldn't fix it on my own, so I contacted Augusto.|
|08.04|Writing|Today I started writing the first part of my thesis. I'm not sure whether or not I should continue coding while waiting for Augustos' response because the last few times I did that, it was hard to locate the problem because I worked on some things simultaneously.|
|09.04|tough schedule|Today I got a mail from Augusto that he's worried about our schedule, which in other words, means I'm too slow. I'm kind of panicking as I'm writing this. I implemented pinned pieces. It's not tested yet, tough since some unit tests fail, so I need to fix them before I change more.|
|10.04|en-passant, testing&fixing| I implemented en-passant but did not test it yet. I fixed various problems with checks that occurred. One of them took me half of the day to find, and it turned out to be in a spot I would have never looked for. I only found it because I tried to optimize something small out of frustration. I also almost finished the pawn promotion, but there is a small detail I don't have an idea how to fix right now.|
|11.04|testing & fixing|I already found so many mistakes, but more and more mistakes have come to the surface. The python code is pretty much done, but there are problems in my almost 1k lines PDDL domain file in certain special cases.|
|12.04|Meeting & pawn promotion|I thought pawn promotion would be easy to implement, but it took longer than I expected. I needed to rewrite some PDDL populating functions to handle more pieces than are present on the board and correctly show them, which means I also had to consider the goal_FEN, which triggered a cascade of changes. Also, the PDDL files needed additional pieces, so I added a function that adds those to promote.|
|12.04|fixing|A lot of fixing has been done today. This PDDL part seems to have no end in sight.|
|13.04|populating|Today I made significant steps forward. The PDDL file is now entirely populated by the logic of the given FEN code. The only missing thing is a few extra pieces for pawn promotions. I'm not sure if this affects performance, and since I still need to test some things, I'll create a different function to define how many extra pieces I want present. Also, I found the mistake plaguing me for weeks now. As soon as the king was current, there was a massive surge in time consumption for a task, and it took forever, so I never really was able to test my implementation except in subcases where I commented out parts of the code. However, if all the code was uncommented, it took forever, and I just assumed that the complexity was just much higher. But after going through all 1300 lines of the domain.pddl file and triple checking the logic, I found a simple negation that made some cases unsolvable, which made the planner run for very long. Those same cases now run within minutes.|
|14.04|Testing|Today was testing day. I discovered some minor issues like pawns that we're able to move to the last rank, which is not a valid move, and the validator still tells me it's an invalid move now even though it promotes to a queen, but I'm gonna leave it at that since the plan is correct in that case. All unit tests that run within a reasonable amount of time give me a correct plan which is validatable with the validate.py class, and I do this in one batch. I also tested the unit tests, which run for a long time, by uncommenting some parts of the PDDL code. Also, since I enlarge the board by adding white space to it so the validator can take my board as an input (it's currently 5x5), there are problems with that since, on a 5x5 board, a pawn may still double move, but on an 8x8 board that pawn cannot since it's in the middle of the board. The planner then correctly tells me it's an invalid move, although, in the original 5x5 board, it would be a valid move. I will not address this issue.|
|15.04|Bitmaps|Today I started the second part of my thesis, which is the implementation of a chess search algorithm in java. For now, I transcribed the FEN decoder from my python file to the java file. I then realized that translating the Fen code to a 2d array makes no sense because I read [this](https://core.ac.uk/download/pdf/33500946.pdf) thesis about how the chessboard can be represented as 12 bitboards. I then started to re-implement the FEN decoder in java to directly translate the FEN-code into a 1d array of length 12 containing strings consisting of 1's and 0's with length 64. 1's represent where the piece is currently at. It then gets translated into a long (64bit) with `Long.parseLong`, which gives me an array of 12 numbers which are my bitboards.|
|16.04|Bitmaps|More reading on bitmaps has been done today. There are some fantastic resources, and I'm in love with the idea of bitboards because it is like programming in PDDL but with more control and error feedback. Lots of ideas can be taken over. I created lots of useful methods which let me structure my code correctly, and I took care that I could instantiate everything at the beginning only once and not every time over, which is ultimately the idea of bitboards; otherwise, they are just like arrays. I also started creating methods which generate a bitboard which marks the files and ranks, but there are some problems with the conversions of some of the bit strings to the 64 long bit.|
|17.04|Bitmaps|I solved the problem with the conversion from bit string to bit long. The problem was that I used `parseLong()`, which is signed instead of `parseUnsignedLong()`. I've gotten used to the bitmaps way more now and was able to create bitboards for white pieces, black pieces, bitboards that mark the queenside and kingside and empty squares. Empty squares are straightforward since I can do a barcode addition with `EMPTY=~(BLACKPIECES+WHITEPIECES)`, which is fantastic and shows the power and speed bitmaps.|
|18.04|Moves (pawns & knights & kings)|Today, I added possible pawn & knight moves (black and white) functions which give me a bitmap representing the squares that can be targeted. This is really fast.|
|19.04|Meeting|Today was another meeting. Augusto decided to look at the PDDL files himself and look at the internals of the fast downward planner to find out where precisely the planner gets stuck and if we can do something about it or if it is just a hard problem for the planner. We also considered using a cloud computer, but since we don't know yet if it would be worth it, he'll first have a look at the files. I also started creating a method that gives me the sliding piece's rows and rank mask. It's harder than I thought because of all the conversions I need to keep in my head while debugging, but I think I'm almost there. I have some mirroring problems in the lower parts of the matrix, and I'm unable to find the problem. I also implemented a matrix that I can manipulate and insert pieces into to be faster when I want to test positions instead of using FEN codes only. I can just comment out one line to make the FEN code translator work again.|
|20.04|sliding piece mask|I finished the vertikal&horizontal mask for a sliding piece. The mistake was the mix up of row and rank at one spot. I don't know why I didn't find this earlier. I also implemented the diagonal mask for sliding pieces like the bishop (&queen). This was a bit more complicated and took me quite some time to get right. I'm a bit worried that if I continue at this tempo, I won't be finished by the end of my contract. I also started encoding the consideration of pieces which block the way since pieces can capture opposite pieces but not pieces of the same colour. I want to implement this as an optimization of the existing code by checking if the current piece is a piece of the opposite colour and if so|
|21.04|diagonal and horizontal premature abortion|Today I started writing down some of the logic I've been implementing over the past few days. I made notes in the code, so I can copy them for later use in the thesis document. The logic is about finding the spots a sliding figure can go to. I've been extending it by a piece which aborts the movements prematurely if we find that the square is occupied by either our own or the opposite coloured piece. This speeds up the algorithm a bit, but the central part is that it allows me to not double compute those spots, but I can simply do it in one step. The logic is crazy, but I tested it thoroughly, and it worked in all cases tested. I read about magic bitboards and their formulas for sliding pieces, and I finally understood it. There was a moment today where I thought about abandoning my approach and continuing with the one that is accepted by most top tier chess engines, but I luckily didn't because my solution is working now.|
|22.04|Fixing|Today I had the idea that I can also fit pins and checks into my function, which marks the way of sliding pieces. This worked great with one exception: the pieces on the border were not added for some reason. It took me all day to find out what exactly the problem was. I finally found it: I checked if the previous figure was capturable in the early stopping part. When I reached the last square, the for loop stopped, so there was no square to check the previous one at the board_ize+1'th court because it stops at board_size. This resulted in some significant changes because the whole logic changed as well. As a side effect, the code got much cleaner and is much easier to understand now. I also noticed that it is a few milliseconds faster now on average.|
|23.04|Red Zone| The red zone to which the king cannot move is implemented. I also now know how many pieces are attacking the king and where precisely those pieces are without generating significant extra calculations since most of it is done only when a king is in check and while we are always in that spot (sliding pieces) this should be efficient. I can now also differentiate between attacking and moving pawns since moving pawns can't check the king or capture a piece. This is all needed because [(here is a concise explanation)](https://peterellisjones.com/posts/generating-legal-chess-moves-efficiently/) when there is more than one piece attacking the king, the only legal move is moving the king while when there is only one piece attacking the king, the attacker piece can also be captured to put the king out of check OR move a piece between the king and the attacker piece to block the check. Furthermore, I cleaned the code, making it more compact. Today I am halfway through my thesis (45 more days to go).|
|24.04|check avoiding|I now added the valid piece movements, which can capture the piece checking the king iff there is only one piece attacking the king (not possible if multiple pieces are attacking the king). I also added blocked locations to which the opposite piece can move to avoid a check (only possible if there is only one attacker).|
|25.04|differentiating between different figures|Today I realized that my approach doesn't quite work the way I have it right now. To solve the problem of knowing which movement belongs to which figure, I had to create new movement maps for every single figure. Movement maps of figures of the same type are stored in an array of that type. There are still some bugs that came with the migration to this new mapping, but I'm confident that this is a good solution because it only generates very minimal amounts of overhead: the non-sliding piece movements need to be calculated one by one to differentiate between the pieces instead of all together. This also solves my complication of the situation with pins: so far, I could only restrict the movements of all pieces of the pinned type because I wasn't able to assign the movements to a singular piece. Now, this is no more a problem.|
|26.04|Meeting & Fixing|Today was another meeting with Augusto, where we had a look at the PDDL files and some concerns he had. The concerns turned out to be misunderstandings, fortunately, which made me more confident in the validity of my PDDL encoding. I also found lots of bugs in my Bitboard generator. Some of them I already fixed, but others need more time.|
|27.04|restructuring|I ran into some performance issues when returning the full list of possible moves. This is not yet implemented correctly, but the issue was lying elsewhere, namely, in the way, I saved the bitmap movements. I united all of them into a single list and operated from there, making it difficult to access the individual moves. The issue is a similar one as I had with the individual maps for the pieces themselves. I now created another 2d array which contains different subarrays of different sizes. Those arrays represent the movements possible by each piece. These arrays were saved in an individual list before, but I united them into one. This change resulted in some big restructuring of the code and enabled me to simplify my code substantially. The issue with the performance is one I don't quite understand why it was happening: The computation time jumped from around 1ms for the same position to 5ms, which is bad. Now it's back down again to around 1ms. I also tested the python-chess module: it apparently needs around 250µs to compute the same valid moves as my move generator. Thus, I can say my engine is around 4 times slower. This is bad, but I'm not sure if I have the time to implement the changes ("Using SIMD instructions to do bit-wise operations on multiple bit-boards at the same time. Use Kogge-Stone Generators when calculating slider moves for multiple pieces simultaneously (e.g. calculating king danger squares or pin rays). Using the o^(o-2r) trick when calculating moves for individual sliding pieces, using the intel PSHUFB instruction to do byte-swaps on 128-bit registers to calculate diagonal attacks." - [source](https://peterellisjones.com/posts/generating-legal-chess-moves-efficiently/)). However, if I add the movement outputs as strings, the computation time jumps to around 15ms. Upon seeing this, I rethought the problem and decided to return the bitmaps instead of converting them to a string representation and dealing with that. In the end, I will convert the path selected by the search algorithm and convert the selected steps to the corresponding string movements. I implemented the generation of all possible bitmaps now, and the runtime is down from 15ms to 1.5 ms (for the same position), which is acceptable now. I will come back to this if it turns out to be a bottleneck.|
|28.04|testing & fixing|I'm now testing my code with various starting positions. I'm finding more and more bugs. So far, I only coded the vertical upwards movement to avoid making changes to multiple spots at once and ending up with mistakes. I now copied and adjusted that upwards move to all 8 locations (4 directions for diagonal and hor-vertical-movements. This was way more work than I anticipated because the changes were subtle and had to be precise. I tested it, but I'm sure there will be more mistakes. It now gives me precisely 20 moves in the starting position (which is correct), and my next task is to check subsequent positions with different depths and check if the amount of moves aligns with the number of possible moves. I need to first implement that functionality of generating the successors up to a certain depth to do this. Also: generating the output bitboards generates an overhead of around 12ms bringing the total to about 13ms. If I have to develop the first depth levels of the move tree (400 nodes), this will take me 400*13ms=5200ms, which is 5.2 seconds. This is way too long! Not sure what to do at this point.|
|29.04|Speed|I now can generate the first 2 iterations (move the tree to depth 2). The weird thing is that it only takes around 50ms instead of the expected 5.2 seconds. I don't exactly understand why that is (maybe some parallelism optimization that java is doing?). Depth 2 generates 424 wrong nodes. The problem seems not to be in the movement generation but in how I generate all possible output bitmaps from the movement maps. What's even more curious is that if I change the structure so that it first gathers all bitmaps and appends them to a single stack, then the runtime goes down to even 6-10ms to reach 424 nodes. Today, I started implementing a recursive algorithm that returns the number of states at each level. I want to use this to verify my implementation. However, I could not finish it due to various problems that arose that needed to be addressed first.|
|30.04|search|I started to go another route today since I got nowhere with the recursive algorithm yesterday. I now do it by hand and select the node I want to expand explicitly. This is a good idea since I can see the algorithm react with itself for the first time. I realize that some variables need to be reset (it took me a painful while to find this out). I'm now able to generate the successors reliably. BUT: In doing so, I found some problems with my implementation: for example, pawns are all disappearing if one is captured. This is now fixed. Also, if one pawn is pinned, all pawns are pinned. I think there are a lot of these problems that I need to address over the next couple of days. I hope I can finish in time. This is quite the time-consuming bachelor's thesis compared to the one my friends are doing...|
|01.05|bugs|Today I made progress, but it feels like I'm getting nowhere. There are still scenarios in which weird behaviour is happening. For example, my bishop captured a rook by going out of the board and coming in on the other side. It cannot move there tough, but it can capture a piece positioned there. This is why I didn't find the mistake so far.|
|02.05|testing & fixing|I fixed the problem with the over the board captures and checks. It needed more if statement to catch this. I also did a test run just now where I let the algorithm run 1'000'000 times in a for loop where it expands the children given to it and sets the 0'th of those children as the parent for the next iteration. The code generates anywhere between 2-40 million nodes per second from the tests I have done. The speeds are very different, but I think that is because there are no more nodes and or empty boards generated at a certain point. I tested this by creating the fools mate scenario and then expanding on it, which produces an array out of bounds which means I can quickly check for mates if the length of the generated children list is =0. Today I will first tackle the pawn promotion problem, and then I will create the en-passant movement logic for which I need the history of the previous move. Both have been implemented as writing this, and it is late evening. I'm now trying to finish casting, so I have that implemented for the meeting with Augusto tomorrow.|
|03.05|Meeting|Today was another meeting with Augusto, I showed him my progress, and we discussed the further steps. I also finished castling and pawn promotions and tested them. It should be working nicely. I also wrote an isGoal() function, which returns true if the given state is equal to the goal state defined at the beginning. This checking is speedy and only takes 1-2µs for the positions I tested it with. Some restructuring was also needed, and some auxiliary functions were written.|
|04.05|Writing|Today I had my wisdom teeth removed, so I did not feel like programming. Instead, I continued writing on the thesis and reading up on the reading material. I finished the introduction, expanded on some parts in the background chapter and started to write the PDDL chapter. I've written a PDDL domain and problem file pair, which solves Guarini's problem, so I have a running example throughout my thesis and don't have to introduce multiple examples. I made quite some progress today.|
|05.05|Writing|Today I read some notes I made from chapters 3,7,10, and 11, which Augusto recommended me to read. For the state-space search algorithm, mainly chapter 3 is important, and most of the work to implement the algorithm has already been done since it's only the search part that's missing (I think). Also, I wanted to finish the first part of the thesis before I continue implementing the search algorithm, so my head gets cleared, and I can focus on the search algorithm, which is a new part. I now have the first 8 pages of my thesis, and the background for at least the PDDL part is done.|
|06.05|Writing|More writing today. I had a big struggle getting the formatting of the PDDL code right, so it looks nice, but I found a way that the pseudocode seems the same: I extended the PDDL.tex package with more formatting rules and added some code which ignores specific keywords if non PDDL code is used. I have my first 10 pages finished, I think. I also started writing on the background of the second part of my thesis (own algorithm).|
|07.05|Writing|Today I almost finished the Background for the second part of my thesis. I think I have more than enough time to finalize everything as most of the code has comments that can be copy-pasted into my thesis as a text since I prepared it that way. I'm not sure how I will describe my code since it's a few thousand lines of code. I'll ask Augusto about it at our next meeting.|
|08.05|Breadth-First Search|Today I started to prepare my code o that I can implement the BFSearch. I needed to make some adjustments and introduce some new classes such as Problem, Node and State. I made sure that the Pseudocode from the book can be used 1:1 so that I don't have to explain it again in the thesis after I already explained it in the Background chapter. This will save me a few pages I hope. I'm not sure If i can put it all in 20-30 pages yet since I already have almost 14 pages for just the background part and I think it will be at 15 pages once finalized. This leaves me with 15 pages to explain everything I implemented which is a lot.|
|09.05|Breadth-First Search|BFS works now. Although I encountered some strange behaviour where it keeps ongoing. For example, if the position given can't be reached. I need to implement some things to avoid this. I got some ideas about what the reasons could be and what I can do, but I'm not sure what way to go, and I'm not sure if I can finish it in time for my meeting with Augusto tomorrow.|
|10.05|Meeting|Today was a meeting with Augusto, we discussed heuristics and what makes sense. We also got into details of how to implement Greedy-best-first search. He also gave me feedback on the Background part of my thesis I sent him. After the meeting I implemented GBFS and ran into some problems where my GBFS implementation expanded way more nodes than my BFS implementation. I suspected that the heuristic was the problem or the queue was ordered the wrong way round but both turned out to be correct as far as I could tell. I wrote Augusto a mail about it.|
|11.05|Error fixing|I discovered some errors when pieces were captured. The bitboard is correct, but the translation to its move is wrong. I extended the actions to show the piece that is moving and whether or not it is capturing another piece "x". It also shows castling if one has been made "O-O" & "O-O-O". Augusto wrote me an answer, but it was not what I hoped for since he wrote me a checklist on how he would go about debugging this problem by checking if the heuristics were correctly implemented. I have some doubts now about whether or not the heuristic implementation is correct, but I'll go through his list and try it anyway to be sure. As of writing this, I've gone through the list and checked all, seems to be correct. I'm not sure where the problem is.|
|12.05|A* & weighted A*|I implemented A* (user can also specify a weight). The algorithm seems to run fine when I use A*, and it does not get stuck on the problems where GBFS appears to get stuck. It's early morning, and today I will focus on writing the thesis until the next meeting with Augusto next Tuesday.|
|13.05|Writing| Today, I made some progress on the writing front.|
|14.05|Grammar & Readability|I focused heavily on grammar and readability Today, which took longer than expected. The next few days will be purely writing focused.b|**
|15.05|Writing|I finished chapter 3, but a few things are still missing.|
|16.05|Writing| I Started with chapter 4, there are many things still missing, but I don't know what I should mention and what not. I have a structure of chapter 4, and I have written quite a lot of text already.|
|17.05|Meeting & Writing|In the meeting with Augusto, we discussed the thesis text so far, and I got a lot of constructive feedback. I plan to finish putting that feedback into effect by the end of this day and finish chapter 4 by tomorrow so I can send it to Augusto and he has enough time to read through it.|
|18.05|PDDL & writing|Today I tried to fix the pins and blocking movements in pddl. I found some mistakes which I fixed and I set up the algorithm to precompute some derived predicates so I can turn them into static predicates. I've also finished chapter 3 of the thesis. There are some minor things that are missing but all in all I'm satisfied.|
|19.05|Writing|Today I almost finished chapter 4. There are a lot of things that are not mentioned because I'm not sure if I should mention them (after all the code is 2500 lines long and the lines are not at all trivial). I also sent augusto a copy so he can send me feedback on the thesis.|
|20.05|PDDL|Today I uncovered and fixed a lot of ploblems in the PDDL file. I also found a way to encode pins and blockings (checks). What I don't have yet is a way to reach a mating position because the current implementation does not accept a mate position as a goal state|
|21.05|Writing|Today I mainly continued writing my thesis. I made some things more precise, and I also started to re-read the entire dissertation and correct all mistakes and unclarities which I saw. I also used Grammarly to help me with the correct spelling and punctuation.|
|22.05|PDDL|I switched some derived predicates to be static predicates by precomputing them. There are no more derived predicates left which can be precomputed. I definetly saw an improvement in speed. I tried to find a solution to a fully initialized 5x5 starting position where one move is made and it isable to reach a solution in 13 seconds which is an extreme time improvement. BUT: there were no kings present on the board. As soon as kings are present on the board there is no solution which is found. I don't know why at this point.|
|23.05|PDDL|Fixing of PDDL & optimizing by changing all precomputable predicates to static predicates.|
|24.05|Meeting|Today was another productive meeting with Augusto. I implemented a lot of the feedback Augusto gave me in the thesis text and made it quite a bit shorter. I also worked on finding the errors in the PDDL file because the optimizations also broke some things. Augusto told me this was dangerous to do this so short before the deadline but i have a feeling that it could be worth it.|
|25.05|PDDL fixing|I tried to fixx the precomputed predicates and some negations which I turned into positive statements but wasn't able to find all bugs so I reverted these changes|
|26.05|PDDL Experiments|I conducted some experiments in PDDL and wrote them down in my thesis. Also Found some new bugs and fixed them.|
|27.05|domain speciffic Experiments & fixing|I tried to run the same tests in the domain speciffic implementation as i did in the PDDL experiments but I stumbled upon some errors which I am trying to fix at the moment.|
|28.05|Finished Experiments|I finished the Experiments and wrote a conclusion. i also had some fixing to do on the domain speciffic solver because I discovered an issue.|
|29.05-2.06|Writing|During the last few days I forgot to write my journal entries. I mostly worked on writing, restructuring, clarifying and shortening the thesis but I also redid some experiments because I found a bug in the PDDL part.|
|3.06|Meeting|Today was my last meeting with Augusto.|
|4.06|Writing|Today I mainly tried to shorten the thesis to get the page count down. I also did some reformatting to make it look more appealing|
|5.06|Finished|Today I finished everything and made the repository public. I sent the thesis to Augusto and Prof. Malte Helmert.|