Tic Tac Toe program in the 1960's | Donald Knuth and Lex Fridman

TL;DR

Tic-Tac-Toe is a game played on a 3x3 grid with empty spaces, Xs, and Os, and its computational representation requires 3^9 bits of memory.

Transcript

what is tic-tac-toe what are we talking about and then um right what how how is it designed right so so you've got you've got a three by three grid and each each each could be in three states it can be empty or it can have an x or an o yeah all right so three to the ninth is a uh well what is how big is it i should know um but it's 80 81 times 81 t... Read More

Key Insights

• 🧘 Tic-Tac-Toe requires significant memory capacity due to the number of possible positions.
• 👾 The Tic-Tac-Toe program was influenced by a demonstration at a science museum and Charles Babbage's interest in programming the game.
• 🖐️ Brain three's learning process focused on avoiding mistakes rather than pursuing optimal play.
• 💦 The author's interest in learning systems was inspired by Rod Brooks' work with small devices.

Questions & Answers

Q: How is Tic-Tac-Toe designed?

Tic-Tac-Toe is played on a 3x3 grid with three possible states for each space: empty, X, or O. The game requires 3^9 bits of memory for every position.

Q: What was the computational representation limitation of the machine used for Tic-Tac-Toe?

The machine had only 2,000 10-digit words, limiting the total number of available bits and requiring efficient representation for the game.

Q: How did the author develop their Tic-Tac-Toe program?

The author created three parts to their program: brain one (random play), brain two (optimum strategy), and brain three (learning from mistakes).

Q: How did brain three learn to play Tic-Tac-Toe?

Brain three learned by avoiding mistakes instead of focusing on winning. It played against other brains until it converged to a safe draw strategy.

Summary & Key Takeaways

• Tic-Tac-Toe is played on a 3x3 grid with empty spaces, Xs, and Os, with a total memory requirement of 3^9 bits.

• The computation machine used for Tic-Tac-Toe had only 2,000 10-digit words, limiting the total number of bits available.

• The author developed three parts to their Tic-Tac-Toe program: brain one (random play), brain two (optimum strategy), and brain three (learning from mistakes).