ChesSkelet: micro chess program - 363 Bytes

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

Re: ChesSkelet: micro chess program - 363 Bytes

Post by reeagbo »

I´m posting the games I played with BootChess and ZX 1K Chess. Notation will be coordinate notation (https://en.wikipedia.org/wiki/Chess_notation), since it can help someone crazy enough to replay the games.

I found both games here:
Bootchess: http://copy.sh/v86/?profile=custom&fda. ... 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.
Some conclusions:
  • 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.
Games:

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.
User avatar
arkannoyed
Manic Miner
Posts: 435
Joined: Mon Feb 05, 2018 9:56 am
Location: Northamptonshire

Re: ChesSkelet: micro chess program - 354 Bytes

Post by arkannoyed »

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

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. :)
reeagbo
Dizzy
Posts: 61
Joined: Mon Apr 29, 2019 9:11 am

Re: ChesSkelet: micro chess program - 363 Bytes

Post by reeagbo »

Chapter 5: Black (computer) moves

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			;

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

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

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

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
As explained in the previous chapter, target piece always counts for piece valuation.
After this, we point HL at the attacked squares status board and see if the origin square is attacked by black pieces (human in this case, remember that at this point the game board is reversed). If not attacked, there is nothing to do and we jump to the next block below.

I have included this optional code that is only added in the full version. I guess this is the right place to discuss it. ChesSkelet has an important design issue. 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  
Now we run a similar check on the target square. Basically, if the target square is attacked, we'll discount the origin piece from that valuation. What's the logic of this? Well, if the computer moves its piece to an attacked square, it takes the risk to lose it. As we do not know anything else about the environment (if the target square is defended by another computer piece, which human piece is attacking that square, etc...), this is the most cautious thing to do. Basically, it will give a bad valuation to this type of moves.

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
Last thing in the move valuation (either capture or escape move). We need some adjustments:
  • 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.
Let's move on now to the target square weight. We´ll calculate the rank and the column weight separately and add them.

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
This first part looks at the column weight. Before finding this method, I was heavier methods like having an array linking columns and its weight or variations of this. Now it's much simpler Depending on the ChesSkelet version we have two settings. Take into account that the small version only move the pawns one rank forward at first move, so that changes how it behaves, and also, the small version settings uses 1 byte less. :-)
What does it do? By adding 2, we are shifting the column values in a way that from column 2 to 5, bit 3 becomes 1. This allows us to decide column valuation using that mask with bit 3 on. Why AND 5, then? 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
Now we´ll evaluate the rank weight. The logic is simpler but it has a couple of inconveniences: rank sits on the high nibble of the square weight, so first thing is to shift if to the low nibble. For the small version I'm not doing the full shift, as it does not really have an impact for most moves (yet, I'm cheating). Yes, and I'm shifting L register directly as all other registers are busy at this point.

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)
This is the end of the loop iteration. We´ll recover the previously saved registers. We´ll compare the maximum saved valuation (C) with the current square valuation. And at the loop exit we´ll recover the other registers and control the loop repetition with B. B is decreased twice (DEC B; DJNZ) since each candidate in the list occupies two bytes.

Next chapter: common code to update the board upon a move is decided.
reeagbo
Dizzy
Posts: 61
Joined: Mon Apr 29, 2019 9:11 am

Re: ChesSkelet: micro chess program - 363 Bytes

Post by reeagbo »

Chapter 6: making the move

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

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

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

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

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

If you have followed this, you´ll notice that I´m leaving 3 bytes in the stack that I'm not extracting every time the board is reversed. Ok, this may destroy the code after several hundred 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
I never thought of including castling due to its high implementation cost, but I agree that this is a critical move to keep the game as something close to real chess. What does it do? We take the moving piece, the origin square and the target square. The move "distance" is -2 for the King castling to the left and +2 for the King right. We calculate that distance and add to the moving piece, and the value we get is the value that needs to be matched. If the condition is fulfilled we´ll erase the move the proper Rook in the board. The King is moved by the regular code.

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

