ChesSkelet /tseske'let/

The dissection

Chapter 1 - General program structure

I guess the first thing before digging into the code details is to explain why the program is built as it is. I need to say that it is the product of many iterations changes and rewriting.

Program structure: in the initial implementation there were many repeated sections and routines that were used several times, with slight differences for white (human) and black (computer) pieces. As I could optimize the structure, I came to the conclusion that none of the elements needed to be called more than once and I could reuse most of the code for both sides, except for the code generating the legal mode list, which is the most complex part and it’s used in several places (there will be a dedicated chapter on that one, called ‘genlis’).

This structure has helped me in making a very simple code, but as weŽll see it introduced some restrictions that are difficult to resolve without important changes.

Here is a simplified code flow:

Also, as part of the learning process, I took some technical decisions on how the code should be written:

 

Chapter 2: declarations and initial code

Let's look into the initial program code. IŽll break it in several sections.

First of all, all constants and variable declarations:

; debug mode: 0 = no, 1 = yes

                debmod            equ 0

; gramod: 0 = minimal interface, 1 = basic interface, 2 = full interface

                gramod            equ 0

; feamod: 0 = no features (if fails at legadd 'ret'), 1 = all features

                feamod            equ 0

; ROM memory addresses

                clescr            equ 3503

                laskey            equ 23560

; memory micro-pages (256B, typically H register) used for simple memory access

                auxsth            equ $7D

                piearh            equ $7E

                movlih            equ $7F

                boasth            equ $80

                boaath            equ $81

                boaoph            equ $82

                canlih            equ $83

 

1) debmod, gramod and feamod are not really parts of the program code. These three are used to include or exclude part of the code when compiling. This is for me the simplest way (not simple anyway) to keep all the versions (full features, full graphics, etc...) in a single code file. Also, debmod allows me to include extra code for debugging, mainly a test board where I can set whatever game position I like. WeŽll discuss the board soon.

2) I'm using two system addresses that I call clescr (clear screen ROM routine) and laskey (RAM position where last pressed key is saved).

3) auxsth...canlih are my different data "micropages" (256 bytes). This data arrangement allows me jumping from data block to data block with 1 byte instructions in most cases. Generally, memory addresses are pointed mainly with a register called HL (you can address 65536 addresses with it). Loading a memory address into this register to point a byte in RAM typically takes a 3-byte instruction. With this method, I place the different data used by the program at the beginning of each 256 byte block. Let me illustrate with an example:

The problem with this second approach is that you cannot use it for data blocks bigger than two bytes. Savings would be gone if you have increase HL one by one to reach a data 10 bytes away from the current HL address.

What did I do? I placed big data blocks in addresses where I can point them by moving the pointer 256B. These addresses are easily pointed by increasing/decreasing the highest byte of this famous HL pointer (INC H / DEC H). The best example in my program is that I keep the game board with all the pieces in 8000h-807Fh (H=80h) addresses and another board with the attacked status of squares in $8100h-817Fh (H=81h). If the code needs to analyze if it's worth capturing a piece, I can check the value of the target piece in the board where H=80h, and with a 1-byte operation (INC H, H=81h now) I can move to the other board and see if the square is being attacked.

; legal moves generation (3B) -----------------------------------------

befmov          call genlis                               ; candidate move list, used for both sides

; switch sides on every loop (6B+1B) ----------------------------------

whomov          ld l, h                                   ; (H)L: $7F7F = movlih + gamsta, ++

                ld a, (hl)                                ; load state

                xor h                                     ; (@johan_koelman) switch turn: bla=0, whi=1

                ld (hl), a                                ; save state back in memory

if feamod>0

                jp z, blamov

else

                jr z, blamov                              ; if 0, jump to black moves, jp maybe

endif

                ; clear screen (3B)

whimov          call clescr                               ; ROM routine set screen mode


Initial part of the code:

prosta   ld a, 2                    ; 2 = upper screen.

         call chaope                ; open channel

Next thing it to clear the screen once per white move. Why? This way I avoided having to call it several times. It's not worth updating the board after white's move since the black moves so fast that you never get to see the board with the black move only. In earlier versions I would have to initiate the screen before anything, but I noticed that the ROM routine clearing the screen does that for me.

Earlier, I would also include a routine creating the board with the initial pieces for me, but as the game is not replayable, the cheapest way to get the initial board in place is not programmatically. I leave the data in the right position for the board to be formed at compilation. So the initialization routine was removed.


Chapter 3: the board

This is a very interesting topic, for both programmers and chess aficionados. There are two parts to this: the design decisions and the implementation. For the first part, no programming skills are needed. The second part, how the board is displayed, may be a little boring to some.

Chess board representation in computer memory is a topic that has been discussed since the 70s in length. There are lots of information, but if you want to have an initial dive into the topic I would recommend this website https://www.chessprogramming.org/Board_Representation. It's a real pity I did not find this since the very beginning as I went through many of the potential issues before I found out that most of them had been sorted out by clever people before me.

There are many ways to represent a chess board in a computer memory, typically classified as:

You can mix all these methods depending on your priorities.

In my case I started experimenting several variants, all of them in the square-centric area since, after some consideration, they seemed less code consuming than piece-centric or bitboards:

My first obvious choice was an 8x8 (64-byte) board, with one byte to store the piece (and potentially other info). It is a good first approach but it is not optimal. First, translating the square coordinates to the byte is easy, but there are other structures with simpler translation.

And the most important: the Out Of Board detection issue (from now on OOB). When you write your code to validate pieces movement across the board, detecting when the piece falls out of the board is not obvious. If the piece moves beyond the board boundaries it may still fall within the board. Imagine a Rook moving from A1 to its left. Although it's illegal moving out of the board, if the board is represented by 64 contiguous bytes, it will fall inside the board. Detecting all these scenarios is not very simple unless you use a slightly different structure (see 12x10 and 16x10 below).

If we need to check what is in square "d6", "6" would be rank 5 (ranks go 0-7), "d" would be column 3 (columns go 0-7 too). We can put this in a byte with this format 0rrr0ccc (rrr=rank, ccc= column), and it will point at byte 53h within the board. With this approach, the translation from alphabetic coordinates is very simple, loops are simple too, and we are never writing on reading anything on the unused right half of the 16x8 board, so it all works super smoothly.

What am I storing in each byte (or square)? A square byte looks like this in bit format: 00cppppp. "c" is the piece color bit (0= black, 1= white) and "p" is the piece value. High bits could have been used for other information (square attacked status), but I found easier to store this extra information in other places.

On the piece values, classical values are similar to P=1, N=3, B=3.5, R=5, Q=8, K=infinite. I wanted to use the minimum amount of bits in this byte. I use this value for both piece valuation and also to find the right figure to be printed in each square when printing the board in the screen, picking the figure (a letter) from an array. The closer the piece values are, the smaller the array becomes.

