Chess

[stepho]

I do remember when I was studying this about 40 years ago that the scoring of each potential board (ie the leaf nodes) was considered vital.

In particular, scoring a group of pieces in relationship to other pieces rather than statically.
See https://books.google.com.au/books?id=dzTY5Nf-IvMC&pg=PA221&lpg=PA221&dq=degroot%27s+law+of+chess&source=bl&ots=gbIBynajKz&sig=ACfU3U12wgwzvvnklFPq1Nu3UBiZSjHY2Q&hl=en&sa=X&ved=2ahUKEwjFlcSpkdjoAhUAH7cAHecDCyIQ6AEwAHoECA4QKQ#v=onepage&q=degroot's%20law%20of%20chess&f=false

DeGroot's Law of Chess said something like "Better chess players play better chess because they are better at playing chess".
By which he meant that better chess players could evaluate (ie score) a potential board better then lesser players.
 

I also remember some early AI software in the 1980's that took everything it knew and tried to form relationships.
It even did things like counted how many black and red squares there were after each move - just in case it changed.
Of course it soon gave up on that but it showed that it was willing to look at anything.
A later version of the same software could win mail based strategy games against humans by finding relationships that nobody else ever thought to look for.
But that was only after playing thousands of games against itself to find the patterns.
Wish I could remember the name of the software.

 

True 6507 based AI is unlikely but perhaps an "expert system" with canned rules for scoring boards is possible.
Something like, a pawn near an enemy queen is good, a knight near the enemy queen is real good, 2 bishops fencing in an enemy non-pawn piece is good.

 

Just had a thought.
The code, constants and strategies never change due to the ROM based nature of the 2600.
But what if we allowed the cartridge a form of NVM (like some carts do for high scores) and allowed it to tweaked some of the weighted values in the board scoring mechanism.
Over time it would get better, depending on what methods lost or won (was it Shannon who did this with a matchbox tic-tac-toe game? damn, my memory is getting worse).

Many of the bigger programs did this (playing against itself thousands of times).
Of course, this is a much more complex program than you have now and I'm truly impressed with what you have so far.

(by the way, I suck at chess)

[+Andrew Davie]

I've put in an extremely rudimentary (and inefficient!) sort in. After the moves are generated at any position (which happens thousands upon thousands of times during the search), I sort them by scanning and finding any captures. Those moves involving captures are placed at the head of the queue, so to speak. The idea is that they are more likely to lead to alpha-beta cutoffs - effectively pruning the search tree. Early alpha-beta prunes means much faster moves.

