ChesSkelet: micro chess program - 363 Bytes

The place for codemasters or beginners to talk about programming any language for the Spectrum.
User avatar
arkannoyed
Manic Miner
Posts: 366
Joined: Mon Feb 05, 2018 9:56 am

Re: ChesSkelet: micro chess program - 363 Bytes

Post by arkannoyed » Mon Jun 03, 2019 8:01 am

reeagbo wrote:
Sun Jun 02, 2019 9:51 am
reeagbo wrote:
Fri May 31, 2019 9:59 pm
arkannoyed wrote:
Fri May 31, 2019 8: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!

:-)

That’s awesome!!!
0 x

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

Re: ChesSkelet: micro chess program - 363 Bytes

Post by arkannoyed » Mon Jun 03, 2019 8:02 am

reeagbo wrote:
Sun Jun 02, 2019 9: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!!
1 x

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

Re: ChesSkelet: micro chess program - 363 Bytes

Post by arkannoyed » Mon Jun 03, 2019 9:19 am

So Alex, what size is it down to now for the super small version?
0 x

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

Re: ChesSkelet: micro chess program - 363 Bytes

Post by reeagbo » Mon Jun 03, 2019 1:48 pm

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

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

Re: ChesSkelet: micro chess program - 363 Bytes

Post by arkannoyed » Mon Jun 03, 2019 2:49 pm

Intense!! :o
0 x

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

Re: ChesSkelet: micro chess program - 363 Bytes

Post by reeagbo » Mon Jun 03, 2019 3:09 pm

arkannoyed wrote:
Mon Jun 03, 2019 2:49 pm
Intense!! :o
There is no other way, I guess. :D
1 x

User avatar
Pegaz
Manic Miner
Posts: 248
Joined: Mon Nov 13, 2017 1:44 pm

Re: ChesSkelet: micro chess program - 363 Bytes

Post by Pegaz » Mon Jun 03, 2019 8:00 pm

I cant follow this, but I can admire you and arkannoyed. :)
2 x

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

Re: ChesSkelet: micro chess program - 363 Bytes

Post by arkannoyed » Tue Jun 04, 2019 8: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.
1 x

User avatar
Morkin
Manic Miner
Posts: 638
Joined: Mon Nov 13, 2017 8:50 am
Location: Bristol, UK

Re: ChesSkelet: micro chess program - 363 Bytes

Post by Morkin » Tue Jun 04, 2019 12:34 pm

arkannoyed wrote:
Tue Jun 04, 2019 8: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-)
2 x

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

Re: ChesSkelet: micro chess program - 363 Bytes

Post by arkannoyed » Tue Jun 04, 2019 12:43 pm

Morkin wrote:
Tue Jun 04, 2019 12:34 pm
arkannoyed wrote:
Tue Jun 04, 2019 8: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:
1 x

Post Reply