Mac Hack

From Chessprogramming wiki
Jump to: navigation, search

Home * Engines * Mac Hack VI

Mac Hack display [1] [2] [3]
Mac Hack on bitmapped display

Mac Hack VI, also called Mac Hack, MacHack VI and the Greenblatt Chess Program, was a chess program, developed in 1966 and 1967 at MIT by Richard Greenblatt assisted by Donald Eastlake for a DEC PDP-6. It was developed entirely in MIDAS, the PDP-6 macro assembler. The Greenblatt Chess Program was the first computer program to play chess in human tournament competitions and be granted a chess rating [4].

Etymology

The name Mac Hack VI comes from Project MAC a large sponsored research program located at MIT. Over time, it became a hack in the sense of Hackers: Heroes of the Computer Revolution, a book by Steven Levy in which Greenblatt appears. The number VI refers to the PDP-6 machine for which it was written [5].

Hash Table

Mac Hack VI was the first chess program which uses a transposition table, but not yet iterative deepening. It regular searched five plies plus quiescence search and a conditional intermediate layer if own pieces were en prise.

In his 1970 paper A New Hashing Method with Application for Game Playing [6], where he introduced Zobrist hashing, Albert Zobrist mentions a possible hashing method to obtain an integer which describes the board configuration, and then to divide the integer by the hash table size and use the remainder as hash address and the quotient as key. However, the integer which describes the board may occupy many computer words, and the divide will be complicated and slow. Further the quotient may occupy several words as well, thus most of the transposition table would be occupied by these keys if type 1 errors were to be avoided. While Zobrist mentions Mac Hack VI used a 32K hash table, he does not made it explicit that Mac Hack used this divide technique.

Type B

Inspired by the Kotok-McCarthy-Program, Greenblatt thought he could do better and he succeeded to do so. Mac Hack VI was Shannon Type B, but was less narrow than Kotok-McCarthy's {4, 3, 2, 2, 1, 1, 1, 1, 0, 0} and used a width of {15, 15, 9, 9, 7, ...} in tournament play. Quote by Richard Greenblatt concerning Mac Hack VI from his Oral History [7]:

Most of this printout was analysis from the Kotok program. And I also saw some kind of a textual thing, which I don’t believe was Kotok’s thesis, but which had some of the same information as Kotok’s thesis. It was probably some kind of a technical report, or something, that was anticipatory to Kotok’s thesis [8]. Anyway, one of the things I remembered, and which I just talked with Kotok, as a matter of fact, a few days ago, was the detail that they had is Alpha Beta, and so forth, and they had these whips, and the whips were set at 4, 4, 3, 3, 2, 2, 1, 1. In other words, that was how many. It would first look at the top ply. It would look at the four best moves. The next plys, it would look at the three best. Next ply, two best, next ply, one best. Well, I just recognized immediately that that was incredibly wrong.

You see, basically looking at only one wide, you just have no signals or noise function. In other words, you look at one move, which you think is the best, but there’s a tremendous amount of noise. Well, you look at some more moves, and if you find that one of those are better, you’ve effectively rejected some noise. Well, essentially the thing that I knew that they did, they were very weak chess players, both McCarthy and Kotok. And basically they had a very romanticized view of chess. And so I knew, however, that chess is a very, very precise game. And you really- the name of the game is take the other guy’s pieces, and you don’t just go along. In any kind of a strong game, you don’t just lose pieces, win pieces, lose pieces, win pieces. I mean, if you lose even a single pawn without compensation, then you may have drawing chances, if you’re lucky. Otherwise, the game is lost. Losing more than one pawn almost invariably results in loss of the game, period.

Opening book

Mac Hack VI incorporated a table of opening positions with selected replies. The opening book was compiled by two MIT students, Larry Kaufman, a chess master and top rated U. S. Junior player, and Alan Baisley a chess expert. It is noteworthy that Larry Kaufman started his computer chess career over 50 years ago as team member of Mac Hack! Quote from Oral History of Richard Greenblatt:

And it was compacted pretty efficiently. And you know, there was a – by later standards it wasn't so big, but at the time it was pretty good sized. I don't know I think it was probably 8,000 or 10,000 moves in there. He – Kaufman spent quite a while doing it. Of course, a number of the moves, you know, would – the game would just play it. There was very little chance of it actually staying in the book. You know, the – but I think Kaufman did a good job and he did – we did perceive some of the – well of course, one of the basic things about computer programs, really to the present day, is that they're very tactical. It's much easier for them to see that the tactics than the strategy. So what's called a closed position is hard for a computer. That's where all the pieces are blocking each other and it's very long maneuvering. Whereas, an open position which is sort of tactical combinations is much more to the computer's liking. So therefore, when designing the opening book, you want to kind of play offbeat and kind of unbalanced type openings that tend to lead to these closed position – open positions, which are then good for the computer. And so we realized that and you know, I think Kaufman did a fairly good job of ...

Matches

Robert Q

First tournament game by a computer, Carl Wagner (2190) - Mac Hack VI aka "Robert Q", January 21, 1967 [9]. "Robert Q", a computer programmed to play chess, was beaten in its first competition with a human, Carl Wagner. The computer, at MIT in Cambridge, Mass., was operated by Allen Moulton, and R. William Gosper, while Wagner made his moves several miles away in the YMCU in Boston. The moves were relayed into the computer by teletype operated by Alan Baisley. "Robert Q" was entered as an experiment, in the monthly Boylston Chess Club Tournament at the Young Mens Christian Union.

RobertQ1967.JPG

Allen Moulton and R. William Gosper operating "Robert Q" on a PDP-6 [10] [11]

RobertQAlanBaisley1967.JPG

Carl Wagner and Alan Baisley (right) [12] [13]

[Event "Boylston Chess Club Tournament"]
[Site "YMCU, Boston"]
[Date "1967.01.21"]
[Round "1"]
[White "Carl Wagner"]
[Black "Robert Q"]
[Result "1-0"]

1.g3 e5 2.Nf3 e4 3.Nd4 Bc5 4.Nb3 Bb6 5.Bg2 Nf6 6.c4 d6 7.Nc3 Be6 8.d3 exd3
9.Bxb7 Nbd7 10.exd3 Rb8 11.Bg2 O-O 12.O-O Bg4 13.Qc2 Re8 14.d4 c5 15.Be3 cxd4
16.Nxd4 Ne5 17.h3 Bd7 18.b3 Bc5 19.Rad1 Qc8 20.Kh2 Ng6 21.Bg5 Re5 22.Bxf6 gxf6
23.Ne4 f5 24.Nf6+ Kg7 25.Nxd7 Qxd7 26.Nc6 Rbe8 27.Nxe5 Rxe5 28.Qc3 f6 29.Rd3 Re2
30.Rd2 Rxd2 31.Qxd2 Ne5 32.Rd1 Qc7 33.Bd5 Kg6 34.b4 Bb6 35.Qc2 Nc6 36.Be6 Nd4
37.Rxd4 Bxd4 38.Qxf5+ Kg7 39.Qg4+ Kh6 40.Qxd4 Qe7 41.Qh4+ Kg6 42.Bf5+ Kf7 43.Qxh7+
Kf8 44.Qh8+ Kf7 45.Qa8 Qc7 46.Qd5+ Kg7 47.Kg2 Qe7 48.h4 Kh6 49.g4 Kg7 50.h5 Qe2
51.h6+ Kf8 52.h7 Qxf2+ 53.Kxf2 Ke7 54.h8=Q a6 55.Qe6# 1-0

The Dreyfus Match

In 1967 AI critic Hubert Dreyfus [14] [15] at MIT was challenged by Greenblatt to play a game against his program. Quote from Oral History of Richard Greenblatt:

And so then as word got around- Well, there was a guy a MIT in those days named Hubert Dreyfus, who was a prominent critic of artificial intelligent, and made some statements of the form, you know, computers will never be any good for chess, and so forth. And, of course, he was, again, very romanticized. He was not a strong chess player. However, he thought he was, or I guess he knew was wasn’t world class, but he thought he was a lot better than he was. So anyway, I had this chess program and basically Jerry Sussman, who’s a professor at MIT now, and who was also a member of our group, had played. It was around and it was available on the machine. People played it, and so forth. And basically Sussman brought over Dreyfus and said, well, how would you like to have a friendly game or something. Dreyfus said, oh, sure. And sure enough, Dreyfus sat down and got beat. So this immediately got quite a bit of publicity.

Herbert Simon, an AI pioneer, watched the match. He said [16] : It was a wonderful game - a real cliffhanger between two woodpushers with bursts of insights and fiendish plans ... great moments of drama and disaster that go in such games.

[Event "The Dreyfus Match"]
[Site "MIT"]
[Date "1967.??.??"]
[Round "1"]
[White "Hubert Dreyfus"]
[Black "Mac Hack VI"]
[Result "0-1"]

1.e4 e5 2.Nf3 Nc6 3.Bc4 Nf6 4.Nc3 Bc5 5.d3 O-O 6.Ng5 Na5 7.Bd5 c6 8.Bb3 Nxb3
9.cxb3 h6 10.Nh3 d5 11.exd5 Bg4 12.f3 Bxh3 13.gxh3 Nxd5 14.Nxd5 Qxd5 15.Bd2 Qxd3 16.b4
Be7 17.Rg1 e4 18.fxe4 Bh4+ 19.Rg3 Bxg3+ 20.hxg3 Qxg3+ 21.Ke2 Qxh3 22.Qg1 h5 23.Bc3
g6 24.Qf2 h4 25.Qf6 Qg4+ 26.Kd2 Rad8+ 27.Kc2 Qxe4+ 28.Kb3 Qe6+ 29.Qxe6 fxe6 30.Rh1
Rf4 31.Be1 Rf3+ 32.Ka4 h3 33.b5 Rd4+ 34.b4 cxb5+ 35.Kxb5 Ra3 36.Kc5 Rd5+ 37.Kc4 b5# 0-1

IFIP Match

In August 1968, at the 4th IFIP conference held in Edinburgh, Mac Hack running on a PDP-10 won an exhibition match versus a program written by John J. Scott, running on a ICL 1909/5. The game was analyzed by Jack Good, as published in Donald Michie's Machine Intelligence 4 [17].

ETH-MIT Match

In 1968, Gerald Tripard, postdoc at ETH Zurich and co-author of the chess program Charly, asked Richard Greenblatt for a match versus Mac Hack VI. Three games were played in October and November 1968 via ham radio [18], all three won by Mac Hack VI [19] [20] [21].

The 70s

Mac Hack was ported to a PDP-10 and was the first computer chess program to be widely distributed. It didn't play any ACM or ICCA tournaments, though. In 1977, Mac Hack played three exhibition games against Bobby Fischer [22]. In 1978, Mac Hack (dubbed Machack) played a match versus the readers of the Computerwoche, a German weekly computer magazine affiliated with the International Data Group, one move per week [23] [24] [25] :

[Event "Schach dem Computer"]
[Site "Computerwoche"]
[Date "1978"]
[Round "?"]
[White "CW-Leser"]
[Black "Machack"]
[Result "1-0"]

1.e4 e5 2.Nf3 Nf6 3.Nxe5 d6 4.Nf3 Nxe4 5.d4 d5 6.Bd3 Be7 7.h3 O-O 8.O-O Nc6
9.Nc3 Nxc3 10.bxc3 Be6 11.Bf4 Re8 12.Re1 Qd7 13.Rb1 Rab8 14.Ng5 Bf5 15.Qh5 Bxg5
16.Qxg5 Rxe1+ 17.Rxe1 Be6 18.Qg3 Rc8 19.Bh6 g6 20.Qh4 f5 21.Qf6 Nxd4 22.cxd4 c6 1-0

