---

Computer Chess
A Memorial to BRUTE FORCE

by Louis Kessler
Winnipeg, Manitoba, Canada


This page is dedicated to my computer program "Brute Force", a chess-playing program that participated in the 8th and 9th North American Computer Chess Championships in 1977 and 1978.

I hope you find this presentation interesting, especially from a historical viewpoint.

I also present several challenges to current computer chess programmers, and in so doing, hope that these can stimulate new thoughts in the advances of computer chess programming and artificial intelligence.

[ next | prev | contents | my pages ]

---

Contents

  1. The Beginnings of a Chess-playing Program
  2. BRUTE FORCE vs FINESSE
  3. Preparing for World-Class Competition
  4. Seattle, Washington, 1977 - The 8th N.A.C.C.C.
  5. Washington, D.C., 1978 - The 9th N.A.C.C.C.
  6. Unfinished Work and Challenges to Chess Programmers
  7. More Information about Chess and Computer Chess
Also feel free to interactively play the BRUTE FORCE games.       Play it!

[ next | prev | contents | my pages ]

---

The Beginnings of a Chess-playing Program

I was fortunate enough to have entered high school at the beginning of the computer revolution. In 1972, our city's high schools were provided access to a Control Data Corporation mainframe computer. The access was via a card reader and printer in our school. We had two keypunches and the students were allowed to keypunch programs onto cards, submit the cards via the card reader, and wait a few minutes for the program listing and output to be returned and printed.

I immediately took to this, card punching programs in the FORTRAN programming language for all sorts of things. I starting keeping statistics for my touch football team. I set up a school date-matching service, and had everyone in school - students and teachers included - fill out an Optical Mark Reading (OMR) card answering questions about themselves and what they would like in their date. I even figured out a way to simulate a hockey game complete with team and individual scoring statistics; we had 12 friends each pick a team and I simulated a complete 72 game professional hockey season, posting the game summaries, team standings, and scoring stats each week.

But the challenge stood before us. My friend Carl Schwarz and I both saw that Chess was the ultimate game to program. We were both reasonably-good high school players, but producing a chess program that would play seemed so much more exciting.

In the October 1974 Manitoba Department of Education Bulletin, we posted the following:

Chess

Man vs. man, man vs. machine, and now machine vs. machine. Two former students of West Kildonan Collegiate, Carl Schwarz and Louis Kessler, are pitting their wits and programming skills in a contest between their two chess programs. The winner will pit his program against all comers (programs only, of course).

Carl has indicated his interest in organizing a Manitoba Schools Computer Chess Tournament for this school year. If you are interested, start working on your chess program.

Carl and I both set to the task to produce a chess-playing computer program. Several steps had to be done. We first had to make the program understand the game and be able to read in moves, determine all possible moves in a position, make a move using some sort of strategy, and finally output the selected move. We scanned through what little literature there was on computer chess and used our own ingenuity to come up with our own versions of what we thought was the chess program of all chess programs.

Finally, the time had come to put the programs to the test. In the April 1975 issue of the Manitoba Department of Education Bulletin, the following announcement was made:

Manitoba Schools Computer Chess Tournament

The October issue mentioned that Carl Schwarz and Louis Kessler were interested in organizing a chess tournament for chess programs and their programmers. Both gentlemen have a program that plays chess. They will play their chess programs against each other and against all comers. The tournament will the held at Phoenix Data Limited, 550 Berry St., Winnipeg on Saturday May 10, 1975 between the hours of 9:00 a.m. and 12:00 noon. If you have given serious thought to writing a chess program, you are invited to apply to attend. Application forms may be obtained by telephoning 943-3473 and asking for a Computer Chess Tournament Application Form. For the assistance of those working of a program, a list of books on programming a computer to play chess is provided at the end of this bulletin.

[ next | prev | contents | my pages ]

---

BRUTE FORCE vs FINESSE

The day of the tournament had arrived. This was to be the first and only Computer Chess Tournament ever to be held in the Province of Manitoba in Canada. As it turned out, there were no other entries. It was Carl's program against mine in a very friendly rivalry. Our tournament was written up in Winnipeg's two daily newspapers. I will let them describe the tournament for you.
Queen to Knight Three As Computer Plays Chess
By Dennis Hryciuk - Free Press Staff Writer
Printed in the May 12, 1975 Issue of the Winnipeg Free Press

Two young men squared off against each other Saturday in a chess game neither man played. Instead, a computer clicked out hundreds of feet of paper and "told" Carl Schwarz and Louis Kessler what moves to make.

The computer, in reality, was playing a game of chess against itself in a contest between programs drawn up by Messrs. Schwarz and Kessler, both 18-year-old students at the University of Manitoba.

"It's a contest between brute force and finesse," said Mr. Schwarz, who grinned about the "finesse" of his program consisting of 1,100 cards with 800 instructions to the computer. Mr. Kessler didn't deny the "brute force" description of his program, which was made up of 350 computer cards containing 250 instructions.

The contest began at 9 a.m. in a data center on Berry Street, after the two mathematics students fed their opposing chess programs into the computer. After that, the two students became a blur of activity as each one rushed to a card-punching machine to record the latest move of his opponent.

"My knight is going to take your bishop," one of them would guess. "No, I forced you to take my bishop," the other would reply.

The guessing about what each man's program would do next continued until 11 a.m., when the computer had to be shut down for installation of equipment in the data center.

Recording the moves was George Dorward, who taught computer programming to Messrs. Schwarz and Kessler when they were students at West Kildonan Collegiate. "There's only one thing more complicated than a chess program, and that's one for scheduling classes," Mr. Dorward said. "I was their instructor in name only," he said of his former students.

Both students said it took them about two years to develop their programs, and Mr. Schwarz estimated it would have taken about three months of "doing nothing else" to develop his.

Although the game of wits was interrupted Saturday, the styles of the two programmers were evident in the ways each program played the game. Mr. Schwarz's program, for instance, consistently took four to six seconds to make a move. Mr. Kessler's on the other hand, was wildly erratic, taking anywhere from one to 32 seconds to move a piece.

Will brute force or finesse prevail? It's anyone's guess, as the game continues where it left off when Messrs. Schwarz and Kessler meet again at 7 p.m. Tuesday in another computer center at 103 Water Avenue.

My program played with what I called a "brute force" style. After this Free Press article, the name stuck, and the program was henceforth known as BRUTE FORCE.

The Winnipeg Tribune covered the end of our tournament:

Students play chess with computer cards
Printed in the May 17, 1975 Issue of the Winnipeg Tribune

A computer chess tournament which began Saturday between two Winnipeg university students finally ended Thursday. Louis Kessler's program checkmated his friend Carl Schwarz' program in 55 moves in a second and deciding game played at the West Kildonan Collegiate.

Saturday's game was cut short because the computer was powered down for repairs. That game resumed Tuesday but ended in a draw. A second game was begun immediately and ended Thursday night. Mr. Schwarz estimated each game took about four hours to play.

The students first became interested in playing computer chess while taking an introductory computer science course in high school.

During the tournament, the computer buffs fed their programmed cards into the computer. "It would take the computer about 35 seconds to go through the cards and tell us what other information it required," said Mr. Schwarz. "We'd type this information onto another card and feed it, along with the rest of the program into the computer again."

