Jump to content
IGNORED

Chess


Andrew Davie

Recommended Posts

@ZeroPage Homebrew featured chess on the show today.

 

I feel a bit like the guy who, amongst a crowd of people about to be shot, begs and pleads for mercy - and it's shown. I've survived, bodies strewn all around and I feel a bit of survivor's guilt, perhaps. Aerlan played two games against a somewhat "propped up" version of chess. It was played on a modified version of Stella which allowed him to "speed up" the emulation when the computer was moving.  This is totally understandable, as chess is hardly the sort of game you could otherwise present live streaming, online.

 

It was really done rather well, and no technical glitches to be seen. Well done to @Thomas Jentzsch for providing a custom version of Stella to allow this to happen. But mostly well done to the ZPH crew. But it wasn't really a true recreation of what it's like to play the game, in terms of thinking time. The game is rather slow, perhaps on par with similar chess games, but still... it came across as very fast in the show. So I'll throw a disclaimer out on that one. It made it look much much better than it really is.

My program won the first game, I think - although in my view Aerlan still had a fighting chance - but the game would have gone on much much longer. I said in the show that the program doesn't know about endgames - in particular, it has absolutely no long-term plan about protecting pawns with the king, so they march forward on their own.  In the second game Aerlan won - and I don't know for sure if he engineered this, but the falling point was when he setup a double-attack on a pawn next to a king. The game at this point sees potential checkmate and basically borks. It discards the best move and just hightails it. So, that's a known bug/ "feature" which I am working on at this very moment.  Up until that point it was not so much even - Aerlan was in a superior position - but it was surviving. Once that move was "allowed", all hell broke out and from a few moves before when Aerlan was saying he was losing, he was suddenly in complete control and wiping the board, literally.  It's a bit like fighting against some opponent but you know you have a secret word that will temporarily paralyse them. I can't wait to fix that one!

 

I was really quite happy about how the whole thing went down. It was a great technical achievement for the ZPH crew to pull off a remote game play, with chess no less, and have it reasonably entertaining and interesting. Very well done. Well, superbly interesting for me, and I hope at least moderately so for others. Given Aerlan's acknowledged expertise in chess playing, well I dreaded seeing him totally destroy the game. Honestly I was not looking forward to watching the show. And I was a bit worried about that being unreasonable expectations. But he was (mostly) constrained to playing quickly, too, and having to talk/present as he played... and that evened things out a lot.

I found it quite interesting watching him move the cursor around piece to piece as he considered, and rejected, moves. I do that too. It gives an insight into the mindset of someone playing. Perhaps the most interesting thing to me was the discussion around opening moves, particularly in the second game.  As we all know, this chess program does not have any sort of opening book, or even any knowledge about what an "opening" is. You give it a chess position. It makes a move.  So, openings are time-honed sequences of moves considered to be the "best" lines to play from the starting position. They're a given. But they are not, generally, calculated by chess programs. A large table/database is thrown at the problem, and most chess programs simply look up the "book" move and play that. This goes on for the first 5 or 10 moves and then the computer starts actually "thinking".  This program, with no book, starts "thinking" from move 1.

So, given the incredibly simple board evaluation algorithm, and particularly the extraordinary low search depth (3-ply), it actually comes up with "reasonable" opening moves. As Aerlan said in the second game, the opening was "unusual". But it was not "ridiculous". Well, not to me, a lowly player anyway. But I was pleased that the game at least looked like it knew what it was doing. Mostly.

 

There's a known bug in there - how it handles check deep in the search. I'm struggling to find the correct solution to that one. But it will come. Meanwhile, if you see the game make an obviously poor move, particularly when you're harassing its king, that's the likely culprit.

Although the game had super speed advantage, nonetheless we were looking more at how well it played, not how quickly. Given the lowest/easiest level was shown, for practical purposes, it did OK and will obviously improve.  I am working on some speed improvements. Based on my earlier measurements on the effect of sorting moves... I'm working on a much more intense sort. One which will allow me to sort by piece type (i.e, perhaps knight moves first, then bishops, then queen, rook, pawns, king).  I'm working on the idea of a scan of the board gives a list of pieces, which are sorted as the scan is happening. And then traverse the (linked list?) of sorted pieces to actually generate the moves. I have high expectations that this will dramatically (say, 2x) increase the speed of moves.

