Go figure: software finally masters the most complex of games

ADVERTISEMENT

Machine has beaten Man at one of the world’s most complex mental games. AlphaGo, developed by Google’s DeepMind subsidiary, has taken an unassailable 3-0 lead in a five-set match against decorated human champion, the South Korean Lee Sedol. > A hard fought game by Lee Sedol, but #AlphaGo’s creative tactics prevailed → https://t.co/MbtYm64lhLpic.twitter.com/QQdfqIdz0i

— Google (@google) 10 mars 2016

While computers have been getting the better of Man at chess for many years (Deep Blue beat Garry Kasparov in 1997), Go is regarded as a more subtle, more mentally-challenging board game.

Go is one of the oldest board games, having emerged more than 2,500 years ago in modern-day China, where it is known as weiqi. The game soon spread through the Korean peninsula to Japan, where it gained more widespread popularity, including among the Imperial family and Japanese elite. Today Japanese and South Korean players regularly dominate international competitions.

Simple in theory, complex in practice

While the rules may at first glance seem relatively simple, the huge amount of permutations possible on the board provide Go with its complexity. It’s played on a 19×19 board or Goban, containing 361 squares (an 8×8 chess board has 64 squares). Players then take turns in placing their pieces, known as ‘stones’, at the intersections of these squares. Like in chess, these opposing pieces are traditionally black and white, but all are identical in shape and purpose. Once played, a piece cannot be moved but may be captured, in which case it is removed from the Goban. A player can make chains of stones by placing pieces on unoccupied intersections – known as liberties – adjacent to their own stones.

Players can capture their opponent’s stones by surrounding them i.e. occupying all their possible liberties.

In the figure below Black has just on liberty, A. If White puts a stone on A he/she captures the two Balck stones, which are now surrounded.

Eventually, when both players pass their move, each player’s points are counted to determine the winner. Points are won in a number of ways, not just by the number of stones a player has left on the board at the end: unoccupied intersections can also count as points if a player controls them by surrounding them with his stones, the number of captured stones also translate into points, and the player with the white stones gets extra points as compensation for being the second to play.

There are certain ‘local’ rules which affect the point system depending on where the game is taking place. The AlphaGo-Lee Sedol match was played according to Chinese rules for example and not Japanese rules.

The size of the Goban makes for an enormous amount of possible plays. According to Demis Hassabis, one of the creators of DeepMind, there are 10 to the power 170 possible permutations of the Goban. That’s 1 with 170 zeros behind it! Compare that to chess where there are ‘only’ 47 zeros.

Likewise, while in chess a player has around 20 possibilities with an average move, in Go there are almost 200 possible plays.

Machines are now “thinking” like humans

In past Man vs Machine matches, the machines (like DeepBlue in chess) used algorithms in a “brute force” manner, meaning they calculate all the possible permutations to decide which moves will win.

AlphaGo goes beyond that and uses “deep learning”, artificial intelligence enabling it to adapt to the evolving strategies of the human player opposite. Its developers created a network of artificial neurones and “fed” them with millions of moves played by professional human Go players. AlphaGo analyses all these past moves and situations to determine the best move for a successful outcome. This process allows it to imitate human intuition. One first-hand witness to that was Fan Hui, a European Go champion beaten 5-0 by AlphaGo last year who says the machine played “like a human”.

Man could yet get revenge over the Google software: 18-year-old Chinese player Ke Jie, who has the highest possible professional ranking of ’9p dan’ has claimed he has a “60% chance” of beating AlphaGo.