Chess

[+Andrew Davie]

Don't forget, if you're playing with Stella and you want it to choose its moves quicker, just TAB to bring up the menu, then select Video and change emulation speed to 1000%.  You will need to change it back to 100% after computer has moved, as the UI is unusable at 1000%.  But it could turn your 30 minute wait into a 3 minute one.

[+Andrew Davie]

OK, here we go...

 

I've been on the edge of making a decision about using a different bank-switch scheme. Now I've had a bit of time to (very briefly) review the DASH and 3E+ schemes, one of those is the most likely candidate for my switch. I'm not saying these are the best schemes out there, but they are close enough to 3E and one of them, at least I'm the actual lead designer of DASH (as I recall, anyway).  I think Thomas did the Stella implementation - I'm vaguely sure it wasn't me! I totally forgot about this scheme, which was designed to correct the limitations @Thomas Jentzsch and I ran into when writing Boulder Dash.  Those are the same as described in my earlier post.

 

Now, I happen to think DASH looks like the bee's knees - I can see that this would work very well with my current design - or at least I think so. And yet, Thomas writes (regarding Stella) "we kicked DASH from the next release, because it was unused for years after I found it very unpractical. If you find out different (which I doubt :)), please let me know."  So, there's that.
 

In some ways that got me to thinking "well, it's now or never" but I had pretty much already decided to attempt DASH (or 3E+, which is derived from it) before I was aware of the above.  I don't know what Thomas found very impractical, but I guess I'm going to find out. I've already had a quick think about implementation, and I think the screen draw is the very first thing to test, because that uses complex RAM-based self-modification and self-switching for banks.  If things are going to fail early on, it will be there.

 

So I guess while I'm playing with that conversion/test there will be a bit of a hiatus on further features/improvement on this version of the game. As noted earlier, I'm practically out of ROM space anyway - at least where it is required. I totally expect the DASH scheme to alleviate this issue and allow me to add much more functionality. Although en-passant code is in there now, it's not functional. But new code would be the prevention of castling when any of the traversed squares in check.

I played a couple of games today - a long battle at 5-ply (q8) where I slowly gained a pawn advantage, pressed home a passed pawn and forced checkmate. It was a really enjoyable game and the program fought hard towards the end, making it awkward to do what I planned. Very happy with that.

The second game was a quick 3-ply (q4) where I really didn't spend long enough planning my game, and eventually the computer ended up a knight (R+N vs R) with both having fairly matched pawns/structure. I was prepared to concede that one, although I probably would have won. Again, it played a good game especially for the speed at which it was moving. 

So, I expect over the next few days - if I can be bothered programming - will be what I learn about the DASH scheme and its shortcomings.

Here's my description of the DASH scheme, from the stella implementation.... oh, the irony of relying on documentation that you, yourself, wrote so many years ago that you don't remember it at all!  This is why we document code!

 

 

 Cartridge class for new tiling engine "Boulder Dash" format games with RAM.
  Kind of a combination of 3F and 3E, with better switchability.
  B.Watson's Cart3E was used as a template for building this implementation.

  The destination bank (0-3) is held in the top bits of the value written to
  $3E (for RAM switching) or $3F (for ROM switching). The low 6 bits give
  the actual bank number (0-63) corresponding to 512 byte blocks for RAM and
  1024 byte blocks for ROM. The maximum size is therefore 32K RAM and 64K ROM.

  D7D6         indicate the bank number (0-3)
  D5D4D3D2D1D0 indicate the actual # (0-63) from the image/ram

  ROM:

  Note: in descriptions $F000 is equivalent to $1000 -- that is, we only deal
  with the low 13 bits of addressing. Stella code uses $1000, I'm used to $F000
  So, mask with top bits clear :) when reading this document.

  In this scheme, the 4K address space is broken into four 1K ROM segments.
  living at 0x1000, 0x1400, 0x1800, 0x1C00 (or, same thing, 0xF000... etc.),
  and four 512 byte RAM segments, living at 0x1000, 0x1200, 0x1400, 0x1600
  with write-mirrors +0x800 of these.  The last 1K ROM ($FC00-$FFFF) segment
  in the 6502 address space (ie: $1C00-$1FFF) is initialised to point to the
  FIRST 1K of the ROM image, so the reset vectors must be placed at the
  end of the first 1K in the ROM image. Note, this is DIFFERENT to 3E which
  switches in the UPPER bank and this bank is fixed.  This allows variable sized
  ROM without having to detect size. First bank (0) in ROM is the default fixed
  bank mapped to $FC00.

  The system requires the reset vectors to be valid on a reset, so either the
  hardware first switches in the first bank, or the programmer must ensure
  that the reset vector is present in ALL ROM banks which might be switched
  into the last bank area.  Currently the latter (programmer onus) is required,
  but it would be nice for the cartridge hardware to auto-switch on reset.

  ROM switching (write of block+bank number to $3F) D7D6 upper 2 bits of bank #
  indicates the destination segment (0-3, corresponding to $F000, $F400, $F800,
  $FC00), and lower 6 bits indicate the 1K bank to switch in.  Can handle 64
  x 1K ROM banks (64K total).

  D7 D6 D5D4D3D2D1D0
  0  0    x x x x x x   switch a 1K ROM bank xxxxx to $F000
  0  1                  switch a 1K ROM bank xxxxx to $F400
  1  0                  switch a 1K ROM bank xxxxx to $F800
  1  1                  switch a 1K ROM bank xxxxx to $FC00

  RAM switching (write of segment+bank number to $3E) with D7D6 upper 2 bits of
  bank # indicates the destination RAM segment (0-3, corresponding to $F000,
  $F200, $F400, $F600). Note that this allows contiguous 2K of RAM to be
  configured by setting 4 consecutive RAM segments each 512 bytes with
  consecutive addresses.  However, as the write address of RAM is +0x800, this
  invalidates ROM access as described below.

  can handle 64 x 512 byte RAM banks (32K total)

  D7 D6 D5D4D3D2D1D0
  0  0   x x x x x x   switch a 512 byte RAM bank xxxxx to $F000 with write @ $F800
  0  1                 switch a 512 byte RAM bank xxxxx to $F200 with write @ $FA00
  1  0                 switch a 512 byte RAM bank xxxxx to $F400 with write @ $FC00
  1  1                 switch a 512 byte RAM bank xxxxx to $F600 with write @ $FE00

  It is possible to switch multiple RAM banks and ROM banks together

  For example,
  F000-F1FF   RAM bank A (512 byte READ)
  F200-F3FF   high 512 bytes of ROM bank previously loaded at F000
  F400        ROM bank 0 (1K)
  F800        RAM bank A (512 byte WRITE)
  FA00-FBFF   high 512 bytes of ROM bank previously loaded at F400
  FC00        ROM bank 1

  This example shows 512 bytes of RAM, and 2 1K ROM banks and two 512 byte ROM
  bank halves.

  Switching RAM blocks (D7D6 of $3E) partially invalidates ROM blocks, as below...

  RAM block    Invalidates ROM block
  0        0 (lower half), 2 (lower half)
  1        0 (upper half), 2 (upper half)
  2        1 (lower half), 3 (upper half)
  3        1 (upper half), 3 (lower half)

  For example, RAM block 1 uses address $F200-$F3FF and $FA00-$FBFF
  ROM block 0 uses address $F000-$F3FF, and ROM block 2 uses address $F800-$FBFF
  Switching in RAM block 1 makes F200-F3FF ROM inaccessible, however F000-F1FF is
  still readable.  So, care must be paid.

  This crazy RAM layout is useful as it allows contiguous RAM to be switched in,
  up to 2K in one sequentially accessible block. This means you CAN have 2K of
  consecutive RAM (don't forget to copy your reset vectors!)

  @author  Andrew Davie

 

 

Edited April 30, 2020 by Andrew Davie

[+Andrew Davie]

Ok, the first bad-design-decision I can see in the above (although I understand the reasons) is the write-address offset for RAM. It's +$800 (that is, you read RAM in bank 0 at $F000 and you write to it at $F800. This means that ROM switched in at $F800 would be inaccessible - treated as writing to RAM at $F000 actually. At the time, 2K of contiguous RAM seemed desirable.

What I think I'll need to do is modify this scheme - and now that I've had a peek at 3E+ by Thomas I see this is already done. He's changed the RAM write offsets, giving the following...

 

  Cartridge class from Thomas Jentzsch, mostly based on the 'DASH' scheme
  with the following changes:

  RAM areas:
    - read $x000, write $x200
    - read $x400, write $x600
    - read $x800, write $xa00
    - read $xc00, write $xe00

 @author  Thomas Jentzsch and Stephen Anthony

So, that means we have 512 bytes of RAM (contiguous) x 4 banks, but the RAM is in 4 distinct memory blocks. That's OK I don't think I need more than 512. So, this is a bit of luck - well, not luck, just good modification by TJ.  I'm going, therefore, to be concentrating on 3E+ instead of DASH.

The design will need to be - 4 separate 1K banks - each of which can be either 1K ROM or 512 bytes RAM.
There will not be a "fixed" bank.

Issues related to the reset vectors I may think later about that - basically with the last bank switchable that means I either have to guarantee the reset vector is in every bank that can switch into that location, or have the hardware switch to the bank that conntains the reset vector (first) before vectoring. Either should work... I think the first option (programmer's responsibility) will be easy enough.

 

 

[+Andrew Davie]

Well, first thing... I want a unique way to differentiate between any binary/screenshots/video of the new version, so it might be something like this interesting effort.... change is as good as a holiday, I guess. I quite like it actually. Click on the picture for a larger view.
 

Edited April 30, 2020 by Andrew Davie

[devwebcl]

On 4/29/2020 at 9:03 AM, Andrew Davie said:

 

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 64 kB · 9 downloads

I played this level in Stella, although it is slow, it has more robust gameplay. I lost in move ~20.

 

[+Andrew Davie]

[Mr SQL]

3 hours ago, devwebcl said:

I played this level in Stella, although it is slow, it has more robust gameplay. I lost in move ~20.

 

X2 - the 5ply rocks!  

 

I played the game on the real hardware and the CPU took about 12-15 minutes a move, I left it on overnight and kept taking breaks, the game probably took about 4 hours. I was ahead at first chasing the night again but then made a blunder and lost after continuing the game the next day, I need to play another round! 

 

Andrew I am looking forward to pawn en passante! 

 

interesting history on this move is that pawns were initially only allowed one square, but the game took so long that an initial jump of two was allowed - this caveat came with the option for an immediate en passante move reply so the pawn couldn't jump past an enemy pawn to escape capture. It's caused some issues for early Chess engines which had release notes the engines could not defend against it.

 

[+Andrew Davie]

4 hours ago, Mr SQL said:

Andrew I am looking forward to pawn en passante! 

 

interesting history on this move is that pawns were initially only allowed one square, but the game took so long that an initial jump of two was allowed - this caveat came with the option for an immediate en passante move reply so the pawn couldn't jump past an enemy pawn to escape capture. It's caused some issues for early Chess engines which had release notes the engines could not defend against it.

 

 

The efficient implementation is problematic, and early chess engines couldn't afford the code space, or the processing time, added by this odd-bod move. Castling is slightly less difficult, as it's effectively just two white moves in a row. En passant is difficult because it involves action of a single piece over more than the two squares (from/to). How do you represent this without having to have a "third square" slot for all moves, or conditional code that has to run thousands of times.

 

Edit: Currently the additional code required for en-passant move generation, and execution, is just on 120 bytes.

Edited April 30, 2020 by Andrew Davie

[AW127]

On 4/30/2020 at 1:56 AM, Andrew Davie said:

"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.

 

Thanks for the info. I had suspected something like that, but was not sure about it.

 

22 hours ago, Andrew Davie said:

Don't forget, if you're playing with Stella and you want it to choose its moves quicker, just TAB to bring up the menu, then select Video and change emulation speed to 1000%.  You will need to change it back to 100% after computer has moved, as the UI is unusable at 1000%.  But it could turn your 30 minute wait into a 3 minute one.

Yes, i know and i use such things since a longer time also with other emulators, when i let various chess-programs play against each other. And i like doing this games, in which i then manually make all the moves. In such games, i often use the Warp-speeds of the different emulators for shortening the waiting-times, until the moves come. And the most programs also don't have problem with a higher-speed, the only thing which i always have to consider then is, that i am boosting both programs or none of them, otherwise it could be unfair, when only one is boosted. The most chess-programs also uses the thinking-time of the enemy for calculating about own moves and when i would boost only one emulator, the program which runs in the other, then could have a little disadvantage.  

Edited May 1, 2020 by AW127

[NE146]

I set up a game between Chess Challenger 7 (lv 2) and AD Chess for kicks, boosting both for speed as needed. AD Chess won pretty nicely. 

 

Note that my recording of the moves was done quickly so I missed notating some captures and possibly some checks. Also I named the rom wrong.. it should be Chess-04-30-2020" (in case anyone was wondering).   

 

 

Next up is level 3.

[+Andrew Davie]

1 minute ago, NE146 said:

AD Chess won pretty nicely. 

Sweet! 

[+Andrew Davie]

Gotta hate that MM/DD/YYYY though.  YYYYMMDD is so much more logical.

 

[NE146]

Re: date format, I fluctuate between both tbh. For example all my home pictures and videos are strictly that format   

 

But yeah that was just hastily typed (and erroneously as well) just to differentiate it from all the other Chess releases. I usually actually just type random letters.

 

 

 

 

 

 

[+Andrew Davie]

I've spent about 6 hours today doing conversion to the 3E+ bankswitch scheme.

But first I needed to pull down and compile a new branch of stella, which has new bankswitch code.

I needed to do that because I discovered a bug in the previous/exisiting stella 3E+ handler, which was not showing up in the new code.

So, I can't expect them to fix the old code, and makes no sense to do it myself... so get the stella build going.

That took a while, because the MacOS project workspace file wasn't updated. So I had a gajillion errors in the stella build to figure out.

But, eventually eventually, with lots of help from Thomas, I got the stella build going.

Anyone wanting to run binaries from now on is also going to need this new bankswitching code. Which means downloading a new version of stella. And, not quite sure when that's going to happen. It will be a beta, of course. So, there's that.

 

Anyway, moving on - having now had some experience with the 3E+ bankswitch scheme and getting to understand how to use it, and its quirks, I'm smiling. I can see great potential here.  I've already got a version compiling, but of course I get complete rubbish when I run it. But it is running... I can step through the beginning of the code, and I've already reworked some of the earlly/initialisation stuff and stepped through it OK.  What I really like is the 4 switchable banks, which means that instead of having a solitary 2K fixed bank which had to act as an intermediary for accessing stuff from switchable banks, I no longer need any of that.  The switchable banks can talk to each other direct. One in [SLOT2] and one in [SLOT3] and they can happily do stuff.  For example, I now have the board in its own (512 byte) RAM bank. It can be switched in to [SLOT3], and the generate move code can be in [SLOT1], while it reads from the board, it can write the moves it generates to [SLOT2] which will be the movelist for the current ply. And I still have an unused [SLOT0] if I need to access something else at the same time.

So, typically, instead of having to do something like this in a loop...

 

LOOP_START

		switch in bank 1
		get data from table

		switch in bank 2
		do some stuff

		switch in bank 1
		get next table data

		switch in bank 2
		manipulate
		switch in bank 3
		write stuff

		go back to  LOOP_START

 

You get the basic idea, I hope - LOTS of bankswitching.

And that code would have to live in the ONLY fixed bank. You can't do a bankswitch from a switched bank.

That's 3E.  Here's 3E+

 

	set [SLOT1] to table
	set [SLOT2] to result
LOOP_START

		get data from table
		do some stuff
		get next table data
		manipulate
		write stuff
		go back to  LOOP_START

 

In other words, dramatically reduced bank switching inside loops, etc.

I'm guessing, but here we go - let's say 10% more efficient overall. That is, I expect the program to be 10% faster.

 

Now, I need to spend a lot of time going through each subroutine and making sure the new bank allocations/switching are OK. There are some 'gotchas'. For example, if code is compiled with address for [SLOT0] then you can't switch it into [SLOT1] and expect it to run. That's because the address of each slot is different. The start of [SLOT0] is at $F000 and the start of [SLOT1] is at $F400. So a subroutine can't be assembled at $F000 and then switched to $F400 and expect to run. It could be "got around" with various trickery, but I have other ways of managing this.  Four slots currently seems like a luxury.

My one concern at the moment, is that 3E+ is relatively new and unused, and integration with the debugger may be a problem for me. We shall see how it goes; I've already run into a few issues. This is pretty much "pulling oneself up by one's bootstraps". 

But, I'm really happy so far with how things are going. I hope I can muster the enthusiasm to keep going for a few days and see if I can get this switchover working. 

 

 

 

 

 

 

[+Karl G]

3 hours ago, Andrew Davie said:

Gotta hate that MM/DD/YYYY though.  YYYYMMDD is so much more logical.

 

Yeah, well, we haven't even switched to the metric system yet, so what do you expect? 

[+Karl G]

Is 3E+ supported yet on either Harmony or Uno?

[Voxel]

6 hours ago, NE146 said:

I set up a game between Chess Challenger 7 (lv 2) and AD Chess for kicks

Great work, I'll be going through the moves on a board when I get time.

 

No pressure, but if you play any more comparisons please share them.

[+Andrew Davie]

7 hours ago, Karl G said:

Is 3E+ supported yet on either Harmony or Uno?

I doubt it but I'm too lazy to look it up.

[NE146]

Dangit.. I decided to enjoy a beer and put up Chess Challenger 10 lv. 3  (the tournament winner in that Popular Mechanics PDF article) against AD Chess.  It was great until the point CC10 made an en-passant capture. Ah well so it goes.   Pity though as it it was a interesting game with AD Chess being somewhat aggressive. 

  

[+Andrew Davie]

36 minutes ago, NE146 said:

It was great until the point CC10 made an en-passant capture.

 

Ha! Me bad. Sorry!

[The Usotsuki]

I use YMD on a series of YT videos I upload every week.

[+fdr4prez]

Week Number tends to throw me for a loop, example - "it will ship in Week 32"

[+Andrew Davie]

Remarkably, I found a major major bug in the evaluation code. Particularly, the code that awards "score" for pieces being in certain positions. You may have seen a few games where the computer rooks migrated to the side and lined up (here, on the left edge). I was tracing through why that seemed to be a good position...

 

Now in a roundabout way, the position of each piece is controlled by a simple table giving the value of each square for each piece. I say roundabout, because it's a holistic thing, affected by moves responding to moves responding to moves. But ultimately, these tables do allow a modicum of "intelligence" in the moves. Here is the table for the rooks...

 

PositionalValue_ROOK

    PVAL   -10, -10,  10,  25,  25,  10, -10,  -10
    PVAL  -120,   0,   0,   0,   0,   0,   0, -128
    PVAL  -128,   0,   0,   0,   0,   0,   0, -100
    PVAL   -70,   0,   0,   0,   0,   0,   0, -100
    PVAL   -5,    0,   0,   0,   0,   0,   0,  -50
    PVAL   -5,    0,  30,  30,  30,  30,   0,   -5
    PVAL    5,   10,  50,  50,  50,  50,  10,    5
    PVAL    0,    0,   0,   0,   0,   0,   0,    0

 

So, this is flipped compared to the image. The value of a rook (for white) on the bottom left square of the board is "-10".  For black, we flip the squares, so the table applies directly as seen. A black rook on A7 is worth "-120".  So far so good.  Now, note that for space reasons this table is bytes. But the evaluation score is a word.  So we're adding signed bytes to a word.  Guess what I got wrong!  I was just assuming in my code that the values in the evaluation tables were all positive.

 

So, wherever you see a negative number in the tables, the evaluation algorithm - instead of adding the small signed value - decided that this was an unsigned value and added that instead. What does this mean?  Well, a black rook on A8 instead of being worth "-10" became worth "256-10" = 246.  Given that a pawn is only worth 100, you can figure what a difference this will make to the evaluation of a position. In theory the game would be willing to sacrifice two and a half pawns if it could get/keep its rook on the A8 position. Whoops!

Another way of looking at this is that it considered a piece in a really bad position much more desirable than a piece in a good position, but with the constraint that it still prioritised material in the long run.

 

It's quite remarkable that the game played as well as it did, given this constraint/restriction. I've now fixed up the additions so that correct + or - is done. This should rather dramatically change the "style" of play for the computer. I've only had the one game, but will be different, I'm sure.

 

I've also had a bit of a stab at working in more randomness into the openings. It starts out (on the 1st move) being 2.5 pawns random, but halves that with each move, so by the 7th move or so it's not random at all.  I expect the upshot of this is that we will see more opening variety. Fingers crossed.

Meanwhile, I'm working on the 3E+ conversion. It's going OK, but there's a LOT of code that does bank switching and I have to just run it, see why it crashed, fix and adjust, rewrite some stuff and continue. Slow work, not terribly rewarding yet. But I can see the benefits at the end and I'll try and keep going.

Meanwhile, here's an updated binary with the fixed evaluations. Should be interesting.

 

 

 

 

 

 

 

 

 

chess20200503_3pq4.bin

Edited May 3, 2020 by Andrew Davie

[+Andrew Davie]

Aside from a minor colour tweak to the board, no changes.

These are 3-ply, 4-ply, 5-ply, and the first 6-ply release. I expect the 6-ply to take about a day per move
Got the idea for releasing it from the "postal chess" option on the chess challenger image, above.

Again, "3pq6" = 3-ply with 6-ply quiescence. This will be the quickest.

"5pq6" = 5-ply with 6-ply quiescence. And so forth.

 

 

chess20200503_5pq6.bin chess20200503_4pq6.bin chess20200503_3pq6.bin chess20200503_6pq6.bin

[+Andrew Davie]

It's still weak on having a plan on endgames. That's basically because it has no endgame at all.

It's still a lot of fun to play, though. Here's one where I was certain I was going to lose, and wanted to record for posterity how it was working on promoting that pawn. But, it wasn't strong enough, in the end.  It did really well to get into that position though. Interesting how it promoted the pawn to a rook because it knew it was going to be captured, and it's less painful to lose than a queen  but still had the same attacking moves, mostly. Ha.
This is just level 3, though, the easiest level. I suspect it would play a lot better on a later level.
Can't wait to start putting some endgame nous in. That will come after 3E+