History Of Computer Chess

[towforce]

Late Fifties

Computers were big, slow and expensive. First chess program. Expectation that computers would beat the world champion within 10 years


Late Sixties

Chess computer tournaments were regular events. Moves would be sent to the competition by teletype devices. Unlike traditional quiet chess competitions, these were more fun: there was socialising and discussions with the teams about likely next moves.

Supercomputers became available to developers like Robert Hyatt, and the "depth of search rules over knowledge" paradigm began.

Around this time, computers became able to compete with GMs in high-speed chess due to their ability to find and exploit tactical mistakes the humans make at this timescale.


Mid Seventies

8-bit microprocessors became widely available and dedicated chess computers began - sometimes with as little as 4k for the program and 1k of RAM for storing the game and building the game tree (and choosing a move). This was the first time it was possible to have a chess computer at home. Main 8-bit microprocessors:

Motorola 6502 Simple instruction set, all instructions executed in one clock cycle (today, ARM CPUs, used in most portable devices, are RISC)

Intel 8080 Compromise (became the most successful architecture due to IBM backing for PCs in 1981 - and IBM set industry standards at that time)

Zilog Z80 Complex instruction set. A single instruction could do a lot of work, and programs could be smaller - but a single instruction could take up to 5 clock cycles

Late 80s The IBM PC and its "clones" won the PC wars hands down because it was an "accepted standard". As the CPUs for it became more powerful (especially the 80486), dedicated chess computers were no longer able to compete in terms of playing strength.

As PCs became ever more powerful, more and more chess developers were removing chess knowledge from the EFs, as increasing search depth more than made up for the lost knowledge. Speed and search depth became dominant.

1996 Kasparov lost to Deep Blue in the first game, but went on to comprehensively crush the computer and make it look bad. The fundamental problems for computers like "horizon effect" seemed to be insurmountable. At this time, I vividly remember reading remarks like "Not in my lifetime" with regards to a computer beating the world champion.


1997 Kasparov lost to Deeper Blue in a 6 game match. Later analysis showed that Kasparov had missed some opportunities to save himself.

Around this time, open source chess programs started. Eventually, they would become the strongest programs - but at first, they were quite weak.


Early 2000s Multiple core CPUs for PCs, and auto-tuning in chess programs both propelled strength.


2008 Stockfish launched (a branch of "Glaurung")


Circa 2010 PC programs became stronger than the human world champion.


2011 Stockfish was handed over to "the community" to develop. The size of the community and the range of tools they developed to tune it propelled it into a long term dominance in terms of strength.


