Alternate Chess Kernel Solved

Posted by , 25 December 2005 · 201 views

attachment

In my last attempt at a chess kernel with playfield graphics, I came up with a technique that would only work with about 27K of code. Since then I've made some advances that make a 4K kernel possible. One trick I developed was a new 32 pixel asymmetrical playfield configuration that takes four loads and six stores. (I believe it's new at least.)

The playfield remains transposed rather than reflected, but unlike before I load the same byte for the right PF0 and PF2 data. The high nybble goes to PF0 and the low nybble goes to PF2. The byte is stored to PF0 first, is AND'ed with #$0F and then stored to PF2. Setting X to #$0F and using the SAX instruction, which stores the value A & X, saves a couple cycles. I already had set X to white for my color changes, and by a fortunate coincidence white is #$0F. In additon, this value can be used to clear PF0 on the left side. This playfield configuration uses a few more cycles than the simple 32 pixel reflection, but the timing is more flexible and frees time to do all the color changes.

; X = #$0F (White) 
; Y = #$00 (Black)
;dynamic_code; starts on cycle 3 
	  pla			 ; load PF2 left side			
	  sta PF2-15,X	; left side. Use index to spend a cycle
	  pla			 ; load PF0 and PF2 for right side				
	  stx PF0,Y	   ; clears PF0 on left side
	  sta temp-15,X   ; use indexed addressing to spend an extra cycle
	  stx COLUPF	  ; color piece 1
	  sta PF0		 ; right side
	  stx COLUPF	  ; color piece 2
	  lda pf1_right   ; load PF1 right side. The operand is inc'd below.
	  stx COLUPF	  ; color piece 3
	  sta PF1		 ; right side  
	  stx COLUPF	  ; color piece 4
	  stx COLUPF+64,Y ; color piece 5; COLUPF+64 mirrors COLUPF
	  lda #$00		; <-- temp is the address of the operand here.		  
	  sty COLUPF+64-15,X; color piece 6   
	  sax PF2		 ; right side
	  stx COLUPF	  ; color piece 7
	  stx COLUPF+64,Y ; color piece 8
	  pla			 ; load PF1 left side	  
	  sta PF1		 ; left side   
	  inc pf1_right_addr		
	  bne dynamic_code; last byte for pf1_right must be $ff	   
	  brk

The RAM can be allocated as follows:
32 bytes to store the board position (1 nybble for each square)
42 bytes of self-modifying code (includes temp variable)
52 bytes for temporary storage of playfield data
2 bytes for everything else

Attached Thumbnails

Attached Files

chess_Jan09.bin (4K)
downloads: 96
chess_17Jun06.bin (4K)
downloads: 99

mos6507
Dec 26 2005 12:51 PM

I think it's a real challenge to represent the chess pieces well enough that you don't get confused distinguishing them from eachother. In your set, the king and queen are almost indistinguishable, for instance.

Here is my take: (top to bottom, rook, knight, bishop, pawn, king, queen).

Is there any way to use an extra pair of scanlines on these pieces to help give them some added height?

Report

Zach
Dec 26 2005 1:54 PM

mos6507, on Mon Dec 26, 2005 1:51 PM, said:

Is there any way to use an extra pair of scanlines on these pieces to help give them some added height?

Thanks for the contribution. I forgot to mention that the pieces can be drawn with full scanline resolution, so you can design pieces with more detail. The dimensions are 3x12. The data for the chessmen graphics is stored in RAM so it can be retrieved quickly, and the 128 bytes limit their height.

EDIT: The new dimensions are 3x13.

Report

mos6507
Dec 26 2005 4:57 PM

Zach, on Mon Dec 26, 2005 12:54 PM, said:

In that case, here are a couple other approaches.

This one may look a little too busy:

This one below might be the best compromise.

Report

Zach
Dec 27 2005 12:54 AM

Nice job. I like the knight, rook, and king. I've posted a mockup with them, plus some new designs for the bishop, pawn, and queen.

Report

MayDay
Jan 7 2006 9:15 AM

One thing serious chess players will probably want is a similarity between all the pieces on the board and proper heights in relation to each other. Not only that, but they should be able to distinguish any one piece from another without seeing the rest of the pieces. With that in mind, here is my take on the Jacques set with the exception of the knight which I think looks much better in mos's version than the Jacques version does.

