Korva is a scroll of the internet’s best ideas.
85 billion ways to start chess
How Big Games Get
Tic-Tac-Toe has 255,000 ways to play, and each extra open square doubles the decision tree. For a computer, with plenty of memory and fast processors, that is a drop in the bucket. For a child, it is far too much to hold in mind.
Chess is another matter. One player moves, then the other, four times over, and those eight moves alone can unfold in more than 85 billion ways because of the permutations on a normal board. Go reaches 266 quintillion ways to play.
The Case for Machine Learning
No current computer can think that many steps ahead, build the full decision tree, and pick the optimal move. Even IBM's Watson, which played Jeopardy years ago, worked by approximating correct answers instead of crunching every number for all day long or a lifetime.
That limit is the motivation for machine learning. Earlier game opponents were code written with ifs, else ifs, and elses that dictated every move deterministically. Machine learning is code that teaches a computer how to find solutions even when no one knows the correct answer, learning from the data it is fed.
How did computers beat chess champions?
IBM's Deep Blue defeated world champion Garry Kasparov in a 1997 match. It did not search the whole game. It evaluated around 200 million positions per second, used pruning to skip hopeless branches, and applied a scoring function tuned with help from chess masters. Human experts supplied the knowledge about which positions were strong.
How did AlphaGo handle a game as big as Go?
DeepMind's AlphaGo beat the champion Lee Sedol four games to one in 2016. It combined neural networks with Monte Carlo tree search, which samples lines of play at random instead of examining every one. One network suggested promising moves, and another estimated who was winning from a given board. Training began with records of human games and continued with the program playing against itself.
How many chess games are possible in total?
Claude Shannon estimated in 1950 that chess has at least 10 to the 120th power possible games, now called the Shannon number. By comparison, physicists estimate the observable universe holds about 10 to the 80th power atoms. The estimate rests on an average of about 30 legal moves per turn across games of around 40 moves per side.
How did Watson win at Jeopardy?
IBM's Watson beat champions Ken Jennings and Brad Rutter in a 2011 televised match. It ran hundreds of different analysis methods on each clue and combined their results into a confidence score for each candidate answer. It buzzed in only when its best answer cleared a confidence threshold. The system's hardware filled a room of servers during the competition.
More from CS50