I think my challenge will be to see if it's possible to get the 4-ply search working well enough to play in "superspeed" mode on some future episode of the show, with improved evaluation algorithm - at which point I'll throw a challenge to Aerlan for a "best of 3" and I expect the game to totally wipe the floor with the lowly human. At that point, I will definitely have the AtariVox working too, and hence expect a lot of chatter during the game. So that promises to be fun. Better brush up on your openings, Aerlan!


Thanks again, ZPH crew.
 

  • Like 12
Link to comment
Share on other sites

I liked the show, even though I was not completely able to follow all moves. I suppose the problem is, that the screen went black immediately after Aerlan made his moves. So when the computer came back, it was almost like two moves had happened. That's not problem for the player as he knows what he just did, but for someone watching a game. Maybe a brief pause before the screen goes all black would help here. 

 

I wonder if there is any randomness in your calculations and decisions. E.g. if two moves are considered almost identical equal, will your engine always select the slightly better one. Or is there a chance for choosing the other one? This would make the game play a bit more human and less predictable.

 

Also, wouldn't it make sense to vary the search depth, making it more time based? E.g. if there are less pieces on the board (or less possible moves), you could try going 1 or 2 (or even more in an endgame) plys deeper? A human player would effectively do the same too.

 

BTW: Even if you improve the engine, there should be an option to come back to this one. Aerlan seems to have liked it.

Edited by Thomas Jentzsch
  • Like 2
Link to comment
Share on other sites

13 minutes ago, Thomas Jentzsch said:

Maybe a brief pause before the screen goes all black would help here. 

Agreed. Will implement soon.

 

13 minutes ago, Thomas Jentzsch said:

I wonder if there is any randomness in your calculations and decisions. E.g. if two moves are considered almost identical equal, will your engine always select the slightly better one. Or is there a chance for choosing the other one? This would make the game play a bit more human and less predictable.

Yes, there is randomness. Consider a tree search;  the evaluation happens at the "leaf" nodes - some 3-ply (or moves) ahead. I add a random value (roughly 1/3 pawn) to each of the leaf nodes, so their evaluation has a bit of "noise" so to speak. This gives randomness to almost equal moves, but still allows the computer to play "good" moves. I can increase the randomness, of course, but then it starts playing bad moves.

 

13 minutes ago, Thomas Jentzsch said:

Also, wouldn't it make sense to vary the search depth, making it more time based? E.g. if there are less pieces on the board (or less possible moves), you could try going 1 or 2 (or even more in an endgame) plys deeper? A human player would effectively do the same too.

Yep. I can count the nodes visited, and since visiting a node is (roughly) a constant time then I can use this counter to throttle the search time. Another way of throttling time is limiting the number of moves analysed at any level. For example, 35 moves average in any position in chess. What if I only consider the "top" 10 of those. Choosing the top-10 is easier than choosing the "best", and you reduce your search from effectively a 35^n problem (n=number of moves to look ahead) to a 10^n problem. In other words a huge difference.  So if you put effort into finding the "top n" moves with the purpose of culling the rest, you can still play really well, but also much more quickly.

As an aside, the alpha-beta algorithm reduces the branching factor from 35 to about 8.5 (in this version of the game). With the new search I expect this to lower to something like 3. Add on TOP of that the "top n" improvements, and it should be dramatically quicker and able to go "deeper" in the search.

 

13 minutes ago, Thomas Jentzsch said:

 

BTW: Even if you improve the engine, there should be an option to come back to this one. Aerlan seems to have liked it.

 

Ha. Well it's always nice to be able to win against a chess computer. This one has a serious bug/issue in handling check in the deepest levels of the search, and that absolutely has to be fixed.

 

Ta for the comments!

 

 

  • Like 1
Link to comment
Share on other sites