Posted Image

The rook and queen are not completely distinguishable when viewed seperately, but put together are quite obvious. For help in recreating them in code, the piece heights are: pawn = 6, knight = 8, rook = 9, bishop = 10, queen = 11, king = 12.

-JD

EDIT: After posting and seeing the image again, the ring around the queen and king should be closer together... probably by adding a pixel to the horizontal part of the king's cross to lower his one and removing the bottom row of the queen's crown to move her's up one.

EDIT 2: Like so...

Posted Image

base size also doubled, as you can tell.

Report

Zach
Jan 9 2006 12:40 AM

That looks really good, Mayday! I went ahead and programmed the full board with your set, slightly modified. I made the queen less rookish, and made all the pieces taller. I was able to free 4 bytes from the self-modifying code and put them towards an extra line on the pieces. Now the dimensions are 3x13. The new screenshot and binary are in the first post.

Report

MayDay
Jan 14 2006 10:34 PM

Zach, on Mon Jan 9, 2006 12:40 AM, said:

I download the binary because I thought your mockup may not be exactly accurate... I don't understand how you have both the board and pieces displayed with the playfield, or am I missing something? It seems as if there are more pixels displayed than should be allowed...

I agree your crown for the queen is better than the one I designed. I also think you should leave the ring in the middle of the piece though so it matches against the king. Speaking of the king, I don't really like his crown either, but can't think of any better way to display the cross. Anyone with ideas?

Chess logic coming anytime soon? I can tell you what it's rated!

Report

supercat
Jan 15 2006 3:08 AM

Looks nice. My earlier pessimism may have been unwarranted.

Using 32 bytes for the board may be excessive. Since there are only 32 pieces on the entire board, it may be possible to do something like using 8 bytes to keep track of which squares are occupied, and then use 16 bytes (32 nybbles) to say what's in the occupied squares from top to bottom. Not sure you'd have enough time for the unpacking, though. My guess would be that average case time would be improved, but worst-case time would be made worse. But I don't know what you're doing at present, so I can't say how the change would affect things.

Otherwise, I must say I'm pretty impressed with your ability to eke out some cleverly-compact code. It took awhile to figure out how the self-modifying parts work since it's not very clear. It would be much more elegant if there were some way to use a fourth PLA.

Report

Zach
Jan 15 2006 4:31 AM

MayDay, on Sat Jan 14, 2006 11:34 PM, said:

I don't understand how you have both the board and pieces displayed with the playfield, or am I missing something? It seems as if there are more pixels displayed than should be allowed...

That's quite a compliment that the screenshot doesn't look realistic.

Actually the way the board is drawn is simple. The darker squares are made of players and missiles. (Can you imagine how it works?) The pieces are all done with the PF.

Quote

I agree your crown for the queen is better than the one I designed. I also think you should leave the ring in the middle of the piece though so it matches against the king. Speaking of the king, I don't really like his crown either, but can't think of any better way to display the cross. Anyone with ideas?

I tried to keep the queen's ring, but that made it harder to distinguish between the queen and king. I'm open to suggestions.

Quote

Chess logic coming anytime soon? I can tell you what it's rated!

Still working on Four-Play, and possibly another game for the 2006 1K contest.

Report

Cybergoth
Jan 15 2006 4:34 AM

Hi there!

Zach, on Sun Jan 15, 2006 10:31 AM, said:

Still working on Four-Play, and possibly another game for the 2006 1K contest.

What is it?

Greetings,
Manuel

Report

Zach
Jan 15 2006 4:43 AM

supercat, on Sun Jan 15, 2006 4:08 AM, said:

Looks nice. My earlier pessimism may have been unwarranted.

Thanks! That means a lot coming from the author of Strat-O-Gems.

Quote

Using 32 bytes for the board may be excessive. Since there are only 32 pieces on the entire board, it may be possible to do something like using 8 bytes to keep track of which squares are occupied, and then use 16 bytes (32 nybbles) to say what's in the occupied squares from top to bottom. Not sure you'd have enough time for the unpacking, though. My guess would be that average case time would be improved, but worst-case time would be made worse. But I don't know what you're doing at present, so I can't say how the change would affect things.

