Can Computers 'Go' Beyond Chess?

by Thomas Caldwell

In 1806, Napoleon was the most talked-about man on Earth. His armies had captured a great deal of Europe, and he was on his way to becoming the greatest conquering general (or thug, depending on your point of view) of all time.

    The Little Corporal fancied himself a strong chess player. As the story is told, Napoleon heard of a chess-playing machine called "The Turk" that was able to beat most, if not all, challengers. Eventually, Napoleon arranged to meet the Turk in Berlin.

    The "machine" was a strange-looking contraption: a large box with a chessboard on top, and a mannequin dressed up in a gaudy Turkish outfit attached. An opening on the side of the device revealed a complex interior network of p leys and gears.

    The French Emperor sat down, and intentionally made an illegal move. The mechanical mannequin shook its head — an "error message" if you will. Napoleon then made another illegal move, and The Turk again shook its head. After several consecutive illegal first moves on by Napoleon, the mechanical chess machine's mannequin violently swept all the pieces off the board.

    Napoleon laughed; he had played "mess up the chess machine," and won. Afterward, Napoleon did play against the Turk, and lost. (Contrary to what you might have heard, the guy was a lousy chess player.)

    The Turk, as you may have guessed, contained within its mannequin portion a very talented chess-playing midget — one of several who would keep The Turk a very successful side show attraction for many years to come.

Deep Blue vs. Kasparov
    Move forward 190 years, to the city of Philadelphia, where a man named Garry Kasparov sat down to play chess against another machine. This one didn't contain a midget, but rather a whole bunch of silicon chips and electronic instructions known as software. Kasparov, who unlike Napoleon was a pretty good chess player, also played "mess up the chess machine." He won.

    But a year later, in a rematch with the chess-playing computer Deep Blue, Kasparov tried the same trick. Deep Blue had learned its lesson, and chess master Kasparov was blown off the board.

    The first chess-playing computers, commercially available in the early 1980s, were easy to beat. Almost anyone who had a good grasp of the game was able to beat one after learning that unconventional moves were often too much for the computer to handle. Anything out of the ordinary that its programmer didn't plan for — which, by the nature of the game, would have been most things — would send its primitive source code running for cover. In those days, we laughed at the thought of a computer ever beating a strong player, let alone a Grand Master.

    There is still great deal of debate as to whether Garry Kasparov's loss to IBM's Deep Blue proves that machines are better chess players than humans. Many chess enthusiasts who followed every move of the match (myself included) feel that Kasparov seriously underestimated his opponent, and tried to play the now-dated game of "mess-up-the-chess-machine." Kasparov didn't play the way he usually does; in terms of reputation, he lost more than Deep Blue won. The rematch, if there is one, should prove interesting.

    Still, the match with Kasparov has proven that the days are numbered when a human will always be able to beat a machine at chess. But does this mean computers are destined to beat us at all games? Is there any game at which we, the human race, still have a chance to consistently come out on top? Poker? Dice? Monopoly?

