Chess

[+Andrew Davie]

Well, much to my surprise I saw that @ZeroPage Homebrew did a brief showing of Chess on the recent show. I do wish you guys would give a heads-up, as I would have fixed a few things. For example, here's a version with the left-column bug fixed. And, much nicer with a computer doing something, anything in opposition!  Oh well. I could see from the lack of comments/response that Chess is not exactly setting the '2600 world on fire anyway.

The left-column bug was an interesting one. Try as I might, I could not position that sprite on the left edge. It finally clicked that the sprite SHAPE was shifted right in the sprite itself - although it looks solid, it was only the rightmost 5 (quad-width) pixels of an 8-pixel wide sprite. So essentially what I needed to fix was to use the leftmost 5 pixels instead!  So simple, but had me stumped for quite a while suspecting emulator bugs for quad-width sprites, etc., etc.

 

chess_20200214.bin

[+Al_Nafuur]

The computer in this version is a tough opponent, continues even when his king has been beaten..

 

Had to beat all his pieces, but then he started to move my pieces..

 

very clever tactics, how do you want to improve this?

Edited February 13, 2020 by Al_Nafuur

[+Andrew Davie]

34 minutes ago, Al_Nafuur said:

The computer in this version is a tough opponent, continues even when his king has been beaten..

 

Had to beat all his pieces, but then he started to move my pieces..

 

very clever tactics, how do you want to improve this?

 

Ha. I think I'm onto something here.

 

Edited February 13, 2020 by Andrew Davie
It's uncanny. This program plays like a 6yo me.

[+ZeroPage Homebrew]

1 hour ago, Andrew Davie said:

Well, much to my surprise I saw that @ZeroPage Homebrew did a brief showing of Chess on the recent show. I do wish you guys would give a heads-up, as I would have fixed a few things. For example, here's a version with the left-column bug fixed. And, much nicer with a computer doing something, anything in opposition!  Oh well. I could see from the lack of comments/response that Chess is not exactly setting the '2600 world on fire anyway.

 

It was more of a news item to give a heads up to people about the game in development and not a proper run down. Aerlan is a chess enthusiast so we'll be holding off until there's some AI in the game to do a full playthrough along with the history of Chess on the Atari 2600. Looking forward to putting it on the show!! I'll let you know well ahead of time before we do that. ?

- James

[+Andrew Davie]

4 hours ago, ZeroPage Homebrew said:

 

It was more of a news item to give a heads up to people about the game in development and not a proper run down. Aerlan is a chess enthusiast so we'll be holding off until there's some AI in the game to do a full playthrough along with the history of Chess on the Atari 2600. Looking forward to putting it on the show!! I'll let you know well ahead of time before we do that. ?

- James

 

Aerlan's comments were mostly correct - and it was great to see someone who had a bit of knowledge about the subject talking about the game.

You covered a few things, but one thing I think you missed as a limitation was the sheer lack of processing power. 1.19MHz doesn't do much in the world of chess.  This is going to be a pretty stock-standard chess algorithm - no way will it be able to do neural nets like Alpha Zero, for example.

 

I kind of like my "completely random" AI because, rarely, but every once in a while.. a long while... it will play the absolute best chess game ever played and be completely unbeatable.

 

 

Edited February 14, 2020 by Andrew Davie

[stepho]

5 hours ago, Andrew Davie said:

Oh well. I could see from the lack of comments/response that Chess is not exactly setting the '2600 world on fire anyway.

I've been avidly watching from the wings and check your new comments every day.
I did an AI project for my 3rd year uni project (modified min/max on a game with probabilities for winning each move instead of clear cut win/lose moves, based loosely on the chess game in "The war against the Chtor" by David Gerrold).
Sadly, much of my knowledge has gone to the bit-bucket but I can still follow most of what you write and am quite impressed.

 

UI idea:
Occasionally have the computer say the speeches from Berserk.
Eg, "Intruder detected", "Destroy the humanoid".
Might be IP issues but you get the idea.
If used only very occasionally while waiting the the human player to make a move then it might surprise the human player enough to make a mistake  (kind of like Kasporov and co kicking each other under the table).

[+Andrew Davie]

1 hour ago, stepho said:

UI idea:
Occasionally have the computer say the speeches from Berserk.
Eg, "Intruder detected", "Destroy the humanoid".
 

 

I love the idea of the computer being a "dirty" player by talking to distract.

There are some online suggestions as to what to say.

 

I might put in the occasional computer laugh when you move, or lose a piece.

Could be lots of fun coming up with stuff.

 

[+Andrew Davie]

"Ha ha ha"

"Ha! You have fallen for my trap!"

"Mate in 236 moves..."

"I saw that!"

