Chess

[+Andrew Davie]

8 hours ago, NostAlgae37 said:

Oh wait Andrew, you are actually one of the programmers of that era, aren't you? 

Yep! I'm very old.

[+Andrew Davie]

I tweaked the visuals of en-passant capture. Shown in this video... I quite like it! Not that anyone's likely to ever see it in anger. But I'll know it's there, and that's what counts

 

 

 

Edited January 17, 2020 by Andrew Davie

[+Andrew Davie]

I'm a bit daunted at getting the ARM functionality into Chess. As I mentioned earlier, I'm planning to use the ARM for the chess engine. This has to be interweaved, so to speak, with the ARM servicing the address and data buss for the 6507. The basic plan is to have the 6507 write to some address at the end of each frame, or perhaps in the two major parts of the frame where there's processing time. The ARM servicing code will detect these addresses and go on its merry way doing some chess processing. It interrupts itself after the allocated time and returns to processing address decoding. Repeat.

Now I have the unocart code to start with. But I have absolutely no idea about how to go about setting up a development environment for this. I don't really want to have to dump to hardware every single time I make a change... so ... waiting on some advice.  I also wonder what's the absolute fastest ARM I can put in the cartridge. If I'm going to use ARM power for the engine, it might as well be the best ARM money can buy.

Meanwhile, I've just been fiddling with the UI code. Short video attached.  I still have to put in sprite capability - I may do that soon.  Sprites will be used for selecting/highlighting squares in move selection. Just something very rudimentary, I think. Given the squares are 20 (single) pixels wide, I'm going to need two double-wide sprites to completely cover that space.
 

[iesposta]

6 hours ago, Andrew Davie said:

Given the squares are 20 (single) pixels wide, I'm going to need two double-wide sprites to completely cover that space  

Why 2 Players and not one quad-size Player?

If you have single line color changes you could match each piece color exactly and smoothly move it in any way.

 

But remember to keep things simple and easy for you. Using a Player to move the piece around is just another visual add-on effect. 

[+Al_Nafuur]

8 hours ago, Andrew Davie said:

Now I have the unocart code to start with. But I have absolutely no idea about how to go about setting up a development environment for this. I don't really want to have to dump to hardware every single time I make a change... so ... waiting on some advice.  I also wonder what's the absolute fastest ARM I can put in the cartridge. If I'm going to use ARM power for the engine, it might as well be the best ARM money can buy.
 

 

If you need more ARM power i would suggest an STM32H750VBT6. It has 480Mhz and 1024Kb RAM, but only 128KB Flash and it's slightly more than double the price of a STM32F407VGT6 breakout board. I have some of them as "fallback" for the PlusCart project:

https://de.aliexpress.com/item/4000300005466.html

with an custom breakout PCB they would fit into an 2600 cartridge.

UnoCart/PlusCart code should work with only a few changes.

 

And it has these old fashion SD-Card slot everybody loves?

 

Or you switch completely from MCUs to MPUs with the STM32MP1. This one has, like the ESP32, two cores a MCU and a MPU. So you can use the MCU to keep the 6507 busy and let the MPU doing the chess.. 

 

Edited January 18, 2020 by Al_Nafuur

[+Andrew Davie]

1 hour ago, Al_Nafuur said:

 

If you need more ARM power i would suggest an STM32H750VBT6. It has 480Mhz and 1024Kb RAM, but only 128KB Flash and it's slightly more than double the price of a STM32F407VGT6 breakout board. I have some of them as "fallback" for the PlusCart project:

https://de.aliexpress.com/item/4000300005466.html

with an custom breakout PCB they would fit into an 2600 cartridge.

UnoCart/PlusCart code should work with only a few changes.

 

And it has these old fashion SD-Card slot everybody loves?

 

Or you switch completely from MCUs to MPUs with the STM32MP1. This one has, like the ESP32, two cores a MCU and a MPU. So you can use the MCU to keep the 6507 busy and let the MPU doing the chess.. 

 

 

Many thanks. That last option - STM32MP1 - is very attractive.

It would greatly simplify the architecture, as you have noted.

 

 

[+Andrew Davie]

2 hours ago, iesposta said:

Why 2 Players and not one quad-size Player?

If you have single line color changes you could match each piece color exactly and smoothly move it in any way.

 

But remember to keep things simple and easy for you. Using a Player to move the piece around is just another visual add-on effect. 

Good points. The design of the kernel makes it a bit more complex shifting sprite shapes across row boundaries. Possible, just difficult.

I was thinking of just square highlight blocks, actually - and yes, a single sprite 4x would work fine.

[+Al_Nafuur]

3 minutes ago, Andrew Davie said:

 

Many thanks. That last option - STM32MP1 - is very attractive.

It would greatly simplify the architecture, as you have noted.

 

 

The STM32MP1 is a new product of ST. They held a 2 days workshop about this product here. We used the STM32MP157C-DK2 dev kit there. I really like their hardware, but their "documentation" system is very frustrating. It's based on downloading various zip and pdf files and hoping you find answers by searching through them.?

 

[+Andrew Davie]

Very first attempt at a title screen v0.00000 alpha alpha.

I know it's barely legible. It will get better...

[Mr SQL]

19 hours ago, Andrew Davie said:

Now I have the unocart code to start with. But I have absolutely no idea about how to go about setting up a development environment for this. I don't really want to have to dump to hardware every single time I make a change... so ... waiting on some advice.  I also wonder what's the absolute fastest ARM I can put in the cartridge. If I'm going to use ARM power for the engine, it might as well be the best ARM money can buy...

 

 

There have been some discussions on creating compatible routines, it would be really cool if you could abstract the Chess engine to support both flashcarts.

 

[NostAlgae37]

20 hours ago, Andrew Davie said:

Very first attempt at a title screen v0.00000 alpha alpha.

I know it's barely legible. It will get better...

 

Ack!  It looks like low-res digitized graphics!  I think that I'm having bad late eighties/early nineties flashbacks...  j/k 

 

[+Andrew Davie]

Wellll.... while I'm idle on other things, I've started writing my own chess engine.

The first part to writing a chess engine is generating "legal" moves. That is, for each piece on the side that's about to move, you build up a list of squares to which that piece can move. Then, after you have that list, you try each of the moves one at a time, and after you try each of those moves, you switch sides and repeat. At some point you stop because the combinatorials get massive and you're dealing with millions of moves/counter-moves/counter-counter moves. And you evaluate the board at the bottom of each branch of that "tree of moves" and you figure out which is the "best". And the "best" is chosen based on what's called the minimax algorithm. That's where each side to move assumes that the opponent will chose the best response, so you choose the move that minimises the best response the opponent can make. Best of the worst of the best of the worst of the best of the worst....   Generally a (low powered) micro chess engine might get to 6 moves deep, give or take.  There are refinements to optimise the "minimax" algorithm, such as early aborts due to figuring out there's no point continuing (alpha-beta pruning). If I get this working, I'll do all that.

But, REALLY, the first part is not generating legal moves. It's deciding on efficient data structures to represent the moves, handle the searching, and evaluating the board at the terminal nodes. So, I'm starting on all that, anyway.  In my view, being efficient in the move generation is important because that part of the code may be executing thousands upon thousands of times.

[+Andrew Davie]

Alpha-beta pruning is interesting.

Let's say we "rate" a position on a scale of 0 to 100, where 100 is great for me, 0 is great for my opponent.

So, I check the first "branch" - that is my move, and then all the responses, and responses to the responses, etc.

And eventually I determine that if I make that move, the opponent can make his best move which leaves the board at a value of 75.

That is, reasonably good position for me. I know if I make that move, the worst I'll end up with after any opponent reply is 75.

So now I check the next move I can make. And while I'm doing that, I look at the opponent's responses.

I get to a situation where the opponent leaves the board with a rating of 23 for me.

Well, I go.... I'm not going to choose THAT move. If I do, the opponent can get to 23 (good for him) whereas if I did that first move the best the opponent can get to is 73 (good for me).  So at that point, you abort the search on that move's branch. We just throw it away and say "hey, if the opponent chooses his best move, I'm much worse off".  That's alpha-beta pruning.

Typically chess "branches" at about a factor of 30.  That is, there are roughly 30 available moves in any position. Give or take.

So each "ply" that you investigate, you're investigating 30 moves.  So on the first ply, 30 moves to check. But on each of those moves there are aother 30 responses. On those responses another 30.  So it's 30^n moves to check, for a depth of n.  If you want to get to 8 ply deep, 30^8 = 656100000000 positions. Clearly that's not going to happen.  But it's been shown that alpha-beta pruning reduces the average branching factor to 7 or 8. Let's say 8, so it's now 8^n. For an 8-ply tree that's now ("just") 16777216 positions. Well, yes that's not going to happen on the 2600 either. But it's better. Then you start to do things like optimising the order in which you generate/check the moves, so that alpha-beta pruning is more likely to happen. You can do that, for example, by checking capture moves first. Those are most likely to cause dramatic changes and lead to earlier pruning. You can also do things like just checking the first n moves instead of all of them. But those things are for later.

First, let's get move generation working. I'll generate a move list, and then have a cursor on the board... when you click on a piece, it will use the movelist and mark on the board all squares (say, with a dot) where that piece can move to. Then I'll know my move generation code is working correctly. Then I can move onto a minimax search. And then hook in alpha-beta pruning.

One thing - for efficiency we don't worry about "check" and illegal moves causing check. That is handled later in the search tree - where we decide if you can take the opponent's king, then the opponent's previous move must have been an illegal one. It's more efficient to find check during a tree search than to try and handle it in the move generation part.

So, right now I'm starting on the move generation code. It needs to be stunningly efficient, so that's a challenge.

[+Andrew Davie]

2 hours ago, NostAlgae37 said:

 

Ack!  It looks like low-res digitized graphics!  I think that I'm having bad late eighties/early nineties flashbacks...  j/k 

 

But... it IS low-res digitised graphics! It's just an image I googled and converted via a tool.

[+Andrew Davie]

Putting things into perspective, assume we were just doing a stock-standard minimax search to 5 ply. That's 30^5 times that the "generate move" routine would be called. 24300000 times. If we waste just a single cycle in the generate move routine, on a 1.19MHz processor that would be around 20 seconds of time waiting for your move just because of that 1 cycle.  It gets worse though - assume that at best we can generate a single move, make that move, evaluate the board in about (say) 1000 cycles per move -- ballpark, perhaps a bit conservative -- but let's say 1000. So the total time for a 5 ply search would be roughly 20000 seconds -- very roughly 6 hours. Per move.

And... 5 ply is tragically small for a chess program - it would play terribly.

Consider an alpha-beta implementation with (again) 5-ply depth. And still 1000 cycles/move. But now the branching factor is 8.

So, total time is 8^5 * 1000 cycles / 1.19MHz --> 27 seconds. Now that's more like it.

But... 5 ply... not great.  If it were 7 ply...  about 30 minutes.

Well, that's what we're looking at if ALL of the CPU time was available. But let's say we don't turn off the screen.

So, about 80% of the CPU will instead be servicing the screen draw, so for a 5 ply move we're now looking at nearly 2 and a half minutes.

In my previous experience with chess programs, 5 ply... meh....  not workable.

So, to increase depth - and assuming the code is relatively efficient - we need to reduce the # of moves on each ply that's being looked at.

Assume we get it from 8/ply to 7/ply (after alpha-beta). Let's just say we only consider the first 7 moves at any depth...

5 ply is now 7^5 * 1000/ (1.19MHz*20%) --> a bit over a minute. Still not really playable.

My conclusion from all this is that it's extremely unlikely that a decent chess engine (and by "decent" I mean something that is not completely clueless) could be possible using a minimax/alpha-beta engine running while the screen is being displayed.  That is, using only the processing time available in vblank/unused screen time.

So. There's that. Chess on a 1.19MHz processor is tricky enough. Running at 20% of that... not going to happen.

 

 

[+TwentySixHundred]

14 hours ago, NostAlgae37 said:

 

Ack!  It looks like low-res digitized graphics!  I think that I'm having bad late eighties/early nineties flashbacks...  j/k 

 

Looks incredible though and Sokoban had an amazing title screen too. IMO it has that old oil painting look to it and leaves the mind in a state of soaking in the contrast ?

Edited January 20, 2020 by TwentySixHundred

[+Andrew Davie]

I've had a go at starting the move-generation code. In particular, the King.

Moving a king - or rather, generating a list of valid moves for a king - is actually quite complex.

Firstly, there's the 8 directions - easy enough.

But then there's castling - and the rules are that the king can't castle unless...

a) he hasn't moved yet

b) the squares between king and rook are vacant

c) the rook hasn't moved yet

d) the king isn't in check

e) none of the squares the king crosses is in check

So, there's a trick about the "in check" bit - and that is to defer the check until the next ply. That is, the move generation for the other side will see that the king can be captured, so obviously the previous move was illegal.

Except (e) is a tad tricky. I'm planning to put a "PHANTOM" king on the board when a castle move is done so that the next ply will detect it. The phantom will of course be removed as soon as that phase is done.

Anyway, I've written all the code for the move generation, so here it is. Just for the curious who are interested in my coding style and if it's efficient or not. Looks like about 220 bytes, give or take, for the complete king move generation. It assembles but I haven't had occasion to run it yet. For architecture reasons I have this living in RAM. I'm trying some new ideas about switching between RAM banks, garnered from a discussion on the forum about the travails in using another bankswitch scheme.

 

; Copyright (C)2020 Andrew Davie

; This is the move handler for a KING
; "Check" is detected in the next ply of the search, so the move generation doesn't have to
; be concerned about that. To assist with castling over squares in check (which is illegal)
; the concept of a phantom king is introduced. Phantom kings are effectively blank squares
; but need to be checked when moving opposite-colour pieces to a square. Messy.

    NEWRAMBANK HANDLER_KING
    ; Handles everything to do with king moving

    include "common_vectors.asm"         ; MUST BE FIRST

;---------------------------------------------------------------------------------------------------
; MACRO - Common code
; Looks at a square offset {1} to see if K can move to it
; Adds the square to the movelist if it can

    MAC MOVE_KING
    SUBROUTINE

                ldy ValidSquare+{1},x
                bmi .invalidK                   ; off board!
                lda Board,y                     ; piece @ destination
                beq .squareEmpty

    IF BLACK != 128
        ERR             ; following optimisation invalid
    ENDIF
                eor currentPiece
                bpl .invalidK                   ; same colour

.squareEmpty    jsr AddMove
.invalidK
    ENDM

;---------------------------------------------------------------------------------------------------
; MACRO - Castling

KINGSIDE        = 3
QUEENSIDE       = -4

    MAC CASTLE
    ; {1} == KINGSIDE or QUEENSIDE
    SUBROUTINE

        ; Most likely failure trigger is there are pieces in the way (N or B) (or Q)
        ; Check these squares first as it's the cheapest "exit" from castle check

        ; Note: castling with squares that are "in check" is problematic
        ; TODO: next ply have a "phantom" king on the positions king moves over...?

        IF {1} = QUEENSIDE
                lda Board-3,y               ; nothing in N pos
                bne .noCastle
                lda Board-2,y               ; nothing in B pos
                bne .noCastle
                lda Board-1,y               ; nothing in Q pos
                bne .noCastle
        ENDIF

        IF {1} = KINGSIDE
                lda Board+2,y               ; check N pos
                bne .noCastle
                lda Board+1,y               ; check B pos
                bne .noCastle
        ENDIF

        ; appropriate N/B/(Q) squares are vacant so we proceed with more checks...

                lda Board+{1},y             ; we expect a R
                sta __piece

                and #PIECE_MASK
                cmp #ROOK
                bne .noCastle               ; not a R

                lda __piece
                eor currentPiece
                bmi .noCastle               ; not correct colour

                bit __piece
                bvs .noCastle               ; it's previously moved so we can't castle

    ; FINALLY -- king can castle
    ; note: when we actually DO the move we MUST insert "Phantom" kings onto the board over the
    ; squares the king traverses so that "check" (and thus illegal moves) can be detected on the
    ; next move. Castling will be detected by K moving > 1 square.

                jsr AddMove
.noCastle
    ENDM


