Chess

[Thomas Jentzsch]

3 hours ago, Andrew Davie said:

@stephena just making sure you get a message related to possible/probable stella issue here.

Don't hesitate to open an issue yourself. Just do a brief check for its non-existence before.

Edited March 23, 2020 by Thomas Jentzsch

[+Andrew Davie]

Well, issue solved. It turns out my local build of Stella was at fault. Stella when built from the command-line on MacOS uses UNIX-thingamajiggy stuff and I've run into an incompatibility/bug in this unsupported-style build. That is, stella does not correctly initialise a port's baud rate.  So, switch to the release version of stella and everything is hunky dory. I now have my headphones connected to the AtariVox and I'm hearing it whisper sweet nothings in my ear. In mono. But that's good.  Now I can get to work with some speech in Chess, and Sokoboo too!

 

[+Andrew Davie]

Had to share this. It's the prototype speech code included into the Chess code. It is speaking gibberish. I think. Anyway, it wanders off and just babbles on as if it's saying something... can't quite put my finger on what it's saying. But it's super-cool. Requires an AtariVox connected, of course. This is going to be lots of fun. Many thanks to those of you who have helped me get this running!

This binary actually has the alpabeta/evaluation code in it, but not quite ready to be called yet. Maybe a week or two and we'll have some decent AI. But I think I'll get some swearing in first

 

 

chess20200323speak.bin

[Voxel]

If it's babbling maybe it's become self aware...

[stepho]

Babbling?
It's turning into a politician - except for the intelligence part.

[Voxel]

On 3/23/2020 at 2:20 PM, Andrew Davie said:

it wanders off and just babbles on as if it's saying something... can't quite put my finger on what it's saying

 

10 hours ago, stepho said:

Babbling?
It's turning into a politician

Agreed.

[Mr SQL]

Saw another awesome Chess game for the VCS on this thread and played it last night - both are tremendously inspiring:

 

 

[+Andrew Davie]

Well, I've done a rather full description of how I'm using dasm to do common/transient variable overlays and save myself heaps of bother in managing memory allocation. It's almost another entry in the "programming for newbies" series, it's so long. Anyway, it's at...
 

Well worth a read, but I wonder if anyone will actually take this to heart.  It's significantly simplifed management of the chess code.

[Voxel]

That was a read, now back to what my brain can cope with, playing games.

[AW127]

On 3/24/2020 at 8:29 AM, stepho said:

Babbling?
It's turning into a politician - except for the intelligence part.

 

True. It's much more intelligent now, than alot politicians are. ?

[+Andrew Davie]

Time for an update!

 

I have the rudimentary move search working. Well early days, but it appears to have some "intelligence" behind it.  Just a 2 ply search, which makes it pretty dumb. And it's just a minimax at the moment, the alphabeta and quiescence is commented out. Still, watch the attached video - it does appear to have some nous. This is looking hopeful. Ignore all the flicker/screen wobbles. I know.... will get to that later.

 

One of the biggest difficulties I had was a 16-bit signed compare. I'd not realised I'd NEVER had to do this before, and my intuitive solution (which was to just subtract and compare the carry flag) was TOTALLY wrong. I had to do extensive debugging to find it, but fortunately there was some documentation online to explain the nifty - yet bizarre - way to do signed compares on the 6502. I extended it from the 8-bit to the 16-bit case, and it worked. Seemingly. Then things started to fall into place.

 

 

Here's the code...

 

;As stated above, after a CMP instruction, the N flag is NOT the signed
;comparison result.  A signed comparison works by performing a subtraction,
;but the signed comparison result is the exclusive-or (eor) of the N and V
;flags.  Specifically, to compare the signed numbers NUM1 and NUM2, the
;subtraction NUM1-NUM2 is performed, and NUM1 < NUM2 when N eor V is 1, and
;NUM1 >= NUM2 when N eor V is 0.  (A program that proves this is given in
;Appendix A.)

    ; We've found a higher scoring move than currently known, so record it

                    clc                     ; !! OK. Could be dropped for a bit of speed
                    lda alpha
                    sbc __bestScore
                    lda alpha+1
                    sbc __bestScore+1
                    bvc .lab                ; if V is 0, N eor V = N, otherwise N eor V = N eor 1
                    eor #$80                ; A = A eor $80, and N= N eor 1
.lab

                    bpl .notScoreGtAlpha

;If the N flag is 1, then A (signed) < NUM (signed) and BMI will branch
;If the N flag is 0, then A (signed) >= NUM (signed) and BPL will branch
;One way to remember which is which is to remember that minus (BMI) is less than, and plus (BPL) is greater than or equal to.

Never too old to learn, right?

 

So, here's a playable binary too. The game has the following disabled as I pared everything back to troubleshoot...

 

1) no castling

2) no en-passant

3) no beta pruning - it's just a minimax search to 2 ply

4) no (real) concept of check although game will generally move out of check

5) other stuff I forgot

6) No quiescence search

 

But, yeah, give this a whirl... it's actually quite aggressive sometimes.  Definitely knows about material value of stuff. Sometimes it does odd moves. Those will be less prevalent when I put those things mentioned above... back in.

Give me some feedback - I'd love to hear how it goes for you.

Let me know of any crashes, too - I haven't seen any in the half hour this has been working, but I'm sure there will be edge cases galore.

 

 

chess20200405.bin

[+Andrew Davie]

Funny observation - the reason the black king marches to the right in some games is that he "knows" that it's safer castling, but since there's no castling move, he takes it upon himself to march over to that safe square earlyish in the game. Interesting, really.

Edited April 4, 2020 by Andrew Davie

[+Karl G]

Well, it was good enough to beat me playing against it casually. I'm a pretty terrible player, and I didn't spend too much time thinking out my moves, but still, it's at least a good start in terms of AI.

[+Andrew Davie]

I've ironed out a few bugs, and now I'm able to go to just about any depth I desire. And the deeper the depth, the stronger the computer gameplay. It's pretty cool. Of course, the deeper the depth, the slower it is. Exponentially. One task coming in the medium-term future is to optimise the alpha-beta pruning (which is now active) to get more efficient cutoffs. That's basically by implementing a search earlier in the tree.

 

Anyway, here's a couple of versions - a 3-ply (about 15s/move), and a 4-ply (about 1 min/move), which both show much improved gameplay (hopefully!) from that first version I posted.  I notice that it's now making moves that "delay" "bad things" by making piece sacrifices - which is a known-thing - basically pushing the bad-thing off it's move horizon, so to speak, by doing something bad (like sacrificing a piece) but less-bad than the "bad thing" would be. That will be fixed when I get the quiescence search in, which shouldn't be too long now.

 

 

Basically, "well bugger me dead!"... it's actually playing somewhat decent chess!  I don't mean "good" chess - there are lots of faults and lots of things to fix. But it's definitely got some idea of what's what, and occasionally catches me out with "gotcha" moves. It's definitely already way better than those chess programs I wrote back in the '80s. Very pleasing. The video shows a bit of long gameplay on the easier/faster 3-ply binary.

 

 

 

 

chess20200405_3ply.bin chess20200405_4ply.bin

[+Andrew Davie]

Haha I just noticed it took my king at about 5:45. Whoops! I lose.

[+mksmith]

Great stuff Andrew ?

[+Andrew Davie]

Put aside the missing en-passant and castling, and the bug on pawn promotion (visuals) and any other issues... the 4ply version is quite strong. I just played a 2 hour game on that level... It gave me a really good run for my money. I'm quite impressed.

[Voxel]

Wow, watching the long play video, I only just noticed the animation.  It was like watching an arcade action game more than a chess game, seeing the players speedily moving to their destination, just the sound conveying the action was missing.

 

With the long interval blanking I was thinking of The hitchhikers guide to the galaxy,  and the name Deep thought chess.

 

11 hours ago, Andrew Davie said:

I notice that it's now making moves that "delay" "bad things" by making piece sacrifices - which is a known-thing - basically pushing the bad-thing off it's move horizon, so to speak, by doing something bad (like sacrificing a piece) but less-bad than the "bad thing" would be.

I would like something verbal from the computer when a player makes a sacrifice.

 

I'm often reminded of the chess term "pawn sacrifice".  To quote from Red Dwarf, "Iron Duke. Iron Duke. This is Pawn Sacrifice. Come in, please!".  On the player making a sacrifice and for the computer to pick up on it would be great.  Though I'm only familiar with "pawn sacrifice".

[devwebcl]

I played the chess20200405.bin version; it was an excellent fast game; however I missed castling (significant feature).

[stepho]

Re: bad things

 

Reminds me of the chess game in "Saturn 3".
Kirk Douglas sacrifices his queen to win against the android.

[+fdr4prez]

25 minutes ago, stepho said:

Re: bad things

 

Reminds me of the chess game in "Saturn 3".
Kirk Douglas sacrifices his queen to win against the android.

Why is that a bad thing?

[+Andrew Davie]

1 minute ago, fdr4prez said:

Why is that a bad thing?

Depends on your viewpoint. If you're a queen.... 

[+Andrew Davie]

16 hours ago, devwebcl said:

I played the chess20200405.bin version; it was an excellent fast game; however I missed castling (significant feature).

Here's the latest.

Castling now appears to be working for both player and computer.

The issue with castling, and en-passant, is that these moves really involve two separate moves.

Castling is the king moving, then (for the same colour) the rook moving.

en Passant involves the pawn moving, then (for a totally different square) taking away a pawn.

Being able to handle both of these efficiently was the tricky bit for me. We don't want to impose a significant castling-enabling bit of code which runs every single move and thus becomes a drain on the speed of the computer choosing moves.
Anyway, castling is done, and done in a way that leads to a solution for en passant, which will come shortly.

Meanwhile, a full-game of 3-ply. Computer puts up a good fight but goes down in the end.

Since it has no idead of draw/checkmate/stalemate, etc., but it does know that the king is really valuable, it tries valiantly to protect the king - until which point it is impossible, and then it tries to extract maximum revenge/damage just before the king gets taken. In other words, it will capture wherever it can, and throw pieces to BE captured... just to avoid that king being taken. Kind of cruel really.

 

 

 

I've included a 3ply and a 4ply binary. 3Ply will play quickly enough. 4ply may give you a decent challenge if you want a longer game.

I'd recommend trying out the 3ply first.

 

chess20200406_4ply.bin chess20200406_3ply.bin

[+Andrew Davie]

#NAN

 

 

 

Edited April 6, 2020 by Andrew Davie

[devwebcl]

Quote

- until which point it is impossible, and then it tries to extract maximum revenge/damage just before the king gets taken. In other words, it will capture wherever it can, and throw pieces to BE captured... just to avoid that king being taken. Kind of cruel really.

Right, I was playing, and my rook checked its king, but instead of avoiding the check (capturing my rook), the CPU moved its rook and checked my king.

So, I am in an inconsistent chess game. Then later, I captured its king, and the CPU is still playing.