God's algorithm facts for kids

God's algorithm is a cool idea that helps us understand how to solve puzzles in the best way possible. Imagine you have a puzzle, like a Rubik's Cube. God's algorithm is a special set of instructions that tells you exactly how to solve it using the fewest moves possible. It's like having a super-smart guide who knows the perfect next step from any situation!

This idea isn't just for Rubik's Cubes. It can be used for many other kinds of puzzles and games that involve different combinations of pieces or moves.

What is God's Algorithm?

Understanding Puzzles

God's algorithm works for puzzles that have a set number of ways they can look (called "configurations") and a clear set of "moves" you can make. Each move changes the puzzle from one configuration to another. The goal is to reach a specific "final configuration" or one of a few possible final states. You start from any mixed-up position and use a series of moves to solve it.

Finding the Best Solution

A "God's algorithm" for a puzzle is a method that takes any starting position and gives you the shortest possible sequence of moves to solve it. If a puzzle can't be solved from a certain starting point, the algorithm would tell you that too.

The shortest number of moves needed to solve a puzzle from its hardest starting position is called God's number. So, God's algorithm always finds solutions that use this smallest possible number of moves.

Some people also think that for an algorithm to truly be called "God's algorithm," it should also be practical. This means it shouldn't need a huge amount of computer memory or time to figure out the solution. For example, if you had a giant list of every possible puzzle position and the best move for each, that would solve it quickly, but it would take an impossible amount of memory!

You can also think of God's algorithm as just telling you the very first best move to make. If you keep applying the best first move, step by step, you'll eventually solve the puzzle in the shortest way.

Examples of Puzzles

Many well-known puzzles fit the description for God's algorithm. These include mechanical puzzles like the Rubik's Cube, Tower of Hanoi, and the 15 puzzle. Even single-player games like peg solitaire and logic puzzles such as the missionaries and cannibals problem can be looked at this way. These puzzles can be thought of like a map, where each puzzle position is a place, and each move is a path connecting two places.

Mechanical Puzzles

The N-Puzzles

The 15 puzzle is a sliding puzzle with 15 numbered squares and one empty space. You slide the squares around to put them in order. The hardest positions of the 15-puzzle can be solved in 80 single-tile moves or 43 moves if you can slide multiple tiles at once.

For bigger versions of this puzzle (called the n-puzzle), finding the shortest solution is extremely difficult for computers. It's so hard that we don't know if a practical God's algorithm for these larger puzzles exists.

Towers of Hanoi

The Tower of Hanoi is a puzzle with three rods and a number of disks of different sizes. The goal is to move all the disks from one rod to another, following certain rules. For this puzzle, we actually know a God's algorithm for any number of disks! The number of moves needed grows very quickly as you add more disks. For example, with 'n' disks, you need `2^n - 1` moves.

Rubik's Cube

The Rubik's Cube is one of the most famous puzzles. In 1997, a method was published to find the minimum number of moves to solve it. Since 1995, we knew that at least 20 moves were needed for the hardest positions. Then, in 2010, after a lot of computer calculations, it was proven that no Rubik's Cube position ever needs more than 20 moves to be solved. So, 20 is officially God's number for the Rubik's Cube! A mathematician named David Singmaster had guessed this number back in 1980.

Unsolved Games

Some games have very simple rules but are still too complex for us to find a God's algorithm for a winning strategy. Good examples are the board games chess and Go.

Both chess and Go have an incredibly large number of possible positions that grow very quickly with each move. For chess, there are about 10¹⁵⁴ possible positions, and for Go, it's even more, around 10¹⁸⁰. These numbers are far too huge for even the most powerful computers today to check every single possibility. (Compare this to the Rubik's Cube, which has "only" about 4.3 x 10¹⁹ positions, and that was hard enough to solve!)

Because of this, a brute-force approach (checking every single option) to find God's algorithm for chess or Go is impossible. Even though chess computers can beat the best human players, they don't calculate every move to the end of the game. For example, Deep Blue, a famous chess computer, only looked about 11 moves ahead. After that, it used special rules, learned from human chess experts, to decide which position was best.

Go is even harder than chess for computers. Besides having many more positions, it's been very difficult to create simple rules for computers to judge how strong a Go position is. So, even for looking a few moves ahead, a God's algorithm for Go hasn't been possible yet.

On the other hand, draughts (also known as checkers) is similar to chess but simpler. In 2007, a team of researchers proved that all perfectly played games of checkers will end in a draw. They did this by calculating a huge database of all positions with ten or fewer pieces. This means they found a God's algorithm for all checkers endgames. Checkers has about 5 x 10²⁰ positions, which is a lot, but still much less than chess or Go, and closer to the complexity of the Rubik's Cube.

The size of a puzzle's positions doesn't always decide if a God's algorithm is possible. The Tower of Hanoi puzzle can have any number of disks, and its number of positions grows very fast. But we still have a solution algorithm that works for any size!

See also

In Spanish: Algoritmo de Dios para niños