Chess

[+Al_Nafuur]

It's your work and it's up to you.

 

I would prefer two white vertical lines moving together (set 1 bit in mirrored PF2 and ROR) as indication for the AI working. Your THINKBAR8 version in white would be alright too.

But please not the full action and all colors, unless you consider an opponent with an epileptical attack as a victory for the AI.

Edited April 27, 2020 by Al_Nafuur

[+Andrew Davie]

And now, the solution that will hopefully make everyone happy.

I've put the thinkbars on the joystick button. If you want to see them, press/hold the button.

This is now a feature (look at the brain thinking) rather than an annoyance.

So, easy to check if it's still thinking - press the button.

 

 

chess20200428_3pq6.bin

[+Nathan Strum]

6 minutes ago, Andrew Davie said:

And now, the solution that will hopefully make everyone happy.

I've put the thinkbars on the joystick button. If you want to see them, press/hold the button.

This is now a feature (look at the brain thinking) rather than an annoyance.

So, easy to check if it's still thinking - press the button.

Could make for a good AtariVox opportunity, too. Press the button, the game belittles you: "Don't bother me pathetic human, can't you see I'm thinking!?"

[Keatah]

16 minutes ago, Andrew Davie said:

So, easy to check if it's still thinking - press the button.

And it seems to work very well.

[+Andrew Davie]

The "regular" alpha-beta search (implemented in the function "negaMax") does the majority of the "thinking" in the game. Or, so I thought!  Coupled to that is the "quiescence" search, which only kicks in when the last move in the current branch of the search tree ("a leaf node") is a capture. The idea is, the quiescence search keeps searching while we have a tit-for-tat capture situation happening. So it knows if it takes your pawn with its queen, that it will immediately lose its queen because you had that pawn defended.

So in the naming scheme I've occasionally been using, I add a suffix like "3pq6" which is basically shorthand for a 3-ply search (3p) with a 6-ply quiescence search (q6) tacked on the end. That means when it does that queen capture, it will see 6 more captures deep from there and really know if the capture exchange was worth it. Now that's all been working for a while, and I thought it was an occasional thing that didn't add much to the search cost. However...!

 

In this version, I have coloured the "thinkbars" (press the button when computer is thinking).  Normally grey during the alpha-beta search, and with colours for the quiescence search. On the first move or two, just occasional colours to be seen. But in the midgame -- colour everywhere. This means that a LOT of time is being spent doing quiescence searching. Now this isn't wrong, it's just unexpected, and interesting!

I guess the thinkbars are truly a visualisation of what the game is "thinking" after all. I learned something about its operation that I didn't really know before.  Anyway, here's yet another version of the thinkbars, with the colouring as described. Play a few moves into the midgame, then have a peek. I've tried, too, to make the thinkbars visually intersesting, with time-based patterning and not just vertical lines.
 

chess20200428_THINKBAR9.bin

[CrazyChris]

On 4/27/2020 at 8:31 AM, Andrew Davie said:

CANNOT BE DONE

I thought the 2600 is all about ball and missile graphics? Couldn't you just place

one of these in the corner of the screen and have it flash?

[+splendidnut]

15 minutes ago, CrazyChris said:

I thought the 2600 is all about ball and missile graphics? Couldn't you just place

one of these in the corner of the screen and have it flash?

No.  The Atari 2600 TIA chip only keeps track of a single horizontal line.  It relies completely on the programmer to keep track of the vertical signal and to initiate the Vertical SYNC (VSYNC) signal at the appropriate time to have a steady television frame.  In this particular case, he is not, because the CPU is spending ALL of its time thinking about chess moves.  While the computer is thinking, the video will roll on an old CRT TV.

 

To implement a simple thing as a blinking cursor would require a ton of work.  Andrew would have to utilize the RIOT timers AND insert a ton of code to check them.  Ton of effort for little reward.

 

I think his solution here is perfect as is.  Deal with it. 

[CrazyChris]

1 minute ago, splendidnut said:

No.  The Atari 2600 TIA chip only keeps track of a single horizontal line.  It relies completely on the programmer to keep track of the vertical signal and to initiate the Vertical SYNC (VSYNC) signal at the appropriate time to have a steady television frame.  In this particular case, he is not, because the CPU is spending ALL of its time thinking about chess moves.  While the computer is thinking, the video will roll on an old CRT TV.

 

To implement a simple thing as a blinking cursor would require a ton of work.  Andrew would have to utilize the RIOT timers AND insert a ton of code to check them.  Ton of effort for little reward.

 

I think his solution here is perfect as is.  Deal with it. 

It might be best, just to blank the screen, to speed up thinking time.

[+Andrew Davie]

17 minutes ago, CrazyChris said:

I thought the 2600 is all about ball and missile graphics? Couldn't you just place

one of these in the corner of the screen and have it flash?

Yes, that would be possible IF there was a screen being drawn.

But, in this situation there is no screen being drawn. The CPU is busy calculating the computer's next move. So what normally would happen (that is, the CPU drawing the screen) doesn't happen anymore. When you get to that situation, the TIA (graphics chip) is still happily feeding scanlines to the TV - but an infinite number of scanlines. No "frame".  And by "frame" I mean the various control signals necessary for the TV to understand when to enter the vertical blank (and retrace the beam to the top of the screen), and when to blank the screen. So, with no frame information, the TV has absolutely no idea where each scanline should be. Or, more particularly, it doesn't know when to reset to the top of the screen. Without any reset to top of screen signal, the TV effectively gets malformed frames. In this case, a bajilion scanlines instead of 276.  So the TV just keeps going on its merry way until (and this is TV dependent) the hardware in the TV effectively wraps to the top of the TV again. This will differ based on TVs, but for the sake of argument let's say on TV1 it's after 400 scanlines, and on TV2 it's after 305 scanlines. There is no standardisation here. LCD TVs will probably just go bluescreen because they don't detect a frame. Just scanlines. Lot of them.
So, in this scenario, with the CPU out to lunch, so to speak, but the TIA still pumping out scanlines, I was looking at what I can change on the TIA (even though I don't know where (vertically) on the screen the electron beam may be).  And the things that I can change are the graphics sent for playfield and ball and sprites and missiles. Yes. But remember, I can just change their pixel data. I don't know (or have control over) the vertical position on the screen. On one TV it may be at the top, while at exactly the same time on another TV it might be at the middle.  And furthermore, since my code takes a variable amount of time (anything from, say 500 cycles to 2500 cycles) between those updates I can make to the TIA... then I am no longer able to tie to the 76 cycles required for forming a TV picture anyway.  In other words, I simply have no control over "when" things go to the TV, or any way to form a proper TV frame. All I can control is the pixels and colours. But not when.  It's like being on a merry go round, you have cans of paint you can open the lids to let paint fly out. But you don't know how fast the merry go round is spinnning, and you don't know when it's at the "start position". Given those constraints, can you form a picture on a wall from the paint splashing out of the cans?  Well, a loose analogy admittedly, but the point being, it's simply not possible to position something in a corner of the TV. Because, and this is the crucial bit... in this situation there is no corner of the TV. It is a meaningless concept.

 

[CrazyChris]

2 minutes ago, Andrew Davie said:

Yes, that would be possible IF there was a screen being drawn.

But, in this situation there is no screen being drawn. The CPU is busy calculating the computer's next move. So what normally would happen (that is, the CPU drawing the screen) doesn't happen anymore. When you get to that situation, the TIA (graphics chip) is still happily feeding scanlines to the TV - but an infinite number of scanlines. No "frame".  And by "frame" I mean the various control signals necessary for the TV to understand when to enter the vertical blank (and retrace the beam to the top of the screen), and when to blank the screen. So, with no frame information, the TV has absolutely no idea where each scanline should be. Or, more particularly, it doesn't know when to reset to the top of the screen. Without any reset to top of screen signal, the TV effectively gets malformed frames. In this case, a bajilion scanlines instead of 276.  So the TV just keeps going on its merry way until (and this is TV dependent) the hardware in the TV effectively wraps to the top of the TV again. This will differ based on TVs, but for the sake of argument let's say on TV1 it's after 400 scanlines, and on TV2 it's after 305 scanlines. There is no standardisation here. LCD TVs will probably just go bluescreen because they don't detect a frame. Just scanlines. Lot of them.
So, in this scenario, with the CPU out to lunch, so to speak, but the TIA still pumping out scanlines, I was looking at what I can change on the TIA (even though I don't know where (vertically) on the screen the electron beam may be).  And the things that I can change are the graphics sent for playfield and ball and sprites and missiles. Yes. But remember, I can just change their pixel data. I don't know (or have control over) the vertical position on the screen. On one TV it may be at the top, while at exactly the same time on another TV it might be at the middle.  And furthermore, since my code takes a variable amount of time (anything from, say 500 cycles to 2500 cycles) between those updates I can make to the TIA... then I am no longer able to tie to the 76 cycles required for forming a TV picture anyway.  In other words, I simply have no control over "when" things go to the TV, or any way to form a proper TV frame. All I can control is the pixels and colours. But not when.  It's like being on a merry go round, you have cans of paint you can open the lids to let paint fly out. But you don't know how fast the merry go round is spinnning, and you don't know when it's at the "start position". Given those constraints, can you form a picture on a wall from the paint splashing out of the cans?  Well, a loose analogy admittedly, but the point being, it's simply not possible to position something in a corner of the TV. Because, and this is the crucial bit... in this situation there is no corner of the TV. It is a meaningless concept.

 

Thanks for explaining.

[+Andrew Davie]

1 minute ago, CrazyChris said:

It might be best, just to blank the screen, to speed up thinking time.

But... that's what I am doing.  The time required to "draw" the thinkbars is negligible. Even in an extremely complex position, with a search taking in the order of 10 minutes, then the thinkbars (and only if you had them visible the whole time) would cost an additional second or two of processing time, give or take. Negligible.

[CrazyChris]

3 minutes ago, Andrew Davie said:

But... that's what I am doing.  The time required to "draw" the thinkbars is negligible. Even in an extremely complex position, with a search taking in the order of 10 minutes, then the thinkbars (and only if you had them visible the whole time) would cost an additional second or two of processing time, give or take. Negligible.

Understood.

[+Andrew Davie]

OK, once more unto the breach. I've put back in "check" handling, and also done a bit of analysis so I understand more why the system makes "poor" moves that it does when check is imminent.
 

Firstly, check handling:  check is only detected when a king is captured. That is, you have to wait until the next side's turn to see if the king is in check. This means that you can't know a move is illegal until you actually make it. So in the normal alpha-beta search, we're recursing anyway so the trick is, how to correctly handle things when the "in check" flag is set. Now this flag is set just after we generate moves for a side and we're sorting the capture moves to put them "up front" (to make the alpha-beta pruning more efficient). If one of those captures is the opponent's king, we set the "flagCheck" variable to non-zero.  Now in the negamax (recursive) function that does that call to "generate moves", it immediately looks at that flag. And if it is non-zero, then the function simply (and this is all it does) returns.

Now, back "up" a level we're at the point where the same function has just called itself (via "jsr negamax").  We know that if the opponent could capture our king (i.e., we're in check), then the "flagCheck" variable will be non-zero.  So, have a look at that, and if it is non-zero, then the move we just made was illegal (king could be captured after the move), so the move cannot be considered as a legal move. At that point I set flagCheck to zero, and simply branch to the next move in the movelist.  In other words, any move which results in my king capture is never considered as "the best" move. It's effectively ignored.

I've tested this with a simple test board position. It seems to work better. I've not seen any of those illegal moves happening when the king is in check, so once more unto the breach, dear friends...

Now I've included two versions of a simple "mate in one" test bed so I can explain something. There's a 3ply version (3pq6_TEST) and a 4ply version (4pq6_TEST). Try loading each of those, and for your first move, move the queen towards the rook.  Now what's the computer to do here?  In fact the only move, I think, is to move the pawn in front of the king down one square. That is, G7-G6. This prevents immediate mate with QxP on G7, or Q to any back row square (mate). In both cases the king has an escape to G7.  Now, the 3ply version doesn't see this. The 4ply does. Why?

 

And here we come back to the "delayed" detection of check. That is, not seeing check until the opponent lists moves. So in the 3ply version, consider you've just moved the queen towards the rook. The computer lists all moves - king can move two squares (H8, F8) and the pawns can all do their one or two move opening.  As the search progresses, each move is tried, in turn with the replies to each of those, and then the replies to each of those. But consider, let's say the computer tries pawn F7-F5. Good move, because the square it now occupies and attacks are valuable. But the reply is QxP. Well, what does the computer see after that?  Firstly KxQ but that's nixed by the quiescence search which now simply flags that as an illegal move because... king capture. So it won't consider KxQ as a response. But how about K-H8 or K-F8.  Yes, both these are illegal because the king is in check (from the Q) but hey, we don't detect check until the next ply. So, next ply... oh but hang on, we're at the bottom already - a 3 ply search!  We did F7-F5, QxP, K-F8 -- and never got a chance to "see" the checkFlag.  So according to the 3ply this happens to be the best move (F7-F5) because although we lose a pawn, we are getting good position, and all other moves (Q-8th rank) lead to a detectable checkmate, or are worse in position.

Now, consider the 4-ply. It gets to the same situation, but when it tries K-H8 or K-F8 after QxP, it then goes to the next ply, sees QxK and thus invalidates the moves F8, H8 for the K. In fact after QxP it has zero moves available.  In fact the only good move that gets detected is G7-G6 because that's the only one (I think) that doesn't lead to mate on the very next move or involve loss of material without compensation (QxG7).

 

And thus, in these situations 3ply (with delayed detection of check) can be extremely weak.  Even with quiescence search, because we can't know that the last move made by the K (NOT a capture!) is illegal, until the next ply. And in this situation we've run out of plies.  So, this is effectively why my goal is to have a 4ply search running quickly enough. We shall see.

Anyway, have fun trying checkmates and stalemates in these. They should be "processed" OK. That is, green background for stalemate, and red background for checkmate. If the computer manages to beat you in this position (shame on you!) I believe it will simply get to a point where there are zero moves available for you (both in checkmate/stalemate) but you won't see any indication of the win/draw other than not being able to select a move. Edit: since you have no king, you can only "lose" by losing all your pieces.

Finally, a full version 4ply version (4pq6) is added for your enjoyment. This should actually be quite difficult/challenging. If anyone can actually be bothered waiting for it to move. You can always press the button to watch it thinking, of course, and if you're in a cheating mode then don't forget SELECT will force a computer move, though it's obviously going to be an inferior one.


 

 

chess20200429_3pq6_TEST.bin chess20200429_4pq6_TEST.bin chess20200429_4pq6.bin

Edited April 28, 2020 by Andrew Davie

[Mr SQL]

10 hours ago, Andrew Davie said:

The "regular" alpha-beta search (implemented in the function "negaMax") does the majority of the "thinking" in the game. Or, so I thought!  Coupled to that is the "quiescence" search, which only kicks in when the last move in the current branch of the search tree ("a leaf node") is a capture. The idea is, the quiescence search keeps searching while we have a tit-for-tat capture situation happening. So it knows if it takes your pawn with its queen, that it will immediately lose its queen because you had that pawn defended.

So in the naming scheme I've occasionally been using, I add a suffix like "3pq6" which is basically shorthand for a 3-ply search (3p) with a 6-ply quiescence search (q6) tacked on the end. That means when it does that queen capture, it will see 6 more captures deep from there and really know if the capture exchange was worth it.

 

59 minutes ago, Andrew Davie said:

Finally, a full version 4ply version (4pq6) is added for your enjoyment. This should actually be quite difficult/challenging. If anyone can actually be bothered waiting for it to move. You can always press the button to watch it thinking, of course, and if you're in a cheating mode then don't forget SELECT will force a computer move, though it's obviously going to be an inferior one.

Fantastic! I don't mind waiting and will give you my feedback on this one after playing Today - very awesome the black screen is back that lets me think more reflectively about the game - excellent option to check the depth of the search with the button, I will use that occassionally and time some of the moves, but I will not use the SELECT to cheat during the game.

 

Some observations on the "quiescense" algorithm from your description - it sounds like the CPU will miss the need for a deeper search during a 3p when the 3p encounters moves that are just setting up to do a capture, or a forced capture that will happen one or two moves deeper than the initial search and not trigger the quiescence.  

 

[+Andrew Davie]

 

11 hours ago, Mr SQL said:

Some observations on the "quiescense" algorithm from your description - it sounds like the CPU will miss the need for a deeper search during a 3p when the 3p encounters moves that are just setting up to do a capture, or a forced capture that will happen one or two moves deeper than the initial search and not trigger the quiescence.  

 

 

It's all about having an *extremely quick* way of knowing if you should search deeper. Typically, quiescence searches (including this one) simply say "if there was just a capture, search deeper". Deciding if there's a forced capture one or two moves in the future is the job of the normal alpha-beta search. The problem is, instead of a "normal" 5-6 ply, this engine is only capable of 3-4 ply. At this stage.

 

[Mr SQL]

7 hours ago, Andrew Davie said:

 

 

It's all about having an *extremely quick* way of knowing if you should search deeper. Typically, quiescence searches (including this one) simply say "if there was just a capture, search deeper". Deciding if there's a forced capture one or two moves in the future is the job of the normal alpha-beta search. The problem is, instead of a "normal" 5-6 ply, this engine is only capable of 3-4 ply. At this stage.

 

I played two games of Chess against the last 4-ply and the engine is playing really well and was fast, most moves under 5 minutes

 

Here are some notes on the games and a pic from my Kodak:

 

I made a blunder and lost the first game just as it got interesting  - in the second game, the engine responded to my classic d2-d4 opening by moving it's Knight, allowing me to chase the Knight for several moves with my pawns gaining position. In the screenshot the Engine just took my pawn with a Bishop (red hilight) using the pawn to capture would have been better but B1-B3 is the next move either way; an opening book to prevent loss of initial positioning or an algorithm to weigh position lost from wasted moves could improve gameplay further but the 4-ply engine is challenging right now! I have to take my time thinking about my moves.

 

I would love to try a 5-ply with this version of the engine if the CPU can move within 20 or even 30 minutes!   

 

[+Andrew Davie]

5 minutes ago, Mr SQL said:

I played two games of Chess against the last 4-ply and the engine is playing really well and was fast, most moves under 5 minutes

I would love to try a 5-ply with this version of the engine if the CPU can move within 20 or even 30 minutes!   

 

 

Thank you for the feedback; I value it.

I am struggling with ROM space. Really struggling. Never say never, but for now no book.

I do have a bit of a philosophical objection to books in computer chess, anyway.
Here's a 5-ply version for you. I don't know how long it will take, but given the alpha-beta branching of about 8.5 then it would be about that many times the average 4-ply move time. So, say 40 minutes? Let me know, if you try it!
 

chess20200429_5pq8.bin

[+Andrew Davie]

Although I'm very, very familiar with 3E bankswitch scheme, it does have some serious limitations.

I'm thinking about using and/or designing a new bankswitch scheme that lets me get around those. I am starting to feel that "chess" is a good reason. There are some things I'd like to add and I'm just getting seriously short of ability to do that, due to those limitations.

 

[devwebcl]

On 4/28/2020 at 10:48 AM, Andrew Davie said:

Finally, a full version 4ply version (4pq6) is added for your enjoyment. This should actually be quite difficult/challenging. If anyone can actually be bothered waiting for it to move. You can always press the button to watch it thinking, of course, and if you're in a cheating mode then don't forget SELECT will force a computer move, though it's obviously going to be an inferior one.

 

 

chess20200429_3pq6_TEST.bin 64 kB · 7 downloads chess20200429_4pq6_TEST.bin 64 kB · 5 downloads chess20200429_4pq6.bin 64 kB · 9 downloads

 

Cool feature the button to show that 2600 is thinking

[Voxel]

4 hours ago, Mr SQL said:

moving it's Knight, allowing me to chase the Knight for several moves with my pawns gaining position

I do like moments like that.

 

4 hours ago, Mr SQL said:

I would love to try a 5-ply with this version of the engine if the CPU can move within 20 or even 30 minutes!

If there was anyway we could know it had a strong next move, we could hit select to force a move without feeling we've compromised it's play.  So far I've held back from using the feature because it's missing best move indicator.

 

3 hours ago, Andrew Davie said:

I'm thinking about using and/or designing a new bankswitch scheme

I'm sensing a game changer on the horizon...

 

 

[Keatah]

Not sure of the size limits of Encore or Melody. But weren't there some demos or that Hi-Fi Zaxxon that used 128K or 512K? I'm not opposed to seeing and uber-big rom sizes used here.

[+Andrew Davie]

2 hours ago, Keatah said:

Not sure of the size limits of Encore or Melody. But weren't there some demos or that Hi-Fi Zaxxon that used 128K or 512K? I'm not opposed to seeing and uber-big rom sizes used here.

The limits I am running into are not how much ROM or RAM I have, but how much I need to fit into an individual ROM bank.

In particular, 3E bankswitch scheme puts limits on access between banks. It has a fixed 2K ROM area and a switchable 2K ROM/1K RAM area.

To access the board, for example, which is in a switchable RAM area, I either have to access it FROM that RAM area, or from the fixed bank. Full stop. If I want to access from a different, switched ROM bank, then that access needs to go through the fixed bank via a "helper" function. But that fixed bank space is limited in side, and it's already chokka with stuff. For example, move generation writes data to movelists. For speed, most of the piece move code is in the same bank as the movelists. But the code to generate moves are too big to all fit into that bank, so the only other place they can go is again, in the fixed bank.  So, it's a continual cycle - add functionality, then try and squeeze more bytes out of the fixed bank, or the move bank.I've just been through another cycle of "optimise" and have 31 bytes free in the fixed bank, and 43 bytes in the ply bank, and 39 bytes free in the move bank. The ply bank is the one that does the negamaz search, and holds data for the tree traversal. But again, not enough room in the ply bank, so the quiescence search was too big for that, so it has to go in the fixed bank (because it needs to access data in the ply bank, and be quick).  There are many of these issues, and the space in the fixed bank becomes incredibly precious because everyone needs it, so to speak.

I'm currently looking at alternate bankswitch schemes. DASH looks promising to me. The irony is, I seem to have been a major part of the design of that scheme, and because it hasn't been used - and because he thinks it's not a good design - @Thomas Jentzsch has informed me it's planned to be removed from Stella in the next iteration. What a coincidence. I can't see much wrong with it, though, and I'm tempted to try it.

 

[+Andrew Davie]

4 hours ago, Voxel said:

If there was anyway we could know it had a strong next move, we could hit select to force a move without feeling we've compromised it's play.  So far I've held back from using the feature because it's missing best move indicator.

This would only be the case if the "strong" move is a capture. Captures are processed first.

If not a capture, then what you think of as strong will not be sorted, and thus appear pretty much randomly in the move list (currently). That means that any "force move" will be luck of the draw, basically. The best of what's been processed so far would be another way of saying it, if the order of moves are picked out of a hat.

[AW127]

One question to the strength of the Chess engine. Is it technically possible, that this engine can exploit the possibilities of the melody-board to play a stronger chess, with more search-depth for example and so on? I mean an engine with a higher ELO-rate at last?

 

Edited April 29, 2020 by AW127

[+Andrew Davie]

2 hours ago, AW127 said:

One question to the strength of the Chess engine. Is it technically possible, that this engine can exploit the possibilities of the melody-board to play a stronger chess, with more search-depth for example and so on? I mean an engine with a higher ELO-rate at last?

 

"this engine" no, as it is written in 6502.

But I did consider, and it is possible, to use ARM code to write an alternate engine which would be much stronger/faster.