So, I tested a 4-ply version with the search against a 4-ply without, from a couple of days ago. The evaluation function is slightly more complex in the search version, too, so that makes it slower than the earlier version. Aside from one move where the new version is quite slow compared to the old version, later in the video you can see a significant improvement in speed. In fact, the 4-ply is quite zippy and playable now. I might spend some time trying to optimise the search, as every cycle counts in this situation. But as a proof of concept (well, I knew it was going to work, didn't I) it's great. 

These versions are all pretty clueless at endgames. If you can hang on till the end, you're likely to win. But, to be fair, you should resign when your position is "hopeless" .  I'll get to endgames later. For now it's all about improving the search speed and evaluation of the board at the leaf nodes of the search tree.  Oh, and that "impossible task" - the quiescence at leaf nodes, which I'll get to soon. I promise.

 

NEW (search) version on the left.  Old (no search) on the right.
I waited until both were ready, then started the old version, then the new version, to compare speeds.

Moves are different because the evaluation has changed.


Although not quite as fast - this 4ply is almost as fast as the 3ply from a few days ago. And the 3ply is very quick indeed.
I recommend testing the 4-ply version, as it's now quite usable.
 

chess20200409_sorting_4ply.bin chess20200409_sorting_3ply.bin

Edited April 8, 2020 by Andrew Davie

[+Andrew Davie]

8 hours ago, stepho said:

I do remember when I was studying this about 40 years ago that the scoring of each potential board (ie the leaf nodes) was considered vital.

In particular, scoring a group of pieces in relationship to other pieces rather than statically.

 

Thanks for taking the time with your reply

There have been many different efforts at programming chess over the years, the most interesting of recent developments being AlphaZero, which has not only redefined computer chess, but has completely rejuvenated human chess. It's well worth reading about. AlphaZero uses a neural network, and is self-trained. It played itself for something like 4 hours, and then went on to thrash the world's best human-programmed effort - Stockfish.

Anyway, a neural network is extremely good at representing "relationships" which is pretty much encapsulating what you are talking about (pawn near queen... etc.).  But those sorts of programs are "heavy" in the evaluation routine - and thus significantly reduce the search depth available - and so you need to put in even more smarts to compensate. They were never able to compete with programs that simply went for depth and smaller evaluation routines. And the human "chess-knowledge" embedded in those sorts of evaluations were often at odds with the computer's desire to put pieces in different places, based on the search.

With my puny little 6507 I'm keeping the evaluation extremely simple, working on getting as much speed optimisation as possible so that I can go down as deep in the tree as possible (looks like about 5 ply will be the max).  That should be good enough to give a fun game for most human players, which is pretty much all I want to do. Oh, and beat Video Chess of course

 

Edited April 8, 2020 by Andrew Davie

[Mr SQL]

43 minutes ago, Andrew Davie said:

I've put in an extremely rudimentary (and inefficient!) sort in. After the moves are generated at any position (which happens thousands upon thousands of times during the search), I sort them by scanning and finding any captures. Those moves involving captures are placed at the head of the queue, so to speak. The idea is that they are more likely to lead to alpha-beta cutoffs - effectively pruning the search tree. Early alpha-beta prunes means much faster moves.

 

This is interesting; I'm not sure how well it will do compared to the version without, falling apart not just in the endgame but anywhere playing Hyper modern strategy; attack, sacrifice for position, trade everything immediately like Bobby Fischer:

https://en.wikipedia.org/wiki/The_Game_of_the_Century_(chess)

 

The 4 ply is really solid I haven't gotten to the slow 5-ply or the 3-ply yet but will try this version to compare first - can you make a fast version of the 5-ply with this idea?

 

I'd like to compare that to the 4 ply with/without the scenario.

 

btw just ordered a UNOCart to play this Chess on my Atari with a real CRT

 

[+Andrew Davie]

1 minute ago, Mr SQL said:

The 4 ply is really solid I haven't gotten to the slow 5-ply or the 3-ply yet but will try this version to compare first - can you make a fast version of the 5-ply with this idea?

 

 

chess20200408_sorting_5ply.bin

[Mr SQL]

!

[+Andrew Davie]

20 minutes ago, Mr SQL said:

 

This is interesting; I'm not sure how well it will do compared to the version without, falling apart not just in the endgame but anywhere playing Hyper modern strategy; attack, sacrifice for position, trade everything immediately like Bobby Fischer:

https://en.wikipedia.org/wiki/The_Game_of_the_Century_(chess)

 

 

 

To clear up any misunderstanding - they play *exactly* the same chosen move, given the same evaluation algorithm.

Sorting just speeds up the alpha-beta search - it does not change the move selected.

 

 

 

[+Stephen]

Again - apologies if off topic.  Courtesy of Kevin Savetz, here is Carol Shaw's 2600 Chess source code:

https://archive.org/details/VCScheckersA/page/n15/mode/2up

 

Original post -

 

[+Andrew Davie]

2 minutes ago, Stephen said:

Again - apologies if off topic.  Courtesy of Kevin Savetz, here is Carol Shaw's 2600 Chess source code:

https://archive.org/details/VCScheckersA/page/n15/mode/2up

That's checkers, not chess. Different game

[+Andrew Davie]

Being curious about how much of a difference the sort made, I put a counter in and ran some tests.

To recap, the moves are sorted just after they are generated, at each ply. All my (inefficient) sort does right now is put any capture moves FIRST in the list of moves. The thinking is; capture moves are more likely to make dramatic gains/losses and thus be good/bad. If we can get good moves early on, then we benefit with the alpha-beta algorithm being able to trim parts of the search tree because it "knows" that certain branches wouldn't be selected.  The results are interesting...

 

The moves are (computer=black)

1. E2-E4, E7-E5

2. G1-F3, G8-F6

3. B1-C3, D7-D6

4. F3xE5, D6xE5

So, first we have the counts with the sort disabled. This is running a 4-ply search.
 

MOVE 1 -- 34977 nodes examined
MOVE 2 -- 59717 nodes examined

MOVE 3 -- 116234 nodes examined.
MOVE 4 -- 24416 nodes

Now, the same moves/board positions, but with the (simple, naive) sort enabled...

 

MOVE 1 -- 17466 nodes examined
MOVE 2 -- 12921 nodes examined
MOVE 3 -- 11155 nodes examined

MOVE 4 -- 12590 nodes examined
 

This is a clear indication of the value of even simple move sorting. Look at that difference on move 3 (highlighted) -- no it's not a typo... over 10x more nodes examined in the non-sort version. In other words, 10x slower.  For exactly the same result (in terms of move selected). That's pretty astounding!

This is pretty convincing data to support the idea of putting even more effort into the move sorting.  I have a few ideas.  For example, something as simple as putting non-pawn moves first may very well also make a dramatic difference. Might give that a go next.

A quick test with 5-ply (sorted version first)

MOVE 1: 202163 vs. 390679. (1.93x)

MOVE 2: 375758 vs. 1163976 (3.09x)

These are at opening moves in the game. I expect alpha-beta cutoffs to be far more prevalent (and thus, beneficial) later in the game.

I have a few bugs. One is that pawn promotions are borked. But more to the point, the program may very well crash as soon as a pawn promotion is within the search horizon. The reason is known; when I make a move, I also need to (at some point) "unmake" the move.  The make/unmake code doesn't take account that the piece type may change (i.e., pawn promote), so the board gets confused and things go haywire. I'll fix that prior to the next release, I hope.

 

[+Stephen]

10 hours ago, Andrew Davie said:

That's checkers, not chess. Different game

Wow.  This is why I need to not post after such long days at work.  Probably also explains why I have always been too dumb to play chess.

[devwebcl]

I played yesterday version chess20200407_mobility.bin.

 

The game was much aggressive than other versions; the queen straightforwardly went for my king.
I am not sure if it was an error I did, or the algorithm changed.

 

[Voxel]

1 hour ago, devwebcl said:

the queen straightforwardly went for my king

She was clearly tired of her own.

[Keatah]

Love all the insights and explanations, still complex enough (for my childlike mind) to not lose the magic & mystery of something so in-depth.

 

[jhd]

 

I am a lousy chess player; I play more re-actively than strategically. 

 

I am, however, very much enjoying following the development process and seeing the various iterations of the work-in-progress, even if much of the technical discussion is above me.  

 

It is like reading drafts of a manuscript or seeing the sketches that would become a finished work of art.  

[+Andrew Davie]

6 hours ago, devwebcl said:

I played yesterday version chess20200407_mobility.bin.

 

The game was much aggressive than other versions; the queen straightforwardly went for my king.
I am not sure if it was an error I did, or the algorithm changed.

 

 

The algorithm is the same (negamax), but the evaluation of board positions changed. In that version, I awarded "points" for mobility.  That is, the more moves the computer/player had available in the last nodes of each branch, then the higher the score. Mobility was worth about 1/100th of a pawn's value.  So, if the computer managed to get into a position where all its pieces combined attacked 100 squares (or, put another way, if it had 100 different moves available), then it would consider that about the same value as a pawn - it might in fact decide to sacrifice a pawn for all that extra mobility.

The later versions are slightly different. On each ply I add mobility (x2) for the current player. And so on down the tree. So at the terminal nodes of the tree, you have +/-/+/- along the entire tree, with the leaf nodes thus having a sort of pseudo-difference in mobility. This is my own idea and I haven't read of it elsewhere. It was just very cheap to do, and seemed to temper the mobility component somewhat.

 

Edited to add:  The reason the queen was hyperactive is because she attacks a lot of squares, so moving her significantly increases the mobility score of any position.  She wasn't really after your king - well, she was, but that was incidental. She just liked getting out of the house for a bit.

 

Edited April 9, 2020 by Andrew Davie

[+Andrew Davie]

Game just genuinely check-mated me "mid-game" with a knight and a bishop.

I've never ever seen that before!  Happy to lose and I was trying to win, too -- not just mucking around.

I think this is the first time it's beaten me in a serious game... yay!

[+Al_Nafuur]

16 minutes ago, Andrew Davie said:

Game just genuinely check-mated me "mid-game" with a knight and a bishop.

I've never ever seen that before!  Happy to lose and I was trying to win, too -- not just mucking around.

I think this is the first time it's beaten me in a serious game... yay!

Poor is the pupil who does not surpass his master.

(Leonardo Da Vinci)

[+fdr4prez]

9 minutes ago, Andrew Davie said:

Game just genuinely check-mated me "mid-game" with a knight and a bishop.

I've never ever seen that before!  Happy to lose and I was trying to win, too -- not just mucking around.

I think this is the first time it's beaten me in a serious game... yay!

 

I'm not terribly good at Chess, but my buddies in high school were all in the Chess Club and they were on Chess Team to play against other schools, and such.

 

When they were bored, they'd play games with custom layouts, such as playing with:

1) No queen