Yeah, freeing more bytes without compromising the height of the pieces would be nice. Right now there are 17 bits free (2 bytes of RAM plus overflow flag), and I think that is barely enough for a playable chess game. However, it would be nice to have more memory for difficulty levels and chess variants. (I'd like to include Losing Chess at least.)

I'll post some code to show how the unpacking is done. Right now there is barely enough time to unpack everything. A few more cycles and I think it'd go over 262 lines.

Quote

Otherwise, I must say I'm pretty impressed with your ability to eke out some cleverly-compact code. It took awhile to figure out how the self-modifying parts work since it's not very clear. It would be much more elegant if there were some way to use a fourth PLA.

Thanks again. Sorry if the code was hard to follow. I put in some more comments to help clear things up. I think the solution came more from refusal to give up than cleverness. I can't tell you how many ideas I tried. Like I said, I was able to take an advantage of a lucky coincidence that #$0F could be used both for the color white and for masking the right side PF2.

The obstacle to a 4th PLA was the number of cycles between color changes. I tried a lot of things, but couldn't squeeze four cycles in. Your right that it would have been more elegant.

Report

Zach
Jan 15 2006 5:38 AM

Cybergoth, on Sun Jan 15, 2006 5:34 AM, said:

What is it?

Might it be related to my new avatar? I'll post details when I either get it working, or I decide it's not feasible.

Report

Cybergoth
Jan 15 2006 6:19 AM

Hi there!

Zach, on Sun Jan 15, 2006 11:38 AM, said:

Cybergoth, on Sun Jan 15, 2006 5:34 AM, said:

What is it?

Might it be related to my new avatar?

No kidding, I already suspected that...

Zach, on Sun Jan 15, 2006 11:38 AM, said:

I'll post details when I either get it working, or I decide it's not feasible.

The avatar could be from a night scene of a racing game...

Greetings,
Manuel

Report

cd-w
Jan 15 2006 7:44 AM

Cybergoth, on Sun Jan 15, 2006 12:19 PM, said:

Zach, on Sun Jan 15, 2006 11:38 AM, said:

I'll post details when I either get it working, or I decide it's not feasible.

The avatar could be from a night scene of a racing game...

Or another attenpt at a Juno First kernel

Chris

Report

supercat
Jan 15 2006 2:10 PM

Zach, on Sun Jan 15, 2006 5:43 AM, said:

Well, presumably you're not going to be displaying the board while you're 'thinking'. During 'thought', the RAM used by the kernel could be used for other things.

Looking through your self-modifying code, I think I see space to store about 16 bits "within" it. Each indexed STA can be done using either X or Y (adjust the operand as needed), and every TIA store can be done with the normal address or with address+64. Further, you might be able to use the ball horizontal position and size to store 9 bits, eleven collision registers to store 11 bits(*), the RIOT timer to store 8 bits, and two bits of SWCHB and SWBCTL to store 4 bits. See--I just saved you six bytes.

(*) The playfield is going to collide with both players and both missiles, but no other collisions would have to occur, leaving eleven collision registers available for use.

Quote

The obstacle to a 4th PLA was the number of cycles between color changes. I tried a lot of things, but couldn't squeeze four cycles in. Your right that it would have been more elegant.

It might be helpful if you offer a version of the demo in which a row of pieces alternates between white and black, and in which the PF data is all $FF, so as to show exactly when the color changes are taking place.

Report

supercat
Jan 15 2006 2:26 PM

Oh, for six more bits, use bits 8, 10, 11, 13, 14, and 15 of PC. Not sure the most effective way to do that since I don't think you can afford a computed jump, and if you don't use a computed jump the code size will double with each bit you want to save, but here's how to save three bits:

 ; Assume we want to save the three MSBs of WOWZO
  lda #32
  bit WOWZO
  bmi b1xx
b0xx
  bvs b01x
b00x
  bne b001
b000
  jmp ZPCODE
b001
  jmp ZPCODE+$2000
b01x
  bne b011
b010
  jmp ZPCODE+$4000
b011
  jmp ZPCODE+$6000
b1xx
  bvs b11x
b10x
  bne b101
b100
  jmp ZPCODE+$8000
b101
  jmp ZPCODE+$A000
b11x
  bne b111
b110
  jmp ZPCODE+$C000
b111
  jmp ZPCODE+$E000

The MSBs of the program counter can easily be retrieved after the BRK instruction.

Another spot you may be able to save a bit is in bit 0 of Y. You'd have to adjust the operands of indexed instructions, but it might be doable.

Another spot to save 4.5 bits (a one-of-24 selection) would be the horizontal positions of P0, P1, M0, and M1. You can permute them any which way without affecting the on-screen appearance. Not sure you could avoid HMOVE lines if you did that, though, since you'd have to HMOVE the squares back and forth.

Report

supercat
Jan 15 2006 4:02 PM

Hope you don't mind my snooping around in your code, but you've got a slight problem.

To generate your indexed stx/sty instructions, you use

  lda #$4A
  adc #$00
  asl
  sta opcode
  lda #$48
  bcs skip1
  sec
  sbc #$0F
skip1:
  bcc skip2
  nop
  nop
skip2:
  sta operand

This doesn't work. The opcode is generated correctly, but carry is always clear after the asl and set after the sbc, so the operand is always $39.

How about

  lda #255
  adc #$00; Make acc. hold 0 or 255
  and #$F1; (COLUPF ^ (COLUPF -15)) & 255
  eor #$08; COLUPF
  sta operand; Acc now holds $08 or $F9
  asl
  and #$02  ; The bit that's different between STY,x and STX,y
  eor #$96  ; If acc. was $08 we want STX,y
  sta opcode

That's a fixed 20 cycles (17 bytes). If you want to reverse the meaning of the carry flag, change the first "EOR" to "EOR #$F9". Alternatively, since Y is not not "live" there:

  bcs color2
color1:
  lda #$96 ; STX,Y
  ldy #COLUPF
  bcc colorstore
color2:
  lda #$94; STY,X
  ldy #[COLUPF-15] & 255
  nop
colorstore:
  sta opcode
  sty operand

That's a fixed 15 cycles (17 bytes) but as mentioned it does use the Y register; it also relies upon branches not to cross a page. If you didn't want to use the Y register, you could make the code 2 bytes longer while preserving the cycle count.

Another approach:

  rol
  and #1
  tay
  lda opcodes,y
  sta opcode
  lda operands,y
  sta operand

A fixed twenty cycles, BUT if you had things formatted differently you could do many squares at once:

; Assume bits 0-3 of accumulator hold color of four squares (the second and third of which need indexed addressing)
  and #15
  tay
  lda opcodes0,y
  sta opcode0
  lda opcodes1,y
  sta opcode1
  lda operands1,y
  sta operand1
  lda opcodes2,y
  sta opcode2
  lda operands2,y
  sta operand2
  lda opcodes3,y
  sta opcode3

Requires a few 16-byte tables, but manages a slight speedup.

Report

MayDay
Jan 15 2006 4:38 PM

Zach, on Sun Jan 15, 2006 4:31 AM, said:

I tried to keep the queen's ring, but that made it harder to distinguish between the queen and king. I'm open to suggestions.

This is what I was meaning... I slightly altered both the king and queen using the new dimensions you listed.

Posted Image

Quote

Chess logic coming anytime soon? I can tell you what it's rated!

Still working on Four-Play, and possibly another game for the 2006 1K contest.

Travesty!!

Your setup is awesome, much better than the striped version the original is. I know this game isn't your primary concern right now, but have you given any thought to having your engine contain opening lines or endgames? Or will it play entirely based on logic? I think at least a few of the most popular opening lines would help immensly to strengthen it's playing ability. Most high-level games today go 15-25 moves "by the book" with several games having followed each line for the players/computer to reference.

-JD

EDIT- also, have you given thought to the most important part, which is what you're going to name the game?

How about Deep Fuji or X3D Fuji?

Report

supercat
Jan 15 2006 6:06 PM

[quote name='MayDay' date='Sun Jan 15, 2006 5:38 PM']
[quote name='Zach' date='Sun Jan 15, 2006 4:31 AM']I tried to keep the queen's ring, but that made it harder to distinguish between the queen and king. I'm open to suggestions.[/quote]

How about (turned sideways)

I think that's visually distinct from all the other pieces.

Report

MayDay
Jan 15 2006 6:20 PM

From supercat's suggestion in the previous post, in picture form. His version had one less line (11 instead of 12) so I just added one pixel to the top of each row.

Posted Image