This one was lighter. Next chapter: move generation (finally).
User avatar
arkannoyed
Manic Miner
Posts: 435
Joined: Mon Feb 05, 2018 9:56 am
Location: Northamptonshire

Re: ChesSkelet: micro chess program - 363 Bytes

Post by arkannoyed »

Would it be possible to save either 2 bytes or get rid of the option [feamod>0] (if I'm interpreting it right?) thus;

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....
I may however be missing something, but as HL is restored straight after, so whatever happens to its contents unimportant?
User avatar
arkannoyed
Manic Miner
Posts: 435
Joined: Mon Feb 05, 2018 9:56 am
Location: Northamptonshire

Re: ChesSkelet: micro chess program - 363 Bytes

Post by arkannoyed »

...or a little cheeky -1 byte

Code: Select all

	ld h,10h
loop:
	add hl,hl
	jr nc,loop
	
	sub h
	add a,b
reeagbo
Dizzy
Posts: 61
Joined: Mon Apr 29, 2019 9:11 am

Re: ChesSkelet: micro chess program - 363 Bytes

Post by reeagbo »

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

To be tested and included in the next version. Thank you!
User avatar
arkannoyed
Manic Miner
Posts: 435
Joined: Mon Feb 05, 2018 9:56 am
Location: Northamptonshire

Re: ChesSkelet: micro chess program - 363 Bytes

Post by arkannoyed »

Great, I thought it looked like it should fit ok. Your code is generally pretty optimised though, so it’s hard to find anything that can be improved in size.
User avatar
arkannoyed
Manic Miner
Posts: 435
Joined: Mon Feb 05, 2018 9:56 am
Location: Northamptonshire

Re: ChesSkelet: micro chess program - 363 Bytes

Post by arkannoyed »

Just another thought, expanding upon the previous improvement in size. Would this work by extending the use of HL a bit further?

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)

Saves another few bytes (I think?!) :?
reeagbo
Dizzy
Posts: 61
Joined: Mon Apr 29, 2019 9:11 am

Re: ChesSkelet: micro chess program - 363 Bytes

Post by reeagbo »

Chapter 6: Move list generation

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

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

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	;
The data in this first block is strategically placed in memory. The info corresponding to each piece sits in the piece value multiplied by 4. Take into account that we are only creating the move list for white pieces (i.e. white bishop value is 24h, 24h x 4= 90h). This allows me to address quite immediately the type of moves every piece can make. What do these two bytes mean?
  • 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	;
The second data block contains generic move descriptions, not specific to a piece, therefore a move descriptor can be used by several piece types. There are three groups: first 4 bytes describe the straight moves, second 4 bytes describe diagonal moves, and the last 8 bytes describe the Knight moves.

Each byte in these blocks indicates how many bytes we need to 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.
Now that now the used of this static data, we´ll see in the very last chapter how the code uses it and how the potential move list is built.
User avatar
arkannoyed
Manic Miner
Posts: 435
Joined: Mon Feb 05, 2018 9:56 am
Location: Northamptonshire

Re: ChesSkelet: micro chess program - 363 Bytes

Post by arkannoyed »

Very good. I'm along the same lines with moves data, but mine is currently slightly bigger data. Good system that works pretty well though.
reeagbo
Dizzy
Posts: 61
Joined: Mon Apr 29, 2019 9:11 am

Re: ChesSkelet: micro chess program - 363 Bytes

Post by reeagbo »

arkannoyed wrote: Fri May 31, 2019 9:10 am Just another thought, expanding upon the previous improvement in size. Would this work by extending the use of HL a bit further?

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)

Saves another few bytes (I think?!) :?
Let me look into it. I'll let you know. Any help is more than welcome. :-)
reeagbo
Dizzy
Posts: 61
Joined: Mon Apr 29, 2019 9:11 am

Re: ChesSkelet: micro chess program - 363 Bytes

Post by reeagbo »

reeagbo wrote: Fri May 31, 2019 10:59 pm
arkannoyed wrote: Fri May 31, 2019 9:10 am Just another thought, expanding upon the previous improvement in size. Would this work by extending the use of HL a bit further?

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)

