Chess

[+Karl G]

Are you no longer doing an ARM-based backend, or are you doing both?

[+Andrew Davie]

1 minute ago, Karl G said:

Are you no longer doing an ARM-based backend, or are you doing both?

I'll do the 6502 one and see how things go.

ARM is not out of the question. One option is to allow multiple choices.

But for now, just 6502. I might be sick of it by the time I get that working.

 

[5x7]

13 hours ago, Andrew Davie said:

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

 

I appreciate you sharing this!

[+Andrew Davie]

Here's an interesting thought; if a 6-ply search can be restricted to analysing just one million nodes, then every single cycle saved in the move generation code will make the computer one whole second faster in choosing its move!

[+nanochess]

Never tested advanced move generation techniques with old 8-bit processors, but there are Chessmaster for Z80 CPU and Novag Super Constellation for 6502 going around the 2000 ELO points mark (more than enough to defeat the typical coffee-shop player like me )

 

But I know the optimization techniques, so some suggestions:

* hash-table, allows to avoid re-searching trees that come to the same position. Not feasible without less than 16K of dedicated RAM.

* null-move, doesn't play and "sees" what the enemy can do, so it can prune trees.

* try all captures first, reduces greatly the size of tree.

* quietness analysis, if it is in check it keeps analyzing a further ply. This avoids pushing checkmate out of search horizon.

* follow recaptures, this avoids pushing captures out of search horizon.

[+sramirez2008]

On 1/27/2020 at 7:16 AM, Andrew Davie said:

I don't think there's a large audience for puzzle games, in general.

Our family loves puzzle games.  My younger son also played chess for school and we would all love to see the game completed and on a cart.  This could will be the definitive chess game for the 2600.

 

[+sramirez2008]

Tested the latest ROM on my UnoCart and it runs and looks good on my CRT.

 

 

[+Andrew Davie]

3 hours ago, sramirez2008 said:

Tested the latest ROM on my UnoCart and it runs and looks good on my CRT.

 

 

IMG_0159.MOV

Thank you - yes, very pleasing to the eye.  It's interesting, because I guess I'm quite used to seeing/interpreting the display now - but to me it looks very easy to recognise. I don't get that 'stripey' or 'blocky' feeling at all. I just get "low resolution but good". Yet I do understand that for some this looks awful. So I'm hardly objective, I guess. But I like it, and happy to see it looking good on an actual CRT. Thanks again.

I've converted/copied the video to a format that can will play on most browsers...

On a side note, the forums appear to have been changed so that you no longer see the number of downloads shown under a file. I really miss this feature, and wonder why it's been taken out.  Yes I know we (sometimes?) have a tool-tip with that value, but that's not nearly the same.
 

 

 

Edited February 1, 2020 by Andrew Davie

[+Andrew Davie]

12 hours ago, nanochess said:

Never tested advanced move generation techniques with old 8-bit processors, but there are Chessmaster for Z80 CPU and Novag Super Constellation for 6502 going around the 2000 ELO points mark (more than enough to defeat the typical coffee-shop player like me )

 

But I know the optimization techniques, so some suggestions:

* hash-table, allows to avoid re-searching trees that come to the same position. Not feasible without less than 16K of dedicated RAM.

* null-move, doesn't play and "sees" what the enemy can do, so it can prune trees.

* try all captures first, reduces greatly the size of tree.

* quietness analysis, if it is in check it keeps analyzing a further ply. This avoids pushing checkmate out of search horizon.

* follow recaptures, this avoids pushing captures out of search horizon.

 

Thanks for the comment.

I am familiar with most of these.

 

1) hash-tables - I don't think I'll be going there. It is, after all, a '2600 and it's never going to be a great chess-player at 1.19MHz 6502.

2) null-move, and 3) captures-first.  These, as you say, prune the search tree. In fact, it's very worthwhile spending EXTRA time at any ply doing calculations such as sorting the available moves in some order such as "captures first" or "last refutation move first" and similar. Perhaps even sorting by the next ply position (which is what I think you may mean by "null move"). The point being, we want to have the BEST moves first, because these lead to early alpha-beta cutoffs and thus dramatically reduce the search tree "width".

4) Quietness I know as "quiescence" but I think it's the same thing. I can't detect check until the NEXT ply, but quiescence keeps deepening the search until there are no captures which is almost the same thing.

 

So, for those reading and not following what alpha-beta pruning is, I'll try and explain.

 

 

Let's say I have some function which returns a "score" for any position. And that score is positive if I'm winning, and negative if I'm losing. The more positive it is, the better I'm doing.

 