Also, the classical valuation above is needed for situation where several pieces could be exchanged in subsequent moves. My evaluation (we'll discuss that later) only looks 1 move ahead, therefore these refined piece values do not give us any advantage. Therefore, I could to simplify the piece valuation without harm. My piece valuation is P=2, N=3, B=4, R=5, Q=7, K=22. WeŽll see why later.

Finally, I have another board storing which squares are attacked by the other side, so that the code can evaluate if it's worth capturing a piece in that square, knowing that it can be re-captured by the other side as well. So, finally, I guess my model would be a hybrid square-centric/bitboard one, since I use more than a board to store the game info.


Chapter 4: Data and variables

Before I go on with more code, let's have a look at the different data structures and variables used by the program. We have several types of data: we have read-only data (i.e. vectors used to generate legal moves) which do not vary through the game, and variable data. Among the later, we have predefined data (i.e. initial board) and data which is generated only during the game execution (i.e. legal move list for the current board position).

As I already explained in previous chapters, data is organized very carefully trying to simplify addressing as much as possible:

One addressing example:

; mark attacked ### str. pawn marked attacked

inc h                    ; H(L)= $81 = boaath ++

ld (hl), h               ; mark attacked ($81)

dec h                    ; H(L)= $80 = boasth ++

dec h                    ; H(L)= $79= movlih ++

Before this code, page 80h (game board) is being pointed. After identifying the target square for a potential move, I need to mark the square as attacked by the moving piece. This "attack" board is in page 81h. As the board structure is the same in both pages, just by changing from page 80h to page 81h I will point at the right place in the attack board (INC H, first code line). After marking the square as attacked (LD (HL), H), I go back to the game board (DEC H). But now, my next action does not use the board but other info in page 79h, therefore I modify the page pointer again (DEC H). This addressing, using a regular approach would need 9 bytes. Here we do it with 3 bytes.

Let's look at the data now, page by page:

; Memory page: 7700h ----------------------------------------------------------

org $7700

auxstr                                                  ; input string stored here

 

The only information stored in this page is the input string typed by the human player. It takes 4 bytes and it's converted into a 1..64 value to pint at the right board square.

; Memory page: 7E00h ----------------------------------------------------------

; used to convert values to pieces

org $7E00

if gramod=0                                     ; opt: space or dot depending on the size

piearr    defb '.'                              ; $2B

else

piearr    defb ' '

endif

          defm "pnbrq"                          ; change this array to any language

org $7E08

          defb 'k'


In this page, an array with the letter representing the pieces is stored. As the piece value goes from 1 to 8, it's very simple to point at this array to pick the letter. In the program, there is additional code to capitalize white pieces if that's the case.

; Memory page: 7F00h ----------------------------------------------------------

; sub-moves and vectors

org $7F00

; leave empty $00-$04-...-$24 for black pieces/empty square pointers

org $7F44                                           ; pawn: 17x4= 68B displacement

; piece, move type, vector list delta address (18B)

; move type / 0 / 0 / pawn straight / pawn diagonal / DDDD (real radius + 7)

movlis

pawgen          defb      $28, 103               ; pawn straight

                defb      $18, 107               ; pawn capture

knigen          defb      $08, 110               ;

org $7F4C

bisgen          defb      $0E, 105               ;

org $7F50

roogen          defb      $0E, 100               ;

org $7F54

quegen          defb      $0E, 100               ;

                defb      $0E, 105               ;

org $7F60                                        ; $18(king)x4=$60

kingen          defb      $08, 100               ;

                defb      $08, 105               ;

 

org $7F64                                        ; vectors: $7F + 100 (arbitrary)

; (y, x) move delta pairs (16B)

veclis

strvec          defb      $FF, $01               ; +0, straight vectors

                defb      $10, $F0               ; +3, straight pawn, last half line

org $7F69

diavec          defb      $0F, $11               ; +5, diagonal vectors

                defb      $EF, $F1               ; +7, diagonal pawn

org $7F6E

knivec          defb      $E1, $F2               ; +10, knight vectors

                defb      $12, $21               ; knight moves listed clockwise

                defb      $1F, $0E               ;

                defb      $EE, $DF               ;

; board status: 0000000 / turn (B=0, W=1)

org $7F7F

gamsta

 

Core data to the program implementation. This page contains the info for the code to generate a list with the valid moves for a piece in the board. WeŽll come to that when we get to the famous "genlis" code.

; Memory page: 8000h ----------------------------------------------------------

                ; board squares format: 00cppppp

                ; pppp (value) : pawn=2, knight=3, bishop=4, rook=5, queen=7, king=22

                ; c (color): white=1, black=0

                ; initial board setup

if debmod=1                                     ;opt: fill board for debugging

                org $8000

                boasta         defb $00, $00, $00, $00, $00, $00, $00, $00           ; <--8

                               defb $00, $00, $00, $00, $00, $00, $00, $00

                               defb $01, $01, $01, $01, $01, $01, $01, $01           ; <--7

                               defb $00, $00, $00, $00, $00, $00, $00, $00

                               defb $00, $00, $00, $00, $00, $00, $00, $00           ; <--6

                               defb $00, $00, $00, $00, $00, $00, $00, $00

                               defb $00, $00, $00, $00, $00, $00, $00, $00           ; <--5

                               defb $00, $00, $00, $00, $00, $00, $00, $00

                               defb $00, $00, $00, $00, $00, $00, $00, $00           ; <--4

                               defb $00, $00, $00, $00, $00, $00, $00, $00

                               defb $00, $00, $00, $00, $00, $00, $00, $00           ; <--3

                               defb $00, $00, $00, $00, $00, $00, $00, $00

                               defb $11, $11, $11, $11, $11, $11, $11, $11           ; <--2

                               defb $00, $00, $00, $00, $00, $00, $00, $00          

                               defb $14, $12, $13, $15, $18, $13, $12, $14           ; <--1

else                                                      ; opt: reduces board size for gameplay

                org $8000

                boasta         defb $04, $02, $03, $05, $08, $03, $02, $04

                org $8010

                               defb $01, $01, $01, $01, $01, $01, $01, $01

                org $8060                                          

                               defb $11, $11, $11, $11, $11, $11, $11, $11

                org $8070

                               defb $14, $12, $13, $15, $18, $13, $12, $14

endif


Game board: you can see two variants, a 32 byte one which is used by the regular versions of the game. First there is a full board used for debug purposes only, and not included in the compilation normally. Last, there is the regular initial board. You can see that IŽm setting only 32 bytes, as the empty squares are 0 after a reset, so no need to set them.


; Memory page: 8100h ----------------------------------------------------------

org $8100

boaata                                                 ; attacked squares board

Here comes the attacked squares board. I keep this information in a different board from the game board, as it's easier to handle pieces and attack info separately. It mirrors the game board, but in a different page.


; Memory page: 8200h ----------------------------------------------------------

org $8200

boaopo                                                 ; reversed attacked squares board

This page is a little trickier. The game board above (page 80h) is reversed at every move, so that the legal move list is generated for white pieces every time. Therefore the attack board needs to be reversed too. I found that the cheapest way to do that was copying it to another board. This is that board, and it's the one the code reads when trying to find out if a square is under attack or not.

As you can see, all three boards are used together, so that changing page to read them can be done at low cost, as explained above.


; Memory page: 8300h ----------------------------------------------------------

; candidate move list at the very end of the program

org $8300

canlis     equ $

Last, but not least, the list of candidate moves:


Chapter 5: Printing the board

Once we know all the data used, it will be easier to explain how the board is printed. We have several sections, some mandatory and some optional, used in the full graphical version only. I tried other approaches to the problem, but this seemed to be the one taking less code.

1- Initialization: I need to pointers to memory to convert piece values to pieces (letters with proper capitalization). When reaching this part of the code A, B and L are always 0. L is particularly good, as I do not need to set it (LD H, N, instead of LD HL, NN).

priboa                                            ; A, B = 0 at this point

                ; initialization (4B)

                ld h, boasth                      ; H(L)= $80, L always 0, load board ++

                ld d, piearh                      ; D(E): piece array pointer, E o/w later

 

2- Squares and pieces: from here on we have a loop that runs through the whole board, including the unused half of the board, which is interlaced with the used one.

2.1 - Print colored squares: This part is optional. Little trick here: Instead of messing with the colors or the reverse, what I do is changing the bright of the character position for each piece being printed. The result is nicer and simpler. The only code optimization here is that I use C register to generate the "oscillation" and the AND 1 decides if the bright of the square will be 1 or 0. Then we "print" that bright.

priloo    ; print colored squares (8B)

if gramod>0                                      ; opt: print colored squares

                ld a, 19                         ; set paper ASCII code

                rst 16                           ; print value

                ld a, c                          ; (@MstrBlinky) C is always $21

                inc c                            ; change C parity

                and %00000001                    ; keep Ab0, alternatively 0/1

                rst 16                           ; print value

endif

2.2 - Printing the piece itself: the square contains both the piece value and the color (00cppppp, C= color, P= piece). The thing is to collect the color only with the first three lines (color stored in B), and the collect the piece (LD E, (HL)), removing its color. I would like to do it all together, but I need A for the operations so I can't do both together. D is pointing at the base of the piece figures (characters) array, so when I set E with the uncolored square value it pointing at the "small" figure directly. Piece is collected (LD A, (DE)). Now, the piece needs to be color set, and that is done directly by subtracting 32 to capitalize them. I don't know if is intended, but the distance between capital and small letters in the ZX character set (therefore ASCII as well) is 32. It is not a random choice (https://en.wikipedia.org/wiki/ASCII#Internal_organization), so I take that bit5 to decide the size. I used to have bit 4 for the color, with this change I'm saving a byte in this routine.

The ZX Spectrum character set looks a lot like the ASCII

https://en.wikipedia.org/wiki/ZX_Spectrum_character_set#Character_set

                ; print piece (10B)

                ld a, (hl)                    ; load piece

                and %00100000                 ; keep color, pih

                ld b, a                       ; Bb5: isolate piece color

                ld e, (hl)                    ; load piece

                res 5, e                      ; uncolor, pih

                ld a, (de)                    ; load piece character

                sub b                         ; capitalize (-32) only for white pieces

                rst 16                        ; print piece

Now it's time to detect when the end of line or board comes, using the board pointer (L) to control the loop. For the end of board the first two lines do the job, since the board is finished at 128, not at 64 (remember the two boards together).

For the end of the rank, I got this trick from Mr. Blinky: we AND the current square with $08. If it's not the end of the line (L=8) it jumps and skips the rest of the operation. If it is the end of the line, 8 bytes need to be skipped to avoid printing stuff from the empty board to the screen. What we do it to add the result of the AND operation which is 8 whenever it's not jumping. The idea is not to add 8, but a registry content which is always 8 at this point. It's a little mess, I know, but it has to do with the two boards’ thing.

Finally, the result is returned to L so that it can continue looping through the board.

                ; next square, end of rank/board detection (15B+1B)

                inc l                            ; next square

                jp m, pricoo                     ; (@johan_koelman) end of 16x8 board, A=128?

                ld a, l                          ; (@MstrBlinky)

                and $08                          ; 8 if end of rank, 0 other cases

                jr z, priski                     ; skip if not end of the rank                       

                add a, l                         ;

                ld l, a                          ; return result to L

                ld a, 13                         ; A= <CR>

                rst 16                           ; print char

 

This little snippet allows me to change the bright step at the end of each rank. Without this, square colors would be vertically aligned, not checkered.

if gramod>0                                      ; opt: print colored squares, end of the rank

                inc c                            ; change C parity

endif

 

3- Coordinates

Initially, I tried to mix this with the squares and print the rank number at the end of each line, and later the column letters after the loop, but this required extra registers and it was not optimal. I also tested printing a string of control characters and characters instead of doing it one by one, but again too complex.

So, how it works? B is the loop counter, and C is a fixed value that will be used twice, (fixed column for rank values, fixed rank for column values). The first half prints the rank values and the second half prints the column values. Small details: Rank is decreasing as the rank grows (LD A, '8'; SUB B) whereas column increases (LD a, 'a'; ADD A, B).

The process is simple: print "PRINT AT" control character, set rank, set column and print the value.

It all end with checking B. Note that DJNZ cannot be used since I need the B=0 iteration to occur.

; print coords (28B+6B)--------------------------------------------------------

pricoo                                                    ; (@MstrBlinky simplified it)

                ld bc, $0709                              ; B: loop count, C: fixed rank/col

nextce          ld a, $16                                 ; ASCII control code for AT         

                rst 16                                    ; print it

                ld a, b                                   ; set rank

                rst 16                                    ; print it

                ld a, c                                   ; set column

                rst 16                                    ; print it

                ld a, '8'                                 ; base rank

                sub b                                     ; decrease rank character (8..1)

                rst 16                                    ; print rank value

                ld a, $16                                 ; ASCII control code for AT

                rst 16                                    ; print it

                ld a, c                                   ; set rank

                rst 16                                    ; print it

                ld a, b                                   ; set column

                rst 16                                    ; print it

                ld a, 'a'                                 ; base column character

                add a, b                                  ; increase rank character (a..h)

                rst 16                                    ; print rank value

 

                dec b                                      ; loop 8 times

                jp p, nextce                               ;

endif

Finally, a <CR> is added so that the input is typed under the rank letters.

                ld a, 13                                  ; A: set <CR> ASCII code

                rst 16                                    ; prints it to go to the next line for input

                ld a, '?'                                 ; set "?" ASCII code

                rst 16                                    ; print it

 

Chapter 6: White moves

White and black moves’ implementation are quite different since the white move comes from the human input and does not use any AI, whereas the black pieces do.

The process for white side has three blocks: input from keyboard, translation to coordinates and optionally check if the move is the legal move list. In general, there's no big mystery in these routines, except maybe for the fact that they are quite miniaturized.

1 - Reading the move

The routine will loop 4 times, one per typed character (register B). DE will point at the memory area where the string will be stored. HL points at a memory address where the ZX leaves the last key pressed.

Secondly, we have this small inner loop that is exited only when a key is pressed. Also, optionally there are two lines of code allowing to skip this move (CP 'S'; JP Z, AFTMOV).

Last thing needed is to store the key pressed, including moving to the next byte (INC DE), store the byte (LD DE, (A)).

                ; 4 times loop for coord input (3B)

                ld b, 4                                  ; loop count

                dec d                                    ; D(E)= $7D =auxsth, E always 0 ++

                ; read key from keyboard loop (8B)

realoo   ld hl, laskey                                   ; LASTKEY system variable ++

                xor a                                    ; A=0

                ld (hl), a                               ; reset LASTKEY, two birds with 1 stone

wailoo  add a, (hl)                                      ; load latest value of LASTKEY.

                jr z, wailoo                             ; loop until a key is pressed.

                ; skip move/switch sides (4B)

if feamod>0                                              ; opt: special move, switch sides to play black

                cp 's'                                   ; if "s" pressed at any time

                jp z, aftmov                             ; skip white's move, ### jr maybe

endif

                ; save pressed key and print it (5B)

                inc de                                   ; (@MstrBlinky) next char, E = 1 to 5

                ld (de), a                               ; save char in string

                rst 16                                   ; print it

                djnz realoo                              ; loop for 4 input chars

               

2 - Translating to board coordinates

Take into account that what has been stored are the pressed key values, and that needs to be converted to the board world. I initially tried to put both blocks 1 (read keyboard) and 2 (translate to coordinate) together in the same loop, but I did not see a way to make it shorter than what is now.

What we do now is to run through the array in memory backwards, since HL is already at the end of it, to allow exiting the loop when L reaches 0. The first character read (last in the array) contains the rank and the second last contains the columns. Rank calculation is 8 - (rank_typed -'8') = 56 – rank_typed. For the exact details, I think that comments in the code will be more useful.

Note that the square format we use is 0rrr0ccc (r= rank, c= column), so once we get the rank we need to shift it 4 bits to place it properly before calculating the column.

Also note that we need for legality check, we need to place the movement in B (origin square) and C (destination square). Two lines slide the results produced on every iteration until everything is in place after the last loop. Don't ask me how I came to do this.

movchk          ex de, hl                            ; (@MstrBlinky routine) DE=end of input string

movloo          ld a, 56                             ; rank calc = 8-(rank input-48) = 56-(HL)

                sub (hl)                             ; A= 56 - (HL)

                rla                                  ; move it to high nibble (x16)

                rla                                  ;

                rla                                  ;

                rla                                  ;

                dec hl                               ; (@MstrBlinky) run backwards through string

                add a, (hl)                          ; rank + column (not 0-7 column)

                sub 'a'                              ; make it a 0-7 column

                ld c, b                              ; slide results through B and C

                ld b, a                              ; at end of 2nd loop everything is in place

                dec l                                ; (@MstrBlinky) beginning of input string?

                jr nz, movloo                        ; if not, loop again

 

3 - Validity check

This section is optional, only for the full featured version. Before any move is typed, the candidate move list has already been generated (by genlis), so the task is simple: we just need to go through the candidate move list and see if there is a match for the inputted move.

HL points at the candidate list and the move just typed is in BC. The first byte in the candidate list contains the number of moves found in the current position, so we will use this as the loop counter (LD A, (HL)). The second byte in the list is not used. That allows us to place the moves in the even positions of the array. Note that the loop does not skip the first two bytes of the list although they do not contain any move. We save 2 bytes and it’s not possible to have a match with these two bytes since the second byte is always 0 (never altered) and there is no move with 0 as target square.

Ideally, I would have used DE, but some of the operations are not allowed. They key here is to be able to have the read candidate in HL, so that we can do (SBC HL, BC) to check each item.

If the item is found we jump to the common code part (aftsid), where the move is updated on the board. If not if keeps looping until the end of the list, and if it is not found if jumps back (whimov) for the first block (read keyboard).

seamov          ld hl, canlis                          ; canli pointer ++

                ld a, (hl)                             ; number of candidates

sealoo          ld d, (hl)                             ; origin candidate move

                inc hl                                 ; next byte

                ld e, (hl)                             ; target candidate move

                inc hl                                 ; next byte, for next loop

                ex de, hl                              ; candidate pair, DE: HL-canli pointer

                or a                                   ; reset carry

                sbc hl, bc                             ; compare input move with cand. move (Z)

                ex de, hl                              ; revert back, canli pointer

                jr z, aftsid                           ; move match: jump out. ready to move

                                                       ; B (origin sq), C (target sq) ready here

                dec a                                  ; count down

                jr nz, sealoo                          ; loop until canli covered

                jp whimov                              ; if not found, back to move input, jp maybe

 

Chapter 7: Piece values

Note: all descriptions will be made for white pieces, but remember that ChesSkelet plays with black pieces. So after running its small brain, the board will be reversed and the computer will be the black side.

Let me start by saying that my implementation will not do everything I’m explaining here. In order to keep things small I’ll be cutting some corners. Initially I thought that any scheme where K > Q > R > B > N > P would work, but it turns out it’s not that simple. Choosing the right piece values will simplify coding and the computer will make better decisions.

I’m using one byte to store the piece information. One bit will be used to store the piece color. In my mind, the highest bit (bit 7) makes more sense. If we need the “uncolored” piece value, we can clear bit 7 and no additional manipulation is needed.

So, let’s say that we use bit 7 of the square byte to store the color and the rest for the piece value:

bit7   bit6    bit5    bit4    bit3    bit2    bit1    bit0

C       P       P       P       P       P       P       P            

(C= color bit, P= piece value bits)

This would leave enough room for a classical K=127 (infinite), Q=9, R=5, B=3, N=3, P=1.

However, we do not need to follow these values strictly. The only good thing about the AI looking only one move ahead (ChesSkelet case) is that calculations where sacrificing a Queen for two Rooks do not make sense. Only the best value for current move is needed. Any K > Q > R > B > N > P scheme would work.

This said, we can try something a little more precise:

With ChesSkelet, I’ve chosen to use bit 5 for color (1=white, 0=black). This is not a random choice. I use capital and small letters to represent pieces, and the “ASCII distance” between capital and small letters is 32, so I can use bit 5 of the piece value (b5=1 is 32 in decimal) to decide capital/small letter depending on the piece color.

Some example of how the square byte scheme would look like. Note that we are introducing new constraints below, therefore values will change:

bit7   bit6    bit5    bit4    bit3    bit2    bit1    bit0

0       0       C       P       P       P       P       P        C= color bit, P= piece value bits

0       0       1       1       1       1       1       1        Example: C=white, P= 31= King

0       0       1       0       1       0       0       1        Example: C=white, P= 9 = Queen     

Take into account that these are not the final values in ChesSkelet, just two examples.

 

7.1 Move valuation

My piece value system is built around that fact that the computer is looking just one move ahead. For every board position, the computer builds a table with all the potential moves for its pieces. With that list, every move is evaluated.

The most basic approach to move valuation would be to capture any piece which is equal or more valuable than ours, just in case it is recaptured. Obvious, isn’t it? This system is the best you can get if the only information you have is the value of the piece you are moving and the value of the opponent’s piece in the target square.

ChesSkelet does a little better than that. For every move, 4 pieces of information are available:

·         Origin square piece value (own piece)

·         Target square piece value (opponent’s piece)

·         Origin square attack status, telling us if the computer piece is under threat.

·         Target square attack status, telling us if the square where we are moving is under threat.

Things get a little more complex, but will also help the computer taking better decisions:

(Whites are capitals and Blacks are small letters)

In the two cases above, a decision taken with no information on the square attacked status would be wrong:

So, in a simple manner, my move decision algorithm evaluates the move as follows (take into account that only legal moves are evaluated, so a piece cannot capture another piece with the same color):

1)      Target piece: Whatever piece value is found in the target square is counted (+)

2)      Origin piece:

a)      If the origin square is attacked, the origin piece is counted too (+), since we save it by moving it.
b)      If the target square is attacked, the origin piece is discounted (-), since moving it to the target square makes it a potential capture for the opponent.

Interestingly, this approach covers both origin and target squares being attacked, as the origin piece is being counted and discounted, making this move neutral, as the piece could be captured by the opponent in both squares.

Also, let me anticipate that most micro chess games will not announce checkmate, they need to actually capture the opponent’s king to finish the game, and therefore this has to be the best valued move.

As we will see later it is important to understand how many bits we need to store the pieces value. Let’s calculate the minimum king value (K=31 above is not optimal), the piece maximizing the number of bits needed. After some iteration I came to the conclusion that the best fittin g value for the Queen is 7.

+K (target square content= King) - 7 (Queen falling in an attacked square) = +K-7
+7 (target square content= Queen) +7 (Queen leaving his attacked square) = +14
K-7 > 14  -->  K>21 --> K=22 would work.

This is important, because we need to deal with negative values. To avoid negative values, I will add this (minimum+1) = 22 or more to any piece valuation, so that all results are positive. I’m adding 32 for different utility reasons. The range for piece valuation would be:

With K= 22 (00010110), bit 4 would still identify the king uniquely.

 

7.2 Square weight