Both men will study mathematics next term, but they'll continue their chess tournaments. "We've already found several bugs that can be fixed-up for the next game," said Mr. Schwarz. They'll break for the summer for jobs and vacations and resume in the fall.

The chess games were part of a tournament for high school students devised by the students. The department of education's computer services sponsored the tournament. However, only Mr. Kessler and Mr. Schwarz entered the competition, said Duncan McKay, a computer consultant for the department. Unless a student had a program worked out or at least started, he couldn't have been ready in time to play, said Mr. McKay. But he hopes the tournament can become an annual event with more students getting their programs ready on time. There are 26 computer terminals in Winnipeg and rural Manitoba available to students.

Mr. Schwarz spent about two years, on and off, developing his program. "But anyone who has taken a high school computer course for about a year and a half and has a basic knowledge of chess could write a program in about three months," he said. "And once you get started on computer chess, you're hooked." Mr. Schwarz would also like to enter his program in the Canadian computer chess championships. "I don't know how well it would do, but I'd like to try," he said.

Unfortunately, neither Carl nor myself had retained a listing of these two games. They were truly very entertaining and the quality of play in these games was quite unexpected.

[ next | prev | contents | my pages ]

---

Preparing for World-Class Competition

As it turns out, Carl never really continued on in the computer chess field, but I did.

Carl did, however, support and encourage my development of BRUTE FORCE. He even managed to exact his revenge with a personal game against it:


Game: June 21, 1976
White: Carl Schwarz
Black: BRUTE FORCE
      Play it!

1. d4 d5 2. Nf3 f6 3. Nc3 g5 4. g3 g4 5. Nd2 Nc6 6. Nb3 Bf5 7. Bg2 e6 8. Bf4 Nb4 9. e4 Bxe4 10. Nxe4 e5 11. dxe5 dxe4 12. Bxe4 Qxd1+ 13. Rxd1 c6 14. a3 Na6 15. exf6 Nxf6 16. Bf5 Nc5 17. Nxc5 Bxc5 18. O-O b5 19. Rfe1+ Kf7 20. b4 Bb6 21. Re6 Rhe8 22. Rxe8 Rxe8 23. Rd6 Re1+ 24. Kg2 Re2 25. Rd2 Rxd2 26. Bxd2 h5 27. Bd3 a6 28. c4 Ng8 29. cxb5 axb5 30. Be4 Ne7 31. Bg5 Nd5 32. f3 gxf3+ 33. Kxf3 Kg7 34. h4 Ba7 35. g4 hxg4+ 36. Kxg4 Bb8 37. Kf3 Bc7 38. h5 Bb6 39. h6+ Kf7 40. h7 Kg7 41. Bh6+ Kh8 42. Bf8 Bd8 43. Bd6 Bf6 44. Kg4 Bb2 45. Kf3 Kg7 46. Kf2 Bxa3 47. Be5+ Nf6 48. Bxf6+ Kxf6 49. h8=Q+ Kf7 50. Qc3 1-0


In the summer of 1976, I entered BRUTE FORCE in a Canadian Computer Chess Tournament that was to have been held in Edmonton. My program was accepted on the basis of sample games I had sent in. I was preparing to attend the tournament when a plane strike intervened and forced the tournament's cancellation.

That fall, I discovered a chess playing program was available on a PDP Minicomputer at our University. (Minicomputers back then were about the size of a refrigerator!) The program was an early version of BELLE, a program developed by Ken Thompson that was a few years earlier, one of the best programs in the world. Finally, I had a chance to benchmark my program and see where it stood. Carl was with me, and we hoped BRUTE FORCE would at least make a game out of it. Every move by either side had us spell-bound, and we could not believe what happened as the game eventually drew to a close:


Game: October 6, 1976
White: BRUTE FORCE
Black: Bell Lab's BELLE on a PDP-11
      Play it!

1. d4 d5 2. Nc3 Nf6 3. f3 Nc6 4. e4 dxe4 5. d5 Ne5 6. fxe4 Bg4 7. Qd4 Nfd7 8. h3 c5 9. Qf2 Bh5 10. g4 Bg6 11. Be3 Rc8 12. Rd1 Nf6 13. Bxc5 Bxe4 14. Bb5+ Ned7 15. Bxd7+ Qxd7 16. Rh2 Bxd5 17. g5 Qe6+ 18. Nge2 Ne4 19. Nxe4 Qxe4 20. Rd4 Qf3 21. Qxf3 Bxf3 22. Bxa7 Rxc2 23. Rd2 Rxd2 24. Kxd2 Bxe2 25. Rxe2 e6 26. a4 Bb4+ 27. Kd3 O-O 28. Re4 Rd8+ 29. Rd4 Rxd4+ 30. Bxd4 g6 31. Bc3 Bxc3 32. bxc3 f5 33. a5 e5 34. c4 Kf7 35. c5 e4+ 36. Kd4 Ke7 37. h4 Ke6 38. Kc4 e3 39. Kd3 e2 40. Kxe2 Kd5 41. c6 {game halted}


By August 1977, I had improved the program to where I felt I could apply to enter BRUTE FORCE in the 8th North American Computer Chess Championships. BRUTE FORCE was accepted on the basis of the following two games:


Game 1: August 22, 1977
White: BRUTE FORCE - Time control set at 120 real seconds per move
Black: Bell Lab's program BELLE running on a PDP-11
      Play it!

1. d4 d5 2. Nc3 Nf6 3. f3 Nc6 4. e4 dxe4 5. d5 Ne5 6. fxe4 Bg4 7. Bb5+ c6 8. Be2 cxd5 9. Bxg4 Nfxg4 10. exd5 Rc8 11. h3 Nf6 12. Qd4 Nc6 13. Qc5 e6 14. Qb5 Nxd5 15. Nxd5 Qxd5 16. Qxd5 exd5 17. c3 Bd6 18. Be3 O-O 19. O-O-O Rfe8 20. Rxd5 Rxe3 21. Rxd6 Rd8 22. Rxd8+ Nxd8 23. Kd2 Re4 24. Kd3 f5 25. c4 Nc6 26. Kc3 a5 27. Nf3 a4 28. Nd2 Re3+ 29. Kc2 Nb4+ 30. Kb1 a3 31. Rd1 axb2 32. c5 Nd3 33. Nf1 Re1 34. Rxe1 Nxe1 35. g3 Nd3 36. g4 fxg4 37. hxg4 Kf7 38. Ne3 g5 39. Nc4 Nxc5 40. a3 Nd3 41. Nxb2 Ne5 42. a4 Ke7 43. a5 Ke6 44. Ka1 Ke7 45. Kb1 Kf7 46. Kc2 Ke7 47. Nd3 Nxg4 48. Nc5 Ne3+ 49. Kd3 Nd5 50. Kd4 Nb4 51. Kc4 Nc6 52. Nxb7 g4 53. Kc5 Kd7 54. a6 g3 55. Kb6 g2 56. Nc5+ Kd6 57. Ne4+ Ke7 58. a7 g1=Q+ 59. Kxc6 Qxa7 60. Nc5 Qa2 61. Nb7 Qc4+ {Adjudicated a win for Black.}


Game 2: August 22, 1977
White: Orest Haluschuk, rated 1700
Black: BRUTE FORCE - Time control set at 30 real seconds per move
      Play it!

