Sargon 1978 - Bringing it back to life

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
jdart
Posts: 3923
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: Sargon 1978 - Bringing it back to life

Post by jdart » Thu May 21, 2020 1:44 am

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
Posts: 163
Joined: Sat Feb 04, 2017 10:57 pm
Location: USA

Re: Sargon 1978 - Bringing it back to life

Post by MOBMAT » Thu May 21, 2020 2:14 am

There was also an article in Byte magazine about Sargon. No idea what year or issue though.
Vince S
Author of MOBMAT

"Reductions, extensions, and pruning, oh my!"

MOBMAT
Posts: 163
Joined: Sat Feb 04, 2017 10:57 pm
Location: USA

Re: Sargon 1978 - Bringing it back to life

Post by MOBMAT » Thu May 21, 2020 2:16 am

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.
Vince S
Author of MOBMAT

"Reductions, extensions, and pruning, oh my!"

Bill Forster
Posts: 20
Joined: Mon Sep 21, 2015 5:47 am
Location: New Zealand
Contact:

Re: Sargon 1978 - Bringing it back to life

Post by Bill Forster » Thu May 21, 2020 3:06 am

MOBMAT wrote:
Thu May 21, 2020 2:16 am
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
Posts: 20
Joined: Mon Sep 21, 2015 5:47 am
Location: New Zealand
Contact:

Re: Sargon 1978 - Bringing it back to life

Post by Bill Forster » Thu May 21, 2020 3:13 am

jdart wrote:
Thu May 21, 2020 1:44 am
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;
Bill Forster wrote:
Wed May 20, 2020 11:18 pm
..... 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
Posts: 163
Joined: Sat Feb 04, 2017 10:57 pm
Location: USA

Re: Sargon 1978 - Bringing it back to life

Post by MOBMAT » Sun May 24, 2020 11:21 pm

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.
Vince S
Author of MOBMAT

"Reductions, extensions, and pruning, oh my!"

User avatar
Deberger
Posts: 45
Joined: Sat Nov 02, 2019 5:42 pm
Full name: ɹǝƃɹǝqǝᗡ ǝɔnɹꓭ

Re: Sargon 1978 - Bringing it back to life

Post by Deberger » Sun May 24, 2020 11:40 pm

Bill Forster wrote:
Thu May 21, 2020 3:13 am
jdart wrote:
Thu May 21, 2020 1:44 am
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
Posts: 20885
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Sargon 1978 - Bringing it back to life

Post by bob » Mon May 25, 2020 6:24 pm

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
Posts: 20
Joined: Mon Sep 21, 2015 5:47 am
Location: New Zealand
Contact:

Re: Sargon 1978 - Bringing it back to life

Post by Bill Forster » Thu May 28, 2020 3:30 am

MOBMAT wrote:
Sun May 24, 2020 11:21 pm
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.

Post Reply