Recently the world has been thrilled by the game of go played between the world top player and a computer program. The program eventually won 4 of the 5 rounds, marking the historical moment in which go had finally been solved. This is almost twenty years after another important game - chess had suffered similar defeat. Why did it take almost 20 years?
You will hear that go is apparently a lot more difficult than chess and therefore the search space is much larger and bla bla bla. Well did we know in advance it was so much harder? Probably not until we started trying to solve it. Do we frankly even now have any reasonable intuition1 as to why go is so much harder? I doubt.
OK, let's look at something simpler - graph problems. Some of them are easy, lets say minimum-spanning-tree or even all-pair-shortest-paths. Some of them are extremely hard e.g. traveling salesman problem. Even though these problems sound very similar. It's all about some minimal path in a graph, it would seem they should be similar, yet their solutions vary greatly in complexity.
[su_frame]
Figure 1. Checkerboard pattern is solved by this net … Read more...