![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
stormsewerSo, I've been toying with genetic algorithms a bit. Making a genetic algorithm basically involves making a list of responses to every situation the algorithm might encounter. Typically you start with a random pool of algorithms, compete them, mutate and mix and match the winners' genomes to make a new generation, and then repeat indefinitely. (Does this process sound familiar?) The idea of encoding a response for every possible situation works well for some problems, but not for others. For instance, it would never work for teaching a computer to play go.
A Genetic Go Algorithm
On a go board, there are 361 intersections, and in any given board configuration each intersection can contain a white stone, a black stone, or nothing. So 361 intersections that can contain one of three things means the number of possible of possible board positions is 3361, or around 1 x 10172. That's the number of possible situations a go-playing algorithm could encounter. An estimate of the number of elementary particles in the visible universe is around 1 x 1089.
To calculate how much space would be required to store all that... In binary terms, you'd need at minimum 2 bits to encode the value for each position on the board (with, say, 00 for no stone, 01 for a black stone, and 10 for a white stone), so each board position would require 722 bits or 90.25 bytes. Thus to store every possible go-board configuration would require on the order of 1 x 10174 bytes, or 1 x 10153 zettabytes. The total amount of stored information in the entire world has been estimated to be around 1 zettabyte as of 2010 (from The Economist, Feb. 25, 2010), and the space that would be required for recording all human words ever spoken has been estimated to be 42 zettabytes (though I would amend that calculation to 210 zettabytes1).
So for a full go-playing genetic algorithm, each such program would have to have 3361 "genes" in its "genome" (which is the list telling it what to play next in every possible board state), and each gene could have 362 different values (361 potential places to play (for the sake of algorithmic simplicity we include illegal moves), plus the option of passing). So the total possible number of go-playing genetic algorithms- in other words, the search space in looking for the ideal player- is 362^(3^361), or 3621083, or 1 x 102771, where each such program takes up 1 x 10151 zettabytes of space2. Somewhere in there is the perfect go player. (More than one actually, because some states, like the state between atari and captured stones removed from the board, will never be encountered in real games, and thus the perfect algorithms can have any possible value for those states. Such states aside, the question of whether there is a single "best" algorithm is an interesting one.)
A Genetic Chess Algorithm
In comparison, in chess you have 64 squares. Each of those squares contains one of these seven possibilities: nothing, pawn, rook, knight, bishop, queen, king. When we take into account that each piece can be one of two colors, we get thirteen possibilities for each square. So the total number of chess board states is 1364, or 1 x 1071. Still huge, but now one quintillion times less than the number of elementary particles in the universe. How much space would be required to store that? Well, the next highest power of two after 13 is 24 = 16, so we'd need 4 bits per square and 256 bits (32 bytes) per board. So storing all of them would require around 3 x 1072 bytes, or 3 x 1051 zettabytes. The total possible number of chess-playing genetic algorithms would be 64^(13^64) = 64832 = 1 x 101503, each taking up 1 x 1050 zettabytes of space.
Go Versus Chess
So you're not going to try using a simple genetic algorithm to play either go or chess, but comparing the numbers involved does give a sense of why artificial intelligences have had so much more trouble beating us in go than in chess. Go is much more complicated. The difference becomes even clearer when you take into account that the number of possible legal moves at any given point is typically much less in chess than in go. In go there are 361 legal first moves, and the number decreases by one every move thereafter (in most cases). In chess there are 20 legal first moves- this will increase as pieces are developed and then decrease again as pieces are captured, but the total for any given chess game won't approach the array of options available to a go player in the course of a game of go.
Actual Go-Playing Programs
Go-playing algorithms do seem to be improving rapidly, though. Perhaps the top computer player in the world is MoGo, which currently is about as good as I personally could ever expect to be (and much better than I am now). That program uses something called Monte-Carlo Tree Search algorithms. I actually talked to one of the guys working on MoGo in 2009 (I think), and he said he expected a computer to defeat the best human go player in the world within five years or so. We shall see, but I expect it's inevitable.
Evolutionary Time in Genetic Algorithms
A related question is how long it would take to evolve your way to the perfect go or chess player if you had the ability to store, say, a few thousand of them at once and run them through games in a reasonable amount of time. I really have no idea, but for comparison...
In Melanie Mitchell's book, the example genetic algorithm she gives is a virtual robot that wanders a virtual 10 x 10 grid picking up virtual cans. It gets points for picking up a can in its square and loses them for failing to pick up a can in its square or for running into a wall. It is only ever aware of five squares: its own square and the four squares adjacent, each of which can be in one of three states: empty, can, or wall. So there are 35 = 243 possible states the bot will encounter. Each state would require 10 bits of memory, and all possible states would require 2430 bits (303.75 bytes). At any given time the robot can do one of seven things (move up, move down, move left, move right, move randomly, pick up a can, do nothing). So, the total number of possible robots is 7243 = 1 x 10205, which is still a lot more than the number of elementary particles in the visible universe or even the number of possible go-board configurations.
The way she evolves them is by starting with a pool of 200 robots with random genomes. They each get set on a randomized grid and get 200 moves to pick up cans, after which their score is tallied. That's repeated 200 times, after which the top robots' genomes are randomly mixed up with each other and randomly mutated to produce a new generation, on which the process is repeated. By around generation 1000, improvements have leveled off, and the robots were averaging reasonably close to a perfect score, complete with some pretty ingenious solutions to the problems they faced. It is pretty amazing how quickly evolution allows you to search through 1 x 10205 possible combinations to find high-performers. Keep that in mind the next time a creationist busts out the improbability of something like a human arising from "random" processes. Anyway, it's hard to translate that result to evolving go- or chess-playing bots, but given the vast increase in complexity you would expect it to take a vastly larger number of generations and/or population size per generation.
Fun Numbers From this Post
Number of elementary particles in the visible universe: 1 x 1089
Total data storage in the world as of 2010: 1 x 1021 bytes (1 zettabyte)
Storage space for all human words ever spoken: 42 or 210 zettabytes1
Number of possible board states in go: 3361 (exactly) or 1 x 10172 (approximately)
Information content of all possible board states in go: 1 x 10174 bytes (1 x 10153 zettabytes)
Number of possible board states in chess: 1364 (exactly) or 1 x 1071 (approximately)
Information content of all possible board states in chess: 3 x 1072 bytes (3 x 1051 zettabytes)
Notes
1Liberman estimates 10 billion people who have ever lived, with a life expectancy of 50. The total number of people who have ever lived is less like 10 billion and more like 100 billion. And the average life expectancy for the vast majority of those would have been more like 25 (this number from Lomborg's The Skeptical Environmentalist, Chapter 4). Thus I'd go with 210 rather than 42 zettabytes.
2Calculated as follows. The robot genome consists of some value for each possible board configuration. So the storage space for a single genome is the storage space of a value times the number of possible board configurations. There are 362 possible moves at every point, so for a value to be able to represent any one of them, it needs to be 9 bits (28 = 256, which is not enough), or approximately (slightly more than) one byte. So that's about 1 x 10172 bytes, or 1 x 10151 zettabytes. The calculation for a chess-playing robot can be done in the same fashion.
3For the chess player, we'd assume it only moves its own pieces, which are 16, and if for the sake of simplicity we consider every square on the board as a place where it could move that piece, then we need enough bits to handle 16 x 64 = 1024 possible values, which would be 10 bits (because 210 = 1024), which I also round to one byte for simplicity's sake. So that's around 1 x 1071 bytes or 1 x 1050 zettabytes.
A Genetic Go Algorithm
On a go board, there are 361 intersections, and in any given board configuration each intersection can contain a white stone, a black stone, or nothing. So 361 intersections that can contain one of three things means the number of possible of possible board positions is 3361, or around 1 x 10172. That's the number of possible situations a go-playing algorithm could encounter. An estimate of the number of elementary particles in the visible universe is around 1 x 1089.
To calculate how much space would be required to store all that... In binary terms, you'd need at minimum 2 bits to encode the value for each position on the board (with, say, 00 for no stone, 01 for a black stone, and 10 for a white stone), so each board position would require 722 bits or 90.25 bytes. Thus to store every possible go-board configuration would require on the order of 1 x 10174 bytes, or 1 x 10153 zettabytes. The total amount of stored information in the entire world has been estimated to be around 1 zettabyte as of 2010 (from The Economist, Feb. 25, 2010), and the space that would be required for recording all human words ever spoken has been estimated to be 42 zettabytes (though I would amend that calculation to 210 zettabytes1).
So for a full go-playing genetic algorithm, each such program would have to have 3361 "genes" in its "genome" (which is the list telling it what to play next in every possible board state), and each gene could have 362 different values (361 potential places to play (for the sake of algorithmic simplicity we include illegal moves), plus the option of passing). So the total possible number of go-playing genetic algorithms- in other words, the search space in looking for the ideal player- is 362^(3^361), or 3621083, or 1 x 102771, where each such program takes up 1 x 10151 zettabytes of space2. Somewhere in there is the perfect go player. (More than one actually, because some states, like the state between atari and captured stones removed from the board, will never be encountered in real games, and thus the perfect algorithms can have any possible value for those states. Such states aside, the question of whether there is a single "best" algorithm is an interesting one.)
A Genetic Chess Algorithm
In comparison, in chess you have 64 squares. Each of those squares contains one of these seven possibilities: nothing, pawn, rook, knight, bishop, queen, king. When we take into account that each piece can be one of two colors, we get thirteen possibilities for each square. So the total number of chess board states is 1364, or 1 x 1071. Still huge, but now one quintillion times less than the number of elementary particles in the universe. How much space would be required to store that? Well, the next highest power of two after 13 is 24 = 16, so we'd need 4 bits per square and 256 bits (32 bytes) per board. So storing all of them would require around 3 x 1072 bytes, or 3 x 1051 zettabytes. The total possible number of chess-playing genetic algorithms would be 64^(13^64) = 64832 = 1 x 101503, each taking up 1 x 1050 zettabytes of space.
Go Versus Chess
So you're not going to try using a simple genetic algorithm to play either go or chess, but comparing the numbers involved does give a sense of why artificial intelligences have had so much more trouble beating us in go than in chess. Go is much more complicated. The difference becomes even clearer when you take into account that the number of possible legal moves at any given point is typically much less in chess than in go. In go there are 361 legal first moves, and the number decreases by one every move thereafter (in most cases). In chess there are 20 legal first moves- this will increase as pieces are developed and then decrease again as pieces are captured, but the total for any given chess game won't approach the array of options available to a go player in the course of a game of go.
Actual Go-Playing Programs
Go-playing algorithms do seem to be improving rapidly, though. Perhaps the top computer player in the world is MoGo, which currently is about as good as I personally could ever expect to be (and much better than I am now). That program uses something called Monte-Carlo Tree Search algorithms. I actually talked to one of the guys working on MoGo in 2009 (I think), and he said he expected a computer to defeat the best human go player in the world within five years or so. We shall see, but I expect it's inevitable.
Evolutionary Time in Genetic Algorithms
A related question is how long it would take to evolve your way to the perfect go or chess player if you had the ability to store, say, a few thousand of them at once and run them through games in a reasonable amount of time. I really have no idea, but for comparison...
In Melanie Mitchell's book, the example genetic algorithm she gives is a virtual robot that wanders a virtual 10 x 10 grid picking up virtual cans. It gets points for picking up a can in its square and loses them for failing to pick up a can in its square or for running into a wall. It is only ever aware of five squares: its own square and the four squares adjacent, each of which can be in one of three states: empty, can, or wall. So there are 35 = 243 possible states the bot will encounter. Each state would require 10 bits of memory, and all possible states would require 2430 bits (303.75 bytes). At any given time the robot can do one of seven things (move up, move down, move left, move right, move randomly, pick up a can, do nothing). So, the total number of possible robots is 7243 = 1 x 10205, which is still a lot more than the number of elementary particles in the visible universe or even the number of possible go-board configurations.
The way she evolves them is by starting with a pool of 200 robots with random genomes. They each get set on a randomized grid and get 200 moves to pick up cans, after which their score is tallied. That's repeated 200 times, after which the top robots' genomes are randomly mixed up with each other and randomly mutated to produce a new generation, on which the process is repeated. By around generation 1000, improvements have leveled off, and the robots were averaging reasonably close to a perfect score, complete with some pretty ingenious solutions to the problems they faced. It is pretty amazing how quickly evolution allows you to search through 1 x 10205 possible combinations to find high-performers. Keep that in mind the next time a creationist busts out the improbability of something like a human arising from "random" processes. Anyway, it's hard to translate that result to evolving go- or chess-playing bots, but given the vast increase in complexity you would expect it to take a vastly larger number of generations and/or population size per generation.
Fun Numbers From this Post
Number of elementary particles in the visible universe: 1 x 1089
Total data storage in the world as of 2010: 1 x 1021 bytes (1 zettabyte)
Storage space for all human words ever spoken: 42 or 210 zettabytes1
Number of possible board states in go: 3361 (exactly) or 1 x 10172 (approximately)
Information content of all possible board states in go: 1 x 10174 bytes (1 x 10153 zettabytes)
Number of possible board states in chess: 1364 (exactly) or 1 x 1071 (approximately)
Information content of all possible board states in chess: 3 x 1072 bytes (3 x 1051 zettabytes)
Notes
1Liberman estimates 10 billion people who have ever lived, with a life expectancy of 50. The total number of people who have ever lived is less like 10 billion and more like 100 billion. And the average life expectancy for the vast majority of those would have been more like 25 (this number from Lomborg's The Skeptical Environmentalist, Chapter 4). Thus I'd go with 210 rather than 42 zettabytes.
2Calculated as follows. The robot genome consists of some value for each possible board configuration. So the storage space for a single genome is the storage space of a value times the number of possible board configurations. There are 362 possible moves at every point, so for a value to be able to represent any one of them, it needs to be 9 bits (28 = 256, which is not enough), or approximately (slightly more than) one byte. So that's about 1 x 10172 bytes, or 1 x 10151 zettabytes. The calculation for a chess-playing robot can be done in the same fashion.
3For the chess player, we'd assume it only moves its own pieces, which are 16, and if for the sake of simplicity we consider every square on the board as a place where it could move that piece, then we need enough bits to handle 16 x 64 = 1024 possible values, which would be 10 bits (because 210 = 1024), which I also round to one byte for simplicity's sake. So that's around 1 x 1071 bytes or 1 x 1050 zettabytes.