Go-ing my way
    A long time ago, in an empire not so far away, a board came into being which, according to its modern enthusiasts, is a long way away from being dominated by heartless silicon. Igo, more commonly known in English as go, could be the strategy game that remains a human-only passion for — well, for a long time to come.

    In brief, go is a game played with black and white "stones" on a board, usually made of thick wood, consisting of 361 "squares" (chess boards have 64). Unlike chess, the rules of go are very few and simple. The idea is to "capture" more territory than your opponent, with the overall objective being to control as much of the board as possible. While chess can best be described as a battle, the game of go is a war.

    Not too far from Tokyo's Ichigaya station sits a rather old office building that houses the next mind sport to be challenged by technology. Nihon Ki-in (established in 1925) is the center of the go-playing world. Yoshio Saheki, general manager of the organization's overseas department (and secretary of the International Go Federation), says that the game's challenge comes from its simplicity. "Actually, it is not complicated. It is very simple. Too simple," he says of the game. "Too simple is too complicated."

    Like chess, the details of the origins of go are lost in the mists of history. It is thought to have originated in China about three thousand years ago. Nobody knows for sure how the game was played initially, or what the rules were, but it is believed the overall objective of early go was somewhat similar to the game as it is played today. Go was brought to Japan through Korea about 1,500 years ago, and has undergone a great deal of development and evolution since. Much of the history of go in China was lost due to wars, revolutions, and the general mayhem that Asian continent is famous for. (In 221 BC, for example, the then-reigning Chinese emperor ordered all books burned.) While there is some historic record of the early years of go, much of the history of the game as it was played in China has been lost.

    In Japan, go quickly caught on with the samurai class, who were turned on by the strategic knowledge needed to play the game well. After all, it was a good way to pass the time when they weren't roaming around the Japanese archipelago slaughtering each other's armies. (Don't forget that until baseball was introduced to the country, the only team sport in Japan was war.)

    Over the centuries, go as it was played in Japan developed into a very simple yet complex game — one thought to be far different from the original game the Chinese came up with. After the Meiji era, the game went into a brief decline, but quickly came back into style. The game also began to received a sort of national officialdom not too dissimilar from what the Soviets did for chess. Go became a regular pastime with the military types, and was even studied by US intelligence agencies during World War II as a way comprehend the thinking processes of the leadership of the Imperial Army and Navy.

    Today, go aficionados can be found the world over: throughout the Pacific Rim nations, across the US, and as far away as Kenya.

Computerizing go
    The difficulty in computerizing the game becomes evident when you compare the way that go and chess are played. While chess has many standard openings that can be "fed" to a computer for analysis, a go player can pretty much do anything he or she wants. There is no "encyclopedia of openings" such as any self-respecting chess player would study (although there are some standard beginnings that players follow for common sense reasons).

    Nihon Ki-in's Saheki feels that there is a certain "feel" for the game, one that, at this point in technology, only a human can understand. A "feeling," he says, is similar to fuzzy logic. "Unless the technology of the computer can solve this fuzzy theory, a good player cannot be beaten by a computer."

    There are just too many variables in the game of go for modern computers to deal with. A machine, according to Saheki, will have to duplicate human thought to accomplish with go what Deep Blue did with chess. Brute force calculation isn't enough.

    However, a few computerized go games do exist. How does the best of these compare to the top human players? When I asked Saheki this question, he picked up three magazines that were sitting on the table. He put two of them next to each other. "This is a professional-level player," he said, pointing to the magazine on his left. "This is a top amateur-level player," he continued, pointing to the magazine on his right. "And the computer would be...." he proclaimed as he tossed the third magazine to his right halfway across the room, "there. Very, very, very weak." Point taken.

Strategy and tactics
    Unlike the game itself, the ranking system of go is a bit complicated — not nearly as scientific as the FIDE (International Chess Federation) or USCF (US Chess Federation) system. Basically, players are separated into Dan (higher class) and Kyu (class) categories. A top player would be a 9 Dan; the best computer version of the game to date is said to be about a 7 Kyu. In chess terms, this would be like a decent amateur player going up against Kasparov in a very serious mood. Not much of a contest, or a challenge.

    Another go person who thinks the microchip's conquest of the game is unlikely is Richard Bozulich. A former chess player turned go fanatic, Bozulich got turned on to the game while studying mathematics at the University of California, Berkeley. "One day a guy came in with a go set, and said that only the Japanese could play go, and nobody could beat them at it." So Bozulich decided that he would, and did, becoming a very strong player (amateur 6 Dan) and one of the leading non-Japanese experts on the game. To date, he has written several books on the on the subject, including The Go Players Almanac , which is the bible for non-Japanese enthusiasts of the game.

    "On the chess board, you have 64 squares. On the Go board, you have 361 squares. For a computer to do a complete search [of moves] involving 361 squares is currently impossible," he told me over a cup of tea outside the Nihon Ki-in's bookstore. "The number of possibilities is enormous considering the size of the board."

    Compared to go, chess is a very "regional" game. In military terms, you may want to compare it to the difference between what sergeants would do as opposed to generals would be responsible for. As Bozulich explains, "You can deeply analyze a move and come out with an advantage locally. But globally, you might come out with a distinct disadvantage." Just like in a real-life conflict; by winning the battle you could lose the war. "Go requires global thinking."

    For example, in chess if you see you are about to lose a piece, the first instinct is to save it, or to exchange it for another, more valuable piece. Exchanges for positions are a consideration, but material power is a major factor in the playing and winning of the game. This "materialism" is something tangible, and a concept that a computer can deal with more easily. But in go, a strong player may give up twenty or more stones and actually gain an advantage. This, Bozulich says, is not a concept that can easily be converted to algorithms. "It takes a certain amount of intuitive judgment. It's something you can't explain, but something you know is right." Bozulich has never found a computer program he can't beat handily.

    If you have hopes of becoming a top go player, the same rule as in chess applies: Start young! The strongest players usually start the game in their preschool or kindergarten years. The current top-seed player, Chikun Cho, became a professional when he was only 11 years old. He started playing at age 4.

    There is a movement underway to get the International Olympic Committee to recognize go as an "international mental sport of competition," just like chess. Given the growing interest in the game around the world, especially in the US and Europe, this could happen in the very near future.

Go software
    The go software market is small compared to chess (or even computer poker). An Internet search will turn up some shareware programs, but few of them are any good.

    In spite of the many difficulties inherent in creating a decent go program, many are trying. Among the best currently available is one called Goliath, which runs on numerous platforms (including the Nintendo Famicom) and is available in English or Japanese. There are also several strong programs coming out of China, but these are not readily available and are sold and distributed mostly by word of mouth.

    Interestingly, computer go tournaments, where programs play other programs, are becoming more and more common. This may help spark more human interest in the game.

    When the first commercial PCs came out in the early '80s, nobody thought they would ever become what they have today. (Remember Bill Gates saying 128K was all the RAM anyone would ever need?) The power of a top-of-the-line laptop is phenomenal compared to a supercomputer of a quarter century ago, and the power of the software used to run the things has also evolved in leaps and bounds. So are we looking at the king of go losing his crown to a machine a few years from now? Perhaps future computer engineers who are now 4 or 5 years old and crawling around on their daddy's go board will create a program that can beat the top human players?

    "Not within my lifetime," Bozulich says with certainty. "Perhaps not for another century or two."