Chess

[+Andrew Davie]

4 minutes ago, Karl G said:

I've added the third screenshot to the same post for comparison.  The new one is the one with the white knight not in the starting position. It does indeed look different, but I'm not sure that I prefer it to the others.

Agreed. squares are too bright. New version just posted.

[RevEng]

1 hour ago, Andrew Davie said:

OK. Please make it stop!

Uh, I seem to have accidentally broken Andrew. Can someone please power-cycle him?

[+mksmith]

1 minute ago, RevEng said:

Uh, I seem to have accidentally broken Andrew. Can someone please power-cycle him?

Perhaps it might be the Queensland heat ?

 

[Keatah]

1 hour ago, Keatah said:

Just wondering. I have two versions of Stella 3.9.3 and 6.1.1. I get different colors between each emulator. But only on this chess game. All other roms I tried look identical between the versions. Ideas? Or not a big deal..?

 

Oh never mind. Stella 6.1.1 detects most (but not all) of the roms as PAL. Switching to NTSC gives me those deep blue hues and ivory whites. 3.9.3 seems to detect it right.

 

Edited April 21, 2020 by Keatah

[+stephena]

These last few ROMs start with 360 scanlines, and hence Stella assumes they are in PAL format.

[+Andrew Davie]

Here's an updated version for the @ZeroPage Homebrew show, based on feedback from Aerlan.

He beat it first go, of course. I've tweaked the quiescence a bit, but also now the randomness on opening moves is a bit more ramped up. From zero, so... not random... now random .  I'm a bit disillusioned having a "good" player comparing this engine at this stage to commercial offerings. Especially as the engine is trying to make moves quickly instead of going deep. That was always going to be an issue, of course - while the game is in its genesis and the evaluation engine is doing next to nothing, then comparing it to other implementations isn't going to be really "fair". For the record, at the moment the evaluation is purely difference in material value + difference in #moves available to each side + positional value of each piece for the square they are on + a bit of random noise.  There is no "chess knowledge" built in. What the game is trying to do right now is simply maximise that sum just given. I do know of several significant improvements I can make, so I'll just try and keep moving forward.

I don't think I can bear to watch the show, though....

 

chess20200421_Aerlan_3ply_8quiesce_rand15.bin

[+Andrew Davie]

Well, something is fundamentally borked.

I just played a game where it spotted a mate in two and made the moves possible to let me do that.

In other words, it saw that if it moved its rook and bishop out of the way, I could mate it.  Kind of the opposite of what should happen.

I'll have to track that one down before the show!!

 

[+fdr4prez]

44 minutes ago, Andrew Davie said:

it moved its rook and bishop out of the way

They're traitors to the Court!!! 

 

Off with their heads!

[+Andrew Davie]

Good vassals are so hard to find, these days.

 

[+Andrew Davie]

Staff involved have left our service and are now holidaying face-down in the moat.

It seems they decided that if our opposition couldn't move, the best thing to do was to call it a draw and go home for nibbles.

The negamax and associated quiescence search are very "touchy" to anything I put in there. I previously had this exact same problem when trying to detect check. This time it was trying to detect a draw. I need to study these better before I start dabbling in their function.

They are quite interesting, having almost exactly nothing to do with chess - except out the end comes "reasonable" moves. 
Anyway, I've disabled the "game is a draw" detection, employed new vassals, and this should be a little less suicidal...
Meanwhile I need someone to clean the moat - it's getting rather full...


 

chess20200421_vassal.bin

[+Andrew Davie]

I got to thinking about the advantage there is in "having" an "opening book". Specifically @ZeroPage Homebrew where a good player "instantly" knows the reply (and even the name!) of openings. This is a huge advantage, to have learned those opening moves. So, just for a bit of fun, I have swapped the opening positions of the knights and bishops in this version. This effectively invalidates 500 years of chess "wisdom" implicit in opening books, and leaves even the experienced player to actually analyse a position/form new strategies. 

I thought this would be fun and very different for some players to have a go at. It's is very very strange to my brain when I start playing.

 

Since the computer is still using the move/position evaluations and tables for the standard opening position, it is also at quite a disadvantage with this swap.

Also, this is the debut of a new move generation idea - I'm generating moves for non-pawns first, then pawns. It's effectively a "sort" which puts pieces most likely to cause alpha-beta pruning (well, maybe) first in the list. One potential advantage of this is that if you use SELECT to "force move", the computer is more likely to have analysed reasonable moves at that point.

 

Edit: Having played a couple of games with this setup, it totally sucks. If Chess was like this, nobody would play it!

 

chess20200421_NOBOOK.bin

Edited April 21, 2020 by Andrew Davie

[+Andrew Davie]

Just while I'm having a bit of fun, here's another brainfuck.

This one just swaps the graphics for knight/bishop. So, brain beware!

 

 

 

chess20200421_SWAP.bin

[+Andrew Davie]

I've done some measurements on the move generation.

The original system simply scanned the board, and then put capture moves first in the list.

The new system either...

 

1) generates moves for pawns first, then other pieces, then shifts captures first

2) generates moves for other pieces, then pawns, then shifts captures first.

The numbers below show the difference between 1) and 2)

 

# shown = board positions evaluated
TOTAL = total nodes evaluated
MULTIPLE = BRANCHING FACTOR

1. generate pawn moves, then non-pawns...
   then scan for capture moves and put them very first
A = nodes evaluated in negamax search
A(Q) = nodes evaluated in quiescence extension (6 ply)

               3-ply     4-ply       5-ply
-----------+----------+----------+----------
A          |     331  |   3477   |   43122
A(Q)       |     135  |   5049   |   65556
===========+==========+==========+==========
TOTAL      |     486  |   8526   |  108678
MULTIPLE   |     6.8  |    7.7   |     8.5    
 

2. generate non-pawn moves, then pawns
   then scan for capture moves and put them very first
B = nodes evaluated in negamax search
B(Q) = nodes evaluated in quiescence extension (6 ply)
TOTAL = total nodes evaluated

               3-ply     4-ply       5-ply
-----------+----------+----------+----------
B          |     118  |    844   |    5430
B(Q)       |     136  |   1321   |   12603
===========+==========+==========+==========
TOTAL      |     254  |   2165   |   18033
MULTIPLE   |     4.8  |    5.4   |     5.6 

Interpretation...
1) given chess has an average branching factor of 35, the branching factors we see ("MULTIPLE" row) show the benefits of minimax and alpha-beta pruning. 
2) I have read that a decent alpha-beta prune can reduce the branching factor to 2.5 or less (!). 

3) The order of pieces in move generation makes a huge difference to the branching factor (and thus, number of nodes processed).  For example, the 5-ply search ended up analysing 108678 nodes vs. 18033 nodes based on the piece ordering alone.  That's 6 times MORE nodes processed just because we were looking at pawn moves first.

4) Consider the 5-ply search. Nominally this (with a 35x branching factor) should visit 35^5 nodes = 52521875.  Yet we actually visited just 5430 (PLUS 12603 quiescent nodes (captures), which took us down another 6-ply to 11-ply).

Conclusion...

If we look at the branching factors, for non-pawn-first 5-ply we have 5430^(1/5) = about 5.6 nodes per ply.

For the pawn-first, it's 43122^(1/5) = about 8.5 nodes per ply.  So, a significant difference.

That 5.6 needs to come down to about 3 and I'll be happy.

 

Put another way, for the 3-ply which is what's currently the "playable" version, the speed improvement is very close to 2x as quick. For 5-ply, which still takes too long to be usable, it's about 6x quicker.

 

Putting extra effort into ordering moves can make a huge difference to the # nodes evaluated, because of alpha-beta branching factor reduction, and therefore playing speed.  Of course I knew this already, but it's interesting to see actual figures from my engine.
 

Edited April 21, 2020 by Andrew Davie

[NE146]

11 hours ago, Andrew Davie said:

I'm a bit disillusioned having a "good" player comparing this engine at this stage to commercial offerings.

That's a little unfair. Unless you think otherwise (due to you creating this in 2020), to me since it's on the VCS the more apt comparison aside from Video Chess, would probably be to the commercial chess microcomputers of the late 70's. E.g. the Fidelity Chess Challenger series, etc. 

 

What's pretty convenient these days is some of them are emulated in Mame such as Chess Challenger 7 (which is what I had as a kid).  That could make for a fun tournament once you get close to the final versions of your engine. On that note here's an article from a 1979 issue of Popular Mechanics that did a similar thing with a few of the retail offerings of the time, like Boris, etc. I thought it was pretty interesting.

 

 

 

Popular Mechanics_ Computer Chess_may_1979.pdf

[+fdr4prez]

5 minutes ago, NE146 said:

On that note here's an article from a 1979 issue of Popular Mechanics that did a similar thing with a few of the retail offerings of the time. I thought it was pretty interesting.

Popular Mechanics_ Computer Chess_may_1979.pdf 3.02 MB · 2 downloads

 

An interesting ad in that 1979 article:

 

 

Who doesn't have spare time on their hands these days?

 

You can still get their mini-dozer today:

 

https://struckcorp.com/products/mini-dozer-md196k/ 

 

 

[RevEng]

I was looking at the list of chess variants, and was thinking that kung-fu chess might be a way for a quick but weak (2-ply?) engine to put a master off-guard. This doesn't jibe that well with the current blank-and-think approach, and I think I recall you mentioning you're running into constraints, but I figured it might be worth mentioning. Some of those other variants might be good for simple 2600-style game variations, along the lines of your knight-bishop swap.

 

One random idea... any time to do any pre-calculations on the move decision, as the player is deciding? I know their eventual move will invalidate weights for pieces near the move (nearby being less meaningful for pieces that don't have limited travel) so I'm thinking this idea may fall into the possible-but-not-practical category on the 2600.

[Voxel]

2 hours ago, NE146 said:

That's a little unfair. Unless you think otherwise (due to you creating this in 2020), to me since it's on the VCS the more apt comparison aside from Video Chess, would probably be to the commercial chess microcomputers of the late 70's. E.g. the Fidelity Chess Challenger series, etc. 

 

What's pretty convenient these days is some of them are emulated in Mame such as Chess Challenger 7 (which is what I had as a kid).  That could make for a fun tournament once you get close to the final versions of your engine.

That's pretty much my take, this game needs to be measured against its' peers.  Lets not forget, ZPH is just spreading the word about what's available on the system and how it plays.  Taking things in context, it plays pretty well given the constraints of the system.  For hobby players like us, it fits the bill really well.

 

I had a quick game on NOBOOK and SWAP, interesting... my mind still needs some time to make the adjustments, puts opening book moves out the game for sure.

[NRV]

5 hours ago, RevEng said:

I was looking at the list of chess variants

Nice page.

I add a vote for the ideas in Really Bad Chess.

It "seems" easy enough to implement and is a lot of fun to play x)

 

[+Andrew Davie]

8 hours ago, RevEng said:

I was looking at the list of chess variants, and was thinking that kung-fu chess might be a way for a quick but weak (2-ply?) engine to put a master off-guard.

Never heard of it before. Fascinating to watch!

 

 

[+ZeroPage Homebrew]

We'll be playing Chess on tomorrow's (Wed Apr 22) ZeroPage Homebrew stream LIVE on Twitch at 6PM PT | 9PM ET | 1AM GMT! Hope everyone can watch!

 

Twitch Stream: https://www.twitch.tv/zeropagehomebrew/

 

Games:

• Chess (2020 WIP) by Andrew Davie (@Andrew Davie)
• Local Hero (2020 WIP Exclusive Premiere) by @satyrsfaction
• Penult (2020 WIP) by Karl Garrison (@Karl G)

 

[RevEng]

20 minutes ago, Andrew Davie said:

Never heard of it before. Fascinating to watch!

That's an interesting implementation, with the movement timer for the pieces. It causes these lovely little moments of helplessness, when your piece is in danger, and you realize your opponent's piece has a bit less time on it than yours.

I think the game is usually just played as fast as either side can move, which must get very messy at times.

 

[edit] I see - "kung fu chess" does specifically refer to the computer game. I thought the computer game was just one specific implementation.

[+Andrew Davie]

45 minutes ago, RevEng said:

That's an interesting implementation, with the movement timer for the pieces. It causes these lovely little moments of helplessness, when your piece is in danger, and you realize your opponent's piece has a bit less time on it than yours.

I think the game is usually just played as fast as either side can move, which must get very messy at times.

 

[edit] I see - "kung fu chess" does specifically refer to the computer game. I thought the computer game was just one specific implementation.

Also interesting, your piece can move out of the way whilst the attacking piece is en-route!  You see some near misses.

[+Andrew Davie]

I've had another stab at handling check inside the negamax search. I found one 'gotcha' that I missed in the previous effort.

So, this version - 3 ply negamax + 8 ply quiescent will be interesting. Gave it a quick play. 

What we're looking for is when you are about to win, the computer doesn't decide to go hell for leather, ignore the check on its king, and start doing weird stuff instead.

 

 

chess20200422_3p8q.bin

[+Andrew Davie]

At first glance it's looking good. I setup a test board, gave it a rook to play with and then proceeded to chase its king around the board. In all cases, even when it was under duress, it made legal moves. Furthermore, the end of game stalemate (1st game) and checkmate (2nd game) were correctly detected. The rook stood by hopelessly instead of going on to "you put me in check... well I'll put YOU in check!!!" which it used to do. So, feeling good so far about this fix.  I'll definitely be wanting to get a new version to @ZeroPage Homebrew for the show, because this fixes a major "bug".
 

 

[+Andrew Davie]

Well, although the last version did indeed fix the illegal when-in-check moves, there's still an issue.

That is, when the human can make a checkmate, the computer doesn't see checkmate-preventing moves as more desirable than (say) a capture move.  For example, in the board shown... (black to move)...

 

 

The computer will choose BxN rather than do something to prevent QxP(mate).

It's all to do with how "check" is handled, how "you have no moves" is handled, and the negamax algorithm which is recursive.

I've been through this a lot of lots. I'll get there eventually. It's just not easy to fix/understand code when it looks straightforward, but your code may be 9 plies deep when it does your fix. And there are all the consequent "decisions" that propogate back up the tree until you come out with a selected move.

I know I can fix this. It's just that I've been working maybe 6-8 hours a night, for months, on this. And I'm out of time to fix for the show.

And I'm thinking I really need a break, once again.

 

So, the previous version is what @ZeroPage Homebrew should probably demo, I guess. Attached again to this message.

I'll see you on the show. Or maybe not. I'm a bit scared/scarred to be honest. Will my baby behave? Will it be mistreated?


 

 

 

chess20200422_3p8q.bin