;---------------------------------------------------------------------------------------------------

    DEFINE_SUBROUTINE Handle_KING

    ; Pass...
    ; x = currentSquare (square the KING is on)
    ; currentPiece (KING of course, but with flags/colour attached)

    ; regular moving...

                MOVE_KING _DOWN+_LEFT
                MOVE_KING _DOWN
                MOVE_KING _DOWN+_RIGHT
                MOVE_KING _RIGHT
                MOVE_KING _UP+_RIGHT
                MOVE_KING _UP
                MOVE_KING _UP+_LEFT
                MOVE_KING _LEFT

    ; castling...

                bit currentPiece            ; WARNING: D6 (=MOVED) assumed
                bvs .noCastle               ; can't castle - king has moved

                CASTLE KINGSIDE
                CASTLE QUEENSIDE

.noCastle
                rts


            CHECK_BANK_SIZE "ENGINE6502 -- full 2K"

 

Handler_KING.asm

[+Nathan Strum]

9 hours ago, Andrew Davie said:

But then there's castling - and the rules are that the king can't castle unless...

a) he hasn't moved yet

b) the squares between king and rook are vacant

c) the rook hasn't moved yet

d) the king isn't in check

e) none of the squares the king crosses is in check

Well, I knew about b.

[CapitanClassic]

@Andrew Davie, how to you plan on representing the board state? (12x12 board, to make it easier to determine if a knights move is legal and on the board), 0x88 method, rotated bitboard?

 

 

https://en.m.wikipedia.org/wiki/Board_representation_(computer_chess)

[+Andrew Davie]

58 minutes ago, CapitanClassic said:

@Andrew Davie, how to you plan on representing the board state? (12x12 board, to make it easier to determine if a knights move is legal and on the board), 0x88 method, rotated bitboard?

 

 

https://en.m.wikipedia.org/wiki/Board_representation_(computer_chess)

I am currently using a 12x12 board, though I had not seen that article. Just using what I remembered from the '80s.

Just last night I was thinking I could easily use a 10(wide) x 12 board, as the indexing would wrap around left/right edges so I'd save 24 bytes.

[+Andrew Davie]

I've completed a first-pass at move generation code for all of the pieces.

Surprisingly, to me at least, was that the pawns were actually by far the most complex.

The code handles en-passant captures (ONLY if the captured piece has JUST moved), pawn promotion, capture and promotion on last rank, double-square move on 1st move and of course the lowly move-one-square.

Split into two files at the moment - one for king and one for the rest of the pieces. I'll split these over several banks, eventually.

As an interesting aside, there's a pretty short/neat python program that plays OK chess.

Of course it is "cheating" with assists from libraries already pre-written, but it's a good template to go by...
See...  https://medium.com/@andreasstckl/writing-a-chess-program-in-one-day-30daff4610ec

 

Handler_PNBRQ.asm Handler_KING.asm

[+Andrew Davie]

I did a brief experiment to see how the old BYO "Greeting Cart" display would work with a chessboard.

Here's the results, for posterity...  looks a lot less flickery than this screen grab shows. 

But still, I think not.
 

byo.bin

[+Andrew Davie]

Things are happening.  It took me a few days to integrate the original display (a testbed) and the new move generator. The main issue was representation of the board as an 8x8 in the display code, and 10x12 in the move code. But also memory is tight in the banks I'm using.  I had to do a fair bit of thinking about how to organise things, but it's finally all come together.

What this video shows is me doing some testing on the move generation. I'm modifying the pieces on the board and then running. It draws the board, and then shows all the valid moves for the piece at left, by placing the piece (ignore the colour changes) on the squares it can visit. This lets me setup various situations/scenarios such as en-passant, capture, etc.  I have yet to check all the moves, but the basic systems are all pretty sound. There is screen roll, but who cares - this is just for visual/testing of the move generation code.

Once I've tested all the moves, I think I'll hook in a joystick/move bit of code, so when you select a piece, then all the valid squares for that piece are shown. That's a couple of days down the track. For now, I'm quite happy with this...
 

[+Random Terrain]

Once the game is working, will it also have movement hints similar to this chess game?

[+Andrew Davie]

Can't play it because it uses flash and that's too much of a security risk for me.
But, based on the description - yes, I plan to have it showing the moves you can do - including captures.

In fact, that's pretty much the next step I described in my earlier post.