Beating Go Thanks To The Power Of Randomness

by Tobias Pfeiffer

In the talk "Beating Go Thanks To The Power Of Randomness," presented by Tobias Pfeiffer at RubyConf 2015, the speaker explores the fascinating complexity of the board game Go, which has resisted AI dominance unlike chess. The key topics covered in the presentation include:

Historical Context: The speaker discusses pivotal moments in AI history, including IBM's Deep Blue defeating Garry Kasparov in chess in 1997, and the events surrounding Go, such as programs playing against strong young players and the development of significant Go programs.
Complexity of Go: Go’s rules are simpler than chess, but the game’s strategic depth and the vast number of potential board configurations (estimated to be much higher than chess) make it notably more complex. Key statistics highlight that Go has a branching factor of around 250, compared to chess's 35.
Game Mechanics: The speaker explains the basics of Go, including the concept of liberties, capture, and territory control, as well as the importance of komi used to balance the first-move advantage.
Differences from Chess: In chess, players focus on dismantling their opponent’s setup, whereas in Go, every move contributes to building the board. This leads to a more dynamic playing experience, where moves have global impacts.
AI Challenges: Traditional AI algorithms like Min-Max used in chess struggle with Go’s complexity, prompting the exploration of the Monte Carlo method, which utilizes randomness to estimate outcomes.
Monte Carlo Method: The speaker highlights this approach, explaining its phases such as selection, expansion, simulation, and backpropagation. An analogy involving casino games illustrates the balance between exploring new possibilities and exploiting known strategies.
Neural Networks & AI Development: The incorporation of neural networks into the Monte Carlo framework is discussed as a promising avenue for improving AI performance in Go, providing a more nuanced approach to predicting strategy.
Engagement with Technology: The talk emphasizes the excitement surrounding the shared exploration of gaming, particularly in terms of developing engines and enhancing strategies.

In conclusion, Tobias Pfeiffer’s talk sheds light on the intricacies of Go, the limitations faced by AI, and how randomness can be harnessed to improve strategy development, illustrating the continued evolution and interest in this ancient game.

00:00:11.990 Thank you all for showing up! Today I want to discuss a fascinating topic.

00:00:24.619 In 1997, IBM's Deep Blue defeated Garry Kasparov in a tournament. This marked the first time a computer had beaten a premier human player in chess.

00:00:36.390 At that time, Garry Kasparov was considered one of the greatest chess players of all time. Around the same period, a tournament called the World Cup took place from 1995 to 2000.

00:00:54.600 It had a total prize of one million dollars for anyone who could defeat 10 to 14-year-old Chinese children who were Go prodigies in an even game.

00:01:12.119 Despite the efforts, in the same year, 1997, a different program did compete against these children in Go.

00:01:19.350 The program won, but with a significant handicap of 4 stones. For those familiar with Go, this is a considerable difference, effectively indicating the gap between a very amateur player and an intermediate player.

00:01:31.830 Let's explore the recent history of computer Go and also discuss why Go is so much harder to master compared to chess.

00:01:50.430 In 2001, a program named 'The Corner' was launched in Japan, revitalizing interest in Go and making it more popular among the youth.

00:02:05.190 Go had been declining in popularity in Japan for some time, but it has remained very popular in East Asia.

00:02:10.430 In 2009, Google introduced a programming language called Go, created in homage to the ancient board game. Additionally, there’s another language named God, which caught attention for its similarity in name.

00:02:29.790 In 2014, a programmer named Jiajia Rami played against a strong program called Crazy Stone, which is one of the two strongest Go programs available. He played against a professional named Yu Da, who is a 9th-dan professional player. Crazy Stone won with a handicap of 4 stones.

00:02:51.720 This was much less than other handicaps previously used, but still indicated a notable difference in playing strength. On October 31, 2015, in a series called the Go Challenge, the program called AlphaGo, which is one of the strongest AI in this realm, played an even game against one of the strongest amateurs.

00:03:24.630 The human player, a German 5-dan athlete, prevailed in a best-of-five series. This marked a notable achievement in the AI vs human competition.

00:03:42.480 On November 3, 2015, Facebook published a blog post revealing their advancements in machine learning, mentioning the development of a Go engine that utilized pattern recognition.

00:04:02.910 However, the technical specifics of the engine were not shared publicly, which was quite surprising. On November 13, 2015, a site allowed users to play against a deep neural network using a Go engine.

00:04:16.200 We will examine some relevant scientific concepts and papers, but don’t worry if you’re unfamiliar with Go; we will cover the basics shortly. This talk is about beating Go thanks to the power of randomness.

00:04:34.560 I'm Toby, and you can find me on Twitter and GitHub as 'fractal'. I'm based in Berlin.

00:04:40.230 I organized the Ruby User Group in Berlin and I am passionate about open source projects.

00:04:46.050 Currently, I work at a great agency named Bitcrow, where we help startups build fantastic products. Moreover, I am thrilled to be here, as my company sponsored my trip to this conference.

00:05:18.300 I should note that some of you might be a bit concerned about my t-shirt! Some might think it's unprofessional, but there’s a saying: Superman wears a Chuck Norris t-shirt. We made this shirt ourselves.

00:06:08.640 Now, let’s continue with the basics of Go. Go is played on a board with a grid of intersections, with the standard size being 19 x 19.

00:06:31.590 There are also smaller boards of sizes 13 x 13 and 9 x 9. Although professional games are typically played on the 19 x 19 board, 9 x 9 is also interesting. In Go, players take turns placing stones on the intersections; Black plays first, followed by White.