"Puny human"

"Don't look a gift knight in the mouth"

"We all learn from our mistakes: you have infinite improvement capability"

"You have a good memory for bad openings"

"You play like a human"

"You play like a computer"

"I was playing that one blindfolded"

"Atari! ..... whoops..... wrong game... Check!"

"If i had feet, I'd be kicking you under the table right now"

I welcome comments/additions!

Edited February 14, 2020 by Andrew Davie

[+Al_Nafuur]

After the human moves:

"I know you would make that mistake"

"Without a CPU i would try that move too"

[+Andrew Davie]

And I'm going to have the computer call the piece a "horsie" instead of a knight

 

[+Andrew Davie]

Don't know how I missed seeing this before...

.

 

[Voxel]

On 2/13/2020 at 2:51 PM, Andrew Davie said:

I need to do sounds, of course - seems like a perfect game to use the AtariVox with, so I guess I'll put that on the plate, too. 

Thanks - for non AtariVox users can I request an ominous sound for each time the machine makes a move.

[scrummy]

16 hours ago, Andrew Davie said:

 

Aerlan's comments were mostly correct - and it was great to see someone who had a bit of knowledge about the subject talking about the game.

You covered a few things, but one thing I think you missed as a limitation was the sheer lack of processing power. 1.19MHz doesn't do much in the world of chess.  This is going to be a pretty stock-standard chess algorithm - no way will it be able to do neural nets like Alpha Zero, for example.

 

I kind of like my "completely random" AI because, rarely, but every once in a while.. a long while... it will play the absolute best chess game ever played and be completely unbeatable.

 

 

I love your idea of making up for the lack of computer horsepower by giving the computer an interesting and unique AI with the opportunity to surprise, makes it like you are playing with a real entity rather than a machine.  That direction should provide a unique and valuable experience. 

[+Stephen]

@Andrew Davie - sorry if this is off topic for your thread, but I just watched it earlier and it reminded me of what you are doing.  If anyone objects, please PM me and I will delete this message.

 

[+Andrew Davie]

I took a bit of a diversion to test out an idea. The video shows my BYO demo, but the source image has been adjusted so that the pixels are 4x width in the horizontal direction. If you ignore the single pixel stippling (which is a result of the BYO ICC dithering), the point of this test is to see if it would be possible to have good colours with full ICC for playfield graphics for the chess program. Instead of sprites, as shown here, I would be using PF graphics. That's why the pixels are 4x wide. The result would be full-screen, just like the existing display. It would be a bit of a major pain changing to this - and there would be significant ROM/RAM and speed overheads. But, for posterity anyway, here's the result. I get triple the vertical resolution going this way, and I can have colours on all lines (for example, the blue squares are now all-blue instead of blue every third scanline). There's a bit of a shimmer from the ICC technique, so a bit of give and take. I think the contrast in the black/white pieces is significantly improved. I don't know if I'll use this... but here it is anyway.

 

[+Andrew Davie]

Castling for humans is now working. Video shows first king-side castle, and then queen-side castle. It takes a few moves to get all the pieces "out of the way" so that the castle move can be done. Note, the game correctly disallows castling if you have moved the king or the relevant rook, but does not at this stage prevent you castling if your king or the squares he crosses/occupies is in check. That's in the rules, you know! That will come later, when I put in some code to remove illegal moves from the movelist at the start of human moves. I've started it already, but it's going to be tricky to fit into "leave the screen on while you do it" bit. I do, however, want to try to get that working because I expect a human vs. human game NOT to blank the screen at any time. We shall see - it's going to be a challenge because to do the check... checks, I have to do all the available moves, and in respond to all of those generate all the opponent moves. Could be up to 1000 moves generated at some points and currently I'm only generating moves for a single piece per frame. So that would be, I guess, about 16 seconds at the start of interaction while it figures which are legal or not. Now that's obviously not on, so... as I said, a challenge.  I'm sure I'll figure something out, but not quite sure how.

Maybe I just leave the move there, let the human make it but then say "hey, sorry... illegal because... check".

 

I'll get to that later, but next I'm going to work on the en-passant capture for human. Computer version is already working, I think.

After that, pawn promotion for human and how that integrates with the UI

 

[+Andrew Davie]

Although I have quite a bit of work to do still on the UI, I'm starting to think about the AI/search. In particular, reducing that 33-fold branching factor down as much as possible. Of course, alpha-beta pruning will significantly reduce it with a well-sorted move list. The idea being to prune as much as possible by having moves that are likely to lead to pruning early. In other words, sorting the movelist before going further down the tree.

