Forty five years ago

[sje]

Forty five years ago the then undergraduate Alex Kotov was finishing up his work on his chess program at MIT. A fifteen page report is available at:

ftp://publications.ai.mit.edu/ai-public ... IM-041.pdf

Alas, the referenced appendices are missing. But it's still a good read and a reminder to be thankful for the advances in theory and other resources that we enjoy today.

Where might we be in 2052, forty five years from now?

[Carey]

Not only is that report available, but so is the complete source code of the program.

It's published in Alan Kotok's thesis.

I have a link to it on my ClassicChess page at

http://ClassicChess.googlepages.com/

The actual paper is available on the Kotok's family website at http://www.kotok.org/AK-Thesis-1962.pdf

[sje]

There's a sample game in appendix three:

[Event "Appendix Three Game"]
[Site "MIT"]
[Date "1962.02.24"]
[Round "-"]
[White "Kotov Chess Program"]
[Black "Garber, M."]
[Result "*"]
[ECO "C26"]
[Opening "Vienna: Falkbeer variation"]
[SOC "7826"]

1 e4 e5 2 Nc3 Nf6 3 Nf3 Nc6 4 d4 exd4 5 Nxd4 Bc5 6 Nxc6 bxc6 7 e5 Qe7 8 Qe2 Ng4
9 Bf4 d6 10 exd6 Bxf2+ 11 Kd2 Qxe2+ 12 Bxe2 cxd6 13 Bxd6 Be3+ 14 Kd3 Ba6+ *

[D] r3k2r/p4ppp/b1pB4/8/6n1/2NKb3/PPP1B1PP/R6R w kq - 3 15

At this point in the game, the program played 15 c4 to shield its king against the checking bishop and demonstrating a novelty where a pawn can jump over a knight when absolutely needed. I suppose every program has a bad day now and then.

[ernest]

Forty five years ago the then undergraduate Alex Kotov was finishing up his work on his chess program at MIT. A fifteen page report is available at:

ftp://publications.ai.mit.edu/ai-public ... IM-041.pdf

Interesting, that Kotov mentions a "alpha-beta heuristic"
Is this already the Newell, Shaw and Simon alpha-beta algorithm (published in 1958)?

[Carey]

First, it's Alan Kotok, not Alex Kotov. That's due to the poor quality of the pdf scan.

And yes, that is indeed 'the' alpha-beta heuristic / algorithm.

It wasn't the first chess program attempt to have the Alpha-Beta, but it was the first playable chess program with it, so the Kotok program is often considered to be the first 'playble' chess program.

The Kotok program definetly had problems and limitations. Many of which were partially fixed in the Kotok-McCarthy program (which is lost).

If you actually examine the source for it, you can see a lot of issues. It took them a long time to reach even that level. You have to remind yourself that this was all new and they were inventing and discovering a lot of new stuff. Plus the difficulties working with machines of that era. (Which makes programs such as Samuel's checkers program even more remarkable!)

But the program is generally considered to be the first real playable program. Reasonably fast computer + compiler (as opposed to slow interpreter) + modern algorithm = first playable program.


As a side note, Alan Kotok died a year or so ago.

[sje]

The machine Kotov used for development was an IBM 7090, first released in 1960. It was the transistorized revision of the earlier and quite popular IBM 709, a vacuum tube machine. Computer time on a 7090 was available at the rate of about US$100 per hour.

A picture: http://www.cozx.com/~dpitts/pix/ibm7090.jpg

The machine's clock rate was about 480 KHz and it had 32,768 word memory of 36 bit words. Kotov could have programmed a bitboard program, but instead he inherited an offset style move generator and used that. (In all, there were seven people who contributed to the program's source.)

[Bill Rogers]

Forty-five years ago I had just arrived in Seattle, Wa. I intended to goto work at the worlds fair. I checked into the YMCA and one of the other guest informed me that the night before there was a great karate match in the Y's gym. It seems that some young man named Bruce Lee just kicked just about everyones butt.
The people at the fair grounds told me that they would not be hiring for another six weeks. On the way back to the Y I passed another employment office. It had people scrambling all over the place so I entered and the next day I was working for Boing Aircraft.
(45) years ago.....
Bill

[sje]

One must wonder if some of the early programs like Kotov's, Greenblatt's, Slate and Atkin's, etc. would have been stronger if only the authors had used algebraic notation instead of the more complicated descriptive and so spent more time on improving playing ability.

Also, although FEN wasn't around 45 years ago, there was plain old Forsyth position notation and it dates from the late 1800's; Kotov would have saved a good deal of programming time using it rather than his descriptive board scan with up to three characters per square.

On the other hand, Kotov's use of console switches for program control and move entry is understandable given that a terminal wasn't always available.

[Carey]

One must wonder if some of the early programs like Kotov's, Greenblatt's, Slate and Atkin's, etc. would have been stronger if only the authors had used algebraic notation instead of the more complicated descriptive and so spent more time on improving playing ability.

I can't really comment on Kotok's program, other than saying it took them a long time to just develop the basic chess playing stuff. The notation wouldn't have taken much time in comparison.

For Greenblatt, he worked on his program for many years. The initial program version was developed pretty quick, but he spent years tinkering, experimenting, refining, etc. with it. It just wasn't in the public eye in those later years.

For Slate & Atkin, the descriptive notation stuff was developed early on, and then reused in the later programs. Modified, ported, etc., but basically reused. So it was pretty much a 'one time' cost. Considering they had many versions spread out over many years, I'd say the cost was darn near zero. (As a side note, they developed Chess 4.0 in just 4 months. It was heavily based on 3.6, but it was still mostly a rewrite / re-thought / re-organization.)

Also, although FEN wasn't around 45 years ago, there was plain old Forsyth position notation and it dates from the late 1800's; Kotov would have saved a good deal of programming time using it rather than his descriptive board scan with up to three characters per square.

It's not unique in Chess programming to spend extra time on fancy I/O. Heck, even I've spent days playing around with output statements and formats just to make something look 'pretty', even though I was the only one going to see it and it wasn't that important.

Also, for chess positions, a board printout is *much* easier to look at and understand, especially by novices and people who don't even play chess (such as programming advisors, thesis review board, etc. etc.)

On the other hand, Kotov's use of console switches for program control and move entry is understandable given that a terminal wasn't always available.

Yup. That's true of the earlier programs, too.

And considering the operating systems of the time prefered batch processing over any form of interactive input, using the sense switches was a good way to do it.

Ironically, that complicates trying to bring the program back into working order on a modern system. I long ago thought of doing a port of it, but assuming I could manage to read the faded assembly listings, trying to do the sense switches would have been too inconvenient to do portably.

[sje]

Had Kotov known of Forsyth input, it would have saved a significant amount of time and code over his approach of descriptive position input. Using it for output would have been less important, but still useful as perhaps it would have stimulated the creation of a second program that constructed diagrams formatted with traditional print graphics.

Anyway, the point is that forty five years later, what is it today that we are missing that will seem so obvious to those chess programmers coding a few decades from now?