algorithms

# In Memory of Claude Shannon

How many bytes of computer memory, at minimum, would it take to store every possible chess position of which there are 10^47 according to the latest calculations? If done right, less than 1 kB!

How come?

Because all those positions are equivalent to the following algorithm:

step 1: take the opening position and append it to an empty list

step 2: calculate all legal moves from the given position (if it’s the last move of a game, go to the next element of the list)

step 3: for each legal move found, write down the corresponding position and append it to the aforementioned list

step 4: proceed to the first unprocessed element in the list of positions and go to step 2, else stop

This algorithm would run for a long, long, long time before completing the task of generating them all.

But the time doesn’t count, only bits do, just like in zipping or unzipping files.

All and every chess position is there, compressed inside the algorithm described above.

The pressing question however, is how to minimize the product of the number of steps required and the bit-length of the algorithm.

It must be done fast and not use up all the resources (free enthalpy) of the observable Universe in the process. What’s the smallest possible effort required to generate all legal chess positions explicitly?

An estimation can be made. To write down all the positions, an Earth mass size object made of C12 and C13 atoms would suffice as storage.

Several self replicating nano-bots could be the seed of the mega structure. As they go, they follow the following procedure:

– multiply

– calculate legal positions, storing them inside yourself, informing your peers about the positions you are calculating, until there is no storage left

– dock and assimilate into the main structure

With the advances in nano technology it would be doable in a century or less, if we really wanted to.

2^6 years after Shannon, we need a century instead of a billion times the current age of the Universe, to do the job he envisioned back then.

Perhaps we will be able to do it in a minute, later in the 21st century, if we are still interested in chess at all.