Jump to content
IGNORED

Chess


Andrew Davie

Recommended Posts

24 minutes ago, bizarrostormy said:

Alternatively, it might be nicer to unconditionally store the last-moved-piece, so you can highlight it in the display, and then have a separate bit to indicate whether it is en-passant-vulnerable.

 

Good thinking on the one-bit saving for en-passant, but I think I'll pass on that since there are a couple bits spare and I'm not quite that desperate. But I do agree with your basic premise.

 

As to the store last-moved piece, this is an excellent idea which I shall try to incorporate. The separate bit for en-passant vulnerable is not necessary, as I will still have the original "en passant square" saved, so that tells me if en-passant can occur. Note en-passant is only operating on a pawn which has just moved +2 squares from its home rank to alongside (same row) as an opponent pawn. That opponent pawn can (on the very next move only) capture that pawn that moved +2 by moving to the +1 square that pawn traversed over.

 

Link to comment
Share on other sites

41 minutes ago, bizarrostormy said:

I’ve been returning to the last few posts because I want to make sure I grok the math on your fractional bits. Isn’t it equivalent to creating one giant number, with each value multiplied by (maximum of combined lower values plus ones), stored as a bitstream? In your previous example that would be a + 55b + 55*41c.

 

Yes, that's effectively how it works.

You get (b+41c) by integer-dividing by 55. Let's call that D

So the original number - (D*55) = a

An you can extract any digits from large-numbers by doing them this way using the base of the lowest digit as the divide... multiply value

 

 

  • Like 1
Link to comment
Share on other sites

This is the first working version of what is, essentially, a bizarrely complex system.

 

As discussed earlier, it is greatly advantageous to have moves in order of "bestness" when doing a search, because finding better moves earlier allows for more alpha-beta pruning on the search tree. But also, it has been noted that to have the moves in best order you need to do a search. Catch 22.

 

Well, this code implements a shallow search just after generating moves, in order to calculate the value of each move.  This shallow search happens for the first two plys (although it is adjustable), and continues for just one ply (although, again, adjustable).  So, what does this all mean...?  It's really hard to explain, but basically when the computer generates a list of moves, it effectively re-calls (recursively) the search on each of those, which in turn generate moves to the replies, which then tries to sort the moves by re-calling (recursively) the search on each of those.

 

This sounds like a normal tree-search, but it's not.  In a normal tree search we go... generate the moves, then for each, make the move, and recurse. In this new system it's more like... generate the moves, sort the moves, then for each, make the move and recurse. But the "sort the moves" part consists of "for each, make the move and recurse". So it's pretty much generate the moves, for each, make the move and recurse, sort them all according to the evaluations, then for each, make the move and recurse. but that first "make the move and recurse" is shallow (1-2 ply) just to get a basic evaluation of the move values for the sort to do its job.

 