On 4/21/2020 at 2:36 AM, Andrew Davie said:

 

Thank you. Changing the colours is complex/difficult.

One set of pieces are made of colours (ABC), the other made of colours (AB), and the board squares made of C

It's not a matter of just choosing a new colour for each side. You have to find colours that mix in the way describe above... that look different enough.

And that's very difficult indeed. I've gone through many, many iterations.

 

Ah okay, thanks for clearing this up.

Link to comment
Share on other sites

9 hours ago, Andrew Davie said:

Ha. Well it's always nice to be able to win against a chess computer. This one has a serious bug/issue in handling check in the deepest levels of the search, and that absolutely has to be fixed.

 

will there be some 'dumbed down' option for the beginners and less advanced players? looking at the goals you set yourself I understand that we still are somewhat far from the final version, but wouldn't it benefit the game if it allowed for some bad moves on the lower difficulty setting? or even programming various 'computer opponents' into it and letting the player either compete with super performance grandmaster or starting easy against chess club Joe.

 

really enjoyed the show yesterday, btw! the game itself looks great

Link to comment
Share on other sites

10 hours ago, Andrew Davie said:

@ZeroPage Homebrew featured chess on the show today.

 

...

 

I was really quite happy about how the whole thing went down. It was a great technical achievement for the ZPH crew to pull off a remote game play, with chess no less, and have it reasonably entertaining and interesting. Very well done. Well, superbly interesting for me, and I hope at least moderately so for others. Given Aerlan's acknowledged expertise in chess playing, well I dreaded seeing him totally destroy the game. Honestly I was not looking forward to watching the show. And I was a bit worried about that being unreasonable expectations. But he was (mostly) constrained to playing quickly, too, and having to talk/present as he played... and that evened things out a lot.

 

Thanks so much Andrew! It was great being able to showcase the hard work you put into the game on the stream. Looking forward to playing it again when the game can cuss out Aerlan after he's able to rejoin us in person!

 

- James

 

Link to comment
Share on other sites

4 hours ago, ZeroPage Homebrew said:

Thanks so much Andrew! It was great being able to showcase the hard work you put into the game on the stream. Looking forward to playing it again when the game can cuss out Aerlan after he's able to rejoin us in person!

 

- James

 

Looking forward to it. Just in case you didn't know -- you can connect AtariVox to Stella, too, so if we are still in quarrantine it would still work.

  • Like 1
Link to comment
Share on other sites

14 minutes ago, Andrew Davie said:

Looking forward to it. Just in case you didn't know -- you can connect AtariVox to Stella, too, so if we are still in quarrantine it would still work.

So true, I think I'll have to break down and buy the USB adapter so I can do that. I've wanted to try that out several times now for various things so I think it'll come in handy in the future.

 

- James

Link to comment
Share on other sites

I think I'll use the savekey feature of AtariVox to detect when you abandon a game (reset/power cycle).

I'll keep special taunts/abuse/mockery for just this situation. Gentlemen resign, not throw the board off the table in anger.
I guess that means I have to add a "resign" menu option, too.

Meanwhile, I'm doing a lot of thinking about what things worked and didn't on the show.

Perhaps the easiest to fix was putting in a few minor delays here and there. In this version, there's a delay after human makes a move, and another delay after the computer has finished thinking but BEFORE it makes a move. They're subtle, but I think they work. What I'm really going to have to get rid of is that screen glitch/flash after the computer has finished moving its piece. That's where the legal human moves are generated. It's going to be a bit tricky to fix, but has to be done.

Here's a binary, and video... just with those aforementioned delays.

 

 