1. d4 d5 2. c4 dxc4 3. Nc3 c6 4. Bf4 Na6 5. e3 b5 6. Nf3 f6 7. Be2 g5 8. Bg3 g4 9. Nd2 f5 10. Bh4 Bh6 11. e4 Qxd4 12. exf5 Bxd2+ 13. Qxd2 Qxd2+ 14. Kxd2 Bxf5 15. f3 O-O-O+ 16. Ke1 gxf3 17. Bxf3 b4 18. Ne4 Bxe4 19. Bxe4 Rd4 20. Bf5+ Kb8 21. Bg3+ Nc7 22. Ke2 Nf6 23. Rad1 Rxd1 24. Rxd1 Nfd5 25. Rd4 c3 26. b3 h5 27. Kd3 a5 28. Rc4 Kb7 29. Bd7 Rh6 30. Re4 c5 31. Re5 h4 32. Bf2 Rd6 33. Bf5 Nf4+ 34. Kc4 e6 35. Be4+ Kc8 36. Rxc5 h3 37. gxh3 Nxh3 38. Bg3 Rd7 39. Rxa5 c2 40. Bxc2 Nd5 41. Rc5+ Kd8 42. Bh4+ Ke8 43. Be4 Nhf4 44. Bg3 Ra7 45. Bxd5 Nxd5 46. h4 Rxa2 47. h5 Re2 48. h6 Re4+ 49. Kb5 Nc3+ 50. Ka6 Nd5 51. h7 Nc7+ 52. Rxc7 Re3 53. h8=Q+ 1-0


In October 1977, the following article was printed in the University of Manitoba Newsletter with a brief description of BRUTE FORCE and an indication of the state of the Computer Chess world as it was in that era:
Computer Chess at the U. of M. A program has resided on TSO for the past two years that plays chess. Apparently not too many users are aware of it. Those who have played the program have been surprised by the quality of its play.

The program is named BRUTE FORCE and was developed by Louis Kessler on the University's TSO system. It is written in FORTRAN H extended, and is relatively small, using only 1,500 lines of code and 40K of main storage. It relies on a "brute force" method of deciding its moves, examining every possible reply to a depth varying from 3 to 7 half-moves. But it does not just stop there. After the complete search, all possible sequences of captures are checked in order to verify that a certain move has no obvious flaws. Those who play chess, but have had no experience with chess programs, will find that the program plays a different type of game. It will not make any obvious blunders, such as giving up a piece for nothing, and will usually win any such tactical struggle. However, its weakness, as in most chess programs, is in its positional play.

Chess programs are a fairly rare commodity. There are probably not more than 50 programs in the world that play an acceptable game. The quality of play by these programs has been increasing at a very rapid rate in the last two or three years. The world's best chess program, CHESS 4.6, is a step ahead of all the rest. With the huge jump in computing speed that it realized when the CDC Cyber 176 was developed, the program shocked much of the chess playing public. The program recently won the 1977 Minnesota Open tournament against expert and high class A players with 5 wins and 1 loss. An emergency meeting of the board of the Minnesota State Chess Association was held to decide if the program would be accepted into the championship. They voted to accept it. In the Minnesota State Championship, it did well scoring 1.5 out of 5, but lost to the expert players who had meanwhile studied its games.

CHESS 4.6 will again be competing in the 8th annual North American Computer Chess Championship which it has won 6 of the 7 preceding years. BRUTE FORCE is also entered in the tournament this year and will be representing the University of Manitoba. Only 12 programs were accepted, of which four are Canadian programs. The tournament is sponsored each year by the Association of Computing Machinery, and will be part of the ACM annual conference in Seattle from October 15 to October 18. David Levy, International Chess Master from England, will serve as director for the four-round Swiss-style tournament. He will also give a simultaneous exhibition against all 12 programs.

Anyone interested in playing against BRUTE FORCE need only type: EXEC 'KESSLER.CHESS.CLIST'. This will access the most up-to-date module, which is continually being improved. The program is self-explanatory.

Don't miss next month's newsletter, to find out how Manitoba's entry fared in the tournament.

[ next | prev | contents | my pages ]

---

Seattle, Washington, 1977 - The 8th N.A.C.C.C

The Association of Computing Machinery was about to sponsor its 8th Annual Computer Chess Tournament. Twelve programs were to compete at the Olympic Hotel in Seattle on October 15-17. These included eight American and four Canadian programs. Nine were mainframe programs, two ran on minicomputers, and there was one "microcomputer". 8080 Chess was to be the first microcomputer to participate in a computer chess tournament. CHESS 4.6 was the reigning champion, had the highest USCF rating of 1935, was running on the most powerful computer, and was the odds-on favorite to win again. The participants included:
BLACK KNIGHT Fred Prouse et al. Sperry Univac UNIVAC 1110, Roseville, Minn.
BLITZ V Robert Hyatt U. of Southern Mississippi Xerox Sigma 9, Hattiesburg (USM)
BRUTE FORCE Louis Kessler U. of Manitoba IBM 370/168, Winnipeg, Manitoba
CHAOS Fred Swartz et al. U. of Michigan Amdahl 470 V/6, Sunnyvale, California
CHESS 4.6 David Slate & Larry Atkin Northwestern University CDC Cyber 176, Arden Hills, Minn.
CHUTE 1.2 Mike Valenti U. of Toronto Amdahl 470 V/6, Montreal, Quebec
DUCHESS Tom Truscott Duke University IBM 370/165, North Carolina
OSTRICH Monroe Newborn McGill University Nova 3, Montreal, Quebec
TYRO Albert Zobrist & Fredric Carlson Jet Propulsion Lab. PDP-10 KL, U. of Southern California
WITA Tony Marsland U. of Alberta Amdahl 470 V/6, Edmonton, Alberta
XENARBOR Donald Miller Control Data Services IBM 370/158, Cleveland, Ohio
8080 CHESS Robert Arnstein Processor Technology, Inc. At Site

Six large upright chess-display boards with magnetic-based chess pieces were set up on the stage. A volunteer manned each board and moved the pieces as the game progressed. David Levy, an International Master and the tournament director would walk up and down the stage and provide commentary and analysis for the benefit of the audience as the games progressed.

Directly in front of the platform on the floor were six long double-tables cluttered, variously, with papers, chess boards, and DECwriter terminal/printers connected via long distance to the participants' computers that were in many cases several thousand miles away - except for the one microcomputer that was on site.


Round 1: October 15, 1977
White: BLACK KNIGHT
Black: BRUTE FORCE
      Play it!

1. e4 d5 {This move often took the opponent out of its "book"} 2. exd5 Qxd5 3. Nc3 Qe6+ 4. Nge2 Bd7 5. d4 Na6 {Obviously, 5. ... Nc6 is bad} 6. Bg5 h6 7. Be3 Qb6 {Pressure on b2 while opening the center} 8. Qb1? {Poor move} g5 9. h4 gxh4 10. d5 Qb4 11. Bd4 e5 {An en passant bug first rears its head} 12. dxe6 f6 13. a3 Qe7 14. exd7+ Kd8 {BF sees the pawn as won and does not see a need to take it yet} 15. Qa2 c5 16. O-O-O cxd4 17. Nxd4 Nc5 18. Bc4 Qg7 19. Ne4 Qxg2 20. Nxc5 Qg5+ 21. Rd2 Qxd2+ {Missing the fork that is coming with 23. Ne6+ and the game is now lost} 22. Kxd2 Bxc5 23. Ne6+ Kxd7 {Finally capturing the pawn} 24. Nxc5+ Kc7 25. Bd5 Ne7 26. Bxb7 Rad8+ 27. Kc3 Rb8 28. Qe6 Ng8 29. Qc6+ Kd8 30. Qd7# 1-0


