Chess engines on C64, Amiga, ST (like Colossus Chess), how did they work?

[rdhoffmann]

I recently dabbled with old hardware emulators, and started to wonder how those amazing chess programs like Colossus or Chessmaster worked on such hardware with extremely limited resources:

1. Board representation was done using byteboards (e.g. 0x88)?
2. Opening book was based on lines (e.g. e4 e5...) rather than full positions to converve memory?
3. No hash tables (too expensive)?
4. No null move pruning or late move reductions due to limited depth?
5. Move ordering using PV and a few basics like captures first?
6. Evaluation only on the root node, then add/subtract value based on captures when traversing the tree?
7. Lots of special code for certain situations (e.g. endgame K+R vs K)?

Those would be my assumptions. Are those anywhere close or am I completely off here?

[Ras]

1. Board representation was done using byteboards (e.g. 0x88)?

10x12 mailbox is also perfectly fine. Btw., I had a 1040STe with 4MB of RAM and 52MB harddisk.

2. Opening book was based on lines (e.g. e4 e5...) rather than full positions to converve memory?

My engine has a position based book of some 23k plies in 13k unique positions, which takes around 115kB. That's no issue on an Atari ST. An even larger book could have been implemented as data file instead of being an engine part, but that would have meant floppy disk access for those without harddisk.

3. No hash tables (too expensive)?

My engine in the microcontroller version is 272kB ROM size plus using 176kB of RAM (including 100kB for hash tables). That includes also low level driver code for the hardware because there is no OS, but let's just ignore that here. In an Atari ST, the ROM part would have been loaded into the RAM as well, so adding that up, it's 448kB of RAM usage. Add some more for a proper GUI, and you should fit that into 512k. The very early models with the OS loaded from floppy disk and only 512kB total system RAM would not have worked, but the most widespread later models had the OS in ROMs and 1MB RAM by default (and up to 4MB), so that would have been fine.

4. No null move pruning or late move reductions due to limited depth?

Null move pruning was probably too new back then, but I do NMP already from depth 2, and LMR from depth 3. That would have been feasible on an Atari ST as well.

5. Move ordering using PV and a few basics like captures first?

Certainly PV, hash table hit, MVV-LVA. Even history ordering would have been possible, I do that in piece-to-square form.

6. Evaluation only on the root node, then add/subtract value based on captures when traversing the tree?

I do eval with material, tapered PSQT, pawn/rook hash table and more. That would have been possible on an Atari ST as well. What didn't exist back then was Texel tuned PSQTs and material values because the tuning process would not have been feasible.

7. Lots of special code for certain situations (e.g. endgame K+R vs K)?

That's not really much code, it's just using a special PSQT for the defending king and keeping the attacking king close, same as for KQ:K, KNB:K and KQ:KR. Even the 24kB bitbase for KP:K is already in the size I mentioned above.

[Vinvin]

A lot of details here : https://www.chessprogramming.org/Coloss ... Evaluation

Code: Select all

Search

    Iterative Deepening
    Aspiration Windows
    Fail-Soft Principal Variation Search
    Transposition Table
    Move Ordering
        Internal Iterative Deepening
        Killer Heuristic
    Selectivity
        Passed Pawn Extensions (in Endgame only)
        Recapture Extensions
        Adaptive Null Move Pruning
        Futility Pruning
        Mate Distance Pruning
        Late Move Pruning
        Late Move Reductions
    Quiescence Search

Evaluation

    Lazy Evaluation
    Material
    Mobility
    Rook on Seventh
    Pawn Structure
        Pawn Hash Table
        Doubled Pawn
        Passed Pawn
        Candidate Passed Pawn
        Pawn Race Code
    Tarrasch Rule
    Wrong Color Bishop and Rook Pawn
    King Safety
    Mate at a Glance

[rdhoffmann]

Thank you Ras for the detailed answers! Makes perfect sense

A lot of details here : https://www.chessprogramming.org/Coloss ... Evaluation

I saw that, but wasn't sure which version it referred to, the original C64 one or a much later version.

[smatovic]

Maybe of interest:

History of Memory Wall in Computer Chess?
viewtopic.php?t=74751

On Sargon 1:
viewtopic.php?p=856414#p856414

--
Srdja

[mclane]

In those days the programmers had to work with 1 mhz cpus and 32 kb rom and maybe 8 kb ram.
And it is amazong what ELO they generated from , lets say 5 mhz 32 kb/ 8 kb .
Ed Schroeder e.g. is the master in this area.
But others also very good.

I am doing a tournament in the moment with machines arround 1981.

https://www.schachcomputer.info/forum/s ... 90&page=21

And in this area cyrus by Richard lang is of course the big leader of the gang.

Some of the machines did not even had permanent brain. Which normally gives you +50 elo if it is well made.

Code: Select all

 Code:
    Motor                                                       Punkte CyMeCoSfChGaPhScFiSaGrCoMaScPsAtLoMyCXVi    S-B