In order to give the computer some direction in its moves, we are not only looking at the captures, but also at where pieces are moving towards. This is how I represent a square value (this representation is aligned to the 16x8 byte board introduced earlier).

bit7  bit6   bit5   bit4   bit3   bit2   bit1   bit0

0      R      R      R      0      C      C      C            R= rank bits, C= column bits

In advanced chess programming there are very complex schemes, depending on the piece and also on the game stage, but I could not afford anything like that, so I figured out a very simple scheme:

Coding: shift (losing bits on the right end, not rotating) the square value 4 times to the right, and there you have it. The only other thing to take into account is that ranks in memory decrease vs. ranks in board increase, so instead of adding the result we subtract it for calculation.

Coding: If I take the square value and do this: ADD A, 2; AND 5. It’s not perfect, but it clears the ranks and gives higher weight to the center columns (and only takes 4 bytes or 3 bytes for the small version with a a slightly different scheme). This is the column weight produced:

col0  col1   col2   col3   col4   col5   col6   col7

0      1      4      5      4      5      0      1   Scheme 1 (preferred): ADD A, 2; AND 5 scheme

0      0      0      4      4      4      4      0   Scheme 2 (short): INC A; AND 4 scheme

Aggregating rank for Scheme 1 and column weight we obtain a board heat map which looks like this.

I could have done it differently with other value in ADD and AND operations, but this particular tuning also helps me preventing initially opening the C column (which becomes F for black. Remember that computer plays with black pieces) and also prevents the scholar’s mate, and also gives the highest weight to the initial king square and F6, so a piece not finding obstacles will tend to go there.

Obviously, this approach is not dynamic. It won’t chase the King as it moves, but being as weak as ChesSkelet is, it’s not likely that the human player is moving his King a lot.

Now weŽll see how to combine the piece valuation with the square weight.

 

Piece valuation + Square weight

In the next step, my intention is to combine both Piece Valuation (PV) and the target Square Weight (SW) in a single byte. That would give us the move value that we can compare with the rest of the candidate moves.

It seems obvious that with this scheme PV needs to have a higher value than the SW. Therefore, PV will occupy the higher bits of the final value byte.

Now we need to sort out an inconvenient: PV needs 6 bits and SW needs 3 bits, and all that info needs to fit in 8 bits. Both values combination with the appropriate PV prioritization would look like this:

bit7   bit6   bit5   bit4   bit3   bit2    bit1   bit0

PV     PV     PV     PV     PV     PV/SW   SW     SW        

We need to decide what to do with the overlapping bit 2. Three possible options:

  1. Keep the overlapping: by leaving this bit open for both uses it may happen that a move with a good SW scores better than a pawn capture. Do we really want that? It would not be so bad, I guess.
  2. Give it to the square weight: we would lose the less significant bit of the piece valuation. That may lead to wrong capture decisions.
  3. Give it to the piece valuation: this would leave us with a very small granularity for the SW, but it would provide a reliable result.

I lean towards options 1 and 3, and I have finally chosen option 1. Yes, it's the shortest to implement.

All of the above is implemented in ChesSkelet with around 70 bytes.

 

Chapter 8: Black moves (computer)

Let's now digest the black pieces move code. Generally speaking, black moves is made of a loop going through all the candidate moves identified by genlis code (2 chapters from now), and as described in the previous post, it generates a piece valuation plus a target square valuation, comparing it to the previous maximum valuation and keeping it in case it's new maximum.