I've started thinking/work on a piecelist. Currently the move generation scans the board looking for pieces to generate moves for. To get a piece-type sorting in, I scan in two passes; for the "big" pieces first, then the pawns, then moved captures to the front. The new way will be no board scanning. I plan a list of hardwired 16 entries (1st is queen, 2nd is knight1, 3rd is night2, etc) that point to the square each piece is on. Then the pieces are already in "order" (in terms of type rook/king/etc). This will save ANY need for sorting. I just go through the piecelist, generate moves for that piece (if it's still alive, of course). After the moves are generated, I'll move captures to the front. But what about promoted pawns, I hear you ask? Glad you asked. Yes, they'll be "unsorted" and out of order. Well, I don't think it's a common-enough occurrence to worry about - in other words, the piecelist will be unsorted for that (promoted) piece, but at that stage of the game it won't make a lot of difference, I hope. Cross that bridge when I come to it.

As a wild prediction, one I get the piecelist stuff working, I expect the move generation itself to be about 20% quicker, give or take, and with the moves sorted by piece type as a consequence, I expect alpha-beta pruning to be much more effective and I think we'll see the ply branching factor come down from 8.5 to something like 4. We shall see, huh?  In practical terms, let's say twice as fast.  This code change will take me most of a week, I think. Or maybe ready tomorrow. 

estimation.png.071c8882b7ece3a8d352bbdf01f797d4.png

chess20200425_3pq8.bin

  • Like 5
  • Haha 1
Link to comment
Share on other sites

1 hour ago, Andrew Davie said:

I think I'll use the savekey feature of AtariVox to detect when you abandon a game (reset/power cycle).

I'll keep special taunts/abuse/mockery for just this situation. Gentlemen resign, not throw the board off the table in anger.

 

I think this is the best use of the Savekey I've ever heard of, ragequit detection! Hahah!!

  • Like 3
Link to comment
Share on other sites

I've hackity hacked and "cleaned up" the display flashing/glitching somewhat.  After the computer makes its move, it used to move, then flash the screen while human move was generated. Now I've shifted things around a bit - major hack actually - the screen just turns off/on the once, for each computer move.  I've also tuned the delays, so now it's quite "clean" - to my eyes, anyway. 

1661926275_ScreenShot2020-04-25at10_00_30pm.thumb.png.0c398bd64eea6f5f398419fa61904113.png
The static screenshot shows an interesting "gotcha" - here the computer will refuse to take the queen with the knight. The issue is clearly that this puts the white king in check, and I obviously have things backwards in the "check checking" somewhere in the search. Again. This is becoming a bit of a repetitive problem. Back to the drawing board. Again.  So, probably most previous releases would avoid taking pieces which could put you in check. I'll get there. In the end. Eventually. You'd think I'd know what I was doing by now, but apparently not

 

 

The video is set to 2ply to make the moves quick.  You're looking at the "clean" nature of the move indications, moving, and screen off/on stuff.
 

 

Edited by Andrew Davie
Binary removed - it has a move bug caused by the "hack". Will replace soon.
  • Like 2
Link to comment
Share on other sites

Fixed the tricky bug. Possibly.  It was caused because after the computer generates the move, but before the move is visibly performed, you need to generate the player moves. But the visible movement relies on the move info being available in the movelist. But the movelist is used by generating the player move. You can't push/pop all the required values - for various reasons. I ended up using different ply # for player and computer moves. So, computer starts at ply 0, and player starts at ply1. I can then generate moves for the computer, get the result in ply 0. Then switch to ply 1, generate human moves, (using ply 1 and 2, as it needs to look for check/responses). And we still have the computer's original move selection in ply 0. Then, after the human move (in ply 1) is verified and performed, we switch back to ply 0 for the computer search/response. Seems to work.

 

Attached binary is just a 2 ply search so it will be incredibly stupid and doesn't realise if it captures a piece, that piece can be captured back. It's pretty dumb, but I thought I'd post the quick version to assist with looking at the UI changes.

 

 

chess20200426_2pq8_BAD.bin

  • Like 2
Link to comment
Share on other sites

I had a bit of an idea about what to do when the computer is thinking, as I can't form a proper display.

Flashing the colours was one option. But I wondered what I could do (cheaply) with playfield.  Here's the result:  "thinkbars".

If they're moving, then the game hasn't crashed. I'm quite curious to see what actual CRT TVs do with this borked display idea.

 

chess20200426_THINKBAR.bin

  • Like 3
Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...