2) No Rooks (or no Knights, or no Bishops)

3) Pick any pair to play - such play with knights and bishops only - or play with Rooks and Bishops only  - or play with Rooks and Knights only - etc

3) Play with one bishop and one knight - etc.

4) Play with a Queen and one other type

 

made for interesting games to watch

 

[devwebcl]

I played version: chess20200409_sorting_3ply

It was much easier than the earlier game I played. CPU didn't see I was capturing its king.

 

the screenshot was my turn after it was capturing a pawn with its bishop.

 

[+Andrew Davie]

1 hour ago, devwebcl said:

I played version: chess20200409_sorting_3ply

It was much easier than the earlier game I played. CPU didn't see I was capturing its king.

 

the screenshot was my turn after it was capturing a pawn with its bishop.

 

In this situation you have its Queen under attack. It can push the loss of the queen off its "event horizon" by putting you in check". It thinks it's about to win a king for the cost of a queen. What it doesn't know is that the bishop move is futile, and it just loses a bishop for nothing. This is explained earlier, and will be resolved by the addition of quiescence, which fully plays out at the leaf nodes of the search tree until there are no captures pending. Also, different versions will have different strenghts as I play with things. The 4-ply versions should be significantly stronger than the 3-ply ones.

 

[azure]

11 hours ago, Stephen said:

Wow.  This is why I need to not post after such long days at work.  Probably also explains why I have always been too dumb to play chess.

It's still interesting to see original source code even if it's off topic. The labels and game variable names are so cryptic. I recall seeing coding style like that when I was interning for a company doing work on a VAX.

 

[+Andrew Davie]

3 hours ago, Al_Nafuur said:

Poor is the pupil who does not surpass his master.

(Leonardo Da Vinci)

“The worst evil which can befall the artist is that his work should appear good in his own eyes.”
― Leonardo da Vinci

I adore quotations.

[AW127]

14 hours ago, Stephen said:

Wow.  This is why I need to not post after such long days at work.  Probably also explains why I have always been too dumb to play chess.

 

Probably you only lost some chess games, because you played checkers all the time, while the opponent played chess?

[+Andrew Davie]

I had a bit of insight and found a way that I could embed the quiescence search into the normal alphaBeta search at little extra cost. It's a bit non-standard, so I'm not sure it's really working as it should be. I've been testing it for a few hours now - inconclusive results.  I've just played a full game on 3ply, which should be pretty easy to beat. It's not. I made a queen-losing blunder mid-game, but decided to play on to see how the computer played. It was pretty darn aggressive, and pretty much wiped the floor with me. I made some more blunders, probably because I was spooked. In any case, you can see how few options I have after I lose the queen - I can hardly move anything, and resort to shuffling things around. Meanwhile the computer starts mopping up pieces and I'm doomed. Anyway, I hang on until the grim end, and the computer forces a stalemate (rather than checkmate). Very interesting - this is probably something to do with the board evaluation in these positions. I'll fix that eventually. But anyway, here's a video of the game just described, and the "quiescing" 3ply version I was playing. It's doing very well indeed for an average move-time of (say) 2-3 seconds on a 1.19MHz 6502.

 

 

chess20200409_quiescent_3ply.bin

Edited April 10, 2020 by Andrew Davie