blamov

chomov          ; preparations (7B)----------------------------------------------------

                ld hl, canlis                         ; candidate list. No H reuse ++

                ld b, (hl)                            ; number of candidates at position 0

                ld c, l                               ; C=0, maximum valuation reset

                inc hl                                ; skip 2 bytes to first candidate in list

                inc hl                                ;

 

No big deal in this first section. HL points at the candidate list, the first byte from the candidate list contains the number of candidate moves is loaded into B for loop control and C will contain the maximum valuation, now is reset.

choloo          ; loop through candidates (6B) ----------------------------------------

                ld d, (hl)                            ; D: origin candidate square

                inc hl                                ; next candidate byte

                ld e, (hl)                            ; E: target candidate square

                inc hl                                ; next candidate byte

                push bc                               ; BC released

                push hl                               ; HL is different from here

 

Once this is done, the loop starts to do the work. D and E will contain origin and target squares, needed not only to collect the pieces in them but also to calculate the target square weight. We also push all these registers to the stack (weŽll recover them later) in order to have them available in every loop iteration.

Piece valuation

                ; pieces valuation ----------------------------------------------------

                ; pieces collection (8B)

evatap          ld h, boasth                          ; board base ++

                ld l, e                               ; target square

                ld b, (hl)                            ; black piece value

                ld l, d                               ; origin square

                ld c, (hl)                            ; white piece value

                res 5, c                              ; uncolor white piece, pih

 

Now we point HL at the game board, and with D/E having the move squares, weŽll collect the content of the squares, this is, the white piece moving, and the black piece or empty square as target. The last line here will uncolor the white piece (bit 5), in order to simplify the calculations. Take into account that the white piece is not always used, as I explained in the earlier post. It all depends on the attacked status of the origin and target squares.

                ; origin attacked square (7B)

evaato          ld a, b                               ; target piece always counts

                ld h, boaoph                          ; H(L): attacked board base, L: unchanged ++

                bit 7, (hl)                           ; target square attacked?

                jr z, evaatt                          ; not attacked, skip counting origin piece

if feamod=1                                           ; opt: rows 2 do not move even if attacked       

                ld a, d                               ; 0rrr0ccc, add origin square    

                and $70                               ; filter ranks

                cp $60                                ; is rank 6?

                ld a, b                               ; target piece always counts

                jr z, evaexi                          ; skip this move

endif

                ; count origin piece (1B) if attacked, general case

evaatc  add a, c                                      ; A: 00pppppp, count white

 

As explained in the previous chapter, target piece always counts for piece valuation.

After this, we point HL at the attacked squares status board and see if the origin square is attacked by black pieces (human in this case, remember that at this point the game board is reversed). If not attacked, there is nothing to do and we jump to the next block below.

I have included this optional code that is only added in the full version. I guess this is the right place to discuss it. ChesSkelet has an important design issue. As it only looks one move ahead and only looks at individual moves, not at the whole board, nothing prevents a piece from moving and uncovering the King from an opponent's attack (illegal move!). This becomes even worse because ChesSkelet algorithm tends to move a piece which is under attack to an unattacked square, since that move gets a good valuation (in the end, it makes sense to save a piece from being captured). Well, in order to partially prevent this, this optional code will prevent pieces in ranks 6 (only rank 6) from having a standard valuation and therefore move if attacked. It actually is not very scientific, but it makes things look a little better in some situations.

Last line adds the origin square piece value to the valuation if not skipped (square is not attacked, square is not in rank 6).

                ; target attacked square (6B)

evaatt          ld l, e                                 ; H(L): point at target square

                bit 7, (hl)                             ; target square attacked?

                jr z, skiato                            ; if target not attacked, skip

                sub c                                   ; if target attacked, count white out 

 

Now we run a similar check on the target square. Basically, if the target square is attacked, we'll discount the origin piece from that valuation. What's the logic of this? Well, if the computer moves its piece to an attacked square, it takes the risk to lose it. As we do not know anything else about the environment (if the target square is defended by another computer piece, which human piece is attacking that square, etc...), this is the most cautious thing to do. Basically, it will give a bad valuation to this type of moves.

                ; compensate + prioritize piece valuation (6B)

skiato          ld h, $20                              ; prepare H for later rotation and use for A

                add a, h                               ; A: 00pppppp, compensate=K+1, pih                 

                rlca                                   ; leave space for square weight

                rlca                                   ; A: pppppp00, piece addition is 5 bits

                ld b, a                                ; B: piece addition value

 

Last thing in the move valuation (either capture or escape move). We need some adjustments:

 

8.1 Square weight

The weight valuation comes right below. The idea is that we always prefer the best capture/escape move, and only in case that we have several moves with the same capture/escape value, the square weight (best destination according to the heat map shown in the previous chapter) will help us decide which move is best.

WeŽll calculate the rank and the column weight separately and add them.

evacol          ld a, e                                           ; A: 0rrr0ccc

                ; these two values below can be tuned for different opening schemes

                if feamod>0

                           add a, 2                               ; A: 0rrr0ccc

                           and 5                                  ; A: 00000ccc

                else

                           inc a                                  ; A: 0rrr0ccc

                           and 4                                  ; A: 00000cc0 (weight: 0,0,0,4,4,4,4,0)

                endif

 

This first part looks at the column weight. Before finding this method, I was using heavier methods like having an array linking columns and its weight or variations of it. Now it's much simpler (depending on the ChesSkelet version we have two settings). Take into account that the small version only moves the pawns one rank forward at first move, so that changes how it behaves, and also, the small version settings uses 1 byte less.

