Artificial intelligence in the game of go
Early in the film A Beautiful Mind, the mathematician John Nash is seen sitting in a Princeton courtyard, hunched over a playing board covered with small black and white pieces that look like pebbles. He was playing Go, an ancient Asian game. Frustration at losing that game inspired the real Nash to pursue the mathematics of game theory, research for which he eventually was awarded a Nobel Prize.
在电影《美丽心灵》里有这样一幕场景:教学家约翰纳什坐在普林斯顿大学的庭院里,俯身注视一种游戏,在一块木板上点缀着黑色和白色的像鹅卵石那样的东西。纳什正在下围棋,围棋是一个源自亚洲的古老游戏。虽然输掉游戏让他沮丧不已,但是却促使他专注于博弈的数学研究,他也最终由此获得诺贝尔奖。
In recent years, computer experts, particularly those specializing in artificial intelligence, have felt the same fascination and frustration. Programming other board games has been a relative snap. Even chess has succumbed to the power of the processor. Five years ago, a chess-playing computer called Deep Blue not only beat but thoroughly humbled Garry Kasparov, the world champion at that time. That is because chess, while highly complex, can be reduced to a matter of brute force computation. Go is different. Deceptively easy to learn, either for a computer or a human, it is a game of such depth and complexity that it can take years for a person to become a strong player. To date, no computer has been able to achieve a skill level beyond that of the casual player.
近几年来,计算机科学家们,特别是专攻人工智能这块的科学家们也同样感受到纳什的这种痴迷和沮丧。其它棋类游戏的电脑程序都比较简单编写,国际象棋也在功能强劲的处理器面前乖乖屈服。五年前,一部叫深蓝的电脑不仅击垮了当时的世界冠军卡斯帕罗夫,而且还重挫了他的锐气。这是因为国际象棋虽然错综复杂,但仍可简化成强力运算。围棋却不大一样,看上去好像很容易学会无论人还是电脑,但事实上要达到精通的水平却要付出多年的摸索。到目前为止,仍没有电脑能够超出业余围棋手的水平。
The game is played on a board divided into a grid of 19 horizontal and 19 vertical lines. Black and white pieces called stones are placed one at a time on the grid's intersections. The object is to acquire and defend territory by surrounding it with stones. Programmers working on Go see it as more accurate than chess in reflecting the ways the human mind works. The challenge of programming a computer to mimic that process goes to the core of artificial intelligence, which involves the study of learning and decision-making, strategic thinking, knowledge representation, pattern recognition and perhaps most intriguingly, intuition.
围棋游戏是在一块由19条水平线和19条垂直线围成格子的木板上进行的。黑色或白色的棋子每次只能下一颗于格子交叉处。目的是通过围格子获得或保卫领土。编程人员认为围棋比象棋更能精确地反映人类思维的方式。要让电脑模仿人那样思考牵涉到人工智能的核心技术,例如要教会电脑如何学习、下结论、战略考虑、知识再现、模式识别,以及也许是最引人注目的技术直觉认知。
Danny Hillis, a computer designer and chairman of the technology company Applied Minds, said the depth of Go made it ripe for the kind of scientific progress that came from studying one example in great detail.
电脑工程师兼Applied Minds科技公司的主席丹尼席立斯表示:科学的进步源于对典型事物的全面研究,而对深奥围棋的研究正是促进科学进步的好时机。
We want the equivalent of a fruit fly to study, Hillis said. Chess was the fruit fly for studying logic. Go may be the fruit fly for studying intuition.
我们要研究的是像果蝇那样具有代表性的东西,席立斯说。国际象棋是研究逻辑的典型物,围棋却是研究直觉认知的典型物。
Along with intuition, pattern recognition is a large part of the game. While computers are good at crunching numbers, peopl are naturally good at matching oetterns. Humans can recognize an acquaintance at a glance, even from the back.
跟直觉认知一样,模式识别在游戏中占了很大部分。电脑在运算数字方面很在行,但人天生就擅长模式匹配,匆匆一瞥甚至是背影都可以认出熟人。
Daniel Bump, a mathematics professor at Stanford, works on a program called GNU Go in his spare time.
斯坦福大学的数学教授,丹尼巴布在空闲时编写一个名叫GNU的围棋程序。
You can very quickly look at a chess game and see if there's some major issue, he said. But to make a decision in Go, he said, players must learn to combine their pattern-matching abilities with the logic and knowledge they have accrued in years of playing.
他说:国际象棋比赛中我们只要看一眼就知道大致的结果,但下围棋时,棋手必须运用多年积累的知识和逻辑并综合自己的模式匹配能力,才能下好一盘棋。
One measure of the challenge the game poses is the performance of Go computer programs. The past five years have yielded incremental improvements but no breakthroughs, said David Fotland, a programmer and chip designer in San Jose, California, who created and sells The Many Faces of Go, one of the few commercial Go programs.
大卫福兰认为衡量一个电脑围棋游戏的标准是围棋软件的性能,在过去的五年里,围棋软件虽然进步很大,却没有重大突破。福兰是加州圣何塞市的编程人员和芯片设计师,他编写并出售一套叫多面围棋的软件为数不多的商业围棋软件之一。
Part of the challenge has to do with processing speed. The typical chess program can evaluate about 300,000 positions in a second, and Deep Blue was able to evaluate some 200 million positions in a second. By midgame, most Go programs can evaluate only a couple of dozen positions each second, said Anders Kierulf, who wrote a program called SmartGo.
游戏软件的性能部分受制于数据处理速度。传统的国际象棋程序每秒可以计算30万步,深蓝每秒更是可以计算2亿步。然而大部分的围棋程序到游戏进行到一半时每秒只能计算几十步,聪明围棋软件的设计者安德可鲁夫这样说。
In the course of a chess game, a player has an average of 25 to 35 moves available. In Go, on the other hand, a player can choose from an average of 240 moves. A Go-playing computer would need about 30,000 years to look as far ahead as Deep Blue can with chess in three seconds, said Michael Reiss, a computer scientist in London. But the obstacles go deeper than processing power. Not only do Go programs have trouble evaluating positions quickly; they have trouble evaluating them corectly. Nonetheless, the allure of computer Go incereases as the difficulties it poses encourages programmers to advance basic work in artificial intelligence.
对国际象棋来说,每一步棋棋手大概有25到35种下法,但围棋却有240多种。照伦敦一位电脑专家迈克尔雷斯的说法,深蓝电脑在3秒钟就能计算出国际象棋很多步以后的各种变化,而处理相同步数围棋的变化情况,围棋程序却需要运行3万年之久。但障碍还不止表现在数据的处理能力上,围棋程序不但计算步数很慢,而且计算的准确性也不高。尽管围棋程序的开发如此之难,编程人员越发产生了浓厚的兴趣,他们必须在人工智能的基础研究上有所突破。
We think we have the basics of what we do as humans down pat, Bump said. We get up in the morning and make breakfast, but if you tried to program a computer to do that, you'd quickly find that what's simple to you is incredibly difficult for a computer.
我们认为我们已经完全掌握了人类的行为规律,巴布说,我们在早上起床,然后准备早餐。但你如果想要让电脑做这种事情,你马上会发现我们轻而易举能做到的事,对电脑来说却难似登天。
The same is true for Go. When you're deciding what variations to consider, your subconscious mind is pruning, he said. It's hard to say how much is going on in your mind to accomplish this pruning, but in a position on the board where I'd look at 10 variations, the computer has to look at thousands, maybe a million positions to come to the same conclusions, or to wrong conclusions.
让电脑下围棋也是一样。当你考虑棋局的种种变数时,你下意识地进行筛选,巴布说,很难说得清这个筛选过程是怎样的,我面对棋盘思考10种可能的变化情况,要得出相同的结论电脑却需要考虑上千种,甚至是上百万种的位置变化,而出来的结果还可能是错误的。
Reiss, an expert in neural networks, compared a human being's ability to recognize a strong or weak position in Go with the ability to distinguish between an image of a chair and one of a bicycle. Both tasks, he said are hugely difficult for a computer.
雷斯他还是神经网络系统的专家,他比较了人类的两种辨别能力,一种是辨别出围棋棋局中的关键位点,另一种是辨别开椅子和自行车的图片,他说,这两种能力对电脑来说都是难乎其难。
For that reason, Fotland said, writing a strong Go program will teach us more about making computers think like people than writing a strong chess program.
正因如此,大卫福兰指出:编写一套好的围棋程序比编写一套好的象棋程序更具挑战性,它能让电脑更接近人的思维方式。