CHEOPS

see main article CHEOPS

In the end of the 70s a brute force version of Mac Hack was ported to the Chess-orientated Processing System CHEOPS [26] , one of the first dedicated hardware approaches in computer chess, which original conception and hardware design was instrumented by Edward Fredkin. Unfortunately it never competed against other programs of that time.

See also

Publications

Chapter IV. The Greenblatt Chess Program

Forum Posts

External Links

References

  1. I resign by Lawrence J. Krakauer
  2. Chess stories by Lawrence J. Krakauer
  3. see also 63-chess.mp4 hosted by MIT CSAIL
  4. Richard Greenblatt, Donald Eastlake, Stephen D. Crocker (1967). The Greenblatt Chess Program. Proceedings of the AfiPs Fall Joint Computer Conference, Vol. 31, reprinted (1988) in Computer Chess Compendium, pdf from The Computer History Museum or as or ps] from [1]] at MIT
  5. Mac Hack from Wikipedia
  6. Albert Zobrist (1970). A New Hashing Method with Application for Game Playing. Technical Report #88, Computer Science Department, The University of Wisconsin, Madison], reprinted (1990) in ICCA Journal, Vol. 13, No. 2, pdf
  7. Oral History of Richard Greenblatt (pdf) from The Computer History Museum
  8. Alan Kotok (1962). Artificial Intelligence Project - MIT Computation Center: Memo 41 - A Chess Playing Program. pdf
  9. MIT Computer Loses to Human in Chess. Sun Journal (Lewiston), January 23, 1967, Google News
  10. MIT Computer Loses to Human in Chess. Sun Journal (Lewiston), January 23, 1967, Google News
  11. See also 50 years ago “Robert Q”, a computer programmed to play chess, was beaten in its first competition with a human in the monthly Boylston Chess Club Tournament in Boston. Reddit
  12. Richard Greenblatt, Donald Eastlake, Stephen D. Crocker (1967). The Greenblatt Chess Program. Proceedings of the AfiPs Fall Joint Computer Conference, Vol. 31, pp. 808
  13. Carl Wagner vs Robert Q from lichess.org
  14. Hubert L. Dreyfus (1965). Alchemy and Artificial Intelligence. Rand Paper
  15. Hubert L. Dreyfus (1972, 1979, 1991). What Computers Can't Do.
  16. Mac Hack Attack by Bill Wall, Chess.com, May 13, 2008
  17. Jack Good (1969). Analysis of the machine chess game, J. Scott (White), ICL-1900 versus R.D. Greenblatt, PDP-10. Machine Intelligence Vol. 4
  18. Computer chess via ham radio by Lawrence J. Krakauer
  19. The first inter-computer chess game via ham radio
  20. October 30, 1968 letter from Richard Greenblatt to G. Tripard
  21. Games 2 and 3
  22. Greenblatt Chess Program versus Bobby Fischer three games played 1977 from chessgames.com
  23. Wer setzt Machack matt?], January 05, 1978, Computerwoche 1/1978
  24. Schach dem Computer: Ivan Kühnmund (32) wird die Partie "CW-Leser gegen Machack" kommentieren, January 20, 1978, Computerwoche 4/1978
  25. Schach dem Computer, November 10, 1978, Computerwoche 46/1978
  26. John Moussouris, Jack Holloway, Richard Greenblatt (1979). CHEOPS: A Chess-orientated Processing System. Machine Intelligence 9 (Jean Hayes Michie, Donald Michie and L.I. Mikulich editors) Ellis Horwood, Chichester, 1979, pp. 351-360, reprinted (1988) in Computer Chess Compendium
  27. Letter from L. Stephen Coles to Allen Newell and Herbert Simon at Carnegie Tech , April 23, 1967 after losing from Mac Hack VI
  28. Bendix G-20 G-21 - Wikipedida
  29. Re: Old programs CHAOS and USC by Dann Corbit, CCC, July 11, 2015

Up one Level