Day #3 Next I completed the move generator for all other pieces. Nb8a6 would be “0217” – a move from square 2 to square 17 on the board. A move was represented by a 4-digit number, referring to the source and target squares. Those moves were then applied one-by-one, MiniMax was invoked again for the next depth, and after returning the move was reverted to bring the board back to its original state. The move generator filled a move list for every search depth level with all possible moves at that point. I also implemented a move generator, initially for pawns and knights, and had the engine make its first moves. Some other Scratch chess engines have a dedicated custom block for each Ply, but I didn’t want to introduce duplicate code (by now we are at a move depth of 25 including Quiescence). So, I applied lists for emulating a call stack. Luckily recursions are possible in Scratch via Custom Blocks, but local state cannot be kept, as local variables don’t exist, and block parameter values cannot be changed. I guessed the program could look ahead three moves (“ Ply 3”) and put a hardcoded limit there. On each tree leaf, that is after the final move, the resulting board would be evaluated. I was aware that this would require a Move Generator and a Board Evaluation Function, combined with a MiniMax algorithm - a recursive approach, with one recursion for each subsequent move, spanning up a tree of moves. Day #2 Day #2 was dedicated to ramping up a chess engine prototype. By adding up all the piece values on the board, one ends up with a material evaluation of the current board. the black queen’s value is “900”, rook is “500”, bishop “330”, knight “310”, pawn “100”, and finally a king is “20000” (capturing a king surpasses everything else combined). The list contains Centipawn values for each type of piece - negative ones for white, positive ones for black. When tinkering about how to represent board data in memory, I ended up with a Scratch List with 64 entries, one for each square. And user input should be intuitive and require just two clicks: first click the piece to move, then click the target square. I preferred a simplistic 2D bird’s eye view to complex 3D graphics or similar. Sprites were only used for animating piece-movement. I found some nice open-usage chess graphics, and drew the pieces via Scratch Pen functions, applying the Stamp operation. This is how that went: Day #1 At first I worked on the graphical user interface. It was Sunday evening, CoderDojo takes place Fridays, so I had four nights for coding and one for writing the tutorial. I had implemented some other Scratch games before, which were all accompanied by step-by-step tutorials for children to re-create the programs on their own. Kochy-Richter checkmate detected by GoK - click image to view video The First Week - CoderDojo Linz Chess The GoK project started as a tutorial for the CoderDojo Linz Kids Programming Club. Other things like alpha/beta-pruning or quiescence search I picked up from there directly. So I still knew MiniMax from University (it's the logical approach for board games), and came up with some kind of move ordering (based on iterative deepening), square piece tables, mobility evaluation and attack tables myself - I just fine-tuned the crude original implementations later, after reading on and other places. My approach was to try different ideas, and only when I was stuck, I investigated about underlying chess programming theory in certain areas. So perfect, it was just the challenge I was looking for. And for the chess engine case, that just meant it was bit more difficult, and that no implementation would ever reach the playing strength of chess games on other platforms (BTW, running GoK on other Scratch engines like TurboWarp shows the performance potential: ). But that hasn't stopped people from writing pen-based 3D games in Scratch. regarding structured programming, there are no bitwise operations (hence no bitboard data structure), it is very slow and even has some performance throttling built in (so that kids wouldn't have to worry about timing). The language's capabilities are limited, esp. It was designed for other purposes - for simple games and animations, programmed by kids. In general, Scratch is probably the least suited programming and runtime environment to implement a chess engine. But luckily, I got help from others, and found valuable online material too. I should mention that I am not a good chess player, know next to nothing about chess in theory, and had only a basic idea about chess programming when I started the project. So, I decided to provide a forum posting on that topic, which might also trigger further discussion. How Game of Kings is implemented Hello Chess Players and Programmers! Over the last couple of months, several Scratch users have asked for more detailed info on how Scratch Chess - Game of Kings works internally.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |