Chess

[+Random Terrain]

2 minutes ago, Andrew Davie said:

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.

 

 

Oh, thanks. I totally missed that sentence.

[+Andrew Davie]

This is a sort of indicator of how that will work - in this image the knight lower right is actually white - I have a colour bug - but the point is that the squares the knight attacks (which are also legal moves) are shown with dots... so just imagine this is how the legal square stuff will work (if you have it enabled, I guess). Note the pawn lower right at H2, and the king E1 and the pawn D2... do not have superimposed dots because they are not legal moves for a white knight at F3. Of course it will be more polished. I'm using this at the moment to 'track' a particular piece's moves in debugging - the squares are dynamically turned on/off as the piece moves, so I can see what the move generator is doing for any given piece.

 

[+Andrew Davie]

It's proving useful. Here I have a queen moving around the board, and after each move putting the "move markers" on the board. You can see at the end, for example, the queen thinks it can move through the pawn and take the knight at G8.  So, that's a bug.  I have to do this for all the pieces, which shouldn't be too much work. I'm pleased that my very first testing of en-passant worked perfectly! Will be interesting to see how the castling code works, too. Just a bit of testing to come really.  I'm a bit reluctant to describe the data structures/method I'm using for move storage and search implementation. I'm sure that someone is going to look at it someday and go "awwww, well that's just cheating!".
 

[+Andrew Davie]

I nominate myself for the "best commented source code" award.

And, the winner is....

 

 

Isn't it pretty!

 

[+Andrew Davie]

so, how much space do I need to reserve for the move list?  In other words, at any single position of the game... what is the maximum number of moves that any side may have?  Well, not so simple. There are contrived positions with 218 moves. This particular actual game (image) has 79 moves for black. So, I think I'll just set my movelist to 256 entries because that's a nice round number. God forbid, so to speak, trying to search positions with 79 moves/side.

[+Andrew Davie]

Well, after a lot of "Hard Work"(TM) I now have some visuals showing that the move generation code is pretty much working, and it's hooked into the display/movement code properly. What's happening in the video is that the code is generating ALL the moves for white, then choosing a random white piece, and a random move for that piece from the generated list, and moving. Repeat.  So, it's just random white move after random white move. And of course the screen glitches every time there's a movegen happening - that won't happen in the final game, of course. But for now if you can blink at the right time you won't notice it  . -- in any case, it seems that the moves are now doing their thing.  This is all hooked into bankswitching and multiple 'ply's too, so when the tree search comes along, it's already implemented.  I don't have "undo move" yet, but that shouldn't be too tricky. And I've kind of lost a bit of efficiency in my debugging to get this working. I'll spend a few days refining the code/register usage just to make sure all is hunky dory, and then I'll move on to perhaps having it do white move/black move/white move/etc. Still no AI/searching, of course. Just random move selection, but "VALID" random moves.
 

 

It's kind of cool, I'm pleased with how it's coming along. Much of the code is very elegant. I really doubt it's going to be possible, though, to make it play decent chess in decent time.  The more I work on this, the more impressive VideoChess by Atari seems to be. I've started a bit of a side project trying to disassemble it, but I see that's going to be a long-term labour of love. Quite a difficult job, reconstructing commented source from a binary, and I have much appreciation for those who have done it.

I was thinking about the very few Atari games I've done over all these years - just mostly lots of demos. But the games - all "puzzlers", really.  Qb, of course, which is an "action puzzler" but then Boulder Dash - another action/puzzler, and Sokoboo - a pure puzzler. And now Chess. I don't think there's a large audience for puzzle games, in general. 

[+Andrew Davie]

As a side-note - the black/white pawns are nearly indistinguishable when close. As I can't really change the colours (the white pawn is just the black pawn with an extra colour every third line)... that means that the black pawn and white pawn are only 3 pixels different. So, I'm probably going to redesign the pawns, make them bigger, and go back to an earlier design.

[+Random Terrain]

Yep, undo would be a handy feature.

[+Andrew Davie]

Just now, Random Terrain said:

Yep, undo would be a handy feature.

You're thinking "take-back", I think. I don't do take-back in chess

I'm talking about reversing the move during a tree-search so that the algorithm can traverse back/forward by just "reversing" what it's just done. It's more efficient than copying entire boards from ply to ply.

But yeah, "take-back" -- nah, that's cheating. Touch it, you move it

 

[+Random Terrain]

Good chess players can see 15 to 30 moves ahead. I see negative three moves ahead.

[+Andrew Davie]

3 minutes ago, Random Terrain said:

Good chess players can see 15 to 30 moves ahead. I see negative three moves ahead.

Ha, well to put your mind at ease, *very good* chess players may see 5 or 6 moves ahead, and only select moves at that.

Good human players deal more with patterns and positional play, goals objectives and relationships between pieces. It's rarely "if he does this, then I'll do that and he'll do this and then that". That's how computers (used to) do it. Alpha Zero is a whole new ball game. If you haven't looked it up yet, I highly recommend watching some youtube videos on alpha zero, as it has completely reinvigorated the game and how we think about it.

[+TwentySixHundred]

24 minutes ago, Andrew Davie said:

You're thinking "take-back", I think. I don't do take-back in chess

I'm talking about reversing the move during a tree-search so that the algorithm can traverse back/forward by just "reversing" what it's just done. It's more efficient than copying entire boards from ply to ply.

But yeah, "take-back" -- nah, that's cheating. Touch it, you move it

 

It's not cheating if you never remove your hand from the piece ?True rule, i actually played chess for the state school championships as a lad *kind of embarrassing*. But yeah i get where you're coming from in a video game ?

Edited January 27, 2020 by TwentySixHundred

[The Usotsuki]

I think it's called "j'adoube" ?

[+D Train]

14 hours ago, Andrew Davie said:

after a lot of "Hard Work"(TM)

deep cut, my man.

 

very.  deep.  cut.

[+Andrew Davie]

Pawn promotions are now working. In the video from 50 seconds to 1:10 there are a bunch of pawn promotions happening - this shows (randomly) promotion to rook, knight, bishop, queen. The promoted pawns then continue as the new piece type.  Things I haven't managed to test, yet... en passant and castling, both of which will require special handling in the move code.

I've reworked the pawns - still not happy, but they are now different shapes for white/black to assist with recognition.  I've also fiddled with the knights once more.  I'll probably be adjusting piece shapes until kingdom come.
 

 

One of the tasks in my to-do-soon list is to change how piece drawing works. Currently to move a piece, you first undraw the piece (which gives black nothingness where the piece was), and then you draw in the appropriate white or black square. So it's a twofold operation. But I got to thinking what if the black/white squares were on the board always, and to draw a knight on a white square, you'd eor-draw in a knight, but that knight rather than being a knight on a white square would be a knight already eor'd with a white square. So it would look nothing like a knight, but when eor-drawn, it would suddenly look like a knight. That would save the "undraw" process, and make the movement code shorter and simpler. It's just a pain to rework the tool - my motivation and workrate is at an alltime low ebb at the moment.

Alternate colour scheme...

 

Edited January 28, 2020 by Andrew Davie

[+Andrew Davie]

I've got a bit of an idea. Normally, for my games anyway, I draw the screen and then try and fit stuff into the two areas where the screen/6507 is 'idle'. That is, where you wait for INTIM at the top and bottom of screen. So, I make sure the code is divided into small tasks that can fit in there, and I fit as many as possible in there, then continue with screen draw.

 

I'm planning to do things the other way around with Chess.  That is, the chess program is going to be calling the screen draw code, rather than the other way around. So, chess will do its stuff, and when INTIM is getting short, then it will call the relevant part of the screen draw. At first this sounds exactly the same thing, but it means that I don't have to have convoluted "which part of the chess program is running?" architecture. I just have the chess program do its stuff, and in various places I put in a check/call for screen drawing. This means breaking up the processing into smaller chunks is going to be MUCH easier.

For example, pseudo-code...

for all pieces {

  if (not enough time for this piece)

    call subroutine to draw appropriate bit of screen
  generate move for piece

}

 

That's the basic principle. "appropriate bit" would be the top of screen before vblank (part 1), the visible screen (part2). The rest is pretty much just waiting for stuff via INTIM.  So I still need to know how long bits take, but the *flow* is easier to manage. And if I don't have/want the screen on, then the "if" in the above pseudo-code would always return false, and never run.

 

That comparison could be a macro which I just pepper through the code, as appropriate.
Seems like a plan.

 

Edited January 28, 2020 by Andrew Davie

[+Andrew Davie]

OK, castling is now working correctly. Each piece has a "MOVED" bit, which is set, obviously, when a piece moves.

The video shows me checking out the castling. First I modify the board setup table, and here we have dummy pawns, but more importantly a king and two rooks. I variously set the "MOVED" flag on the rooks and king and watch the behaviour, which is as expected. It does queenside or kingside castling as appropriate. Or more to the point, it puts the moves in the movelist and then later on down the track if that move is selected, then the pieces are moved correctly for castling moves.  Just en passant to go now and the moves - for the most part - will be complete.

I do not think I will be implementing the 50 move rule, or the repeated position rule. Maybe.
 

[Mr SQL]

On 1/27/2020 at 9:18 AM, Andrew Davie said:

You're thinking "take-back", I think. I don't do take-back in chess

I'm talking about reversing the move during a tree-search so that the algorithm can traverse back/forward by just "reversing" what it's just done. It's more efficient than copying entire boards from ply to ply.

But yeah, "take-back" -- nah, that's cheating. Touch it, you move it

 

Sure I agree don't implement take-back but the player should still be able to cancel the move if they change their mind before they finish the move because this is pretty standard in Video Chess and ChessMaster, everyone is used to playing computer chess that way and can play a better game with that feature kept on. 

 

Increase the challenge by hiding the board between moves instead - some trippy Lava Lamp demo's between moves would be really cool if you want to one-up the Video Chess mood ring effect!

 

[+Andrew Davie]

I spent a bit of time fixing up the timings so that the glitches were removed. It's a bit ironic, because I don't anticipate the final form requiring such optimisations. But anyway, they're done. Here's a video showing random move selection. The moves selected are *slightly* different - now it's just a random move from the total move list, whereas before it was a random move of a random piece. So in this new version, pieces with more moves are more likely to move. It's not really important, as it's just a test of the moves anyway.

There's a 'natural' king-side castle chosen in there, too. I cleaned that up a bit visually.  'Natural' in that I didn't force it, and it just happened to be one of the valid moves (king had not moved, rook had not moved, no pieces in between). Glad to see that working properly.

I think the next thing to work on might be the joystick-based entry of moves. Maybe. And after that, perhaps removing illegal moves (moves leaving you in check) from the movelist. Normally that will be handled during a search, but for the user-input it would be nice to have that functional. I'd also like to get that legal-move-dot thing working for the UI.  I'm thinking you highlight a square with a piece on it, the dots show all legal squares for that piece... you press the button and the piece starts flashing and you move it with the joystick to a square with a dot... press again, and the move happens visually. As to "take-back" - my thinking is that if you return the piece to its original square and press the button again, it stops flashing and you can instead select another piece to move.

Perhaps I'd be better getting that optimised draw (eor/eor) going first.

Edited January 29, 2020 by Andrew Davie

[+Andrew Davie]

I tested out black to see if the pieces moved OK. For the most part, they did. A few glitches. Then I toggled the side to move, and it's playing itself... sort of. Just random moves, of course. But they're valid moves. And every now and then it locks - I have a diagnostic there that causes that, but I'm not quite sure why the diagnostic event is triggered. Anyway, early days.  This vid is about 5 minutes after I saw it doing this for the first time, so... pretty stoked...

Piece now flashes briefly at end of move, too - seems to work better for following what's happening.

 

Edited January 29, 2020 by Andrew Davie
I suspect with all my videos I'm one of the prime disk space hogs of Al's server

[+Andrew Davie]

Here's a binary.  It will do the same thing every time, except if you press the joystick button (anytime) - that gives a kick to the random sequence, and subsequent moves will be different.

chess_20200129.bin

[CrazyChris]

Looks really good. I like the fat pixels.

[Voxel]

This is a masterpiece in the making, thank you for sharing your development work.

[+Andrew Davie]

I'm almost ready to do a tree-search for best-move.