What does it do? By adding 2, we are shifting the column values in a way that from column 2 to 5, bit 3 becomes 1. This allows us to decide column valuation using that mask with bit 3 on. Why AND 5, then? It provides a slightly more precise output.

                ; ranks weight (ranks weight is 8..1, aiming for board's end)

evarnk          add hl, hl                             ; HL: 00100000 0rrr0ccc (before)

                add hl, hl                             ;

                add hl, hl                             ; HL: 000000rr r0ccc000 (after)

                sub h                                  ; A:  00000cww (w=r+c)

                add a, b                               ; total value: pieces + weight

Now we evaluate the rank weight. The logic is simpler but was not easy to find a cheap way to do it (thanks, Arkannoyed!): rank sits on the high nibble of the square weight, so first thing is to shift if to a low nibble. By using HL I’m shifting from L to H, subtracting the shifted result in H from the column weight.

evaexi          pop hl                                 ; recover canli

                pop bc                                 ; recover previous maximum value

                cp c                                   ; compare with current maximum

                jr c, chonoc                           ; if current eval (A) <= max eval (C), skip

                ld c, a                                ; update best evaluation

                pop af                                 ; remove old maximum to avoid cascades in stack

                                                       ; ### initial push to compensate?

                push de                                ; push best candidates so far

chonoc          dec b                                  ; decrease loop counter 2 by 2.

                djnz choloo                            ; loop through all candidates (canto)

                pop bc                                 ; recover saved values (B: origin, C: target)

 

This is the end of the loop iteration. WeŽll recover the previously saved registers. WeŽll compare the maximum saved valuation (C) with the current square valuation. At the loop exit weŽll recover the other registers and control the loop repetition with B. B is decreased twice (DEC B; DJNZ) since each candidate in the list occupies two bytes.


Chapter 9: making the move

At this stage, we've managed to produce the move to be made, either by black or white pieces and store it in registers B and C. This way, the code needed to update the board with such move is the same for both sides. This, which may seem so obvious, only became clear to me after many coding iterations.

This part of the program would be pretty simple if I did not have to deal with special moves. So let's have a look at the mandatory code first and later weŽll discuss the special moves.

aftsid          ld h, boasth                           ; point at board (canlih=$83 before) ++

                ld l, b                                ; point at origin square

                ld d, (hl)                             ; D: get origin piece

                ld (hl), 0                             ; write origin piece         

                ; write target square with origin piece (5B)

aftdes          ld l, c                                ; (H)L: target square

The code to move the piece can't be simpler. We will point HL at the board. "HB" will give us the source board. From there, weŽll extract the piece and set the square to 0 (empty). And weŽll write the piece in "HC". For the moment the board will not be updated in the screen. This only happens after white moves, as we saw in an earlier chapter.

revboa          ; push full board to stack (7B)

                inc h                                      ; H = $80 = boasth ++

                ld l, h                                    ; (H)L: end of board. trick: start from $8080

revlo1          dec l                                      ; countdown squares

                ld a, (hl)                                 ; read piece

                push af                                    ; copy piece to to stack

                jr nz, revlo1                              ; loop down to beginning of the board

                ; collect board back in reverse order + switch color (15B)

                ld l, $78                                  ; (H)L: end of board again

revlo2          pop af                                     ; collect piece from stack

                or a                                       ; is it an empty square?

                jr z, revski                               ; if yes, skip

                xor %00100000                              ; otherwise, reverse color (b5), pih

revski          dec l                                      ; countdown squares

                ld (hl), a                                 ; piece back into board

                jr nz, revlo2                              ; loop until beginning of board

                jp befmov                                  ; back to white move, too far for jr

 

And the last section of the main program will reverse the board. This is the typical coding exercise for good coders to show off. In my case, after more typical approaches, with two counters (one increasing and one decreasing) to move the data, I ended up using the stack. In the first half of the section, I'll start reading the board from its end. Actually a little beyond the end (8080h) as it was cheaper to set. Every byte read goes to the stack.

In the second section, IŽll extract the data from the stack. This is the nice thing about using the stack here: the data comes out in reverse order with no extra effort. I will point again at the end of the board (this time really at the end). IŽll take the byte and reverse its color (XOR %00100000) before writing it to the board again.

If you have followed this, youŽll notice that IŽm leaving 3 bytes in the stack that I'm not extracting every time the board is reversed. Ok, this may destroy the code after several hundred moves. Nothing to be worried about.

Finally weŽll jump to the common code before moves are made, where it's decided who moves next.

Now, let's have a look at the special moves, which is optional code. For special cases (castling, Pawn 2 squares forward, promotion, etc...), not only in this section, you'll see that instead of checking every condition to verify if the move can be made I tend to add all the values involved and make one single condition check, and that saves code. In most cases, things can be arranged so that this addition value is univocal and can only be the result of the expected move.

casroo          ld a, (hl)                               ; origin piece

                add a, b                                 ; + origin square

                sub c                                    ; - target square

caslon          cp $38                                   ; $36(king) + $74(ori) - $72(tar)= $38, pih

                jr nz, cassho                            ; no long castling

                ld l, $70                                ; long castling rook square (a1)

                ld (hl), d                               ; erase rook (D=0 here)

                ld l, $73                                ; rook destination (d1)

                ld (hl), $25                             ; move rook, pih

cassho          cp $34                                   ; $36(king) + $74(ori) - $76(tar)= $34, pih

                jr nz, casend                            ; no short castling

                ld l, $77                                ; short castling rook square (h1)

                ld (hl), d                               ; erase rook (D=0 here)

                ld l, $75                                ; rook destination (f1)

                ld (hl), $25                             ; move rook, pih

casend


I never thought of including castling due to its high implementation cost, but I agree that this is a critical move to keep the game as something close to real chess. What does it do? We take the moving piece, the origin square and the target square. The move "distance" is -2 for the King castling to the left and +2 for the King right. We calculate that distance and add to the moving piece, and the value we get is the value that needs to be matched. If the condition is fulfilled weŽll erase the move the proper Rook in the board. The King is moved by the regular code above.

                ld a, c                                  ; A: 0rrr0ccc

                and %01110000                            ; A: 0rrr0000

                add a, (hl)                              ; A: 0rrxpppp

                cp $22                                   ; white pawn ($22) on rank 8 ($00), pih

                ld l, b                                  ; restore origin square

                ld d, (hl)                               ; original piece

                ld (hl), 0                               ; write origin piece

                jr nz, aftdes                            ; if not a pawn, skip

                ld d, $27                                ; make piece a queen, pih


Promotion (not under-promotion) follows a similar process: we take the target square (C), filter it and keep the rank only (0rrr0000), we add the moving piece. Target rank must be 0 and white Pawn is 22h, therefore the sum has to match 22h. If that condition is fulfilled we just empty the origin square and make the piece a queen. The regular code will store it in the proper place in the board.

 

Chapter 10: Move list generation

As announced, here comes the last chapter of this dissection that IŽll split in two parts. I will explain what the data used means and later, in a separate sub-chapter weŽll look into genlis code.

The idea of using static data to describe the pieces moves over the board is quite common and I'm not really doing anything different from other programs. However, I've tried to give it some more value to it. The potential moves for a piece are described in two steps, therefore we have two data blocks:

org $7F88                                           ; pawn: $22x4=$84

; piece, move type, vector list delta address (18B)

; move type / 0 / 0 / pawn straight / pawn diagonal / DDDD (real radius + 7)

movlis

pawgen               defb      $28, $E3               ; pawn straight

                     defb      $18, $E7               ; pawn capture

org $7F8C

knigen               defb      $08, $EA               ;

org $7F90

bisgen               defb      $0E, $E5               ; bishop

org $7F94

roogen               defb      $0E, $E0               ; rook

org $7F9C

quegen               defb      $0E, $E0               ; queen

                     defb      $0E, $E5               ;

org $7FD8

kingen               defb      $08, $E0               ; king: $($16+$20)x4=$D8

                     defb      $08, $E5               ;

 

The data in this first block is strategically placed in memory. The info corresponding to each piece sits in the piece value multiplied by 4 (4 is how much the info for each type of piece needs in memory).  Take into account that we are only creating the move list for white pieces (i.e. white bishop value is 24h, 24h x 4= 90h). This allows me to address quite immediately the type of moves every piece can make. What do these two bytes mean?

·         Byte 1: The first byte indicates the type of move the piece makes. It contains 2 pieces of information: in the low nibble we have what I call the radius. A Knight or the King have radius=1, and a Bishop, Queen or Rook have a radius=7. This is how far they can reach when moving in a direction. This value is used to control the loop when the code tries to move the piece in one particular direction. That was the original value. Later I increased that by 7 so that when I decrease it I can detect the 0 by looking at bit 3 of this radius. This helps saving some code.

Very important, the values produced by adding this delta to the current square are aligned to the 0x88 (we saw this some time ago) code to detect pieces going out of the board. WeŽll see more about that soon.

The higher nibble contains what I call special moves info. These are specific flags in bit4 and bit5 indicating the special Pawn moves. Take into account that a Pawn behavior is not regular: it cannot capture when moving straight and it can only move diagonally when capturing, and these are not standard behaviors, so the code needs to know about it, and it's easier to provide this information directly to the code, than having the code deriving it from  the piece info, where we have a Pawn moving this way or the other.

·         Byte 2: The second byte is just a pointer to the move vectors (that’s how I call it) that weŽll see below.

Again, note that these two blocks of data are placed in the same micro page in RAM, so H does not need to be altered during this process.

org $7FE0                                        ; vectors start at: $7FE0 (arbitrary)

; (y, x) move delta pairs (16B)

veclis

strvec          defb      $FF, $01               ; +0, straight vectors

                defb      $10, $F0               ; +3, straight pawn, last half line

org $7FE5

diavec          defb      $0F, $11               ; +5, diagonal vectors

                defb      $EF, $F1               ; +7, diagonal pawn

org $7FEA

knivec          defb      $E1, $F2               ; +10, knight vectors

                defb      $12, $21               ; knight moves listed clockwise

                defb      $1F, $0E               ;

                defb      $EE, $DF               ;

 

The second data block contains generic move descriptions, not specific to a piece, therefore a move descriptor can be used by several piece types. There are three groups: first 4 bytes describe the straight moves, second 4 bytes describe diagonal moves, and the last 8 bytes describe the Knight moves.

Each byte in these blocks indicates how many bytes we need to move from the current piece square (byte) to reach the target square. If you remember, we've been discussing the board as a 16x8 byte space. Actually, that space is a linear array of bytes. Using the King example, to move it to the right we just add 1 to the current square, to move it left we subtract 1 to the current square. What may be less obvious is that to move it one rank ahead we just need to subtract 16 to the current square (remember, each rank is made of 16 bytes, 8 used and 8 unused), which is actually a very simple operation. Same idea applies to diagonal and Knight moves.

This is what each byte means. How do we reach the right blocks for each piece?

Let me illustrate it with some examples:

Now that now the used of this static data, weŽll see in the very last chapter how the code uses it and how the potential move list is built.

 

Chapter 11: Move list generation (II)

Here comes the much announced "movlis" routine, which is the longest and more complex routine in the program. What does it do? Independently of the side moving, "movlis" generates a list with all the potential moves the side moving can make. Once again, remember that the program is reversing the board after every move so that white pieces are always moving. Making every routine to work for both sides would be a nightmare and reversing the board takes only a few bytes.

When human side moves, the list generated is optionally used to determine if the move typed is valid or not. When black pieces move, the list is used to evaluate each and every move and decide which one is best.

All of the above was implemented since the beginning. When I introduced the idea of having the attacked squares board I noticed that I could reuse all the code with a minimum change, so in parallel to generating the candidate move list it updates the attacked squares board.

Now, fasten your seat belts and let's dive into "genlis".

genlis

bacata          ; backup attack board in reverse order, used in evaluation (13B)

                ld l, $FF                                ; (H)L = $80FF (boaata-1), H always $80

                ld de, boaopo + $78                      ; DE: same thing, 1B passed end of board

bacloo          inc hl                                   ; HL: increase 16b counter to hop to next page

                dec e                                    ; E:  decrease 8b counter to hit Z flag

                ld a, (hl)                               ; load attack status

                ld (hl), 0                               ; clear attack status, no alternative!

                ld (de), a                               ; backup attack status

                jr nz, bacloo                            ; loop down to square $00

                                                         ; exit values: DE=$8200, HL=$8177

 

Before looking into this section, I need to explain how the reverse squares board works. I had to do it in two steps: there is an attacked squares board, but this board is not reversed simultaneously with the game board. Not only that. It has to be reversed so that it can be used during move evaluation, but it also has to be reset so that I can generate a new one for the next side moving. It would make sense to do it sequentially, but it would take more code, so we actually have two attacked square boards: the one which is filled in by “genlis” and the reverse one used for move evaluation.

In the code above, I'm copying the first one, by reversing it, into the second and resetting the first board, so that "genlis" can fill it again during the new moves generation. It is actually a simple loop. This would be again a show-off for programmers trying to find the shortest way to implement it. In my case, I take advantage of the fact that the two attacked square boards live in contiguous mini pages, so setting HL and DE properly becomes very simple.

                ; prepare environment (4B)

                inc d                                      ; D= $83= canlih

                xor a                                      ; reset

                ld (de), a                                 ; cantot= 0

                ld b, l                                    ; B= L = 77, SQUARE COUNT

 

We are now in the preparations area. DE will point at the mini page where the candidate moves will be stored and the number of them is set to 0. It's the first byte in the page. We also load B with the last square in the board (77H = 01110111b, remember: 0ccc0rrr). The main loop (outer loop) will use B and will countdown through the board.

IŽm going to use an example with a Bishop in A1. WeŽll follow the code with it.

                ; read piece from board (4B)

squloo          ld h, boasth                             ; H: board base ++

                ld l, b                                  ; point at current loop square

                ld a, (hl)                               ; read piece from board

                ; get move type and pointer to move list (6B)

squgon          dec h                                    ; H(L)= movlih, moves vector base ++

                add a, a                                 ; x4, each piece vector is 4B long

                add a, a                                 ;             

                ld l, a                                  ; (H)L points at the move vector now

 

We are entering the main loop. We will see that the register usage is pretty tight. This is why I'm pushing registers all the time to free them for use in inner loops. WeŽll recover them when needed.

As we did in previous chapters weŽll discuss the special moves separately, to avoid distractions from the main routine.

We'll start by reading the piece from the board. With the piece value we are ready to see in which directions the piece can move, as we saw when discussing the static data associated to this. WeŽll multiply the piece value by four and that will leave HL pointing at the "move type" linked to the piece. This move type contains: the special Pawn move flags, the move radius and a pointer to the direction the piece can go.

I know this is becoming a little tricky...

Bishop example: the big loop will count down reading all the squares to 70h (A1 is rank 7, column 0, therefore byte 70h in memory). It will find our white Bishop in 70h. This is 24h (reminder: 20h is white and 04h is the piece value for the Bishop).

                               ld d, 2                       ; 2 submoves per piece

subloo                         ; byte 1 - move type (5B)

                               ld a, (hl)                    ; move type loaded

                               or a                          ; =cp 0, 2nd move type not used case

                                                             ; black/empty: move type=0 leads here

                               jr z, squexi                  ; ---v exit: square is done

                               ld e, a                       ; E: MOVE TYPE (B,C,D used here)

                               ; byte 2 - movlis delta (3B)

                               inc hl                        ; next piece sub-entry

                               push hl                       ; Save HL for 2nd loop  

                               ld l, (hl)                    ; pointer to move delta

 

For each piece in each square we have a two iterations loop (middle loop), as each piece may have one or two types of moves. Rooks, Bishops, Pawns, and Knight have one type of move (meaning 1 direction). King, Queen and Pawns have two (they combine straight and diagonal). In the first place, the exit condition: if the move type is 0 it means that we are done with the piece, either with one or two types of moves. Also, code for empty squares ends up here, so the same code is used for both exit conditions.

We load the move type in E. Then we jump to the next byte in the move type which is the pointer to the move delta (second block of data described in the previous chapter).

Bishop example: this is the data block corresponding to the Bishop:

                bisgen  defb      $0E, $E5               ; bishop


vecloo                                         ; vector read (8B)

                                               ld c, b          ; TARGET SQUARE init

                                               ld a, (hl)       ; vector delta

                                               or a             ; =cp 0

                                               jr z, vecexi     ; ---v exit: vectors end with 0, next sq.

                                               push hl          ; save current delta

                                               push de          ; save move type + radius

                                                                ; E: variable radius within loop

                                               ld d, a          ; D: store delta within loop

Now we take the current square (remember, squares are covered by the big loop) and add the delta that goes to the next square the piece can move to. The exit condition here is again having a delta=0. We push all DE and HL to free them and we store the new square calculated in D. We are going to use it on every iteration to calculate the new target.

Bishop example: From A1, the Bishop can only move in one direction. We'll see how the OOB moves are detected in a minute.

org $7FE5

diavec          defb      $0F, $11               ; +5, diagonal vectors

                defb      $EF, $F1               ; +7, diagonal pawn

From A1 it can only go in the B2 direction. This is from 70h to 61h. If you see 70h + F1h= (1)61h. Bit 9 is gone so we keep 61h. The other three vectors will give us out of the board squares.

celloo                                           ; prepare x88 check (7B)

                                                 ld a, d          ; delta loaded

                                                 add a, c         ; current target (sq. + delta)

                                                 ld c, a          ; current target

                                                 and $88          ; 0x88, famous OOB trick

                                                 jr nz, vecnex    ; ---v exit: OOB, next vector

                                                 ; read target square (3B)

                                                 inc h            ; H(L)= $80 = boasth ++

                                                 ld l, c          ; point at target square

                                                 ld a, (hl)       ; read target square content

                                                 ; mark attacked ### str. pawn marked attacked

                                                      inc h          ; H(L)= $81 = boaath ++

                                                      ld (hl), h     ; mark attacked ($81)

                                                      dec h          ; H(L)= $80 = boasth ++

                                                 dec h            ; H(L)= $79= movlih ++


Here we start the inner loop that will visit all the squares a piece can move to in a particular direction. There is no specific exit condition for this loop, as it can be exited fir different reasons that weŽll explore later.

Now we add the delta plus the current square into A. If we have either bit3 or bit7 set to one, it means that the calculated target square is OOB. You can try at home but it works. The logic here is that any board square has ranks and columns between 0 and 7. Therefore, valid ranks can go from 0000xxxx to 0111xxxx, and valid columns can go from xxxx0000 to xxxx0111. If bit3 of bit7 is not zero, AND 88h will detect that for us. Incredibly simple. If it's not a valid target square to move to, weŽll jump to the next vector for that type of move.

If it is a valid move, weŽll read the target square to see what's in there. And we also mark that square as attacked in the attacked squares board. This introduced a little inconsistency, since straight pawn moves have the target squares I did not marked as attacked although the Pawn cannot capture going straight. It does not result in illegal moves, but makes the computer a little shy since it wonŽt move in front of Pawns as those squares are not safe. I did not find a simple solution to this, so there it is.

                                                 dec h             ; H(L)= $79= movlih ++

                                                 ; target is white (4B)

                                                 bit 5, a          ; is it white?, pih

                                                 jr nz, vecnex     ; ---v exit: WHITE b4=1, next vector

                                                 ; target not white (3B)

                                                 or a              ; =cp 0, is it empty?, pih

                                                 jr z, taremp      ; if not 0, it's black: legal, no go on

tarbla                                           ; target is black (7B)

                                                 bit 5, e          ; special move: pawn straight check

                                                 jr nz, vecnex     ; ---v exit: no str. cap., next vector

                                                 ld e, a           ; radius=0 (=<8, canonical: ld e, 0)

                                                 call legadd       ; 

taremp                                           ; target is empty (14B)

                                                 bit 4, e          ; special move: pawn on capture check

                                                 jr nz, vecnex     ; ---v exit: no diagonal w/o capture

                                                                   ; next vector       

                                                 dec e             ; decrease radius

legadj                                           bit 3, e          ; if radius < 8 (Cb3=0), radius limit

                                                 jr nz, celloo     ; ---^ cell loop

 

This is an interesting part. Depending on the target square content, weŽll do different things. Following the sequence:

Last thing we do is to check radius: if it's still positive (bigger that 7 in the code) we can week moving in that direction, so we go back to "cello" tag.

Bishop example: in the case of the Bishop in A1 moving to B2 (empty), weŽll add the move to the list, the original 0Eh radius will be decreased, and the inner cell loop will be run again, but now with radius one square smaller, and the base square will be B2 (61h) instead of A1.


vecnex                                ; next vector preparation (5B)

                                      pop de                 ; DE: recover move type + radius

                                      pop hl                 ; HL: recover current vector

                                      inc hl                 ; HL: next vector

                                      jr vecloo              ; ---^ vector loop

This is the boring part of the code where not much happens. We recover old values from the stack that we need so that we can use them at this point. Theoretically, this inner loop is repeated forever until one of the many exit conditions occurs.


vecexi          ; next square preparation (5B)

                pop hl                             ; HL: recover pointer to sub-move list

                inc hl                             ; HL: next byte, point at 2nd sub-move

                dec d                              ; 2 sub-move iterations loop control

                jr nz, subloo                      ; if not 2nd iteration, repeat loop

                ; end of loop (2B)                           

squexi          djnz squloo                        ; ---^ squares loop

                ret

We keep on recovering data from the stack as we leave the inner loop.

We go to the 2nd sub-move, which in the case of the bishop does not exist. After the second iteration we would exit the middle loop.

Finally we decrease the global square counter, which count down to 0 (DJNZ). For those who noticed it, the outer loop will go through the unused help of the 16x8 board too, but since these squares are empty, nothing will happen on them.

Here ends the main code. There are two optional sections for special moves. In both cases, this routine was the best place to implement it as here is where the legal moves are identified.

                kincas         ld l, a                ; save A (can't use push AF, flags lost)

                               add a, b               ; A: 0rrr0xxx + 000ppppp (uncolored white p.)

                               cp $AA                 ; king($36) at E1($74)= $AA, pih

                               ld a, l                ; recover A

                               jr nz, kinend          ; if no match, skip adding legal move

                               ld c, $72              ; E1-C1 move, rook's move missing

                               call legadd            ; add king's move

                               ld c, $76              ; E1-G1 move, rook's move missing

                               call legadd            ; add king's move and go on with king's moves

                kinend

The first one is covering castling. It's a big cheat, but I combine the current square and the piece in the square. If it is a white king (36h) in E1 (74h) weŽll add the two possible king moves for castling to the legal move list (E1-C1, E1-G1). We already was the Rook's part, which is executed only if one of these King's moves is made.

                genpw2         add a, b               ; piece square + move type

                               and %11111000          ; masked with relevant bits

                               cp $88                 ; $28(str.pawn)+$60(rnk 6) ### univocal

                               jr nz, skppw2          ; if not, skip

                               inc e                  ; increase radius: 1 -> 2

                skppw2

For the pawn moving 2 squares forward. Same process I typically use: in this case I will combine the rank (it has to be in rank 6, therefore 60h) and the move type (28h, for straight pawn). If it's a match, I just increase the radius for this straight move to 2. Simple, isn't it?


Chapter 12: Games

Now that the code is fully reviwed, IŽm posting the games I played with ChesSkelet against BootChess and ZX 1K Chess. I'm using coordinate notation (https://en.wikipedia.org/wiki/Chess_notation), since it can help someone crazy enough to replay the games.

I found both games here:

Bootchess: http://copy.sh/v86/?profile=custom&fda.url=http://copy.sh/v86/images/bootchess.img

ZX81 1K Chess: http://www.zx81stuff.org.uk/zx81/tape/1KZXChess

Notes before the games:

Some conclusions:

·         NanoChess is pretty weak in all aspects. Chesskelet is not far, pretty weak too, but at least graphics are better and it has some features (switch side, castling) which boot chess does not have.

Games:

ZX81 1K Chess, King opens (0.5) - ChesSkelet (0.5)

1.E2-E3 E7-E6               A00 Van't Kruijs opening, rally crappy, rarely played

2.E3-E4 F8-B4               Out of any known opening, none has the 2 squares forward pawn move.

3.E4-E5 B4-C5               Black become super conservative. With no free space, they will wait.

4.F2-F3 C5-B4               White go on with their weird development

5.F3-F4 B4-C5               Black keep on with their conservative strategy.

6.G1-E2 C5-B4

7.H1-G1 B4-C5               Black threaten white's rook

8.G1-H1 C5-B4               White escape back

9.H1-G1 B4-C5

10.G1-H1 C5-B4              …etc, draw on threefold repetition

Very short game. 1K Chess was developing better, but its stubbornness to develop the rook served this undeserved draw opportunity to ChesSkelet, which is very lazy (repetitive) when there is no free space to move.

 

ZX81 1K Chess, Queen opens (1) - ChessKelet (0)

1.D2-D3 E7-E6             A00 Mieses opening, also rarely played

2.D3-D4 F8-B4+            Surprisingly, Black checks white King with the Bishop.

3.C2-C3 B4-D6             White defends with its pawn (great defense, it shows advanced skills), and blacks have to retreat.

4.H2-H3 C7-C6             White starts its weird development.

5.C3-C4 D6-B4             Black insists with the check.

6.B1-C3 B4xC3             Now White defends with the Knight (good defense again) and Black captures.

7.B2xC3 D7-D6             Whites recapture.

8.A1-B1 B7-B6

9.A3-A3 B6-B5??           Clear Black mistake, as weŽll see.

10.C4xB5 C6xB5

11.B1xB5 B8-C6            White gets a pawn advantage

12.B5-H5 C6xD4??          Another big mistake (this one was unexpected from ChesSkelet).

13.C3xD4 D8-B6

14.D1-A4+ E8-E7           Whites queen checks the King, the King escapes.

15.C1-G5 E7-D8???         Whites check now with a bishop, and blacks, although they had escape options, made an illegal move (unexpected too).

ChesSkelet made several unexpected decisions here (moves 9, 12, 15), but still 1K Chess was playing  better. It would need some troubleshooting to see what went wrong.

 

Boot Chess (0) - ChessKelet (1)

1. E2-E4 E7-E6            C00 French defence, seldom played

2. G1-E2 F8-B4            Black move is out of any book. What is an opening book? :-)

3. B1-C3 B4xC3            Blacks capture white Knight

4. B2xC3 D7-D6

5. C1-B2 C7-C6            White develop the Queen side, and Blacks walk with the center Pawns.

6. H2-H3 C6-C5

7. H1-H2 B7-B6

8. G2-G3 B6-B5

9. F1-G2 D8-B6

10. G2-F3 B6-C6           Black enters the wait mode...lazy bastard!

11. E2-F4 E6-E5

12. E1-E2?? E5xF4         It seems like White does not notice the threatened Knight.

13. G3xF4 C6-B6           White takes the capturing pawn.

14. E2-E3 B6-C6           The King becomes adventurous, and it that will have a cost...

15. D1-E2 B5-B4

16. C3xB4 C5xB4           Pawns exchanged

17. B2xG7 C6xC2           But it opens this diagonal for the Bishop

18. G7-H8 C2-C5+          White captures the Rook. Blacks surprisingly check whites King

19. E2-D3 C5-E3           Whites makes an illegal move and the King is captured.

Both sides play an awful game. BootChess ignores the check and loses on an illegal move.