Round 2: October 15, 1977
White: OSTRICH
Black: BRUTE FORCE
      Play it!

1. e4 d5 2. exd5 Qxd5 3. Nc3 Qe5+ 4. Nge2 a5 5. d4 Qf5 6. Be3 g5 7. Ng3 Qg6 8. Bd3 f5 9. O-O Nf6 10. Nb5 Kd8 11. d5 g4 12. Bd4 e6 13. dxe6 Bb4 14. Bxf5 Ke7 15. Bxg6 hxg6 16. Bxf6+ Kxf6 17. Qd4+ Ke7 18. Qg7+ Kxe6 19. Nxc7+ Kd6 20. Nxa8 Re8 21. Qc7+ Ke6 22. Rfe1+ Bxe1 23. Rxe1+ Kf6 24. Rxe8 Bd7 25. Qe5+ Kf7 26. Qe7+ 1-0


Round 3: October 16, 1977
White: BRUTE FORCE
Black: WITA
      Play it!

1. d4 Nf6 2. Nc3 Nc6 3. d5 Nxd5 4. Qxd5 d6 5. a3 e6 6. Qd2 Be7 7. b4 Bf6 8. b5 Ne5 9. f4 Ng4 10. Nf3 c6 11. bxc6 bxc6 12. h3 Bh4+ 13. Kd1 Nf2+ 14. Ke1 Nxh1+ 15. g3 Nxg3 16. Qe3 Qf6 17. Nxh4 Qxh4 18. Qf3 d5 19. Qg4 Qxg4 20. hxg4 Nxf1 21. Kxf1 a6 22. Be3 e5 23. fxe5 Bxg4 24. a4 h5 25. a5 h4 26. Ra4 Be6 27. Bf2 h3 28. e3 h2 29. Bg3 h1=Q+ 30. Ke2 Qc1 31. Kd3 Rb8 32. e4 Rb2 33. Ra3 Rxc2 34. Na2 Qd2+ 0-1


Round 4: October 17, 1977
White: BRUTE FORCE
Black: 8080 CHESS
      Play it!

1. d4 d5 2. Nc3 Nc6 3. Bf4 Nf6 4. Nb5 e5 5. Bxe5 Bb4+ 6. c3 Nxe5 7. dxe5 Bxc3+ 8. Nxc3 Ne4 9. Nxe4 dxe4 10. Qa4+ Bd7 11. Qxe4 b5 12. g4 O-O 13. Bg2 c6 14. h4 a5 15. O-O-O Ra6 16. Qd4 f5 17. Qxd7 Qxd7 18. Rxd7 fxg4 19. Rd6 Rxf2 20. Bxc6 Rf5 21. Bd5+ Kf8 22. Rxa6 Rxe5 23. e4 a4 24. Rb6 g5 25. hxg5 Kg7 26. Rb7+ Kg6 27. Rhxh7 Kxg5 28. Rxb5 Kf4 29. Ra5 a3 30. Rf7+ Ke3 31. Rxa3+ Kd4 32. Rg7 Kc5 33. Rxg4 Kd6 34. Ra6+ Kc5 35. Nf3 Re7 36. Rc6+ Kb4 37. e5+ Kb5 38. Nd4+ Ka5 39. Nb3+ 1-0


CHESS 4.6 drew with DUCHESS in the final round to end up with 3 points out of 4 and won the tournament on tiebreak points over DUCHESS and CHAOS who also had 3 each. Four programs tied with 2 points, and BRUTE FORCE and four others ended with 1 point each.

In the evening after Round 3, David Levy the Tournament Director, and an International Master held a simultaneous exhibition against all twelve programs, winning 10, drawing one, and losing to CHESS 3.6. The next day, after the tournament was over, he played two games of speed chess against CHESS 3.6 and DUCHESS and lost both. This was an important turning point in Computer Chess. The best program had finally reached the level of an International Master - at least at speed chess!


Simultaneous Exhibition: October 16, 1977
White: David Levy
Black: BRUTE FORCE
      Play it!

1. e4 d5 2. exd5 Qxd5 3. Nc3 Qe6+ 4. Be2 Qg6 5. Bf3 Qe6+ 6. Nge2 Nf6 7. O-O g5 8. d4 g4 9. Nf4 Qf5 10. Be2 Bh6 11. Bd3 Qd7 12. Nfe2 Bxc1 13. Rxc1 Nc6 14. Bc4 Na5 15. Bb5 c6 16. Bd3 b5 17. Ne4 Qe6 18. Nxf6+ exf6 19. Nf4 Qe7 20. Re1 Be6 21. Nxe6 fxe6 22. Qxg4 Kf7 23. Bf5 h5 24. Bxe6+ Kf8 25. Qf5 Rd8 26. Bb3 Qd6 27. Re6 Qd7 28. Rxf6+ Ke8 29. Re1+ Qe7 30. Rxe7+ Kxe7 31. Qe6+ 1-0


When I returned, I was interviewed by Joan Saltzberg, and she put together an excellent summary of the tournament and my feelings about it. Her article was printed in the December 1, 1977 issue of the Jewish Post:

Computerized Chess Comes to Manitoba

A proud distinction has been achieved by Louis Kessler, who gave Manitoba a unique status by being the first representative from this province to be accepted in a North American computerized chess tournament.

The Eighth North American Computer Chess Championship took place in Seattle, Washington in mid-October. To the personable young chess enthusiast, the thrill of being part of the tournament far outshone the honor of having his chess program chosen among the select dozen. "It was an experience I'll never forget," was his exclamatory summing-up.

To this reporter, a computer playing chess, after having been fed opposing program's moves, seems like scientific reality carried into a most surreal fantasy. However, Louis has spent five arduous but enjoyable years perfecting his "Brute Force" program, which is made up of computer cards containing no less than 800 instructions. Obviously, then, he had patience and forbearance enough to explain it even to me!

A computer playing chess doesn't seem quite so formidable when Louis explains the process. "A computer program is just a set of instructions for altering the contents of various words in the computer's memory. For example, a certain word may contain the number representing a move that has been made in the chess game. The computer will then use this word to alter the words representing the chess board."

"Part of the computer program is used to evaluate a chess position," he added. "A human might say that the position is good or bad, but the program assigns a numerical value to the position. There are two methods that a chess program can use to play. In the first method a "Brute Force search" utilizes the computer's speed to examine many more moves than a human could ever possibly examine, as much as two million positions while choosing one move. The second method tries to simulate how the human would play chess."

The Swiss-style four-round tournament which took place in Seattle can be likened to curling, said Louis, whereby the winners play the winners and losers play the losers in subsequent rounds.

