ChesSkelet: micro chess program - 363 Bytes

The place for codemasters or beginners to talk about programming any language for the Spectrum.
reeagbo
Berk
Posts: 38
Joined: Mon Apr 29, 2019 8:11 am

Re: ChesSkelet: micro chess program - 363 Bytes

Post by reeagbo » Wed May 01, 2019 12:50 pm

ChesSkelet code - Chapter 1 - General program structure

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:

Image

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.
4 x

reeagbo
Berk
Posts: 38
Joined: Mon Apr 29, 2019 8:11 am

Re: ChesSkelet: micro chess program - 363 Bytes

Post by reeagbo » Sat May 04, 2019 11:05 am

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:

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
1) debmod, gramod and feamod are not really part 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 board where I can set whatever game position I like for testing. 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 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
Initial part of the code:
  • (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).
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.

Code: Select all

prosta	ld a, 2          	; 2 = upper screen.
       		call chaope		; open channel
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.

Next topic: Board format and how it's printed.
3 x

reeagbo
Berk
Posts: 38
Joined: Mon Apr 29, 2019 8:11 am

Re: ChesSkelet: micro chess program - 363 Bytes

Post by reeagbo » Sun May 05, 2019 11:06 am

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 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
And the 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, 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.
What am I storing in each byte (or square)? A square byte looks like this: 000cpppp. "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 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.
4 x

reeagbo
Berk
Posts: 38
Joined: Mon Apr 29, 2019 8:11 am

Re: ChesSkelet: micro chess program - 363 Bytes

Post by reeagbo » Tue May 07, 2019 7:22 am

Chapter 3: 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:
  • 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.
One addressing example:

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 ++
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 my 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 baord (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:

Code: Select all

; 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.

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'
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.

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
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.

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
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.

Code: Select all

; 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 totally mirrors the game board, but in a different page.

Code: Select all

; Memory page: 8200h ----------------------------------------------------------
org $8200
boaopo				; reversed attacked squares board
This page is a little trickier. The game board avobe (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 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 $
Last, but not least, the list of candidate moves. First byte stores the number of items in the list. Byte 2 is unused. After that, every move occupies 2 bytes, one with the origin square and one with the target square. I chose to place is at the end since its size could exceed the size of a page (http://www.talkchess.com/forum3/viewtop ... 26&t=39332). I do not think that would happen with ChessKelet, but just in case.

That's is for today.
2 x

reeagbo
Berk
Posts: 38
Joined: Mon Apr 29, 2019 8:11 am

Re: ChesSkelet: micro chess program - 363 Bytes

Post by reeagbo » Tue May 07, 2019 7:33 am

Guys, it would be nice to have some sort of feedback, if you have a minute? Is this meaningful at all? Is it understandable? Going too fast?
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!
0 x

User avatar
arkannoyed
Manic Miner
Posts: 360
Joined: Mon Feb 05, 2018 9:56 am

Re: ChesSkelet: micro chess program - 363 Bytes

Post by arkannoyed » Tue May 07, 2019 8:07 am

Great so far Alex!

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!
1 x

User avatar
utz
Dizzy
Posts: 53
Joined: Wed Nov 15, 2017 9:04 am
Contact:

Re: ChesSkelet: micro chess program - 363 Bytes

Post by utz » Tue May 07, 2019 8:22 am

Excellent write-up, I'm thoroughly enjoying this. Gears creaking quite a bit in me ol' brain, but so far I could mostly follow your explanations.
1 x

reeagbo
Berk
Posts: 38
Joined: Mon Apr 29, 2019 8:11 am

Re: ChesSkelet: micro chess program - 363 Bytes

Post by reeagbo » Thu May 09, 2019 4:59 pm

Chapter 3: 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).

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- Squares and pieces: from here we have a loop that runs through the whole board, including the famous 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.

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
2.2 - Printing the piece itself: the square contains both the piece value and the color (00c0pppp, 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 A need A for the operations so I can't do both together. D is pointing at the beginning 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. This does not look like a random choice, so I take that bit5 to decide the size. I used to have bit 4 for the color, but this is a recent change and I'm saving a byte in this routine (small chesSkelet is 365 bytes now!).
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
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.

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
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.

Code: Select all

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.

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
Finally, a CR is added so that the input is typed under the rank letters.

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
In the next torture session we´ll look at how we read white's moves.
3 x

User avatar
arkannoyed
Manic Miner
Posts: 360
Joined: Mon Feb 05, 2018 9:56 am

Re: ChesSkelet: micro chess program - 363 Bytes

Post by arkannoyed » Fri May 10, 2019 7:31 am

Great tutorial Alex, even if it is slightly brain-frazzling. It is giving me a few very useful pointers for my development.

Keep up the great development in the meantime.
1 x

reeagbo
Berk
Posts: 38
Joined: Mon Apr 29, 2019 8:11 am

Re: ChesSkelet: micro chess program - 363 Bytes

Post by reeagbo » Mon May 13, 2019 6:56 pm

Chapter 4: White moves.

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
	
2 - Translating to board coordinates
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
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 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
As you can see there is not much science here.

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.
1 x

Post Reply