|
Winning ways
Ever since the stunning victory of Deep Blue, a program running on an IBM supercomputer, over Gary Kasparov, then world chess champion, in 1997, it has been clear that computers would dominate that particular game. Today, though, they are pressing the attack on every front.
They are the undisputed champions in draughts and Othello. They are generally stronger in backgammon. They are steadily gaining ground in Scrabble, poker and bridge. And they are even doing pretty well at crossword puzzles. There is one game, however, where humans still reign supreme: Go. Yet here too their grip is beginning to loosen.
Go is a strategic contest. Each player tries to stake out territory and surround his opponent. The rules are simple but the play is extraordinarily complex. During a game, some stones will "die", and some will appear to be dead but spring back to life at an inopportune moment. It is often difficult to say who is winning right until the end.
Deep Blue and its successors beat Mr Kasparov using the "brute force" technique.
Unfortunately, brute force will not work in Go. First, the game has many more possible positions than chess does. Second, the number of possible moves from a typical position in Go is about 200, compared with about a dozen in chess. Finally, evaluating a Go position is fiendishly difficult. The fastest programs can assess just 50 positions a second, compared with 500,000 in chess. Clearly, some sort of finesse is required.
In the past two decades researchers have explored several alternative strategies. Now, however, programmers are making impressive gains with a technique known as the Monte Carlo method. Given a position, a program using a Monte Carlo algorithm contemplates every move and plays a large number of random games to see what happens. If it wins in 80% of those games, the move is probably good. Otherwise, it keeps looking.
This may sound like a lot of effort but generating random games is the sort of thing computers excel at. In fact, Monte Carlo techniques are much faster than brute force. Moreover, two Hungarian computer scientists have recently added an elegant twist that allows the algorithm to focus on the most promising moves without sacrificing speed.
The result is a new generation of fast programs that play particularly well on small versions of the Go board. In the past few months Monte Carlo-based programs have dominated computer tournaments on nine and 13 line grids. MoGo, a program developed by researchers from the University of Paris, has even beaten a couple of strong human players on the smaller of these boards-unthinkable a year ago. It is ranked 2,323rd in the world and in Europe's top 300. Although MoGo is still some way from competing on the fullsize Go grid, humanity may ultimately have to accept defeat on yet another front. 参考译文：
取胜之路
自从1997年深蓝--一个运行于IBM超级计算机上的程序战胜当时的世界国际象棋冠军加里•卡斯帕罗夫起，计算机可以统治这一特殊的游戏就变得不言而喻了。计算机还对每个前沿流域发起攻击。它们是国际跳棋及黑白棋游戏无可争辩的冠军。在西洋双陆棋上它们通常表现得更好。它们正在稳步获得拼字游戏、扑克和桥牌的一席之地，它们在纵横字谜游戏中也有着优异表现。然而，还有一项游戏人类仍然占据统治地位：围棋。即便如此，人类在这一领域的控制力也开始丧失。
围棋是一种战略竞争。每位选手都要设法夺取领域并围住其对手。在一次游戏中，一些棋子将会"死掉"，而另一些看起来死掉但却会在不可思议的时候重获生机。通常不到最后是很难分出胜负来的。
深蓝及其后继者打败卡斯帕罗夫所用的是暴力破解技术。
然而不幸的是，暴力破解在围棋中将失去作用。首先，这一游戏有着远多于象棋的棋位。第二，一个围棋中的标准棋位上的走法大约有200种，而在象棋中大约是12个。最后，评估一个围棋棋位极度困难。最快的程序每秒可以估测出50步棋，而在象棋中，这一数字是500000。显然，还需要一些更好的策略。
过去的二十年间，研究人员探究了若干种可选性策略。然而现在，程序员利用一项被称为蒙特卡罗方法的技术取得了重大进展。给定一个棋位，应用蒙特卡罗算法的程序预测每一步走法并进行大量随机走法将会带来什么结果。如果它在那些游戏中获胜率是80％，那么这一步可能就是好棋。否则，它就会继续寻找。
这听起来需要花费大量努力，但是进行随机游戏正是计算机擅长的地方。事实上，蒙特卡罗技术要比暴力破解技术快得多。此外，两名匈牙利计算机科学家最近又向其中增加了一种一流的手法使得该运算法则能够在不损耗速度的前提下集中关注最可能的棋路。这一切的结果是能够很好地在小棋盘上进行围棋的新一代快速程序的研发。
在过去几个月中基于蒙特卡罗技术的程序已经统治了9格和13格计算机围棋大奖赛。MoGo，一个由巴黎大学研究人员开发的程序已经在过去一年在小棋盘上出乎意外地打败了诸多人类围棋高手。该程序目前的世界排名是2323位，而在欧洲则处于前300位。尽管MoGo在完整棋盘上的竞争还有一段路要走，但是人类最终将不得不接受又一个领域的失败。
相关资料
| 