The chess set was situated in the middle of the table with a chess clock beside it just as chess between two human players. The only difference is that there is also a hook-up by long-distance telephone lines to the computer through a terminal. My program was located on the computer system at the University of Manitoba. The terminal would print out the move the program decided on based on a series of calculations mimicking the human chess player's thoughts. I would make the move on the chess board, press the chess clock, and then wait for the computer program I am playing against to make a reply."

Exciting Tourney. The atmosphere at the tournament was very exciting to the University of Manitoba student who is in his graduate year in Honors Statistics. "There was always the feeling you never knew what would happened next because the programs often played very well. Other times they made obvious blunders. Sometimes a crowd of 100 people watched the games, which were recorded by TV cameras, and when a good move was made, they would break out in applause. For the last round the people in the crowd were so intense that they remained in their places until 2 a.m. when everything was over."

The exhilarating matching of wits at the tournament was the culmination of an exciting learning process which began in friendship and developed into a dedicated pursuit of the craft of computerized chess. In grade 11, Louis and a fellow classmate at West Kildonan Collegiate took up computer programming together. The Collegiate had its own computer terminal for the students.

"Carl Schwarz and I had played chess together in school. We though it might be a good idea to design a computer program to play chess. We developed our own programs; mine was called "Brute Force" and Carl's "Finesse", which reflected the general strategies of our respective programs. Finally in May of 1975 the programs were ready to be played against each other and we had a little tournament. Needless to say, they didn't play very well, but my program won one game and the other was tied. After the tournament I saw a lot of places I could improve."

Now a concentrated and intense period of polishing his program followed. This involved spending weekends alone in front of a computer terminal at the university, and a continuous round of making changes, testing, correcting and making new changes to enable the program to play chess at an acceptable level. Finally it reached the stage where Louis felt confident enough to enter his program in the North American Computer Chess Tournament in Seattle.

To Louis, returning home victorious form the championships was incidental. It was more vital to him that he have the opportunity to gather experience. His score of one win and three losses pleased him. "My involvement at the tournament gave me the impetus to further improve my program," he stressed, "and hopefully get accepted for the 9th Computer Chess Tournament next year in Washington, D.C."

[ next | prev | contents | my pages ]

---

Washington, D.C., 1978 - The 9th N.A.C.C.C

I knew I had my work cut out for me. During the year, time was scarce, but I made several important improvements to BRUTE FORCE's positional and tactical strategies. I thought I had the en passant bug fixed. The two games submitted with my entry for the Washington tournament show off these improvements:
The first game was played against the version of BELLE on our PDP-11. This was the same program that BRUTE FORCE lost to last year. Now, BRUTE FORCE was able to beat BELLE.
Game 1: October 7, 1978
White: BRUTE FORCE - Time control set at 60 real seconds per move
Black: Bell Lab's program BELLE running on a PDP-11
      Play it!

1. e4 e5 2. Nf3 Nc6 3. Nc3 Bc5 4. Bc4 d6 5. O-O Be6 6. Nd5 Bxd5 7. Bxd5 Nf6 8. Bxc6+ bxc6 9. d3 O-O 10. Be3 Bxe3 11. fxe3 Rb8 12. Rb1 Qe7 13. Ng5 d5 14. Qf3 Nxe4 15. Nxe4 dxe4 16. Qxe4 Rb6 17. Rf5 Re8 18. Kf2 c5 19. Qd5 g5 20. d4 exd4 21. Rxg5+ Kf8 22. Qxc5 Qxc5 23. Rxc5 dxe3+ 24. Ke2 Rf6 25. Rf1 Rxf1 26. Kxf1 e2+ 27. Ke1 Re7 28. Rd5 Re6 29. c4 Kg7 30. Rf5 Re8 31. Ra5 c5 32. Rxc5 Kg6 33. h4 f5 34. g3 h6 35. Rd5 Kf6 36. Rd6+ Kg7 37. Rd7+ Kf6 38. Rxa7 h5 39. Rd7 Re3 40. Rd6+ Kg7 41. Rd5 Rxg3 42. Rxf5 Kg6 43. Re5 Rg1+ 44. Kd2 Rh1 45. Kxe2 Rh3 46. Kd2 Rh2+ 47. Kd3 Rxb2 48. a4 Rf2 49. Ke3 Rb2 50. Kd3 Rf2 51. Ke3 Rb2 52. Kd4 Rb3 53. a5 Ra3 54. Rg5+ Kh6 55. Rf5 Kg6 56. Ke4 Rc3 57. Rg5+ Kh6 58. c5 Rc4+ 59. Ke3 Rxh4 60. Rf5 Kg6 61. Rd5 Rh3+ 62. Kf4 Rb3 63. c6 Rb4+ 64. Ke5 Kg7 65. c7 Rc4 66. Kd6 h4 67. Rc5 Rd4+ 68. Ke5 Rd3 69. c8=Q Re3+ 70. Kf5 1-0


The second game was also quite interesting. I played the present version of BRUTE FORCE against the program entered in the Seattle 1977 tournament. I let the older version be white (since it plays its best opening as white) and I gave the programs equal amounts of time. The older version was prone to pushing pawns, and it eventually causes a locked pawn structure which neither program could break through. However, the positional strategy of the newer program and the tactical gain of a pawn later in the game are notable.
Game 2: October 8, 1978 - 1 a.m. to 4 a.m.
White: BRUTE FORCE (1977 Version)
Black: BRUTE FORCE (1978 Version)
Time control for both versions set at 30 real seconds per move. Due to the early morning hours this game was played, over 90% CPU utilization was achived, with about 28 CPU seconds out of every 30 real seconds.
      Play it!

1. d4 d5 2. Nc3 Nf6 3. f3 Nc6 4. e4 e6 5. e5 Nd7 6. h4 Be7 7. g3 O-O 8. a3 f5 9. f4 Rf7 10. Be2 a5 11. Nb5 Ra6 12. Nxc7 Qxc7 13. Bxa6 bxa6 14. c3 Bb7 15. Kd2 Qb6 16. a4 g6 17. Ke3 h5 18. Ra2 Kg7 19. Ra1 Rf8 20. Qc2 Re8 21. Ke2 Rc8 22. Nf3 Nb4 23. Qb1 Nc6 24. Ng5 Bxg5 25. hxg5 Qb3 26. Ra3 Qc4+ 27. Ke3 Re8 28. Kf2 Ne7 29. b3 Qc7 30. b4 axb4 31. cxb4 Qc4 32. Rd3 Bc6 33. Qb3 Qxb3 34. Rxb3 Bxa4 35. Ra3 Bb5 36. Rd1 Bc4 37. Rh1 Nc6 38. Kf3 Nb6 39. Re1 Re7 40. Ra1 Rd7 41. Be3 Kf7 42. Bg1 Kg7 43. Ra3 Kf8 44. Be3 Kg7 45. Raa1 Kf8 46. Bf2 Kg7 47. Re3 1/2-1/2


BRUTE FORCE was again accepted as an entrant in the 9th North American Computer Chess Championship. I headed to Washington, D.C.

The Participants this year included 8 programs running on mainframes, two on mini-computers, and two on microcomputers (now commonly referred to as Personal Computers). One of these PCs, Sargon, would become the first PC to win a Computer Chess tournament game. BRUTE FORCE would have the dubious distinction of being the program it would defeat.

