Computers Are Still No Match For Japan's Shogi Masters

TOKYO - Intrigued by the challenge of a game far more difficult than chess, artificial-intelligence specialists from unlikely places such 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 Garry 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 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 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 more complex than chess

Shogi and Western chess share the same origins in India, but the Japanese version is believed to have arrived via China in perhaps the eighth 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 20 to 30 possible moves, while a shogi player has a maximum of 536 possible moves, including 200 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."

At the First International Shogi Forum, 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 program.

"Computers can think very fast. I can't," Rollason said.

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, 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," said 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 kind of questions to play a game well as to solve problems in real life."

To analyze the exponentially expanding chain of possible moves in a shogi or go game, a program needs a 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, Tanaka-Ishii said. It also might 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 of the software version of the Chinese game of go in eight countries, including the United States.

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

Demonstration of skill

Japanese believe that it is the desire to earn hard currency, as well as the drive to improve their computer technology, that has drawn 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," said 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.

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 to high-paying artificial-intelligence applications.

"I'm still waiting to be snapped up," Reiss said.