I've had a good think about this, and I think/suspect that the best way to do this sort might be to actually do a short traversal of the tree!  In other words, let's say I'm doing a 6-ply search.  First I generate the moves (ply 0). Now the job would be to sort them. Instead (or as well as) heuristics like put captures first, refutation moves (found in previous moves) first... etc., how about I just do a (sub/recursive) tree search to a lower depth for each move. That is, look (say) 3-plys ahead. That would then allow me to rank the moves according to the evaluation routine 3-plys lower.  Of course I'm adding extra tree-searching but it's only a 3-ply cost, and by spending that "3 ply of time", I now have lots more information about how good each move is. In fact, not only can I sort the moves more reliably, I could even consider just choosing (say) the first 7 moves (because they're nominally "the best 7" now) and discarding all the rest.

It will be really interesting to see how (nested) shorter tree searching embedded within the alpha-beta search... will affect the speed.

 

[+Andrew Davie]

Having just squashed a tricky bug related to castling, I thought I'd post a binary before embarking on the next thing. I have various "flags" attached to pieces, that give information about the piece. Things like colour, if the piece is en-passant capturable, if the piece has moved, and if the piece is castling. Well, normal castling was working fine, but if I moved the king one square instead of two... crash.  I found that in the two-square case, the "castle" flag was set (correctly) and the code went and looked for and moved the appropriate rook. But in the one-square case, the "castle" flag was ALSO set (incorrectly). And yet, there was only one place in the code where that flag was set - when generating a two-square move for a king to castle.

It took quite some time to find. What was happening was that when you clicked on a square, the code grabbed the piece information from the move list (correctly). You can't grab it from the board, because you need those extra flags. Basically it found the "from" square in the movelist. But.. but... in the case of castling, yes the from-square gives you "king" but actually there are king moves WITH and king moves WITHOUT the "castle" flag. And it just so happens that every time the code was getting the king/flag WITH the castle flag set. In other words, several moves for the king from that start square, but only one of them has castle flag set. 

So, the solution was -- once the "to" square has been selected, then search the movelist for the from AND to square, and get the piece/flags for that move. And continue. That solved my little problem, but took a while to find and a bit of head scratching.

 

I've also done some thinking about that "castling in check" stuff. My thinking so far... rather than make all the moves and look at all replies to all moves, what I can do is generate moves for the opponent up-front (even though it's not the opponent turn). Then I can mark in an array all squares to which opposition pieces can move to.  That gives "all the squares being attacked".  We should not allow MY king to be on an attacked square, OR the squares king moves across to be an attacked square. So this will remove the need to do a move-by-move move/response and I junk that earlier 1000 move estimate for this particular issue. I may get that sorted before moving onto other stuff.

 

Here's a binary...  have a play with castling, if you want... I think it should be pretty solid.  Other than the "castle while in check" bit.



 

chess_20200216.bin

[+Random Terrain]

Once most of the computer pieces were killed off, the computer thought my queen was its piece and moved it, then the screen went black.

[+Andrew Davie]

Just now, Random Terrain said:

Once most of the computer pieces were killed off, the computer thought my queen was its piece and moved it, then the screen went black.

Thanks, I'm not too concerned about boundary conditions at this stage. Basically you won't be ABLE to kill off all the computer pieces when it's all working, because you can never actually capture a king. There are a few things like you report - I'll track them down one by one. Basically I'm making a few assumptions for the extra speed. Stuff like you will ALWAYS find a piece to move, for example.

[+Andrew Davie]

I spotted this chess "computer" in the Falken video from the movie War Games (1983). What a hoot.

[+Random Terrain]

Here's a video of that Robo Chess game I was talking about the other day:

 

youtu.be/jWWS4HOYLy0

 

It makes comments like "you must be cheating."

Edited February 17, 2020 by Random Terrain

[+Andrew Davie]

2 minutes ago, Random Terrain said:

Here's a video of that Robo Chess game I was talking about the other day:

 

youtu.be/jWWS4HOYLy0

 

It makes comments like "you must be cheating."

 

Thanks. It even has a very similar "show available moves" thing.  Damn, I thought I invented that

 

 

[stepho]

18 hours ago, Andrew Davie said:

I spotted this chess "computer" in the Falken video from the movie War Games (1983). What a hoot.

"A strange game. The only winning move is not to play. How about a nice game of chess?"

Love that movie.
Maybe use sound clips from the movie: "Would you like to play a game?"

[+Andrew Davie]

4 hours ago, stepho said:

"A strange game. The only winning move is not to play. How about a nice game of chess?"

Love that movie.
Maybe use sound clips from the movie: "Would you like to play a game?"

The warbling sound of the WOPR computer "thinking" is awesome, too... I will have to see if I can use that in the game.
Here's a clip with exactly what I'm talking about!