Eight of the twelve programs were improved versions of the programs that competed in the previous year. One of the new programs was Ken Thompson's entry of his latest version of BELLE. Even though it was running on a minicomputer, this version was the first to use chess-specific hardware to speed up its search. This made it by far the fastest-searching program at the tournament.

The participants, along with the language they were written in, their opening book size, and the computer used were:
AWIT ALGOL-W 9,000 Amdahl 470/V6, Edmonton, Alberta
BELLE C 160,000 PDP 11/70, Murray Hill, NJ
BLACK KNIGHT FORTRAN 96,000 Univac 1100, Minneapolis, MN
BLITZ 6.7 FORTRAN 5,000 Univac 1100/42, Washington, DC
BRUTE FORCE FORTRAN 0 IBM 370/168, Winnipeg, Manitoba
BS'66 76 FORTRAN 1,000 IBM 370/168, Toronto, Ontario
CHAOS FORTRAN 7,500 Amdahl 470/V6, Sunnyvale, CA
CHESS 4.7 COMPASS 5,000 Cyber 176, Minneapolis, MN
DUCHESS Assembly 3,000 IBM 370/165, Research Park, NC
MIKE Assembly 0 Motorola 6800, On Site
OSTRICH IV Assembly 0 Super Nova, Montreal, Quebec
SARGON II Assembly 0 Jupiter III, On Site

Several celebrities from the world of chess attended the tournament. Edward Lasker, an International Chess Master and the author of many chess books including Chess Strategy and The Game of Chess celebrated his 93rd birthday on the first day of the tournament. Robert Byrne, former U.S. champion and International Grandmaster also enjoyed the proceedings.


Round 1: December 3, 1978
White: BRUTE FORCE
Black: OSTRICH
      Play it!

1. e4 c6 2. Nf3 d5 3. Nc3 dxe4 4. Nxe4 e6 5. Bc4 b5 6. Be2 Be7 7. O-O Ba6 8. d4 Nf6 9. Nxf6+ Bxf6 10. Ne5 O-O 11. Be3 Qc7 12. f4 h6 13. Qd3 c5 14. Bf3 b4 15. c4 bxc3 e.p. 0-1

Disaster! BRUTE FORCE would not let me enter the en passant move. I know I had programmed it in, but BRUTE FORCE kept responding "illegal move". The tournament rules stated that being unable to enter the move into the program constitutes a loss.

I spent several hours that night on the terminal trying to fix the bug, but this was a line-by-line terminal that made it nearly impossible to do so. I had to give up on that, and hope that an opponent's en passant would not come up in the remainder of the games.

An independent writeup about this game was in the German Computerwoche magazine. See below.


Round 2: December 3, 1978
White: SARGON
Black: BRUTE FORCE
      Play it!

1. e4 e5 2. Nf3 Nc6 3. Nc3 Nf6 4. d4 Nxd4 5. Nxd4 exd4 6. Qxd4 Be7 7. Bf4 O-O 8. Nb5 c5 9. Qa4 a6 10. Nd6 Ng4 11. Be2 h5 12. Bxg4 hxg4 13. O-O-O Qc7 14. Qc4 g5 15. Be5 Qc6 16. Qe2 Bxd6 17. Rxd6 Qa4 18. Qxg4 Re8 19. Qxg5+ Kf8 20. Rh6 Qxc2+ 21. Kxc2 f6 22. Qxf6+ Kg8 23. Qg7+ 1-0


Round 3: December 4, 1978
White: BRUTE FORCE
Black: BS'66'76
      Play it!

1. e4 d5 2. exd5 e5 3. Nc3 f5 4. Nf3 e4 5. Ne5 Bb4 6. Bc4 Ne7 7. Qh5+ g6 8. Qd1 Nd7 9. Nxd7 Bxd7 10. O-O c6 11. dxc6 Bxc6 12. Be6 Qd6 13. Bc4 Qd4 14. Be6 Qe5 15. Bc4 O-O-O 16. Re1 h5 17. Re3 b5 18. Bf7 h4 19. Qe2 Rh7 20. Bb3 Bc5 21. Rh3 Rdh8 22. d4 Bxd4 23. Kf1 Kb8 24. Bg5 b4 25. f4 exf3 e.p. 0-1

And again it happens. BRUTE FORCE lost because it could not enter the en passant move.


Round 4: December 5, 1978
White: BRUTE FORCE
Black: BLACK KNIGHT
      Play it!

1. e4 c5 2. Nf3 Nc6 3. d4 cxd4 4. Nxd4 Nf6 5. Nc3 d6 6. Bc4 Bd7 7. Nxc6 Bxc6 8. Qd4 e5 9. Qe3 Qb6 10. Qxb6 axb6 11. Nd5 Bxd5 12. Bxd5 Nxd5 13. exd5 Ra5 14. Be3 Rxd5 15. c4 Ra5 16. Bxb6 Ra6 17. Be3 Ra4 18. b3 Ra8 19. O-O Be7 20. Rfd1 O-O 21. Rd5 Ra3 22. Rb5 Rb8 23. Kf1 h6 24. Ke2 Rba8 25. Rxb7 Bh4 26. Rd1 Rxa2+ 27. Kf3 Re8 28. Rxd6 e4+ 29. Kg4 Bxf2 30. Bf4 Be1 31. Kh3 g5 32. Be3 Re2 33. Bd4 h5 34. g4 hxg4+ 35. Kxg4 Bf2 36. Kxg5 Bxd4 37. Rxd4 Rg2+ 38. Kf4 Rxh2 39. Rbd7 e3 40. Kf5 e2 41. Rg4+ Kh7 42. Rxf7+ Kh8 43. Re4 Rxe4 44. Rf8+ Kg7 45. Rf6 Rh5+ 46. Kxe4 e1=Q+ 47. Kd4 Qd2+ 48. Ke4 Kxf6 49. b4 Rf5 50. b5 Rf4+ 0-1


The March 1979 issue of Personal Computing Magazine had an extremely well-written eight-page article about the tournament. Their analysis of BRUTE FORCE's play was complimentary, considering its 0-4 result:
BRUTE FORCE turned out to be the only program at the tournament that would fail to win a single game. Its play in the first round ended abruptly when the program had to resign to OSTRICH because it could not enter en passant pawn captures. Potentially, though, it is a strong program and when minor inadequacies have been eliminated, it will be a tough competitor.

A Final Analysis. The true reason for BRUTE FORCE's poor result, in my opinion, was caused more by a computer-timezone difficulty than anything else, a circumstance that I did not foresee:

The previous year, the tournament was held in Seattle. Seattle was two time-zones later than Winnipeg, and the games starting at 7:30 p.m. would begin at 9:30 p.m. Winnipeg time. Within an hour, the computer at the University of Manitoba was being very lightly used, and BRUTE FORCE was getting about 80% of the CPU processor.

This year, however, Washington was one time-zone earlier. Now the game started at 6:30 p.m. Winnipeg time, and by middle game the University computer was heavily loaded. In addition, this tournament was held in early December and the University students were all finishing off their final projects adding to the computer load. BRUTE FORCE was getting only about 10% of the CPU time. Despite improved algorithms, the depth of BRUTE FORCE's search was no deeper than it was the year before, when a 1 to 2 ply improvement was expected. This was a great disappointment.