Saves another few bytes (I think?!) :?
Let me look into it. I'll let you know. Any help is more than welcome. :-)
I took your idea and with a little tuning it seems to make things even smaller:

Code: Select all

	; compensate + prioritize piece valuation(6B)
skiato	ld h, $20		; prepare H for later rotation and use for A
	add a, h		; A: 00pppppp, compensate=K+1, pih				      					       
	rlca			; leave space for square weight
	rlca			; A: pppppp00, piece addition is 5 bits
	ld b, a			; B: piece addition value
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		; HL: 00100000 0rrr0ccc (before)
	add hl, hl		; 
	add hl, hl		; HL: 000000rr r0ccc000 (after)
	sub h			; A:  00000cww (w=r+c)
	add a, b		; total value: pieces + weight
Many thanks! This is from now on the arkannoyed patch! :-)
reeagbo
Dizzy
Posts: 61
Joined: Mon Apr 29, 2019 9:11 am

Re: ChesSkelet: micro chess program - 363 Bytes

Post by reeagbo »

Maybe we can still cross the 350 bytes line! :P
reeagbo
Dizzy
Posts: 61
Joined: Mon Apr 29, 2019 9:11 am

Re: ChesSkelet: micro chess program - 363 Bytes

Post by reeagbo »

Maybe we can still cross the 350 bytes line! :P

One general question. I´m sure some of the folks in the forum can help: how do I get ChesSkelet included in ZXDB?
User avatar
arkannoyed
Manic Miner
Posts: 435
Joined: Mon Feb 05, 2018 9:56 am
Location: Northamptonshire

Re: ChesSkelet: micro chess program - 363 Bytes

Post by arkannoyed »

reeagbo wrote: Sun Jun 02, 2019 10:51 am
reeagbo wrote: Fri May 31, 2019 10:59 pm Let me look into it. I'll let you know. Any help is more than welcome. :-)
I took your idea and with a little tuning it seems to make things even smaller:

Code: Select all

	; compensate + prioritize piece valuation(6B)
skiato	ld h, $20		; prepare H for later rotation and use for A
	add a, h		; A: 00pppppp, compensate=K+1, pih				      					       
	rlca			; leave space for square weight
	rlca			; A: pppppp00, piece addition is 5 bits
	ld b, a			; B: piece addition value
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		; HL: 00100000 0rrr0ccc (before)
	add hl, hl		; 
	add hl, hl		; HL: 000000rr r0ccc000 (after)
	sub h			; A:  00000cww (w=r+c)
	add a, b		; total value: pieces + weight
Many thanks! This is from now on the arkannoyed patch!

:-)

That’s awesome!!!
User avatar
arkannoyed
Manic Miner
Posts: 435
Joined: Mon Feb 05, 2018 9:56 am
Location: Northamptonshire

Re: ChesSkelet: micro chess program - 363 Bytes

Post by arkannoyed »

reeagbo wrote: Sun Jun 02, 2019 10:55 am Maybe we can still cross the 350 bytes line! :P

One general question. I´m sure some of the folks in the forum can help: how do I get ChesSkelet included in ZXDB?
Twist R-tapes arm, he’ll get you in!!
User avatar
arkannoyed
Manic Miner
Posts: 435
Joined: Mon Feb 05, 2018 9:56 am
Location: Northamptonshire

Re: ChesSkelet: micro chess program - 363 Bytes

Post by arkannoyed »

So Alex, what size is it down to now for the super small version?
reeagbo
Dizzy
Posts: 61
Joined: Mon Apr 29, 2019 9:11 am

Re: ChesSkelet: micro chess program - 363 Bytes

Post by reeagbo »

Chapter 7: Move list generation (II)

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

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

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

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

Code: Select all

genlis
bacata	; backup attack board in reverse order, used in evaluation (13B)
	ld l, $FF		; (H)L = $80FF (boaata-1), H always $80 
	ld de, boaopo + $78	; DE: same thing, 1B passed end of board