Now, I have (say) 10 moves to choose from.

So, I try the first one, and then my opponent has the same problem. Say, 20 moves to choose from, with negative scores being better for him, positive worse for him. So, he tries the first one... and repeat... now two plys down my side is again looking at the moves (which are in reply to the moves in reply to the move I initially am trying).  That can go quite deep. But let's say we go 5 ply deep. At the BOTTOM (or leaf-node) of the tree, instead of trying moves, we just evaluate (score) that position.  It might be +10 - so, that leaf position shows me in a very slightly better position than my opponent.  Now the opponent tries the next move, and the score for that might be +5. Well, that's better for HIM, so when he's in the position where those two moves are available, he's going to choose the +5 one.  If we keep going for moves available to him we might find a node where the best score (for him) that can be found is about -200. Well, that sucks for me.  But if we get to the position where he has a choice, we now know that he CAN choose a move leaving the score at -200.  So that's the score for that NODE. All of the moves that eventuate from that node, doesn't matter what they are, we know he can end up choosing one that leaves the score at -200.

Now, step back a level. Now I know that choosing that branch of the tree will at worst for me score -200. It's possible that the opponent might not choose the optimal move for him, but I do know that if he does, I will be left with a position value of -200.  So I try the next move, and I see that the score I can achieve (given the opponent has chosen the best move for him) might be -100. Well, that's still bad for me, but not as bad as -200. In fact, given the two choices so far I would certainly choose the current move (-100) than the first (-200). It leads to a better position.

Now, let's consider the next move available to me... I test that move, and then it's the opponent's turn.  On his first move check, I see he can get (say) a score of -500. That' dreadful for me - and in fact, I know already that my opponent could choose that. So why should I choose the move that lets the opponent get -500?  I already KNOW I can choose a move that at worst (for me) leads to a value of -100.  So at this point, we don't even BOTHER checking any of the other moves the opponent has. We already know that particular branch is much worse for me. So we PRUNE it - don't even bother looking at any more of the moves for the opponent, because we know no matter what they are, the score for the node will at BEST be -500 for me. And that's not even anywhere near -100 which I know I can get to. So, that's an alpha-beta prune right there.

We come back to the level where I'm (at best) so far able to achieve -100.  So we check another move, and say the score might come back at even better - +100 for me. Yay!  But hey, on the previous ply, the opponent was moving and let's say he so far knows that the best move for him gets a score of -50.  Good for him. Slightly. But now, on the next ply, I've just discovered a move that gives me +100. Well, he's hardly likely to choose this branch, giving him the best score of +100 (good for me, bad for him), when he already has a move that gives -50 (good for him, bad for me). So again, another alpha-beta prune and we go back a ply and abort any more checking of moves on this ply.
And that's basically how it works. It doesn't matter how deep we are in the search tree. We can always determine if there's an early-exit from checking moves and responses and more moves and responses...  by checking if there's an alpha-beta cutoff at any of the branches.  And this propogates up the tree, so to speak - we are doing pruning at all levels.

Now, a typical branching factor of chess is about 30, give or take. This means from any position we are likely to be looking at about 30 possible moves. So the number of nodes increases exponentially... 30^n, basically, where n is the depth. That pretty quickly builds up. But alpha-beta pruning, when optimised, can reduce that to about 7 moves/ply.  So, 7^n - which is obviously hugely different.

So, we want to reduce the branching factor - and alpha-beta pruning does a great job of this. But it gets even better if we can SORT the moves so that "good" moves are early. Because "good" moves tend to produce dramatic changes in the score/valuation. Things like captures. If we put the captures first in a list of moves we're checking, then we are much more likely to find "good" scores early in the search, leading to early alpha-beta pruning and thus reducing the size of the search tree dramatically.

And because it's sooooooo costly to have more moves/ply, it's actually worth spending a LOT of time doing a decent ordering of the moves. So not just "captures first" but also things like recording moves that caused alpha-beta cutoffs and perhaps putting them early in the sorted move list, and other factors that I only dimly remember. But anything that's "good" should be early, as it saves the # nodes searched.

It's a bit ironic really. To put the "good" moves first is a good idea, because it reduces the search tree. But to know which moves are "good" is the whole point of the search tree - you traverse it to find the "good" moves. If you already know which are "good" then why do you search the tree?  And the answer is, you don't know which is the "best" "good" move - you only have an idea of what might be "good". And sometimes, all the "good" moves are in fact "bad".  

 

 

 

 

 

 

[Omegamatrix]

On 1/31/2020 at 8:57 PM, Andrew Davie said:

It's a bit ironic really. To put the "good" moves first is a good idea, because it reduces the search tree. But to know which moves are "good" is the whole point of the search tree - you traverse it to find the "good" moves. If you already know which are "good" then why do you search the tree?  And the answer is, you don't know which is the "best" "good" move - you only have an idea of what might be "good". And sometimes, all the "good" moves are in fact "bad".  

Searching for good moves sounds a little bit of like a chicken before egg, or egg before chicken kind of thing, eh?

 

I read you post twice to try and absorb it all. Sorting absolutely makes sense to have a better chance of hitting the best solution early on. Loved the talk of logic deciding how to prune the branches. 

[+Andrew Davie]

On 1/30/2020 at 4:04 AM, Voxel said:

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

Thanks for the kind words. Pressure is on!

 

[Voxel]

Oh no, never should pressure be from he with no coding talent.

 

It's best left to let you develop it in your methodical way.

[+Andrew Davie]

A screen full of goodies!

Sokoboo top left, Boulder Dash top right, and Chess at bottom.

 

 

I'm currently working on the display, freeing up some space and reorganising things so that I can put sprites on top of the chessboard. I'll be using a sprite to highlight the piece you want to move, and to where you want to move it. I know it's possible - putting sprites on top of this sort of display - but I had to peek at the Sokoboo/BD code to remind myself how to fit it all in. I have a bit of reorganising to do.

Meanwhile, @Thomas Jentzsch has just updated Stella with a request I made - a cycle count displayed in the debugger which gives cycles since last stop. This is great, as it lets me get some accurate cycle counts on some of the code. Specifically, move generation. I've seen the occasional 800 cycle-plus count for generating moves for a single piece (for example a queen with many moves available). This new debugger assist will allow me to trim some cycles from that code, hopefully.

 

 

Edited February 4, 2020 by Andrew Davie

[+Andrew Davie]

I've done some reworking of the image/shape formats to allow me to optimise the screen drawing. Essentially, "unrolling" part of the draw display means that I have more cycles/scanline free to do sprite stuff. That's working now, but took quite a bit of fiddling with tools/utilities and formats. I also took the opportunity to mangle the graphics so that I can now flash a piece, without affecting the square it overlies.  So for example, whereas before when a piece was about to move, the whole piece/square would flash on/off... now only the pice flashes on/off and the square remains unaffected. I think it's an improvement, though nobody would have noticed, I think, unless I mentioned it.
Now I've done the necessary changes unrolling the draw kernel, I have "plenty" of room to get my sprite draws in for the move cursor, so that will come next, I'm sure.
 

[+Andrew Davie]

Updated binary for anyone wanting a look-see...

 

chess_20200205.bin

[Goochman]

Andrew - I did notice the blue squares going dark on selection from previous videos.  Wasnt that big of a deal in the context of what you've been able to pull off here but I can say the new flash routine looks great.

[+Andrew Davie]

The unrolling of the kernel has been optimised a bit and that's allowed me to get the two sprite shape draws into each row. Here I'm just displaying a solid sprite, but it's changeable of course. The idea is that there is a red and a green selector to highlight a square. You will only have one of each on the screen. First, you move around the green one to the piece you want to move, press the button. Then the red one appears and you move that around to the destination square (while the green one stays still).  So, at the moment we see a band along the entire screen - that's because every row is drawing the selector squares. I just need to enable/disable based on the row you're currently "at". 

[+Andrew Davie]

Here's a short vid of rudimentary selection-cursor movement. I'm just moving the green selection square around the board with the joystick. I'm avoiding column 0, as the sprite positioning currently borks when it's there
 

[+Propane13]

Hello!  I'm really liking watching this project come along.

 

I have a very small nitpick on the graphics.  I'm actually not a huge fan of the top of the bishop-- I think it looks a little out of place.  From afar, it appears more to be a floating grey line above the piece instead of a shadow connected to the piece.  I think it may look better without that single line, and would be curious to see what that would look like as a comparison.

 

I know, this may be the most useless comment you get all day, but I hope it's at least a tiny bit helpful for polish reasons.  I'm curious if others think it's worth the change, or if it's just me.

 

Good luck with the project, and I'll keep following your progress.

[+Andrew Davie]

8 hours ago, Propane13 said:

Hello!  I'm really liking watching this project come along.

 

I have a very small nitpick on the graphics.  I'm actually not a huge fan of the top of the bishop-- I think it looks a little out of place.  From afar, it appears more to be a floating grey line above the piece instead of a shadow connected to the piece.  I think it may look better without that single line, and would be curious to see what that would look like as a comparison.

 