As far as the en passant bug goes, it turns out this was my own misinterpretation of the rules. I read that "The en passant capture must be done on the very next turn, or the right to do so is lost”. I had interpreted that as losing the right to do any en passant for the remainder of the game, not just for that one specific en passant. My personal lack of experience in tournament chess led to that, and it cost me.

A final article was written about BRUTE FORCE in the December 11, 1978 issue of the Winnipeg Tribune:

Brute Force meets its match in Washington
By George Jacub - Tribune Staff Writer

Louis Kessler tried Brute Force at an international chess tournament last weekend and got creamed each time. A masters degree student at the University of Manitoba in computer science, he was one of four Canadian competitors at the North American Computer Chess Championship. Brute Force was his computer program.

Mr. Kessler admitted on his arrival home that his scorecard from the tourney in Washington, D.C., read no wins and four losses. His program's search capabilities had suffered, he explained, because the U of M computer was being heavily used because exams were approaching, and he was able to get only 10 per cent of its time for his program to use.

"Writing a chess program for a computer entails three phases: giving it the ability to play legal chess, allowing it a way to determine the best move to make, and continuously refining its methodology. You do the latter by playing lots and lots of games, to get the bugs out," Mr. Kessler said. "I left a bug in."

His computer program was one of 12 accepted for the competition, sponsored annually by the Association of Computing Machinery. The victor in Washington was a program called Belle prepared by the Bell Telephone Laboratories from Murray Hill, New Jersey. It had a perfect score of 4 wins and no losses. In the final round, it upset the Chess 4.7 program which had held the title for seven of the past eight years.

Mr. Kessler said the best computer chess programs can now beat 99 per cent of all human players. It has been predicted, he said, that the world's chess champion will be a computer within 30 years.


After the tournament, I quickly made a set of corrections and just to see what would happen, played this one final game - the last program vs program game that BRUTE FORCE would ever play:


Game: December 11, 1978
White: Bell Lab's program BELLE running on a PDP-11
Black: BRUTE FORCE
      Play it!

1. e4 e5 2. Nc3 Nf6 3. Bc4 Nc6 4. Nf3 Bc5 5. Ng5 O-O 6. O-O Nd4 7. Nxf7 Rxf7 8. Bxf7+ Kxf7 9. d3 d5 10. Nxd5 Bg4 11. Qd2 Nxd5 12. exd5 Qxd5 13. c4 Qc6 14. b4 Ne2+ 15. Kh1 Bd4 16. Bb2 Bf3 17. Qg5 Bxg2+ 18. Qxg2 Qxg2+ 19. Kxg2 Nf4+ 20. Kf3 Bxb2 21. Rad1 Bd4 22. Rg1 h5 23. h4 Rd8 24. b5 Rd6 25. a4 Rf6 26. Ke4 Ne2 27. Rxg7+ Kxg7 28. f4 Nc3+ 29. Kf3 Rxf4+ 30. Kg2 Nxd1 31. b6 axb6 32. a5 bxa5 33. c5 Nf2 34. c6 bxc6 35. Kg3 Nxd3 36. Kg2 e4 37. Kh2 e3 38. Kg2 e2 39. Kh2 Rf2+ 40. Kh3 e1=Q 41. Kg3 Qe3+ 0-1

A nice way to end!

I had many more ideas for improvements to BRUTE FORCE. But my time was running out. I was soon to graduate from the University of Manitoba and start full-time employment. I continued to work on BRUTE FORCE, primarily on its user interface - but the seven years of part-time work on the program and full-time thinking about it was taking its toll.

[ next | prev | contents | my pages ]

---

Unfinished Work and Challenges to Chess Programmers

What follows is my final wish list of where I wanted to go with my program, and where I had hoped computer chess in general would lead to. These include the following topics:
  1. The Search Algorithms
  2. Endgame Efficiencies
  3. The Opening Book
  4. The Evaluation Routine
To my dismay, many of my objectives have still not been attempted by even the best computer chess programmers today. Maybe, by presenting them here, one of you will find one of these goals worthwhile, and will pursue it.
The Search Algorithm

I have always been intrigued by the idea of "Brute Force" searching in chess. I was inspired by the program TECH that competed in the early 1970's and placed second in two of the earlier North American Championships. The idea behind TECH was simply to produce a program with minimal chess knowledge that would simply search as much as it could to produce the best move. Its goal was to simply measure the "technology" of the day by using itself to act as a measuring stick for how fast computers were. The faster they would get, the better (presumably) TECH would become.

So I put what I could into BRUTE FORCE. I used a non-recursive version of the Alpha Beta algorithm to back-calculate the best move. This was supplemented by a brand-new "strategy 2" killer heuristic suggested by Monty Newborn in his 1977 article "The Principal Continuation and the Killer Heuristic". I used iterative deepening, searching on opponent's time, swap-off value capture analysis, and many other techniques that were quite advanced at the time. In so doing I was able to analyse up to 5000 positions per CPU second on the IBM 370-168 mainframe. This was as much as any other program at the time.

That all changed when Ken Thompson added chess-specific hardware to BELLE in 1978. The nature of the search had now changed, and had increased the search capabilities up to about 100,000 positions per second. By comparison, twenty years later in the late 1990's, the computer chess-champ DEEP BLUE boasted over 200,000,000 positions per second.

All this power may make the programs sound invincible, but the game of chess is much more complex than it sounds. In a typical middle game position, each side may have about 30 possible moves. After 8 moves in the game (4 by each side), there are about 30 x 30 x 30 x 30 x 30 x 30 x 30 x 30 or about 600,000,000,000 (600 billion) possible moves! Advanced search algorithms such as Alpha-Beta can reduce the search to look at about 5 out of the 30 moves, and still be mathematically sure of getting the optimum result. Well, 5 x 5 x 5 x 5 x 5 x 5 x 5 x 5 is only about 400,000. This was about the maximum capability of BRUTE FORCE in a 100 second move. BELLE was able to add 1 1/2 more "plies" to this, and DEEP-BLUE probably can search about 15 plies deep in a 3-minute move. That is 8 moves for one side and 7 moves for the other.

So in conclusion, even the best programs today cannot see all possibilities, and are not invincible (as Kasparov is demonstrating). My challenge is: is it possible to make them invincible, i.e. let's solve the game of chess! This is being done for simpler games. The game of Othello (6x6) has been solved. Checkers has been getting close to being solved. How about chess? [Note: This paragraph was written prior to Kasparov's 1997 loss to Deep Blue and prior to the solving of checkers in 2007 by Jonathan Schaeffer at the University of Alberta. Computers are now much stronger than people, but are still not invincible, as computer vs computer tournaments like TCEC show.]

To do so, we need a game plan. There are an estimated 10 to the power of 300 possible games of chess. That is a "1" with 300 "zeros" following it. This number is too huge to fathom. It would be impossible to ever play all possible games.

What about computing every possible position. Well, the number of possible positions is about 10 to the power of 60. This number is approximately equal to the estimated number of atoms in the visible universe - still too large to be useful.

For a possibility about this, keep reading ...


Endgame Efficiencies

The only crack available in solving the game of chess may be by solving all possible board positions for a given configuration of pieces one-by-one, and working them back. For example, King and Rook against King is known to be a winning position for the side with the Rook in all but stalemate positions. King and Rook against King and Pawn is much more difficult, but has been solved. The key point is that in the latter positions, if the Pawn is captured, then the board immediately transforms into a King and Rook against King position - and the immediate result is known.

