Can you believe that computers have been beating humans ever since 1956? That year the MANIAC, not the weirdo down the street, but an actual computer called the Mathematical Analyzer, Numerical Integrator, and Computer or Mathematical Analyzer, Numerator, Integrator, and Computer, became the first computer to beat a human at Chess. It defeated a novice human in 23 simple moves. Called Chess Computers, they started beating the best of the players. The most epic battle of the machines was the success story of Deep Blue. This IBM machine, beat World Chess Champion, Gary Kasparov in 1997. And by early 2005, chess games could be found on commercial machines all over the world.
The machines now can beat us in Othello, Scrabble, backgammon, poker, even Jeopardy. But these machines just can’t seem to wrap their huge virtual brains around this classic Chinese game, Go. In Game Theory terms, Go is “a zero-sum, perfect-information, partisan, deterministic strategy game,” putting it in the same class as chess, checkers and Othello. In simple terms it means that no information is hidden from the other during game play and that there are no elements of chance, such as dice. It’s a two player game that was invented by the Zhou Dynasty in 1046–256 BC. Interestingly, the game can be played by toddlers just 3 years of age, but no super computer can ever be programed to beat humans at this.
Gameplay
The game play is actually quite simple – two players alternately place black and white playing pieces, called stones on a grid of 19×19, 13×13 or 9×9. The objective of the game is to cover as much of the board area as you can. Pieces once placed, can not be moved. But they can be removed if the opponent captures your stone. This is done by surrounding your opponents stone with your own.
Although the rules are simple, the game play is extremely complex. The game serves to emphasize the importance of balance on multiple levels.By placing the stones close to each other, you can easily secure a small area on the board. But the objective is to cover the largest area possible, to do this, one needs to spread out, perhaps leaving weaknesses that can be exploited. Playing too low (close to the edge) secures insufficient territory and influence, yet playing too high (far from the edge) allows the opponent to invade.
Just why can’t computers do it
This poses a unique challenge to computer programmers. The best of Go Programs are only an amateur level. Wikipedia tells us the reasons why computers do not play Go at a professional level,
- The number of spaces on the board is much larger (over five times the number of spaces on a chess board—361 vs. 64). On most turns there are many more possible moves in Go than in chess. Throughout most of the game, the number of legal moves stays at around 150–250 per turn, and rarely falls below 50 (in chess, the average number of moves is 37).Because an exhaustive computer program for Go must calculate and compare every possible legal move in each ply (player turn), its ability to calculate the best plays is sharply reduced when there are a large number of possible moves. Most computer game algorithms, such as those for chess, compute several moves in advance. Given an average of 200 available moves through most of the game, for a computer to calculate its next move by exhaustively anticipating the next four moves of each possible play (two of its own and two of its opponent’s), it would have to consider more than 320 billion (3.2×1011) possible combinations. To exhaustively calculate the next eight moves, would require computing 512 quintillion (5.12×1020) possible combinations. As of March 2014, the most powerful supercomputer in the world, NUDT’s “Tianhe-2”, can sustain 33.86 petaflops. At this rate, even given an exceedingly low estimate of 10 operations required to assess the value of one play of a stone, Tianhe-2 would require 4 hours, to assess all possible combinations of the next eight moves in order to make a single play.
- The placement of a single stone in the initial phase can affect the play of the game a hundred or more moves later. A computer would have to predict this influence, and it would be unworkable to attempt to exhaustively analyze the next hundred moves.
- In capture-based games (such as chess), a position can often be evaluated relatively easily, such as by calculating who has a material advantage or more active pieces. In Go, there is often no easy way to evaluate a position. However a 6-kyu human can evaluate a position at a glance, to see which player has more territory, and even beginners can estimate the score within 10 points, given time to count it. The number of stones on the board (material advantage) is only a weak indicator of the strength of a position, and a territorial advantage (more empty points surrounded) for one player might be compensated by the opponent’s strong positions and influence all over the board. Normally a 3-dan can easily judge most of these positions.
Is anyone trying?
In 1968, a Game Theory genius, Alfred Zobrist was successful in creating a code that could only beat the most absolute of beginners. But the success was never worth the energy, time, and calculations it took to achieve this. Wired tells us,
To understand this, think about Go in relation to chess. At the beginning of a chess game, White has twenty possible moves. After that, Black also has twenty possible moves. Once both sides have played, there are 400 possible board positions. Go, by contrast, begins with an empty board, where Black has 361 possible opening moves, one at every intersection of the 19 by 19 grid. White can follow with 360 moves. That makes for 129,960 possible board positions after just the first round of moves.
The rate at which possible positions increase is directly related to a game’s “branching factor,” or the average number of moves available on any given turn. Chess’s branching factor is 35. Go’s is 250.
In 2006, a breakthrough happened called the Monte Carlo approach. The Monte-Carlo Tree Search was developed as an heuristic search algorithm, and it has helped in developing programs for many games. In fact, Pac Man was one such game. Go programs showed a rapid development after this.
At event called Computer Shogi Challenges Professional Players was conducted at the University of Electro-Communications in March 2012. Here a computer Go program Zen won games against the professional player Masaki Takemiya (who is a 9 dan, the games highest rank). Though he was given handicaps of five and four stones, this was never imagined 10 years ago by any computer Go program developers.
It’s 2014, and no one has rested. In the city of Chōfu, Tokyo, Japan, the University of Electro-Communications hosts an annual tournament called the UEC Cup every March. This unique tournament rewards the top two finalists with matches against a “Go Sage”. The organizers call these machine-versus-man matches the Densei-sen, or “Electric Sage Battle”.
Rémi Coulum is part of a small community of computer scientists hoping to solve this riddle. His program called “Crazy Stone” was a clear favorite at this years UEC Cup. It went undefeated in the first round of elimination – placing it at it’s much deserved throne. Another participant Viennot, developed a program called Nomitan. It uses many of the same tricks as Crazy Stone, if not all. But interestingly, both the programs have a 58% confidence level.
Believe it or not, the Go Sage at this years tournament is actually called Yoda. Nothing like a bit of Star Wars thrown into ancient Chinese games.
Though this might not determine the end of virtual intelligence, it poses a limitation of a human derived intelligence as compared to the human brain. Obstacles such as these serve to show how long the road of artificial intelligence really is. In fact, computers won’t really win at anything until they have experienced the joy of winning or the sadness of losing –an actual human feeling which makes programming a Go game seem like tic-tac-toe.
Image Courtesy: Wired, Wikipedia, Computer-Go-Adventures