Now it all appears to be working - not as fast as I hoped - but early days. What this enables me to do is to first do a shallow evaluation (for the first n ply0 at each node, to sort the movelist at that node by the evalated value found by the shallow search. And once sorted, I can cull the movelist to "the top n" moves according to the sorted scores. So instead of a branching factor of (say) 35 moves/ply, I can in theory cut it down to something like "the best 10" moves/ply. In other words, if the shallow search+evaluation is good enough to (mostly) get the best move into the top 10 on the list, then I can ignore the other 25 and get orders of magnitude (literally) speedups.  That's a bit down the track, and it's going to miss good moves sometimes, as you can't always get in the "top n" with a shallow search. But it should do an OK job, and compensated by allowing you to go deeper on those moves after culling. All very interesting.

Anyway, this binary is 4PQ3 and appears to be playing OK.  I played half a game, and it appears to be taking about 40 seconds, give or take, per move... which isn't really all that bad - short enough to wait for.

As an aside, I did some work on the speaking stuff today. No wonder I've been having so much trouble - it turns out when I put the (non working) binary on actual hardware it turns out to be working perfectly after all. It's only intermittent/non-functional/babbling when run on the emulator. So there's either an emulator bug, a wiring bug in my setup, or the converter dongle, or an OS bug on the USB handling, or maybe in Stella/MacOS combination. But it kind of solves a mystery why i've been having so much trouble getting the speech code to work. It seems it was working all along, I just had an issue with the setup I am using.

So anyway, have at it - the first version using the recursive recursive sorting evaluation pre-culling negamax algorithm.

 

 

 

 

chess3E+20200726.bin

  • Like 4
Link to comment
Share on other sites

After much effort - probably because I didn't RTFM - I now have the AtariVox working.

I've thrown in a greeting at startup, and a couple of random phrases when the computer makes its move.

Short video so you can hear it in action, if you don't have an AtariVox...

 

 

 

chess3E+20200727speaking.bin

Edited by Andrew Davie
  • Like 9
  • Haha 1
Link to comment
Share on other sites

I know versions are coming thick and fast, but that's just the nature of creativity, right?  Get it while it's hot.

I put back in the mobility component of the evaluation function, but toned it down just a touch. The bitch is back.

Well, not so much, but this thing is now a very aggressive but still reasonably sound player.

I'm posting a 4PQ3 version, which will take a few minutes/move.

In my opinion, though, quite strong compared to previous versions. I may dig out some opponent programs to check.

Have at it. Would love to hear some impressions from anyone willing to spend half an hour or so challenging it.

 

 

 

Completely destroyed any structure I had, and has a kept a good solid defense of his king.

Managed to get a rook up with a queen sacrifice, of all things, effectively QxR, RxQ, BxQ RxB, which was impressive.

I'd be resigning against a decent human player.
 

chess3E+20200728.bin

Screen Shot 2020-07-27 at 11.49.10 pm.png

Edited by Andrew Davie
  • Like 3
Link to comment
Share on other sites

The latest build jumps and rolls on my OLED TV, and it tried to detect it as PAL based on what it showed on the screen. Maybe it's too many visible scan lines now for it to accept it as NTSC. I can try upload a video if it would be helpful at all. The voice part did work on my AtariVox, however.

Link to comment
Share on other sites

23 hours ago, Al_Nafuur said:

This is not (yet) a checkmate, can it resign?

IMG_20200728_002230.thumb.jpg.b157005c34298bdcc9ff3e529e512914.jpg

Thank you for testing.

 

Whilst technically there is no specific code in there to resign, in this case I'm fairly sure the computer has detected a forced mate-in-2 and ended up with zero valid moves that lead to a better result than "negative infinity" in the evaluation. As I see it, king is in check, and only move is C7-C8, then reply is knight at D7 to any square, discovered check, then only response is rook D8-D7 and then QxR (F5-D7) mate.  So, no matter that it can move the king, that move leads to inevitable loss given you will play the best moves for you.  It therefore ends up with NO valid moves, and is in check, so it flags the game as a loss.

I'm kind of pleased that it's seen this one. I'm calling it mate-in-4, because K-B8, N-N6+ (or N-B5+, or N-B6+, or N-N8+, or N-B8+), R-Q7, QxR++ check mate! It's definitely seen all of those combinations and seen that it's a win for you.  Not a bug, but perhaps people might like to play to the bitter end instead of having the computer deny them the pleasure.

So, congrats you won. What did you think of the gameplay?

 

Edit: Technically this is a "mate in 2", but since computer chess usually refers to half-moves as one ply, to me at least it's a 4-ply mate.

 

 

Edited by Andrew Davie
Corrected my incorrectness
Link to comment
Share on other sites

11 hours ago, Karl G said:

The latest build jumps and rolls on my OLED TV, and it tried to detect it as PAL based on what it showed on the screen. Maybe it's too many visible scan lines now for it to accept it as NTSC. I can try upload a video if it would be helpful at all. The voice part did work on my AtariVox, however.

Thanks. Will be fixed next version, but just as a test can you please flip the right-difficulty switch and try again?

Cheers

A
 

 

... edit: right difficulty controls interlaced/non-interlaced. left difficulty controls PAL/NTSC.

 

Edited by Andrew Davie
Link to comment
Share on other sites

5 hours ago, Andrew Davie said:

So, congrats you won.

thanks

5 hours ago, Andrew Davie said:

What did you think of the gameplay?

it did a quit good opening, but i think it gives a higher priority to the piece value than to the position. The turning point was when i exchange one of my rooks for the two pawns (g & h) in front of it's (casteled) king. Then it's defense line was opened and it's queen far off, so i could chase it's king with my queen and my other rook.

iirc the position before it all ended was like this:
grafik.png.f33bae890fbc2c680474c6af986f7ad9.png

(black to move): R-D8, R-H6+, KE6, R-E6+, B-D6, R-D6+, K-C7, R-A6+

 

Link to comment
Share on other sites

1 minute ago, Al_Nafuur said:

maybe you should use a dynamic position evaluation, not a static? So a field near to the opponent king should have a higher value than a field far away from it.

Well, strangely enough I have been working exactly on this idea.  Thanks for the suggestion; maybe we will see it in action in the next few days :)

