Sargon 1978 - Bringing it back to life

[jdart]

The github docs say in a couple places it has a "full width" search, but it also mentions "minimax." The latter term usually indicates the alpha-beta algorithm but I am not really clear from the description whether Sargon implemented this. The basics of the algorithm go back to Shannon's 1950 paper, so the Sargon authors should have been aware of it.

[MOBMAT]

There was also an article in Byte magazine about Sargon. No idea what year or issue though.

[MOBMAT]

There was an article about Sargon's move generation in Byte magazine back in the day. Not sure of what year or issue though. I recall it had a flowchart of how it generated moves. If I recall, it was move offset on a 10x12 board.

[Bill Forster]

There was an article about Sargon's move generation in Byte magazine back in the day. Not sure of what year or issue though. I recall it had a flowchart of how it generated moves. If I recall, it was move offset on a 10x12 board.

The Byte magazine article (October 1978) is linked from the Sargon chessprogramming.org pagehttps://www.chessprogramming.org/Sargon I link to on the Github project page -> https://www.computerhistory.org/chess/d ... 14f6da6d4/

Your memory is correct, move offset on a 120 byte 10x12 board. So 8x8 with 2 padding rows before and after, 1 padding column before and after. The padding rows and and columns are 0xff filled and landing there indicates you've gone off the edge. This works because move generation is step by step orthogonally, or diagonally, or by knight move. A knight move might take you out two rows or columns. So why is one padding column sufficient? Because at the column edge you are going to wrap around to the other padding column on the other side. Yes I've spent too much time inside this Sargon code.

[Bill Forster]

The github docs say in a couple places it has a "full width" search, but it also mentions "minimax." The latter term usually indicates the alpha-beta algorithm but I am not really clear from the description whether Sargon implemented this. The basics of the algorithm go back to Shannon's 1950 paper, so the Sargon authors should have been aware of it.

I will have to re-read my documentation because I thought I'd made it very clear indeed that Sargon implements minimax and alpha-beta. Alpha-beta is a speed-up optimisation of minimax, properly implemented it generates exactly the same output as minimax. Also quoting myself from a previous post, my Sargon port can generate ascii-art diagrams of the minimax and alpha-beta algorithms as they run;

..... In particular, I made executable documentation - a kind of window into the code, in which Sargon draws little ascii art diagrams of the minimax and alpha-beta algorithms as they do their work. You can observe as you step through with a debugger or just capture everything in this single file https://github.com/billforsternz/retro- ... output.txt and study it after the fact. I was amazed how alpha-beta is implemented in a few lines of assembly...

[MOBMAT]

here is a link to the article about Sargon that appeared in the October 78 issue of Byte magazine.

https://archive.computerhistory.org/pro ... 035.sm.pdf

I miss that magazine.

[Deberger]

The github docs say in a couple places it has a "full width" search, but it also mentions "minimax." The latter term usually indicates the alpha-beta algorithm but I am not really clear from the description whether Sargon implemented this. The basics of the algorithm go back to Shannon's 1950 paper, so the Sargon authors should have been aware of it.

I will have to re-read my documentation because I thought I'd made it very clear indeed that Sargon implements minimax and alpha-beta. Alpha-beta is a speed-up optimisation of minimax, properly implemented it generates exactly the same output as minimax. Also quoting myself from a previous post, my Sargon port can generate ascii-art diagrams of the minimax and alpha-beta algorithms as they run;

The "full-width" classification indicates Shannon Type A Strategy

[bob]

I think a higher-level language version of Sargon was published somewhere. And I think Slate did a "chess 0.5", maybe in Byte Magazine. And thinking back, maybe Personal Computing (I knew Harry Shershow pretty well.)

[Bill Forster]

here is a link to the article about Sargon that appeared in the October 78 issue of Byte magazine.

https://archive.computerhistory.org/pro ... 035.sm.pdf

I miss that magazine.

Checking the ChessProgramming Wiki again I found a second Sargon article in BYTE, the very next month (Nov 1978). This time it's a deep dive into details of the exchange evaluator.

https://archive.org/stream/byte-magazin ... 7/mode/2up

The ChessProgramming Wiki says this is an example of SOMA https://www.chessprogramming.org/SOMA. SOMA stands for "Swapping Off Material Analyser" and was invented as early as 1961 by Maynard Smith apparently. The basic idea is that it is possible to reduce the depth of search by getting the leaf scoring function to evaluate possible exchanges. That way the search doesn't have to continue to quiescence. SOMA works the same way a human player does - count the attackers and defenders to determine whether it is possible to win material - all the while making sure both that pinned pieces are excluded and the order exchanges will take place won't mess things up, to ultimately assess the material return versus the material invested. I first came across SOMA in David Levy's famous 1975 Batsford book. Levy describes how when it was first invented it was only practical to try it out with hand simulations. On page 45 he says "I am amazed that no real chess program has ever used [SOMA] as they would considerably improve the accuracy of the evaluation of terminal positions". I am not sure if he was actually correct in this assertion, and certainly within three years at least one real chess program (Sargon) was using SOMA.

Some previous posts here have expressed surprise that Sargon does a full width, shallow search (Shannon type A strategy). Full width search does drastically affect search depth (I talk about this a lot on my Github page). But SOMA does make it possible for Shannon type A to play reasonable chess, despite very shallow depth, without obvious blunders. However it's not a perfect solution, sometimes there will be tricks, details, and complications in the series of exchanges that SOMA ignores. If SOMA worked perfectly it could only mean chess was a much less interesting game with much less scope for beautiful combinations.

I wish I had noticed this BYTE article when I was actively working on this project. The code in question is very, very dense and tricky. I had a general idea of what was going on, but never understood the details. The BYTE article breaks down the details very well. I am just thankful I didn't really hit problems in this area that I had to debug line by line. There's a part of me that thinks I should work through some examples and double check everything is in order. My x86 emulation of the Z80 RRD and RLD instructions for example are crucial here (these instructions are basically nibble processors, that the Spracklens cleverly applied to their SOMA machinery). But I have spent far too much time on the project already and I have contented myself with setting FixedDepth to 1 and doing a single experiment on a single pair of positions "7k/2pp2pp/4q3/4b3/4R3/4Q3/6PP/7K w - - 0 1" (White can take the free bishop), "7k/2pp2pp/4q3/4b3/4R3/3Q4/6PP/7K w - - 0 1" (the bishop is sufficiently protected). Fortunately the experiment does not indicate SOMA is broken, I'll try to leave it there, for now at least.

[Essay]

Hi Bill,
What an excellent project to revive Sargon and so well implemented by you, many thanks for all your efforts.
Many years ago I attempted to get Sargon running on my Sinclair Spectrum using HiSoft's DevPac assembler and a copy of the Spracklen's Book, I did get it to run without crashing and playing decent chess, however it always played the odd illegal move which was very annoying. Despite my best efforts I never did get it to run without that issue. It may well have been due to the unusual hybrid Z80 code utilized by the Spracklen's and my inability to correctly convert the listed code to pure Zilog Z80.
One thing that always nagged me was whether there might have been an error in the original listing printed in the Hayden publication, it's unlikely I know, but did you find any errors or anomalies as you worked on your project?
Once again, many thanks for such an interesting project, I've played a few games against the UCI Sargon and it plays a surprisingly decent game!