As a start, I wrote a shell of an "alpha-beta" function. This is a recursive routine that generates moves for a level, iterates each of the moves.. makes the move, and recurses a level deeper.  Anyway, the shell does nothing but simluate 7 moves (which I believe is an achievable # moves per level on average, using pruning), and calling itself - bottoming out at ply #8.  That is, it's like making a move, looking at all the opponent replies (now level 2), looking at all the replies to the replies (level 2)... etc... (level 3).. .... ... (level 7).  8 in total.  So that's something like 7^8 (=5764801 positions). Give or take. Now the alpha-beta routine doesn't generate the moves, or do any evaluations. But when I add that stuff in, it's a linear multiplier of the time taken, not exponential. 
So, for an 8-ply bare-bones structure simulating a 7 move/ply situation, just the scaffolding to do this and actual recursive calls (5764801 of them) takes pretty much exactly  1 minute. No way am I going to get an 8-ply search on a '2600, but I might get a 4 ply one. The 6-ply search takes roughly 1 second. Assume (say) that we need 4000 cycles per move checked (that is, create movelist, do a move, evaluate the position)... and we want to generate a move within (say) 1 minute, then we have 60s x 1190000 cycles total roughly. That's 7140000 cycles. Now, 4000 cycles/move, so that would be 17850 moves checked in a minute. Seems a bit low, but let's go with it. So what's the log(7) of that... it looks like just a tad over 5.  So that suggests an 5-ply search would execute given those constraints. That would be how many plys we might get to in 1 minute...  but, let's be realistic - the # moves/ply is probably going to be higher (though I can constrain it), and there will be other overheads. But I suspect I might just be able to push for a 5-ply search in 1 minute.  That'd be workable and might play an workable game. Not great, but workable.  Hope I don't have my calculations wrong. Please correct me if I do.

    DEFINE_SUBROUTINE alphaBeta

                inc currentPly
                lda currentPly

    ; Do we bottom out here?

                cmp #MAX_PLY+RAMBANK_PLY
                beq .bottomOut
                sta SET_BANK_RAM                    ; self-referential weirdness!

                lda sideToMove
                eor #128
                sta sideToMove

                jsr NewPlyInitialise

                lda currentPly
                sta SET_BANK_RAM
                ;jsr GenerateMovesForAllPieces

        ; Perform a search

            lda #7
ploop       pha

                jsr alphaBeta

            pla
            sec
            sbc #1
            bne ploop


        ; check the results, update scores and move pointers
        ; and return vars to expected

.bottomOut      lda sideToMove
                eor #128
                sta sideToMove

                dec currentPly
                lda currentPly
                sta SET_BANK_RAM                    ; self-referential weirdness!

                rts

 

[+Andrew Davie]

Definition: a 1ply search means:

generate moves for position, iterate all moves { make move, EVALUATE position }

If we trim (manually) or via alpha-beta the average # moves/ply to 7, then....

 

1 ply = 7 moves made ... generate moves for position, iterate all moves { make move, EVALUATE POSITION }

2 ply = generate moves for position, iterate all moves { make move, generate moves for position, iterate all moves { make move, EVALUATE POSITION }}

 

 ~= 50 nodes

2 ply ~= 400 nodes

...

6 ply = 823543 nodes

Let's say 1 million nodes generated during the 6 ply search. How long will that be?

 

A five ply search, generating ALL moves for the start position at every node, and then iterating 7 moves on each ply... takes just on 12 seconds (tested). That's not doing any board evaluations, or actual moving. Just generate moves, loop for 7, recursive call.  That's not too bad, actually - says that the move generation code is reasonably efficient, as it's being called 16806 times in ~12 seconds. That's an average of around 850 cycles (remember, this is for the opening position, which has far fewer moves than normal).  18 moves, actually. Which puts it at about 50 cycles per single move generated. That's pretty good, a bit low because of the situation.  This seems about right, from testing. I see about 3000 cycles for complex positions. I can certainly generate all moves for any position in < 3200 cycles, absolutely sure of that. All these figures are just helping me settle on expectations and what I need to vary to get improved performance. I expect the evaluation code to take let's say 200 cycles (it's incremental), and the movement/takeback code another 200.  Let's say 500 cycles/move. So we're now looking at 550 (but let's take that up to 750 for estimation) cycles/move. 

 

So, 6 ply --> 1000000 nodes * 750 cycles / 1190000 (CPU)

 = 630 seconds.

That's 10 minutes, give or take.

That's pretty reasonable for a 6 ply search.

 

5 ply --> 117649 nodes * 750/1190000

 = 74 seconds

 ~= 1 minute

 

So, 5 ply it is. That seems very do-able.

 

5 ply

generate moves (#1)
for all moves {
    make move
    generate moves (#2)
    for all moves {
        make move
        generate moves (#3)
        for all moves {
            make move
            generate moves (#4)
            for all moves {
                make move
                generate moves (#5)
                for all moves {
                    make move
                    EVALUATE BOARD
                }
            }
        }
    }
}

Just for the record, a 10-ply search using these figures would take just over 14 days