It's going to help with making the system perform mates, I hope.

  • Like 2
Link to comment
Share on other sites

13 minutes ago, Al_Nafuur said:

thanks

it did a quit good opening, but i think it gives a higher priority to the piece value than to the position. The turning point was when i exchange one of my rooks for the two pawns (g & h) in front of it's (casteled) king. Then it's defense line was opened and it's queen far off, so i could chase it's king with my queen and my other rook.

iirc the position before it all ended was like this:
grafik.png.f33bae890fbc2c680474c6af986f7ad9.png

(black to move): R-D8, R-H6+, KE6, R-E6+, B-D6, R-D6+, K-C7, R-A6+

 


Thanks for the update/analysis.

 

Remember, when I started the goal was to just have it playing legal chess. I think it's actually good enough now to give enjoyable games - albeit flawed. This is better than I'd ever have hoped, so I'm quite happy with it.

 

Link to comment
Share on other sites

8 hours ago, Andrew Davie said:

I'm kind of pleased that it's seen this one. I'm calling it mate-in-4, because K-B8, N-N6+ (or N-B5+, or N-B6+, or N-N8+, or N-B8+), R-Q7, QxR++ check mate! It's definitely seen all of those combinations and seen that it's a win for you.
 

btw. i call it mate in 2: K-B8, N-B6++

Link to comment
Share on other sites

Just now, digdugnate said:

the discussion of the chess strategy and logic has far outpaced my knowledge set but this is a fascinating read.  very cool to see the progress :)

Feel free to ask for a more detailed explanation of anything in the program that's not clear, and I would be happy to (try to) explain :)

 

  • Like 2
Link to comment
Share on other sites

On 7/27/2020 at 7:07 AM, Andrew Davie said:

After much effort - probably because I didn't RTFM - I now have the AtariVox working.

I've thrown in a greeting at startup, and a couple of random phrases when the computer makes its move.

Short video so you can hear it in action, if you don't have an AtariVox...

 

 

 

 

chess3E+20200727speaking.bin 32 kB · 13 downloads

I have recognized the PlusCart in your video. Have you tried the new version of the STM32CubeProgrammer to flash it?

Maybe this version works better with your Mac...

..or maybe it supports you to screw up your Mac more efficiently.?

Link to comment
Share on other sites

4 minutes ago, Al_Nafuur said:

I have recognized the PlusCart in your video. Have you tried the new version of the STM32CubeProgrammer to flash it?

Maybe this version works better with your Mac...

..or maybe it supports you to screw up your Mac more efficiently.?

I have tried and failed both with MacOS and with Windows inside VirtualBox

The cartridge itself will connect to my WiFi but no update is available in the menu, so I tried STM32CubeProgrammer

That tool fails to install on MacOS, but after finding that fault it failed because of a java versioning error.

So, over to windows, and once again I had a total failure of the software - I can't recall the exact reason.

At that point I gave up in absolute disgust at STM32CubeProgrammer, and put the pluscart aside for another attempt another day, when I am less angry with crappy computer software installs.

  • Sad 1
Link to comment
Share on other sites

10 hours ago, Andrew Davie said:

Thanks. Will be fixed next version, but just as a test can you please flip the right-difficulty switch and try again?

Cheers

A
 

 

... edit: right difficulty controls interlaced/non-interlaced. left difficulty controls PAL/NTSC.

 

I was not able to see a difference with the switch in either setting, unfortunately.

  • Thanks 1
Link to comment
Share on other sites

Something that just occurred to me - and the attached binary is this thought implemented.