I know, this may be the most useless comment you get all day, but I hope it's at least a tiny bit helpful for polish reasons.  I'm curious if others think it's worth the change, or if it's just me.

 

Good luck with the project, and I'll keep following your progress.

Thanks for the comments.

Here are three variations for you to choose from

 

[+Propane13]

13 hours ago, Andrew Davie said:

 

Thank you for rendering a few options; it's nice to be able to have comparisons.

 

From my perspective, the third rendering is the best of the bunch-- it looks the most clean to me.

 

[+Andrew Davie]

2 hours ago, Propane13 said:

Thank you for rendering a few options; it's nice to be able to have comparisons.

 

From my perspective, the third rendering is the best of the bunch-- it looks the most clean to me.

 

How about this one?

 

Not that I really expect anyone to actually play with these, but in any case below is the 'template' from which my tools create the piece shapes. The large one is just to make things easy to see. If you want to load the smaller one into your paint package and have a play... have at it. You should see that there is an 8-colour palette for you to use.  The 8 colours from the palette are converted into 3 ICC scanlines, with bits D2D1D0 (representing palette 0-7) converting into scanlines just like that.  1 line D2, then 1 line D1, then 1 line D0. Depending if the bits are clear or set, then you get an on or off pixel on that line.  The actual colours used at the moment are ...

 

COLOUR_LINE_1 = $4A ("red") = colour #4 in palette
COLOUR_LINE_2 = $2C ("yellow") = colour #2 in palette

COLOUR_LINE_3 = $96 ("blue") = colour #1 in palette

 

The other colours (3,5,6,7) in the palette are from mixes of the above 3

 

I should mention, you do not need to do the blending - all you do is draw in any of the 8 colours available. The tool converts from the 8-colours into the 3 scanline ICC pixel for you. Anything you can draw in those 8 colours will come out fine.

 

Here's a close-up of some pieces as rendered, from the template at the bottom... and an extreme close-up of a bishop, clearly showing the ICC scanlines.

 

 . 

 

Here's a zoomed-in template...

 

And here is the ACTUAL one used for generating pieces  ...

Edited February 7, 2020 by Andrew Davie

[+Andrew Davie]

What you're looking at in this video is the beginnings of move selection for the human player. The (initially red) cursor is controlled by the joystick. Here, I move it around, and what is happening is that the code is checking the move list to see if the square under the cursor has a piece on it that can move (for the current player). If it does then the cursor changes to pulsing green.  I go over a bunch of my pieces, and you can see the cursor is green for all the pawns, and the knights, but no other pieces. When I've found the piece I want to move (in this case, a pawn), I press the button - at which point the pawn starts flashing. Now the cursor is checking for valid squares to which that piece can move to. So initially, it's under the pawn still - and it's red - not a valid square. When I move the cursor around, it remains red except for the two squares to which that pawn can validly move.  I have lots of bugs in this, and buggered if i can figure out how to position a quad-width sprite far left of screen.

As an aside, the fixed bank is very precious in the 3E bankswitch scheme, and I ran out of space. At this point a consolidation was required and I spent quite some time rewriting the code so that things could live in other banks. After a few hours work I had just over 500 bytes free once again. I'll treat them as precious things.
 

 

[+ZeroPage Homebrew]

10 hours ago, Andrew Davie said:

What you're looking at in this video is the beginnings of move selection for the human player. The (initially red) cursor is controlled by the joystick. Here, I move it around, and what is happening is that the code is checking the move list to see if the square under the cursor has a piece on it that can move (for the current player). If it does then the cursor changes to pulsing green.  I go over a bunch of my pieces, and you can see the cursor is green for all the pawns, and the knights, but no other pieces. When I've found the piece I want to move (in this case, a pawn), I press the button - at which point the pawn starts flashing. Now the cursor is checking for valid squares to which that piece can move to. So initially, it's under the pawn still - and it's red - not a valid square. When I move the cursor around, it remains red except for the two squares to which that pawn can validly move.

 

Incredibly intuitive selection mechanism! Makes complete sense to use red and green to show which selections and moves are valid. This will really help beginners understand visually what are legal moves, way better than a "rude beep" for invalid spaces. ?

 

- James

[+Andrew Davie]

Just now, ZeroPage Homebrew said:

 

Incredibly intuitive selection mechanism! Makes complete sense to use red and green to show which selections and moves are valid. This will really help beginners understand visually what are legal moves, way better than a "rude beep" for invalid spaces. ?

 

- James

TY. The next thing I'll be doing is once you select a piece and it starts flashing, I will populate the board with dot-markers to show the legal squares to which that piece can move. Shouldn't take me too long to implement.