Thursday, January 19, 2017
Hans Berliner Was a Pioneer in Computer Chess
By Byron Spice
Hans Berliner was at the center of computer chess research for two decades.
Former Carnegie Mellon University School of Computer Science faculty member Hans Berliner, a world champion correspondence chess player who built the first game-playing computer ever to defeat a human champion at any game, died Jan. 13 in Riviera Beach, Fla. He was 87.
Berliner, who earned his Ph.D. in computer science at Carnegie Mellon in 1975 and served as a senior research scientist until his retirement in 1998, was at the center of computer chess research for two decades. He led the development of Hitech, the first chess computer to achieve the rank of senior master and, in 1988, the first to beat a grandmaster.
"Hans really was the father of computer chess," said Scott Fahlman, an emeritus faculty member in CMU's Language Technologies Institute (LTI). "Hans not only made major early contributions himself, but his students and those clearly influenced by his insights went on to dominate the field and to finally realize the dream of creating a chess machine that could compete with human players at the world-champion level."
Berliner was born in Berlin in 1929 and emigrated with his family in 1937 to Washington, D.C. At age 13, he learned chess from a friend one rainy day at summer camp. By age 20, he had achieved master status. He eventually became a champion in correspondence chess, in which moves are exchanged via postcard and games could last months or even years.
He won the Fifth World Correspondence Chess Championship in a match that began in 1965 and ended three years later. It was an earlier game against Yakov Estrin of Russia, however, that grandmaster Andy Soltis would rank number one in his 2000 book, "The 100 Best Chess Games of the 20th Century."
Berliner was offered a CMU job soon afterward by Herb Simon and, at age 40, he began work on computer chess and his own Ph.D.
"He was into all kinds of mental games," recalled Michael Shamos, distinguished career professor in the Institute for Software Research and LTI. One day, about 40 years ago, Shamos was playing bridge with friends in the Computer Science Department lounge in Wean Hall, while Berliner was across the room, playing chess or some other game. Berliner was listening to the bids, however, and after the first trick said, "The trump king is offside." Shamos remains amazed at Berliner's ability to determine the location of the key card in the hand based only on the bidding.
In addition to computer chess, Berliner worked on a program for the simpler game of backgammon. In 1979, the program, called BFG, beat the reigning world backgammon champion, becoming the first computer program to beat a world champion in any game.
Chess remained his focus, however. The number of possible moves in chess is astronomical, but Berliner found a way to effectively narrow the choices and make the problem computationally feasible. Called B* (or B-star), the algorithm evaluated decision trees, assigning an "optimistic" or a "pessimistic" score to each node on the tree. The idea was to prune the tree, finding a path that was sufficient to solve the problem, but not necessarily the perfect path.
This and other innovations were implemented in 1984 in Hitech. This computer used 64 very-large-scale-integrated, or VLSI, circuits, one for each square on the chessboard, which operated in parallel to help determine strategy. It could consider 175,000 positions per second.
"There was such an enthusiasm for Hitech that I've never seen before," Berliner recalled to SCS's The Link magazine in 2012. "Everyone wanted to know what the latest developments were and if they could help."
By 1987, Hitech was ranked 190th in the United States and the only computer among the top 1,000 chess players.
Shamos said Berliner had no patience for nonsense and could be curmudgeonly, "but he was completely immersed in chess."
"You can't become a top-rated chess player like Hans without being competitive and self-confident, but I never saw him as being 'over the top,'" Carl Ebeling, one of his students and the designer of Hitech's VLSI circuits, told The Link. "He led by example more than anything else. There was a constant attention to detail and he was always thinking, looking out for the next idea that might work," added Ebeling, who retired in 2012 as a computer science professor at the University of Washington, and is currently working as a senior chip architect at Intel Corporation, in Santa Clara, California.
Ebeling's Ph.D. thesis, "All the Right Moves", won an ACM Doctoral Dissertation award, and describes HiTech’s innovative architecture in detail.
Berliner retired to Florida in 1998. He is survived by a brother, Ernest. Read his New York Times obituary.