And that is, let's think about all the current moves that have been generated from the current position.  Now I have this "force move" option, which will cut short the computer's "thinking" and get it to make the best move found so far. But the best move found can only be one of the moves that have actually been examined and evaluated by the search. So, typically when first implemented this could mean something like the rook's pawn moves forward or something pretty bad. Almost a random move, depending on how quickly you pressed SELECT (to force the move) and of course the search depth.  The search depth being the most critical, because if you are playing a 5-ply search binary, then the way the search works is to look at the first move for the computer, the reply, the reply to that, the reply to THAT... etc. and then the next one at the leaf node of the tree. So, if we had (say) 33 moves at the top level, then each would take (roughly, for the sake of argument) about 3% of the total search time.  If you cut that time short, then you're only looking at a very small number of the available moves, and in particular, on a fraction of the top-level moves. Your chances of having the computer choose a reasonable move are pretty random. So for that reason, forcing a move has been pretty unfair/unrewarding.

But I got to thinking, with the new ordered-search. Originally I had a system that put the capture moves first, and pawn moves last - the thinking being that captures were likely to be dramatic in terms of good/bad, and pawns were pretty much "meh" moves, for the most part.

And then that got superceded by the really weird recursive-recursive move ordering technique explained earlier. That is, rather than a full depth-first search, each time a list of moves is generated for any position, a mini-search at a shallower level is done to allow the moves to be sorted into a semblance of good-to-bad.  That appears to be working OK, although not (yet) as much of a speedup as I'd hoped.

 

 

EDIT: appears to be making weird moves, at least when I have it playing itself. So, I'll check that out. If it's not playing well, just use the previous version :)  The price of risk taking.

 

But anyway, continuing on from that... with the new system we know that after a certain amount of time (that is, the time it takes to do the sub-search so as to enable the computer to sort the moves into a reasonable order before doing an actual search). Well at that point, we do have a fair idea of the value of each move, and so forcing a computer move AFTER that time will actually lead the computer to choose a good (not necessarily great, but definitely not random) move.  So how long is "a certain amount of time"?  Well, unknown really. It depends on how deep the preliminary search (done for sorting) takes.  It can take 10 seconds - or more!  Depends on the settings.  If you want to force a computer move, you don't really want to wait that long, nor do you want to have bad moves if you don't wait that long.

So I got to thinking - well, let's do a breadth-first search.  But just for the sorting.  So what's a breadth-first search?  Well, instead of going deeper... we go wider.  Do ALL the moves for 1-ply, and now we at least have a rough idea of their value after one move. It's a pretty bad idea but a whole lot better than random, or only knowing a small fraction of them. After that 1-ply search is done, which takes a fraction of a second, we could allow a force-move and expect the computer to at least not make major goofs (like missing a queen capture).  But after doing the 1 ply search, then we immediately do a 2-ply search. 2-ply is pretty damn quick - say a second or so.  So that's going to give us an even better idea of the search orders.  If a force move is done at any point (even before the 2 ply is finished) we still have some of the 2-ply nodes done, and the rest are done 1-ply. We will have the best move found so far, which is exactly what we want, and we'll definitely at least have looked at all moves on the top level at least once.  And likewise, after the 2-ply is done, then go to a 3-ply.  That can take a fair whack of time, but hopefully sped up because of the sort ordering of the moves increasing the alpha-beta pruning efficiency.

Now at this stage I continue with the original depth-first search (to, say, ply 4 or 5). It starts to become prohibitive to redo all the moves at each level again and again. 3-ply (say 10 secs) x 30 moves = a long time and it's not practical. So the depth-first search seems to be here to stay. But this hybrid system with (at least) a 2-ply breadth-first search seems the best of both worlds.

The attached binary is rudimentary, but it seems to be working fine. The proof in the pudding, so to speak, is to make your move and wait a short time - say 4 or 5 seconds, and then press SELECT to force a computer move. In most cases the computer should select a reasonable move. Not a good move, not a great move, but generally not a terrible move. And the longer you wait, the better the computer move should be.
Have at it.

I also shifted the talking to the bottom of the frame, hopefully will sync better.

But I've seen some timing flashes on "show me my moves" so I'll have to rework all the timing again sometime soon.

 

chess3E+20200729.bin

Edited by Andrew Davie
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...