Weiqi is a strategy game where two players take turn placing stones on a board, which is wildly popular in China. There are only two types of stones: black stones and white stones.
After Deep Blue defeated Garry Kasparov in 1997, Time Magazine presented a new challenge: Let the computer battle with human.
Peter Norvig in Google pointed out that even plenty of experts are invited, a hundredfold hardware, software, using correct machine learning algorithms, combined with the achievements of neurological science, it may not be able to reach the computer "Deep Blue" in terms of achievements in chess. Now Chess-playing softwares can compete with the best humans, however even strong amateurs can beat the top Weiqi-playing programs, why? There are three main reasons for this:

2. Lack of a good heuristic: Chess programs are able to evaluate quite accurately and quickly whether a given position is better than another one. On the contrary, no good heuristic has been found for Weiqi yet.
3. Pattern-recognition: strong Go players rely heavily on recognizing the shapes the stones take. There are too many of them for a computer to try to recognize in a game timeframe, and humans are much better than them at this.
Time Magazine predicted that the computer will use one hundred years or even longer to defeat humans on Weiqi, it seems be a forgone conclusion. But recently, Computer Crazy Stone which is designed by Prof. Remi Coulom of Computer Science at the Third University of Lille, France defeated Ishida Yoshio, a Weiqi master has won five titles. Precisely, Ishida had a four-handicap, this is an unfair duel, and also he is not in his peak condition. However, Crazy Stone is quite an achievement.
The use of randomly played games helped Crazy Stone get much stronger. Crazy Stone adopted the Monte Carlo method. It was found that the best way to evaluate a position is to play, from this position, a lot of games where each player puts stones at random on the board. Norvig in Google explained that this algorithm is an important innovation. After 20 steps, we can not say for sure who will win the game, and so finally we used the Monte Carlo method to determine the position’s score simply by the percentage of won random games. The computer begins with a prior probability distribution for every possible move. It picks one according to this distribution, plays a random game from the corresponding position and uses the result to update the probability for this move. It then selects another possible move according to the updated distribution and so on. So it learns during the game and the randoms play-outs that some kind of responses to his opponent’s moves are likely to have a bad result, and assigns them a lower probability.
It is reasonable to believe that, given time, Crazy Stone will become stronger and stronger and it seems that the prophecy from Time Magazine is soon to be dashed.
没有评论:
发表评论