01: Cyrus Dragon Chess {Brettcomputer}                          6,0/7  · =         1   1   =       1   1 1       19,25
02: Mephisto ESB II {Brettcomputer}                             5,5/7  = · 1 1 1   0               1 1           25,00
03: Conchess 2 mhz {Brettcomputer}                              5,5/7    0 ·   1 = 1 1   1     1                 20,25
04: Sfinks4 TRS-80 {Brettcomputer}                              5,5/7    0   ·   1       = 1 1   1       1       17,50
05: CheckCheck 1.75 XT 350 cycles                               5,0/7    0 0   ·         1 1 1             1 1   10,50
06: Gambiet81 TRS80 {Brettcomputer}                             4,5/7      = 0   · =     1     = 1   1       ?   15,00
07: PhilidorChess XT {Brettcomputer}                            3,5/7  0 1 0     = ·   1 0     1                 14,25
08: Scisys Senator Chess                                        3,5/7      0         ·     = 0 1 0     1   1      8,50
09: Fidelity Chess Challenger Grandmaster Voice {Brettcomputer} 3,5/7  0           0   ·     =   1       0 1 1    6,00
10: Sargon 2.5 Applied Concepts / Chafitz {Brettcomputer}       3,0/7      0 = 0 0 1     · =             1       10,25
10: Grandmaster Chess C64 {Brettcomputer}                       3,0/7  =     0 0     =   = ·   =       1         10,25
12: Conic Computer Chess Modell 7012 {Brettcomputer}            3,0/7        0 0     1 =     · 0     =     1      8,25
13: Mattel Chess Aquarius {Brettcomputer}                       3,0/7      0     = 0 0     = 1 ·             1    6,75
14: SciSys Chess Champion MKIV {Brettcomputer}                  3,0/7        0   0   1 0         · =   =     1    6,25
15: Psi Chess Sinclair ZX Spectrum {Brettcomputer}              3,0/7  0 0                       = · = 0 1   1    5,50
15: Atari Video Chess VCS {Brettcomputer}                       3,0/7    0       0           =     = · = =   1    5,50
17: Logichess2.2 Lynx {Brettcomputer}                           2,5/7  0             0     0     = 1 = ·   =      6,75
18: Mychess DOS IBM XT 350 cycles {Brettcomputer}               2,5/7  0     0         1 0         0 =   · 1      6,50
19: CXG Sphinx Seville CXG-807 {Brettcomputer}                  1,5/7          0     0 0     0         = 0 · 1    1,25
20: Video Chess TI99/4A {Brettcomputer}                         0,0/7          0 ?     0       0 0 0 0     0 ·    0,00

70 Partien von 190 gespielt
Name des Turniers: Zep tepi summer2024
Ort/ Land: DESKTOP-9MPCCNS, Deutschland
Spielstufe: Turnier 40/120 20/60

E.g. the cyrus engine runs on a dragon32 homecomputer.

https://en.wikipedia.org/wiki/Dragon_32/64

The Dragon is built around the Motorola MC6809E processor running at 0.89 MHz.

This machine has a motorola cpu at 0.89 !!!! Mhz. Nevertheless Richard langs engine not having permanent brain,
Is doing very well.

[Vinvin]

...
I am doing a tournament in the moment with machines arround 1981.

https://www.schachcomputer.info/forum/s ... 90&page=21

I like tournaments with computers from the past.
A couple of days ago I played Colossus 4 on a online C64 emulator : https://c64online.com/c64-games/colossu ... ptothegame

And in the doc ( https://gb64.com/oldsite/gameofweek/8/c ... s4docs.txt) , I found old results ...

Code: Select all

 5.c Results
 
 Colossus 4.0 has been tested against numerous other home computer systems and has beaten them all. In tests, sixteen games were played on various levels, with an equal number of whites and blacks for each program. One point was awarded for a win, half a point for a draw, no points for a loss. The result of these tests were as follows: 
 
 Colossus 4.0 (Apple II) beat the following programs by:-
 
 Mychess 2.0          Beyond             CBM 64         10-6
 White-Knight Mk 12   BBC Publications   BBC            11-5 
 Sargon III           Hayden             Apple II       12-4
 Superchess 3.5       CP Software        Spectrum       12-4
 White-Knight Mk 11   BBC Publications   BBC            14-2
 Parker Chess         Parker Games       Atari          14-2
 Cyrus IS Chess       Sinclair           Spectrum       14-2
 Superchess 3.0       CP Software        Spectrum       15-1
 Chess 7.0            Odesta             Apple II       16-0
 Sargon II            Hayden             Apple II       16-0
 Chess                Atari              Atari          16-0
 Chess                Acornsoft          Electron       16-0
 Grandmaster          Audiogenic         CBM 64         16-0
 Chess                Psion              Spectrum       16-0
 Master Chess         Mikro-Gen          Spectrum       16-0
 
Of course, the results cannot be guaranteed precisely, in every set of sixteen games. In practice, they are bound to vary slightly either way, but they do give a very good guide to the relative strengths of the program. 

[Vinvin]

And more results here : forum3/viewtopic.php?p=517062#p517062

[mclane]

Yes. On the c64 cyrus II and colossus are very strong indeed.

I wonder how the strongest c64 engine plays versus clockchess on spectrum.
I think superchess has no permanent brain while clockchess , the successor engine has.

Cyrus II and colossus chess 4 have permanent brain.

That can make 50 elo difference.

I could not take colossus 4 into the tournament because it came out in 1985.

[mclane]

My tournament has been enhanced.
Now chess 7.5 C64 in and also white knight MKII on Acorn Electron. Video Chess TI99/4a was taken out and replaced with millennium chess champion 2.0.