There are probably only about 100,000,000 different selections of chess pieces that can be put onto the board. Some of these positions have already been solved. Ken Thompson throughout the 1980's took to the task of solving as many endgames as he could. It took databases of even hundreds of millions of moves and days of computer time to solve some of them. He has published many of his results in the International Computer Chess Association Journal.

Many of these solutions were unbelievably complicated, with some lines being mate in over 100 moves, and very convoluted moves to force the opponent's pieces to go to certain parts of the board. Some of these endgames are an artform unto themselves and would take months of study for a human chess player to master them.

Today, computers are much more powerful that they were in Ken's days. Multi-gigabyte disk drives are very common. Using known solutions, and adding one piece at a time, the game of chess can be slowly (very slowly!) solved backwardly. There is no reason why thousands of PCs could not simultaneously be working on different parts of the problem. And 100 years from now - it is anyone's guess as to how powerful computers may become. Maybe, 100 years from now the game might be solved.

In the early 1970's in Scientific American, there was a short parody that caught my attention. It was an announcement that the game of chess was solved by a Russian chess computer. It had determined that there is one perfect move for white that would ensure a win with perfect play by both sides, and that move is: 1. a4!


The Opening Book

Many computer programs include a database of opening moves that it could look up. This way much time could be saved in the opening, and good lines of play could be ensured.

I never did program an "opening book" into BRUTE FORCE. One of my difficulties was the amount of labor on my part to manually determine the lines of interest, and then type them all in myself. However, a more severe problem was when most programs ran out of moves in their book and now had to rely on their evaluation function, they often did not like the position they were in and wasted several moves moving pieces that had just been moved. In other words, the opening books were not naturally compatible with the program's method of play. Since BRUTE FORCE already played the opening half-decently, I saw no reason to fight with this problem.

Thinking about the problem led me to think about the opening. I had I.A. Horowitz's "Chess Openings: Theory and Practice". It has 784 pages chock full of openings, and each one is rated as either: (1) better for white, (2) better for black, or (3) approximately equal. These can be thought of as +1, -1, and 0.

I was always intrigued by the possibility of putting all these positions into a single database and back-calculating the optimum moves at each position as a chess program would. This would be akin to solving the game of chess for the small sample space of positions that are in the one book of openings. What would happen? Would white be able to force an advantage? Would black be able to equalize? Or maybe white is zugzwang in the opening position, and black will come ahead.

I do not believe that this type of analysis has been fully explored. It should prove helpful in finding errors in the books on openings, and may even lead to transpositions into other openings that had never been seen. You might also use this to compare one book of openings with another, or to combine the sets from the books. Another book that can be used is Kasparov and Keene's "Batsford Chess Openings". With the technology of scanners and the availability of databases of openings, this could be an excellent project for any university computer science student.

Ken Thompson may have done some work on minimaxing openings and (I seem to recall) had an article in the International Computer Chess Association Journal about it. He apparently found some published typos and errors in the process. I think more work can be done in this field. If chess programmers can cooperate with each other, and open their books (so-to-speak), we can work together to build a "definitive" book of openings that would be useful to everyone.


The Evaluation Routine

Chess programs use some sort of evaluation routine to assess and give a point value to a position. Development of pieces, King protection, pawn structure, and many other factors often combine to produce a single-number evaluation.

The difficulty with these static evaluations is that the program tries to achieve a "best" position, but has no plan of attack. DEEP BLUE loses games to Kasparov for just this reason. Kasparov has a plan of attack and works to achieve the desired result. DEEP BLUE tries to achieve a position that remains a moving target as moves are made by each side. The program HITECH by Hans Berliner was the best program at the sort of planning required for ultimate chess. It used what he developed and called a B* search algorithm that explored interesting lines the way humans do. However, it had nowhere near the searching power of DEEP BLUE. A combination of the two programs may be the route for improvement. As far as I know, no other chess programmer made use of the potential of Berliner's B* algorithm to play chess more human-like.

On a slightly different line of thinking, lets go back to the evaluation. I always had the concept that in order to enhance the search, you must minimize the evaluation. Allowing as many "ties" as possible enhances the reduction in moves to search due to the optimization of the Alpha-Beta algorithm.

BRUTE FORCE primarily relied on a very unique and simple evaluation function. The majority of the weight was based on the minimization of the mobility of the opponent. I had found that reducing the number of possible moves of the opponent was the best way to simply get a chess program to play aggressive attack-oriented chess.

I wanted to explore this further but had reached the end-of-the-line with BRUTE FORCE. I present this concept here to allow other chess programmers to think about it, and possibly increase the weighting of opponent-mobility in their own programs.

[ next | prev | contents | my pages ]

---

More Information about Chess and Computer Chess - and Interesting Links

I was a member of the International Computer Chess Association for about 15 years until about 1994. In that time, I maintained an extensive collection of Computer Chess articles, books, clipping, and a complete collection of the wonderful ICCA Journal, right back to the very rare Volume 1 Number 1. All of these materials have been donated to the University of Manitoba, and are available at the U.of.M's Science Library for anyone to view. A listing of this material is on my Computer Chess Books page.
In an online archive from the German magazine COMPUTERWOCHE is an article about the Washington tournament: http://www1.computerwoche.de/index.cfm?pageid=267&type=ArtikelDetail&id=119022&cfid=120578&cftoken=91787019&nr=66. Highlighted is the 1978 game between BRUTE FORCE and OSTRICH. Roland Pfister was kind enough to translate it for me. This is what it has about BRUTE FORCE:
The Canadian Louis Kessler of the University of Manitoba was not exactly enthusiastic about the performance of his child "Brute Force" (in spite of the IBM 370/168 basis).

After the moves 1.e4 c6 2.Nf3 d5 3.Nc3 de4 4.Ne4 e6 5.Bc4 b5? 6.Be2 Be7 7.0-0 Ba6? 8.d4 Nf6 9.Ne5?? - leaves his knight with peace of mind. 9... 0-0 - The black horse is still being ignored. 10.Be3 Qc7 11.f4 h6 12.Qd3 - shielded at last! 12 ... c5? 13.Bf3 b4 14.c4 bc4 en passant. For the White one (Brute Force) there was no input for the capture en passant. "Thanks" to this malpractice, this program, which is written in Fortran, brought up the rear.


My friend Carl Schwarz is now a Statistics Professor at Simon Fraser University in Vancouver, B.C., Canada. He has a web page at: http://www.stat.sfu.ca/~cschwarz/
Finally, for a whole set of links to Computer Chess related web sites, visit my Computer Chess Links page.

[ next | prev | contents | my pages ]

---

My Home Page
What's New | Your Last Stop
My Family Research | My Genealogical Activities
Jewish Heritage Centre | Cem Photo Project | Jewish Winnipeg Links
Beginning Genealogy | Jewish Gen Links | Speaker Topics
Computer Chess | Game Viewer | Deep Blue | CC Books | Chess & CC Links
Cheryl | Brenna | Brittany
New Addams Family | Mummies Alive! | SOMA
Behold

You can reach me by e-mail at: - my Privacy Notice

Copyright © Louis Kessler
All Rights Reserved