00:07:09.800 Every stone has what are called liberties, which are the adjacent empty intersections. For example, a solitary Black stone has four liberties, and when another stone is placed adjacent to it, they form a group that shares liberties.

00:07:47.620 If White plays next to the Black stone, both stones would reduce their liberties by one. If White plays a third stone that touches the group, the Black stone can be put into Atari, which means it's one move away from capture.

00:08:20.790 If White captures it, the Black stone will be removed from the board, earning a point for White. However, a savvy player can stretch the game, maintaining their liberties and resistance.

00:09:00.810 Winning in Go is about occupying more territory than your opponent. At the end of the game, the player with a greater area of controlled intersections wins. The concept revolves around strategy and territorial gain.

00:09:53.490 For example, if Black encircles a territory and must sustain some liberties, they gain points. The game is highly dynamic, with movement affecting positioning globally across the board.

00:10:38.210 Here’s an illustration of a game concluded between a professional player and one of the strongest Go engines. When counting the stones, positions with no chance of survival are removed, and territories are calculated.

00:11:52.630 The concept of 'komi' plays a significant role in Go, as the player moving second receives a bonus to balance the advantage of going first. This complex balance further exemplifies the strategic depth of the game.

00:12:38.000 In a professional match format, players occupy corners first, competing for strategic advantage. The game’s highly intricate nature means it can be difficult even for seasoned players to determine the leading position.

00:13:59.740 As gameplay progresses, the global impact of each move can move one player ahead or turn the tables. Captured groups or incorrect assumptions can resonate throughout the board.

00:14:27.180 Let's transition now to discuss the difference between Go and chess. In Go, every player contributes to board development, while in chess, players aim to dismantle their opponent's setup.

00:14:46.420 An interesting parallel arises when discussing complexity in games. While Go has fewer formalized rules, the sheer number of possible board configurations leads to immense complexity. Conversely, chess has many rules governing piece movement, making it complicated but less sprawling in terms of possibilities.

00:15:41.680 Famed chess grandmaster Edward Lasker remarked that the elegant rules of Go suggest that if intelligent life exists elsewhere, they would likely play Go.

00:16:50.970 Discussing AI, the ranking system in Go is vital to understanding performance assessments. Beginners start from 30 kyu and can reach the ranks of Dan through rigorous practice.

00:18:16.090 At an amateur level, differences in strength are quantified through handicaps—9 kyu against a 5-dan, for instance, plays with a 4-stone handicap. Contemplating AI's performance in this context provides immense insight into strategy development and player strength assessment.

00:19:28.450 What makes Go so significantly more challenging than chess? Firstly, the 19 x 19 board presents a far higher number of potential legal moves, leading to an average branching factor of approximately 250 compared to just 35 in chess.

00:20:44.100 Moreover, the state space complexity in Go, expressed in terms of valid board configurations, is staggering. For instance, while chess boasts about 10 to the power of 47 configurations, Go expands far beyond that.

00:22:12.460 The significant difference also lies in the nature of moves: a single move in Go can have a global impact, affecting distant regions on the board and influencing an array of strategies.

00:23:48.670 Moving on to AI, traditional algorithms like Min-Max, frequently employed in chess, face hurdles in Go management due to its complexity. In pursuit of viable approaches, we arrive at the Monte Carlo method.

00:24:20.130 Though perhaps not the most ancient mathematical quandary, pi provides an example to illustrate the Monte Carlo approach—using random sampling to achieve estimations. By harnessing randomness, one can glean meaningful insights amidst vast possibilities.

00:25:53.320 The Monte Carlo tree search algorithm undergoes selection, expansion, simulation, and backpropagation phases. During the selection phase, nodes with the highest success estimates guide the traverse towards potential moves, enhancing strategic decision-making.

00:27:22.800 To showcase, let's explore a casino-related analogy. You might be in a scenario where you're consistently winning on a machine, yet you ponder whether others yield better results. Thus, the balance between exploration of new options versus exploitation of known successful strategies unfolds.

00:28:57.890 This intrinsic dynamic drives performance metrics within the Monte Carlo framework. Properly selecting moves based on both winning potential and prior results can yield significant success in gaming.

00:30:22.430 AI looking to emulate human thought processes should ponder: how can a random rollout transform decision-making? It exemplifies the modern computational approach—recognizing scenarios beyond instinct, much like how engines analyze countless outcomes and adapt accordingly.

00:32:54.090 Optimizing gameplay via Monte Carlo is an ongoing study, with findings frequently published among developers and researchers. These ongoing enhancements have propelled the sector's understanding and practical applications.

00:34:29.550 Incorporating neural networks into the Monte Carlo framework shows promise, as they prospectively predict professional moves, in this augmentation, yielding essential refinements to gameplay.

00:35:56.090 Engaging with various game engines, whether through Ruby in developing Rubicon or utilizing other languages, cultivates a rich landscape encouraging exploration and the sharing of experiences and strategies.

00:37:35.680 It's been a pleasure delving into the complexities of Go and its relevance within AI. The exhilarating journey from random moves to strategic dominance highlights how innovative approaches revive interest in age-old games.

00:39:04.360 Thank you for your time and attention. I look forward to seeing your contributions to this exciting field!

00:40:12.489 Thank you very much for listening to me ramble on about gaming, Go, and the power of randomness. This concludes my talk on beating Go thanks to the power of randomness.

00:41:36.790 If you have any questions, feel free to reach out to me after.