2016 Alpha Go v Lee Sedol: first time a Go program beat a top player (speed and search depth doesn't work in Go because of the higher branching factor). This introduced the idea of using NNs in board game programs.


2018 LC0, an open source project inspired by Google's Alpha, was launched


2020 Sockfish obtained NNUE, which boosted it's rating by several hundred elo points.


Early 2020s

Other chess developers incorporated NNUE into their programs and also obtained a boost of several hundred elo points.

Correspondence chess ran into the "death by draw" problem.

[Alexander Schmidt]

A nice site in german about the history of computerchess: http://www.andreadrian.de/schach/index.html

[pepechuy]

Hi.

There is something quite wrong with your timeline:

Late sixties.
Supercomputers became available to developers like Robert Hyatt, and the "depth of search rules over knowledge" paradigm began.

Bob Hyatt had access to Cray supercomputers. But the first ones are from the mid seventies (not late sixties, at any rate).
I am not an expert on his career, but from what I understand, he began to use those supercomputers in the early eighties (not in the seventies).

Probably other chess programmers had access to supercomputers in the late sixties.
But Bob Hyatt would be a bad example for that time frame.

Greetings.

[smatovic]

Would like to add "Kramnik versus Deep Fritz 2006" as the last big match:
https://www.chessprogramming.org/Kramni ... Fritz_2006

And, algorithmic point of view*:

1912, Ernst Zermelo, Retrograde Analysis
https://www.chessprogramming.org/Retrograde_Analysis
1928, John von Neumann, Minimax
https://www.chessprogramming.org/Minimax
1948, Norbert Wiener, in depth limited minimax search with evaluation heuristic
https://www.chessprogramming.org/Norbert_Wiener
1949, Claude Shannon, Type A/Type B
https://www.chessprogramming.org/Claude ... .27s_Types
1956, John McCarthy, Alpha-Beta
https://www.chessprogramming.org/Alpha-Beta
...

*several ideas/concepts/theories were found independently by different scientists on different timelines.

...and maybe the special purpose hardware timeline:

~1980s Belle
https://www.chessprogramming.org/Belle
~1980s HiTech
https://www.chessprogramming.org/HiTech
~1990s Deep Blue
https://www.chessprogramming.org/Deep_Blue
~2000s Hydra
https://www.chessprogramming.org/Hydra
~2017 AlphaZero
https://www.chessprogramming.org/AlphaZero

--
Srdja

[towforce]

Hi.

There is something quite wrong with your timeline:

Late sixties.
Supercomputers became available to developers like Robert Hyatt, and the "depth of search rules over knowledge" paradigm began.

Bob Hyatt had access to Cray supercomputers. But the first ones are from the mid seventies (not late sixties, at any rate).
I am not an expert on his career, but from what I understand, he began to use those supercomputers in the early eighties (not in the seventies).

Probably other chess programmers had access to supercomputers in the late sixties.
But Bob Hyatt would be a bad example for that time frame.

Greetings.

You are right: the program that became "Cray Blitz" started in 1968 - but it wasn't run on a Cray supercomputer until the mid seventies:

https://www.chessprogramming.org/Cray_Blitz

That wouldn't be the only mistake I've made: I've checked, and the first instance of a computer beating a GM at blitz chess was Chess 4.6 v Michael Stein in 1977.

My main intention is to get the history into a very concise format and ensure that the events which I personally consider to be the most important from the point of view of "high level overview" are included. As always with my writing, "very easily understandable" is also a priority.

[hgm]

Instructions on the 6502 took at least 2 clock cycles, even 1-byte instructions. And since the memory interface had only one 8-bit port, so an instruction using direct memory addressing required 4 clocks: one to fetch the opcode, two to fetch the address, and one to fetch the data.

The 6502 was also not from Motorola, but from a competing company set up by a group of engineers that had left Motorola. Motorola produced the 6800, and later 68000.

[towforce]

Would like to add "Kramnik versus Deep Fritz 2006" as the last big match:
https://www.chessprogramming.org/Kramni ... Fritz_2006

Agreed: this is a very reasonable choice of the end of man v machine in chess - and hence very important.

And, algorithmic point of view*:

1912, Ernst Zermelo, Retrograde Analysis
https://www.chessprogramming.org/Retrograde_Analysis

Wow - never heard of this before! However, it does seem to have similarities with dynamic programming, with which I am familiar. It also seems to be a basis for the endgame tablebase. Should tablebase technology be included in my list? I'm not convinced. They are extremely useful, they are a brilliancy, and they are a big contributor to the strength of chess programs. I am certainly very grateful to the people who have created them and made them available online. Having said that, it will sound churlish to say this - but they would never be capable to pushing computer chess to an ultimate level, whereas people used to believe that other technologies would (it seemed to me that many people implicitly believed that increasing search depth would eventually cover up all lack of knowledge and push chess to ultimate levels, but you could never say that about EGTBs: they simply cannot get big enough).

1928, John von Neumann, Minimax
https://www.chessprogramming.org/Minimax

1948, Norbert Wiener, in depth limited minimax search with evaluation heuristic
https://www.chessprogramming.org/Norbert_Wiener

1949, Claude Shannon, Type A/Type B
https://www.chessprogramming.org/Claude ... .27s_Types

1956, John McCarthy, Alpha-Beta
https://www.chessprogramming.org/Alpha-Beta

All tremendously important. The trouble is, they all occurred before computer chess began. Similarly, should the history of railways include the invention of the wheel?

...and maybe the special purpose hardware timeline:

~1980s Belle
https://www.chessprogramming.org/Belle

~1980s HiTech
https://www.chessprogramming.org/HiTech

~1990s Deep Blue
https://www.chessprogramming.org/Deep_Blue

~2000s Hydra
https://www.chessprogramming.org/Hydra

~2017 AlphaZero
https://www.chessprogramming.org/AlphaZero

Interesting one: special purpose hardware demonstrates how much money and effort used to go into the pursuit of stronger computer chess, so yes - very important for understanding how important computer chess used to be. In particular, IBM put a lot of resource into Deep Blue, and Google put a lot of resource into AlphaGo.

[towforce]

Instructions on the 6502 took at least 2 clock cycles, even 1-byte instructions. And since the memory interface had only one 8-bit port, so an instruction using direct memory addressing required 4 clocks: one to fetch the opcode, two to fetch the address, and one to fetch the data.

The 6502 was also not from Motorola, but from a competing company set up by a group of engineers that had left Motorola. Motorola produced the 6800, and later 68000.

These are both very obviously correct: good catch!

https://en.wikipedia.org/wiki/MOS_Technology_6502

From that article: "Typical instructions might take half as many cycles to complete on the 6502 as on contemporary designs"

[hgm]

Although that could be true, comparing clock cycles while disregarding clock frequency has always been misleading. On the Intel 8080 a single-byte instruction took 4 clocks, and each additional memory cycle needed for fetching or execution took 3 clocks. But since memory speed was usually the bottleneck, its clock frequence could be much higher than that of contemporary 6800/6502. In fact the latter required a 4-phase clock, where a second clock input was driven 90-degrees out of phase with the main clock, and served to divide the cycle into 4 parts, each part executing different actions. Later models (like 6809) had a built-in clock generator, which had to be connected to a crystal of 4 times the cycle frequency.

But even in terms of memory cycles the 6502 was a bit smarter than the 8080: the latter needed 1 memory cycle (3 clocks) to fetch the opcode, and then took 1/3 of such a cycle to decode it, before deciding if it had to fetch additional bytes. The 6502 speculatively fetched the byte following the opcode, in parallel with decoding the first, and just discarded it when the decoding revealed it was a 1-byte instruction. Since far fewer than 33% of the instructions in a typical program were single byte, this was a win. But not a dramatic one. The main performance advantage was a smarter architecture / instruction set. On the 8080 one quarter of the instructions served to move data between registers where it could not be processed other than moving it again.

[smatovic]

[...]
All tremendously important. The trouble is, they all occurred before computer chess began. Similarly, should the history of railways include the invention of the wheel?
[...]

Hmm, von Neumann, Turing, Zuse....all pondered about how to use a computer to play chess, the ideas and paper work came first, then the computers, or alike.

--
Srdja