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.