bacloo	inc hl			; HL: increase 16b counter to hop to next page
	dec e			; E:  decrease 8b counter to hit Z flag
	ld a, (hl)		; load attack status
	ld (hl), 0		; clear attack status, no alternative!
	ld (de), a		; backup attack status
	jr nz, bacloo		; loop down to square $00
				; exit values: DE=$8200, HL=$8177
Before looking into this section, I need to explain how the reverse squares board works. I had to do it in two steps: there is a attacked squares board, but this board is not reversed simultaneously with the game board. Not only that. It has to be reversed so that it can be used during move evaluation, but also it has to be reset so that I can generate a new one for the next side moving. It would make sense to do it sequentially, but it would take more code, so we actually have two attacked square boards: the one which is generated and the reverse one used for move evaluation.

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

Code: Select all

	; prepare environment (4B)
	inc d			; D= $83= canlih
	xor a			; reset
	ld (de), a		; cantot= 0
	ld b, l			; B= L = 77, SQUARE COUNT
We are now in the preparations area. DE will point at the mini page where the candidate moves will be stored and the number of them is set to 0. It's the first byte in the page. We also load B with the last square in the board (77H = 01110111b). The main loop (outer loop) will use B and will countdown through the board.

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

Code: Select all

	; read piece from board (4B)
squloo	ld h, boasth		; H: board base ++
	ld l, b			; point at current loop square
	ld a, (hl)		; read piece from board
	
	; get move type and pointer to move list (6B)
squgon	dec h			; H(L)= movlih, moves vector base ++
	add a, a		; x4, each piece vector is 4B long
	add a, a		;	
	ld l, a			; (H)L points at the move vector now
We are entering the main loop. We will see that the register usage is pretty tight. This is why I'm pushing registers all the time to free them for use in inner loops.

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

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

I know this is becoming a little tricky...

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

Code: Select all

	ld d, 2			; 2 submoves per piece
subloo		; byte 1 - move type (5B)
		ld a, (hl)		; move type loaded
		or a			; =cp 0, 2nd move type not used case
					; black/empty: move type=0 leads here
		jr z, squexi		; ---v exit: square is done
		ld e, a			; E: MOVE TYPE (B,C,D used here)
	
		; byte 2 - movlis delta (3B)
		inc hl			; next piece sub-entry
		push hl			; Save HL for 2nd loop	
		ld l, (hl)		; pointer to move delta
For each piece in each square we have a two iterations loop (middle loop), as each piece may have one or two types of moves. Rooks, Bishops, Pawns, and Knight have one type of move (meaning 1 direction). King, Queen and Pawns have two (they combine straight and diagonal). In the first place, the exit condition: if the move type is 0 it means that we are done with the piece, either with one or two types of moves. Also, code for empty sqaures ends up here, so the same code is used for both exit conditions.

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

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

Code: Select all

