Computer Chips Stacked to Master Japanese Chess

Intrigued by the challenge of a game far more difficult than chess, artificial-intelligence specialists from such unlikely places as England and North Korea have programmed computers to play shogi, or Japanese chess--and are aiming to beat the Japanese at their own game.

Ever since the IBM supercomputer Deep Blue trounced chess master Gary Kasparov in 1997, shogi fans--Japan has about 12 million of them--have been wondering when their ancient art might also be humbled by the microchip.

So far, the Zen-like composure of the shogi masters hasn’t cracked because neither the computers nor the burgeoning ranks of foreigners who have taken up the game are within striking range of Japan’s revered human champions.

But the computer interlopers are advancing fast. The game has attracted computer experts, chess buffs, students and hobbyists. Some hope to score big by selling their software to games companies, and others are drawn by the sheer intellectual thrill of trying to teach a computer to outthink a human in complex problem-solving. Industry sources speculate that the North Koreans are attracted by the promise of hard currency.

At an international shogi tournament in Tokyo earlier this year, an entire session was devoted to discussing whether a computer needs to or can be taught shogi intuition, and how soon the silicon onslaught might begin.

“If I have to play a two-day game with a computer like Deep Blue, then at least I want the computer’s power to be shut off while I’m resting,” joked shogi master Yoshiharu Habu, 28, already anticipating that an insomniac computer might gain an unfair advantage.

Habu, who has held all seven of the top Japanese shogi titles and reportedly once earned more than $1 million a year, is considered by some to be the best shogi player. Predictions about when a computer might be good enough to beat Habu vary, from 10 years hence to never.

Habu said he would prefer any machine competitor to play “computer-like shogi” rather than “human-like shogi,” which might prove unnerving. Some have argued that Kasparov is a better chess player than Deep Blue and lost because he was rattled by the computer’s jarring, distinctly nonhuman style.

Shogi and Western chess share the same origins in India, but the Japanese version is believed to have arrived via China in perhaps the 8th century. Each shogi player has 20 pieces and wins by checkmating the opponent’s king. But unlike in Western chess, captured shogi pieces can be redeployed on the board to attack their former master.

“That makes it a nightmare because the number of permutations is huge,” said Jeff Rollason, a British computer scientist. A Western chess player typically has to consider only 20 to 30 possible moves, while a shogi player has a maximum of 536 possible moves, including 200 moves during the critical endgame, Rollason said.

