ChesSkelet: micro chess program - 363 Bytes
Re: ChesSkelet: micro chess program - 363 Bytes
Let’s how far I can get in dissection this code for you, guys. First of all, sorry for the typos and mistakes. My English is not bad, but not yet native.
I´m giving some general details in http://chesskelet.x10host.com/development.html, for a general introduction to the program. However, I´m not totally satisfied with the information in it.
I guess the first things 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:
• Board implementation: there are tons of literature on the topic over the internet, but this article (https://www.chessprogramming.org/Board_Representation) is particularly good. Most works out there are focused on execution speed, and not so much on simplicity and memory requirements. After some consideration, I discarded bitmaps, as the memory requirements were much higher, and ended up writing the initial coding using an 8x8 board. Soon I found the famous out of board detection problem and the 0x88 solution (https://www.chessprogramming.org/0x88). I went through several board variants where the 0x88 out of board detection worked (12x10, 12x8) and ended up using a 16x8 board, where half of the squares are never addressed or used, but the code to run through the board squares was much simpler. It's a pity I did not fully understand all these articles before I went through the learning process the hard way. Only later I found that all my findings had been found long ago by someone else.
• Micro-paging: one of my main finds during this development. I have placed (almost) every data structure in different 256-byte pages, mainly at the beginning of each page. This allows me to hop from one data area to another just by modifying H register, since HL is used for data addressing. Furthermore, if the program follows a linear execution sequence, data pages can be arranged in a way that just by increasing/decreasing H register by one (INC H, DEC H, only 1 byte!), we can jump to the required data page at each point.
• Data scattering: in regular programming, data is placed in memory without taking into much consideration whether access to these data is simple or not. In my case, I have placed data structures in memory areas where addressing them is simple. In other words, data location is adapted to the code and not the opposite. Micro-paging is part of that, but there are other tricks.
• Long instructions: I avoided using long instructions as much as possible (Z80 has 1-byte to 4-byte long instructions). I totally avoid using 4-byte instructions, and reduce 3-byte instructions to the minimum. This approach has several aspects:
o Avoid IX and IY registers extended instructions (2 to 4 bytes long). It is hard sometimes to avoid it as in some cases all registers are busy. On the other hand, using the stack to save and release busy registers temporarily and recover them afterwards is typically lighter.
o Avoid temporary variables (memory positions). Only registers are used in this program. For instance, R/W operations of memory positions require at least 5 bytes (LD HL,XX; LD A,(HL), LD (HL),A), where R/W of a register takes only 2 bytes.
o Avoid procedure calls, as CALL + RET set requires 4 bytes.
o Avoid absolute jumps (JP, 3 bytes) are avoided as much as possible. As the code is so small relative jumps (JR, 2 bytes) are possible in almost all cases.
o Coding optimization: some operations have an alternative way to be implemented with a shorter instruction. For instance, the most famous one: if you need to set A=0, the standard instruction would be LD A, 0 (2 bytes). There is another method you can use in most situations, XOR A (1 byte). There are many other optimization tricks, most of them covered in these two sites:
Z80 heaven - Optimization (http://z80-heaven.wikidot.com/optimization)
brandonw.net - Z80 Optimization (http://wikiti.brandonw.net/index.php?ti ... timization)
Hope this is not too heavy for starters. So far I did not include a single line of code, which is good, I guess.
Re: ChesSkelet: micro chess program - 363 Bytes
Let's look into the initial program code. I´ll break it in several sections.
First of all, all constants and variable declarations:
Code: Select all
; 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
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 data 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:
- If I place two bytes of data in RAM and need to read them I would need to point at each of them individually in order to read them. That would need 2x3 bytes just to address them. (LD HL, XX / LD HL, YY)
- If date are consecutive, the second instruction to point the data can be shorter, just by increasing the pointer by 1 we will get the same result (LD HL,XX / INC HL)
- The problem with this second approach is that you cannot use it for data bigger than two bytes. Savings would be gone if you increase HL one by one to reach a data 10 bytes away from the current HL address. What did I do? I place 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 a byte board with all the pieces in 8000h-807Fh (H=80h) addresses and another byte board with the attacked status of squares in another board 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.
Code: Select all
; 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
- (call genlis) First thing done is to generate a list with all the valid moves for the white side. I could do this later, but it leaves registers in a state I can reuse in later operations instead of having to assign nominal values to H and L. The details of genlis will come in a separate chapter (it's complicated and it's really heavy stuff.
- Then I take a memory position that is not used for anything else and "oscillate" (0/1) its value in every turn. If value results 1 it's white's turns and the code for white side comes right underneath, and if it's 0, then it's black's turn and I conditionally jump to the black's code. The way to "oscillate" is to use a XOR instruction. The code optimization here is that instead of oscillating on a fixed value (XOR 1; 2 bytes), I use a register that has always the same value at this execution point (XOR H; 1 byte).
Code: Select all
prosta ld a, 2 ; 2 = upper screen.
call chaope ; open channel
Next topic: Board format and how it's printed.
Re: ChesSkelet: micro chess program - 363 Bytes
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 it's printed, my be a little boring to many.
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:
- Square centric ones, with a 64 register structure, each register being from 1/2 byte to many bytes, depending of the amount of information stored in each square register. Typically you can store the piece, its value, its color, if it has been moved, if the square is under attack from the opponent (and by whom), if it's defended (and by whom), the weigh of the square and others. You may put them all in or keep some of them for other type of structures.
- Piece centric ones: instead of a board we focus in keeping a register per piece wit all the relevant information from above, plus its current position.
- Bitboards: we have a 64 bit table (8x8) with position information on every type of piece. In a way, it's like splitting the single board depicted in the square centric method, having one board per characteristics to be represented, i.e. one board for white pawns position, one for balck pawns, one for attacked squares, etc, etc...This is a method of choice for fast processing, since the full 64 bitboard can be moved/modified in a a 64 bit processor, but
In my case I started experimenting several variants, all of them in the square centric area since, after some consideration, them all seemed less code consuming than piece centric or bitboards:
- My first obvious choice was a 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. An the most important, the Out Of Board detection issue (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 (byte 57 of the board)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 (bytes 56, 55, etc...). Detecting all these scenarios is not very simple unless you use a slightly different structure (see 12x10 and 16x10 below)
- I also tested 1/2 byte (nibble) per square, 32 bytes in size, saving 32 bytes compared to the on above, at least in theory. The problem of this implementation is that you need an intermediate routine to read/write on the board every time you need to access it, and it costs more than the savings. Also, it does not leave space for other info than a simple piece value and its color.
- 12x10 byte board: it solves the OOB detection issue, since it allows the use of the 0x88 algorithm. Basically, this code allows automatic OOB detection if you use a specific way to express the square number (https://www.chessprogramming.org/0x88). Basically, this type of board have unused squares. The code can identify them easily and therefore detect if the piece is OOB. The problem is that the 12x10 ranks and columns are not aligned with power of 2 as it is the 64 byte. This 8x8 made quite simple writing code to loop through the board, and we lose that advantage.
- 16x8 byte board: the definite format in my search. Imagine two boards, one beside the other. The one on the left is used to store the pieces and the other is not. This becomes a little bigger in memory, but with all the advantages: the empty half allows us for the 0x88 OOB detection as it provides unused squares. End of rank and end of board is aligned to power of two numbers, so detection of those ends in code is simpler, and finally it allows us to express the byte of the board in a very simple way:
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 with approach, the translation from alphabetic corrdinates 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.
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 only the lower half byte of the square to keep the piece value. The reason for this is that, for simplicity, I use this value for both valuation and 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, complex valuation is needed for long term evaluations where several pieces could be exchanged in several 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=1, N=2, B=3, R=4, Q=5, K=8. K=8 allows me for a simple mate detection. It's not perfect even for my implementation in some extreme cases (I challenge you to guess why), but I think I can fix it easily.
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.
Next topic: how the board is printed.
Re: ChesSkelet: micro chess program - 363 Bytes
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:
- Data is split in what I call the micro-pages (256 bytes). Changing from one page to another only requires to modify the higher half of the 16 bit register to address the position. Typically, that would be HL, so setting H (LD H, N) would cost 1 byte less that the full address (LD HL, NN). Exploiting this concept a little more, if data is placed properly in these pages, it can be addressed just by increasing/decreasing the H pointer by 1 (INC H/DEC H). This costs 1byte only. If, as in the case of Cheskelet, the code does not have many branches and data is accessed following the same sequence all the time, most data can be accessed following this approach (Note: if you look at the code you can find all page changes marked with "++" in the comments section of the line, so it's easy to find them.
- Most data is placed in positions where address calculation by the program is most simple and saves code. For instance, most common data is placed at the beginning of the micro pages. That means that the low part of the addressing register needs to be 0 (i.e. board if stored at 8000h). It's impossible to make this happen all the time, butI try to apply this as much as possible.
Code: Select all
; 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 ++
Let's look at the data now, page by page:
Code: Select all
; Memory page: 7700h ----------------------------------------------------------
org $7700
auxstr ; input string stored here
Code: Select all
; 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'
Code: Select all
; 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
Code: Select all
; Memory page: 8000h ----------------------------------------------------------
; board squares format: 000cpppp
; pppp (value) : pawn=1, knight=2, bishop=3, rook=4, queen=5, king=8
; 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
Code: Select all
; Memory page: 8100h ----------------------------------------------------------
org $8100
boaata ; attacked squares board
Code: Select all
; Memory page: 8200h ----------------------------------------------------------
org $8200
boaopo ; reversed attacked squares board
As you can see, all three boards are together, so that changing page to read them can be done at low cost, as explained above.
Code: Select all
; Memory page: 8300h ----------------------------------------------------------
; candidate move list at the very end of the program
org $8300
canlis equ $
That's is for today.
Re: ChesSkelet: micro chess program - 363 Bytes
It takes me a significant time to write this entries, so I need to know if I'm going in the right direction.
Thank you!
- arkannoyed
- Manic Miner
- Posts: 436
- Joined: Mon Feb 05, 2018 9:56 am
- Location: Northamptonshire
Re: ChesSkelet: micro chess program - 363 Bytes
It is fairly in-depth and some of the aspects of it complex to grasp initially, so you might need to slow down a little to allow it to be read a few times and anyone who has questions can post them.
I need to find the time to slowly read through it again, then I'm sure I'll either get it, or need to ask.
Very useful posts though, thankyou!
Re: ChesSkelet: micro chess program - 363 Bytes
Re: ChesSkelet: micro chess program - 363 Bytes
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).
Code: Select all
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.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.
Code: Select all
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
https://en.wikipedia.org/wiki/ZX_Spectr ... racter_set
Code: Select all
; 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
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.
Code: Select all
; 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
Code: Select all
if gramod>0 ; opt: print colored squares, end of the rank
inc c ; change C parity
endif
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.
Code: Select all
; 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 ; sets 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
Code: Select all
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
- arkannoyed
- Manic Miner
- Posts: 436
- Joined: Mon Feb 05, 2018 9:56 am
- Location: Northamptonshire
Re: ChesSkelet: micro chess program - 363 Bytes
Keep up the great development in the meantime.
Re: ChesSkelet: micro chess program - 363 Bytes
White and black moves are quite different since white move comes from the human input and does not involve any AI, which is the case for the black pieces.
The process has three blocks: input from keyboard, translation to coordinates and optionally see 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 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)).
Code: Select all
; 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
Take into account that what has been stores is the pressed key value, 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 array) contains the rank and the second 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 slides 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.
Code: Select all
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
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 is not used. That allows us to place the moves in the even positions of the array.
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).
Code: Select all
seamov ld hl, canlis ; canli pointer ++
ld a, (hl) ; number of candidates
inc hl ; skip to first candidate (+2 bytes)
inc hl ;
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
Next chapter: not sure yet. (1) a reflection on piece values, squares and others, needed for later code sections, or (2) how the computer moves. Most likely the first one.
Re: ChesSkelet: micro chess program - 363 Bytes
Re: ChesSkelet: micro chess program - 363 Bytes
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:
b7 b6 b5 b4 b3 b2 b1 b0
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. Any K > Q > R > B > N > P scheme would work.
This said, we can try something a little more precise:
• It’s convenient to have all pieces with different values. This way, we can differentiate them directly by its values. Therefore, B and N shall both not be 3. (chesSkelet uses N=2, B=3).
• The King needs to be easily spotted from the rest of the pieces (i.e. checkmate detection). This is easy, since its value is much bigger, so, for instance b6 or b5 are only used by the king (programming note: a BIT 6, X instruction would identify the king for us).
• Optionally, it may be good to be able to uniquely identify pawns by leaving bit 0 only for them (chesSkelet is not doing it, but I’m considering it).
• Finally, we’ll see that the move valuation system introduces more constraints than the plain piece values.
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.
This leaves my square scheme as follows (not exactly, but we´ll get there):
b7 b6 b5 b4 b3 b2 b1 b0
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
Move valuation
My piece value system is built around that fact that the computer is looking just 1 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 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:
• In board 1, the Queen would capture the Rook, not knowing that the queen would be captured as well. The target square attacked status would help us preventing that.
• In board 2, the Rook would capture the Knight, which is wrong, since we´ll be losing the other Rook. Knowing the origin square attacked status would prevent that problem too.
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 can 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.
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:
• In order to avoid specific coding for capturing the king, the best possible move is capturing the opponent’s king, even in the least favorable conditions, a queen with the king’s square being defended:
+K (target square content= King) -9 (Queen falling in an attacked square) = +K-9
• The second best move would be an attacked Queen capturing the opponent’s Queen. With the current scheme that is:
+9 (target square content= Queen) +9 (Queen leaving his attacked square) = +18
• Therefore, in order for the first move to be preferred over the second:
K-9 > 18 --> K>27 --> K=28 would work.
• Another situation to consider, the worst possible valuation, which would be the King moving to an empty and attacked square: 0 - 28 = -28.
This is important, because we need to deal with negative values. To avoid negative values, I will add this (minimum+1)=29 to any piece valuation, so that all results are positive. The range for piece valuation would be:
• Maximum, attacked queen capturing king: (+28 + 9) + 29 = 66
• Minimum, King to an empty attacked square: (0 - 29) + 29 = 1
With K= 28 (00011100), bit 4 would still identify the king uniquely.
In general, this approach could be good, but in my case, as we´ll see later I don’t want to have such big compensated valuation of 66. Ideally, I’d like to use 5 bits or 6 bits maximum.
After several iterations, I’ve come to a slightly different valuation that would help the compensated valuation in 6 bits with Q=8 and K= 25. All the requirements above would be fulfilled and the compensated valuation would range from 1to 60.
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).
b7 b6 b5 b4 b3 b2 b1 b0
0 R R R 0 C C C (R= rank bits, C= column bits)
In more advances 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:
• Pieces would naturally move forward, so the further the rank, the better. Ideally, this gives us a 0-7 weight (3 bits).
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.
• Also, center pieces activity should be favored. Here I tried different schemes, like looking up an array that would give us a column weight. Finally, I found another method, not so precise, but much cheaper in size. If I take the square value and do this:
ADD A, 2; AND 4
It’s not perfect, but it clears the ranks and gives higher weight to the center columns (and only takes 4 bytes!). This is the column weight produced:
c0 c1c2 c3 c4 c5 c6 c7
2 3 4 5 6 7 0 1
Aggregating rank 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 opening the C column (which becomes F for black. Remember that computer plays with black pieces) at least initially, 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:
b7 b6 b5 b4 b3 b2 b1 b0
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. I’m still experimenting with both.
All of the above is implemented in ChesSkelet with around 70 bytes.
- arkannoyed
- Manic Miner
- Posts: 436
- Joined: Mon Feb 05, 2018 9:56 am
- Location: Northamptonshire
Re: ChesSkelet: micro chess program - 363 Bytes
You're way ahead of me in terms of the size and efficiency. My early attempts yielded nothing near 70 bytes to achieve even some of what you've done. Early days though, and a long way to go to get anywhere near playability.
This is a really useful read, thanks!
Re: ChesSkelet: micro chess program - 354 Bytes
This last version contains some minor optimizations, and I moved some code used to protect the king from being uncovered and left under check to the full version. The reason for it is that I played vs. BootChess and ZX 1K Chess and it was not used, so I guess this is only for games with humans. By the way, I will post the games separately. It's really fun.
For loyal readers, don't worry. I'll finish the dissection, but no further coding...not now, please.
Re: ChesSkelet: micro chess program - 363 Bytes
It's a real pleasure to read these two amazing chess treads.
I especially look forward to the tournament games, between these chess giants under 1K.
Re: ChesSkelet: micro chess program - 363 Bytes
I found both games here:
Bootchess: http://copy.sh/v86/?profile=custom&fda. ... tchess.img
ZX81 1K Chess: http://www.zx81stuff.org.uk/zx81/tape/1KZXChess
Notes before the games:
- For ZX81 Chess,I played two games, as it has one version with the king opening and one with the queen opening.
- ChesSkelet had to play with black pieces in both cases, as none of the two have the option to switch side as ChessKelet.
- I could not find Toledo AtomChess online to have this game.
- All of them are pretty bad players, but this is not what we are aiming anyway.
- All games are replayable, as none of the games has a random element to its strategy.
- ZX81 1K Chess remains to me as the most complete one. It's much bigger, though. Except for the opening, it's playing is much stronger.
- 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.
ZX81 1K Chess, King opens (0,5) - ChessKelet (0,5)
1.E2-E3 E7-E6 A00 Van't Kruijs opening, rarely played
2.E3-E4 F8-B4 Out of any known opening, none of the games has the 2 squares forward pawn move.
3.E4-E5 B4-C5 After this, blacks become super conservative. If the space they want to go to is not free, they will wait.
4.F2-F3 C5-B4 Whites go on with their weird development
5.F3-F4 B4-C5 Blacks 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.
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, blacks check white king with the bishop.
3.C2-C3 B4-D6 Whites defend with its pawn (great defense, it shows advanced skills), and blacks have to retreat.
4.H2-H3 C7-C6 Whites start its weird development
5.C3-C4 D6-B4 Black insist with the check.
6.B1-C3 B4xC3 Now whites defends with the knight (again, good defense) and black capture knight.
7.B2xC3 D7-D6 Whites recapture.
8.A1-B1 B7-B6
9.A3-A3 B6-B5?? Clear blacks mistake. as we´ll see.
10.C4xB5 C6xB5
11.B1xB5 B8-C6 Whites get a 1 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 ckecks 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). 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 Blacks move, out of any 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 Blacks enter the wait mode...
11. E2-F4 E6-E5
12. E1-E2?? E5xF4 It seems like Whites do not notice the threatened Knight.
13. G3xF4 C6-B6 Whites take 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 ones this diagonal for the Bishop
18. G7-H8 C2-C5+ Whites capture the Rook. Blacks surprisingly check whites King
19. E2-D3 C5-E3 Whites make an illegal move and the King is captured.
Both sides play awful. BootChess ignores the check and loses on an illegal move.
And this was the tournament. Maybe I should play BootChess vs. 1K Chess to close the tournament, but given the previous games, I anticipate a 1K Chess victory.
- arkannoyed
- Manic Miner
- Posts: 436
- Joined: Mon Feb 05, 2018 9:56 am
- Location: Northamptonshire
Re: ChesSkelet: micro chess program - 354 Bytes
Very well done! I know exactly what you mean, the intensity of almost living inside the code for a length of time is totally exhausting eventually. You find yourself dreaming about it, and its completely distracting from everything going on around you.reeagbo wrote: ↑Sun May 19, 2019 11:14 am Today I posted the last ChesSkelet version v0.809. Finally it goes down to 354 bytes. And here it will stay for a long time I guess. After 11 months I'm exhausted with this project.
This last version contains some minor optimizations, and I moved some code used to protect the king from being uncovered and left under check to the full version. The reason for it is that I played vs. BootChess and ZX 1K Chess and it was not used, so I guess this is only for games with humans. By the way, I will post the games separately. It's really fun.
For loyal readers, don't worry. I'll finish the dissection, but no further coding...not now, please.
It may stay at 354 bytes for now, but I'm quite sure you'll get that feeling in the back of your mind that just grows and grows, telling you to have another look, as there must be a way to save another byte or two!
I revisited my proportional text scroller last week and managed to save a byte when I'd though it impossible once to reduce the size any further.
I needed a short break from Chess to refresh my mind.
Re: ChesSkelet: micro chess program - 363 Bytes
Let's now gut 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.
Code: Select all
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 ;
Code: Select all
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
Code: Select all
; 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
Code: Select all
; 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
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. At 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, as that move gets a good value (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).
Code: Select all
; 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
Code: Select all
; compensate + prioritize piece valuation(6B)
skiato add a, $20 ; A: 00pppppp, compensate=K+1, pih
;rlca ; removed v0.808 due to 6 bit piece val.
rlca ; leave space for square weight
rlca ; A: pppppp00, piece addition is 5 bits
ld b, a ; B: piece addition value
- first, we´ll add a number ($20=32d) that will prevent from having negative valuations, and therefore having to deal with sign flags, etc...
- We'll rotate the total valuation 2 bits to the left (multiply by 4), so that any good piece valuation is better than any square weight valuation. 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.
Code: Select all
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
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? We´ll, I tried them all (4 to 7) and 5 gave me the best opening moves. That's it.
Code: Select all
; ranks weight (ranks weight is 8..1, aiming for board's end)
evarnk sra l ; L: 0rrr0ccc, L=E
sra l ;
sra l ; L: 0000rrr0
if feamod>0
sra l ; L: 00000rrr
endif
sub l ; A: 0ppppxww (x=p+r)
add a, b ; total value: pieces + weight
In the last lines we first add rank and column weights and at last we add piece valuation and square weight together. So now we are ready to see if this is our best choice or not.
Code: Select all
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)
Next chapter: common code to update the board upon a move is decided.
Re: ChesSkelet: micro chess program - 363 Bytes
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.
Code: Select all
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
Code: Select all
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 ir 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
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 moved. 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 spacial 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.
Code: Select all
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
Code: Select all
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
This one was lighter. Next chapter: move generation (finally).
- arkannoyed
- Manic Miner
- Posts: 436
- Joined: Mon Feb 05, 2018 9:56 am
- Location: Northamptonshire
Re: ChesSkelet: micro chess program - 363 Bytes
Code: Select all
evarnk:
ld h,00h
add hl,hl
add hl,hl
add hl,hl
add hl,hl
sub h
add a,b
evaexi:
pop hl
etc....
- arkannoyed
- Manic Miner
- Posts: 436
- Joined: Mon Feb 05, 2018 9:56 am
- Location: Northamptonshire
Re: ChesSkelet: micro chess program - 363 Bytes
Code: Select all
ld h,10h
loop:
add hl,hl
jr nc,loop
sub h
add a,b
Re: ChesSkelet: micro chess program - 363 Bytes
Wow! Yes, I have not tried it, but this surely works. As you say, HL is recovered so we can play with it. Never thought of H being used for this.arkannoyed wrote: ↑Tue May 28, 2019 12:43 pm ...or a little cheeky -1 byte
Code: Select all
ld h,10h loop: add hl,hl jr nc,loop sub h add a,b
To be tested and included in the next version. Thank you!
- arkannoyed
- Manic Miner
- Posts: 436
- Joined: Mon Feb 05, 2018 9:56 am
- Location: Northamptonshire
Re: ChesSkelet: micro chess program - 363 Bytes
- arkannoyed
- Manic Miner
- Posts: 436
- Joined: Mon Feb 05, 2018 9:56 am
- Location: Northamptonshire
Re: ChesSkelet: micro chess program - 363 Bytes
Code: Select all
; compensate + prioritize piece valuation(6B)
skiato add a, $20 ; A: 00pppppp, compensate=K+1, pih
ld h,a
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
; ranks weight (ranks weight is 8..1, aiming for board's end)
evarnk add hl,hl
add a,h ;
ld h,00h
add hl,hl
add hl,hl
add hl,hl
sub h ; A: 0ppppxww (x=p+r)
Re: ChesSkelet: micro chess program - 363 Bytes
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:
Code: Select all
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 ;
- Byte1: 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.
Also, 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.
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 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, instead of the code having to derive it from knowing that we have a Pawn moving this way or the other.
- Byte2: The second byte is just a pointer to the move vectors 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.
Code: Select all
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 ;
Each byte in these blocks indicates how many bytes we need to displace 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:
- the Rook pointer in the first data block (E0h) will only point at the first group in this second block for straight moves. As the Rook has a its own radius 7 (0Eh with the delta=7) everything will be fine.
- the King will point at this same group as the Rook (E0h), but also at the second group (E5h) for diagonal moves. The difference with the Rook is that radius for the king is 1 (08h).
- the nice thing about this arrangements is that Pawn moves (only one direction) can be found too as part of the straight (E3h) and diagonal move (E7h) blocks too. So we do not need additional descriptors for them.