bisgen	defb	$0E, $E5	; bishop
0Eh means: 0xh non special move, xEh is the radius, meaning it can reach 7 moves in each direction (remember I add 7 to the radius for code economy, that's why we have 0Eh=14d).
E5h is the pointer to the move vectors, the deltas applied to calculate moves in each direction. Don't abandon yet, we´ll see how it goes in a minute.

Code: Select all

vecloo			; vector read (8B)
			ld c, b		; TARGET SQUARE init
			ld a, (hl)	; vector delta
			or a		; =cp 0
			jr z, vecexi	; ---v exit: vectors end with 0, next sq.
			push hl		; save current delta
			push de		; save move type + radius
					; E: variable radius within loop
			ld d, a		; D: store delta within loop
Now we take the current square (remember, squares are covered by the big loop) and add the delta that goes to the next square the piece can move to. The exit condition here is again having a delta=0. We push all DE and HL to free them and we store the new square calculated in D. We are going to use it on every iteration to calculate the new target.

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

Code: Select all

org $7FE5
diavec	defb   	$0F, $11	; +5, diagonal vectors
	defb  	$EF, $F1	; +7, diagonal pawn
From A1 it can only go in the B2 direction. This is from 70h to 61h. If you see 70h + F1h= (1)61h. Bit 9 is lost so we keep 61h. The other three vectors will give us out of the board squares.

Code: Select all

celloo				; prepare x88 check (7B)
				ld a, d		; delta loaded
				add a, c	; current target (sq. + delta)
				ld c, a		; current target
				and $88		; 0x88, famous OOB trick
				jr nz, vecnex	; ---v exit: OOB, next vector
			
				; read target square (3B)
				inc h		; H(L)= $80 = boasth ++
				ld l, c		; point at target square			
				ld a, (hl)	; read target square content

				; mark attacked ### str. pawn marked attacked
					inc h		; H(L)= $81 = boaath ++
					ld (hl), h	; mark attacked ($81)
					dec h		; H(L)= $80 = boasth ++
					
				dec h		; H(L)= $79= movlih ++
Here we start the inner loop, that will visit all the squares a piece can move to in a particular direction. There is no specific exit condition for this loop, as it can be exited fir different reasons that we´ll explore later.

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

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

Code: Select all

				dec h		; H(L)= $79= movlih ++
				; target is white (4B)
				bit 5, a	; is it white?, pih
				jr nz, vecnex	; ---v exit: WHITE b4=1, next vector

				; target not white (3B)
				or a		; =cp 0, is it empty?, pih
				jr z, taremp	; if not 0, it's black: legal, no go on
					
tarbla				; target is black (7B)
				bit 5, e	; special move: pawn straight check
				jr nz, vecnex	; ---v exit: no straight capture, next vector
				ld e, a		; make radius=0 (=<8 in code, canonical: ld e, 0)
				call legadd	;
				
taremp				; target is empty (14B)
				bit 4, e	; special move: pawn on capture check
				jr nz, vecnex	; ---v exit: no diagonal without capture, next vector	  
				dec e		; decrease radius
legadj
				bit 3, e	; if radius < 8 (Cb3=0), radius limit
				jr nz, celloo	; ---^ cell loop

This is an interesting part. Depending on the target square content, we´ll do different things. Following the sequence:
  • if the target is white we cannot move there and we cannot move in this direction anymore, so we skip to the next vector, to test other directions.
  • if the target is black, we stop moving in that direction (by making radius <8) and we add the move to the legal move list. There is a special case: if it's a pawn moving straight, as it cannot capture we skip adding the move and we go to the next vector.
  • if the target is empty, we will add the move to the legal move list, and we´ll decrease the radius by one (E register), so that we can go on testing squares in this direction. There is also a special case: if it's a pawn moving diagonal we´ll skip addition since it cannot move without capturing.
Last thing we do is to check radius: if it's still positive (bigger that 7 in the code) we can week moving in that direction, so we go back to "cello" tag.

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

Code: Select all

		
vecnex			; next vector preparation (5B)
			pop de		; DE: recover move type + radius
			pop hl		; HL: recover current vector
			inc hl		; HL: next vector
			jr vecloo	; ---^ vector loop
This is the boring part of the code where not much happens. We recover old values from the stack that we need to use at this point. Theoretically, this inner loop is repeated forever until one of the many exit conditions occurs.

Code: Select all

vecexi	; next square preparation (5B)
	pop hl			; HL: recover pointer to sub-move list
	inc hl			; HL: next byte, point at 2nd sub-move
	dec d			; 2 sub-move iterations loop control
	jr nz, subloo		; if not 2nd iteration, repeat loop
	; end of loop (2B)		
squexi	djnz squloo		; ---^ squares loop
	ret
We keep on recovering data from the stack as we leave the inner loop.

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

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

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

Code: Select all

	kincas	ld l, a		; save A (can't use push AF, flags lost)
		add a, b	; A: 0rrr0xxx + 000ppppp (uncolored white p.)
		cp $AA		; king($36) at E1($74)= $AA, pih
		ld a, l		; recover A
		jr nz, kinend	; if no match, skip adding legal move
	
		ld c, $72	; E1-C1 move, rook's move missing
		call legadd	; add king's move
		ld c, $76	; E1-G1 move, rook's move missing
		call legadd	; add king's move and go on with king's moves
	kinend
The first one is covering castling. It's a big cheat, but I combine the current square and the piece in the square. If it is a white king (36h) in E1 (74h) we´ll add the two possible king moves for castling to the legal move list (E1-C1, E1-G1). We already was the Rook's part, which is executed only if one of these King's moves is made.

Code: Select all

		genpw2	add a, b	; piece square + move type
			and %11111000	; masked with relevant bits
			cp $88		; $28(str.pawn)+$60(rnk 6) ### univocal
			jr nz, skppw2	; if not, skip
			inc e		; increase radius: 1 -> 2
		skppw2
For the pawn moving 2 squares forward. Same process I typically use: in this case I will combine the rank (it has to be in rank 6, therefore 60h) and the move type (28h, for straight pawn). If it's a match, I just increase the radius for this straight move to 2. Simple, isn't it?

Still alive? Anybody there? As I said this part is pretty heavy.

One general request, if you have the time. I'm planning to put all the chapters together and add them to the website, so if you think any of the sections or paragraphs is particularly cryptic, let me know and I will re-write it.

Thanks very much if you managed to read it all!
User avatar
arkannoyed
Manic Miner
Posts: 435
Joined: Mon Feb 05, 2018 9:56 am
Location: Northamptonshire

Re: ChesSkelet: micro chess program - 363 Bytes

Post by arkannoyed »

Intense!! :o
reeagbo
Dizzy
Posts: 61
Joined: Mon Apr 29, 2019 9:11 am

Re: ChesSkelet: micro chess program - 363 Bytes

Post by reeagbo »

arkannoyed wrote: Mon Jun 03, 2019 3:49 pmIntense!! :o
There is no other way, I guess. :D
User avatar
Pegaz
Dynamite Dan
Posts: 1209
Joined: Mon Nov 13, 2017 1:44 pm

Re: ChesSkelet: micro chess program - 363 Bytes

Post by Pegaz »

I cant follow this, but I can admire you and arkannoyed. :)
User avatar
arkannoyed
Manic Miner
Posts: 435
Joined: Mon Feb 05, 2018 9:56 am
Location: Northamptonshire

Re: ChesSkelet: micro chess program - 363 Bytes

Post by arkannoyed »

It may seem incredibly difficult, but its nothing more than a case of carefully going through parts of any routine and working out the mechanics of whatevers going on. Then armed with that info its possible to find more efficient ways of achieving the same goal.
User avatar
Morkin
Bugaboo
Posts: 3251
Joined: Mon Nov 13, 2017 8:50 am
Location: Bristol, UK

Re: ChesSkelet: micro chess program - 363 Bytes

Post by Morkin »

arkannoyed wrote: Tue Jun 04, 2019 9:35 am It may seem incredibly difficult, but its nothing more than a case of carefully going through parts of any routine and working out the mechanics of whatevers going on. Then armed with that info its possible to find more efficient ways of achieving the same goal
...you missed out the "with a maniacal obsession" part... :lol:

Just joking obviously, it'll be great to see the eventual collision between graphics and code. 8-)
My Speccy site: thirdharmoniser.com
User avatar
arkannoyed
Manic Miner
Posts: 435
Joined: Mon Feb 05, 2018 9:56 am
Location: Northamptonshire

Re: ChesSkelet: micro chess program - 363 Bytes

Post by arkannoyed »

Morkin wrote: Tue Jun 04, 2019 1:34 pm
arkannoyed wrote: Tue Jun 04, 2019 9:35 am It may seem incredibly difficult, but its nothing more than a case of carefully going through parts of any routine and working out the mechanics of whatevers going on. Then armed with that info its possible to find more efficient ways of achieving the same goal
...you missed out the "with a maniacal obsession" part... :lol:

Just joking obviously, it'll be great to see the eventual collision between graphics and code. 8-)
Well, yeah, that too. Best avoided, but I know only too well that if I obsess over saving a byte somewhere, when the code just looks 'wrong' it can become a bowel shatteringly intense experience :lol:
Post Reply