Rollason quit his job at the University of London and now works full time on his shogi software program, “Shogi for Daddy.” It is one of about 20 commercial shogi software programs on the market in Japan. (His Web site is https://ourworld.compuserve.com/homepages/pocketware/.)

At the First International Shogi Forum here, teams of programmers pitted their software against each other on a bank of ordinary personal computers, not the supercomputer that ran Deep Blue. Rollason’s latest program tied for fifth, and the competition was won by a dark-horse Japanese programmer, Hiroshi Yamashita. A program written in North Korea--a nation that doesn’t play shogi--ranked third.

What amazes Rollason’s Japanese competitors is his cheerful admission that he is a lousy shogi player who loses every game to his own program.

“Computers can think very fast. I can’t,” Rollason said with a shrug. “I don’t think they want me to win.”

Deep Blue beat Kasparov by plotting 14 moves ahead, but a good shogi program would require a computer to read at least 20 moves ahead--professional shogi players can think 30 to 40 moves ahead, said Kazuro Morita, the creator of another well-known shogi program.

Another lure for programmers is the ancient Chinese game of go, which is even harder for computers than shogi, and so has caught the eye of artificial-intelligence experts as well as hobbyists.

“If you develop a new technique with artificial intelligence, you first want to test it where it can do no harm: in a game,” explained Martin Mueller, an Austrian who has written a go program at Japan’s government-run Electrotechnical Laboratory in Tsukuba, north of Tokyo. “I have to solve the same kinds of questions to play a game well as to solve problems in real life.”

In order to analyze the exponentially expanding chain of possible moves in a shogi or go game, a program needs a very powerful search capability, said Kumiko Tanaka-Ishii, who also works on artificial intelligence at the lab.

This kind of search function and complex pattern recognition could be useful in such areas as DNA sequencing, in which a computer must scan countless combinations of the four components of DNA in order to identify a particular gene, Ishii said. It might also be applied to Internet search engines, weather forecasting or earthquake prediction, she said.

A Taiwanese foundation has offered a $1-million prize for the first computer to beat a professional go player. But no one has succeeded, and programmers are not making big bucks on game contracts--at least not yet.

“It’s a struggle,” said Michael Reiss, the British author of “Go4++,” which has sold more than 250,000 copies in eight countries, including the U.S. (His Web site is https://www.reiss.demon.co.uk/webgo/compgo.htm.)

“Good secretaries earn more than me,” he wrote in an e-mail. “It’s the desire to be world champion that drives me.”

Added Mueller: “It’s a fact that computer programmers love games, and go is the ultimate challenge in games of skill. But it does not explain why so many people spend so much time on it. . . . It is certainly not a mainstream activity, and I don’t think it is a smart career move to work in games research.”

Nevertheless, Japanese believe that it is the desire to earn hard currency, as well as the drive to improve their computer technology, that has drawn the North Koreans into computer game programming.

They burst onto the international go scene about 2 1/2 years ago with a program called “Silver Igo” developed by a North Korean state-run trading enterprise called Silver Star. Competitors were amazed that North Korea could afford to channel top computer experts into game programming at a time when the cash-strapped Stalinist state was begging for food aid.

“They are probably thinking about other businesses,” explained Naritatsu Yamamoto of Silver Star Japan, which represents the North Korean go and shogi programs. “They want to demonstrate their technical skills in order to get other work.”

Silver Igo beat 40 other programs from around the world to win the FOST cup, run by an artificial-intelligence group, in Tokyo in August 1998.

But soon after, the Chinese author of one of the most successful go programs, Chen Zhixing, accused the Silver Igo program of having plagiarized his “Handtalk.” Chen, 69, a retired chemistry professor from Guangzhou, China, has posted the accusations, along with details of the allegedly cribbed computer code, on his Web page at https://www.wulu.com/ and demanded the return of the FOST cup title.

Masahiro Okasaki, who was the chief judge for the tournament, said Silver Igo was not a direct copy of Handtalk, although like many programs, it imitated the ideas of the powerful Chinese program.

The legalities of software plagiarism remain vague in Japan, and the North Koreans were allowed to keep their title. But in a bit of intrigue around the same time, the Silver Star head was executed in North Korea, reportedly for political reasons having nothing to do with the go program, according to Okasaki.

The go world remains abuzz with rumors about the incident and questions about whether the Silver Star executive might have been executed because the plagiarism charges had embarrassed the North Korean leadership. Okasaki emphatically denies that version of events.

Japanese media did report the execution of a trading company executive in September 1998 but did not name the official or even the date when he was reportedly shot. Chen, in a telephone interview, said he has had no response to his allegations. And hermitic North Korea’s “bamboo curtain” has made the rumors virtually impossible to confirm or deny.

Meanwhile, Silver Star has been shut down, and the 22 or 23 people working in the games section have been moved to North Korea’s largest computer enterprise, called KCC, according to Silver Star Japan’s Yamamoto.

Despite the attention the North Korean programs have attracted, their authors have never visited Japan.

“They’re afraid they’ll defect,” Habu said.

But British programmer Reiss said he doesn’t know of any hotshot go or shogi programmers who have been lured away to high-paying artificial-intelligence applications.

“I’m still waiting to be snapped up,” Reiss said.

(BEGIN TEXT OF INFOBOX / INFOGRAPHIC)

SHOGI

* Shogi is much like chess: Two opponents maneuver pieces on a board, with the capture of the enemy king the objective. As in chess, a checkmate occurs when a king cannot avoid capture on the next turn. But there are no stalemates in shogi, and draws are very rare. There are other differences: Shogi is played on a 9-by-9 board that usually doesn’t have alternating color squares. Because the board is larger than a chessboard, each side has 20, instead of 16, pieces. Also, there are no color or design differences between pieces of opposing sides. The pieces are wedged and pointed, and the direction in which a piece points indicates which side it is on. The biggest difference from Western chess, however, is that captured shogi pieces can be redeployed on the board to attack their former master.