Smart computers directing chessmen to slash through bishops and knights to capture a chess grandmaster’s king no longer raise exclamations of awe. Computers’ ability to outwit professional chess players has long been accepted as a fact of life. But this was not always the case.

Machines have made alarming progress since the first computers programmed to defeat amateur players in chess-like games were introduced in 1956. Slowly but steadily higher-ranked players were defeated, culminating in Deep Blue’s defeat of world champion Garry Kasparov in 1997. 

Since that first defeat of a world champion, machines have become even more efficient. Deep Blue was a computer specially designed for chess, and could compute 200 million moves per second. In 2006 the program Deep Fritz beat world champion Vladimir Kramnik on a regular PC capable of calculating just 8 million positions per second.

Computer science professor Monty Newborn, an organizer of the Kramnik match, said the result showed that “the science is done” — indicating there was no need to further test the ability of computers.

Yet, unconquered territory remains. Computers are now poised to take on an even older board game, Go, known as “baduk” in Korean. Whereas chess is essentially a game ending when a king is captured by one of the opponent’s many different chessmen, Go is a territory game ending when either of the two players can place no more pieces. Whichever player holds more territory on the board is the winner. Played on a 19-by-19 grid of black lines, one of the black or white identical game pieces, called stones, is alternately placed on any line intersections in each move.

Despite its rather simple rules, Go is an extremely complex game, because the large board allows a huge number of possible positions to come into play. For instance, while there are 20 possible opening moves in chess, there are 361 possible moves in Go, making it more difficult for computers to keep track and eliminate positions.

Additionally, because pieces cannot be moved once placed, players modify their overall strategy while deciding each move, making it harder for computers to evaluate each move, as they can only predict the immediate outcomes of moves and cannot creatively visualize the result of the game.

Nonetheless, computers have made significant progress. With developments in technology with deep-learning machines and the revolutionizing Monte Carlo method that sees all possible outcomes in 2006, computers have successfully competed against professional Go players.

Software engine Crazy Stone defeated Yoshio Ishida in 2013, making it the first computer to win against a 9th dan player, the highest professional rank in Go, albeit with handicaps, and in 2015, AlphaGo won 5-0 against European champion Fan Hui without any handicaps.

Whether science is done in the realm of Go will be decided in the coming battle between AlphaGo and Lee Se-dol.

By Lee Seo-young (seoyounglee@heraldcorp.com)