Moscow parks : Tsaritsino (Царицыно)

One of the nicest park that we can find in Moscow is Tsaritsino. This park is situated at the south side of Moscow. I have been there already many times and enjoyed all of them. The Tsaritsino park is very well maintained, large enough to walk for several hours, and has a mixture of historical monuments together with nice natural spots. I strongly recommend to visit the park earlier than noon because in the afternoon, specially during the weekends and when the weather is sunny, there are tons of people coming to visit. In the summer, there is some refreshing fontains dancing under some soviet-style chill-out music.

There are tons of pictures on the internet of this park : you can find few on wikipedia (along with history) and in Mikhail Fursov's folder of pictures. I am sharing here a couple of pictures I made.

The first one is a general view of the park. This photo and the one below were made in end of october 08. There is a large lake in the park with a couple of neat islands which are full of ducks because no one can get on these islands to bother them!



This second picture shows nice contrasts between the blue sky and the "blue" water. It was taken from one of the corners of the park.



This third picture shows another view on the lake. The photo as well as the two following ones, were taken in the summer, in the period of July. As you can see, there is a lot of green...!



The following two pictures were made close to the Tsaritsino Museum. This is one of the bridge leading to the park.


This is a picture of a small artificial lake made to decorate the park.

Decrypting the chess DNA

The subject of how much chess is complex has been in my mind since I have started to play chess. I will try to give here a good view on the complexity of chess and to assess how long it will take to finally decrypt this game, using some simple mathematics.

When will chess be solved ? Imagine that the opening theory reaches the level of endgame tablebases that we already have. In other words, we would know with 100% accuracy, for every chess position, moves that lead to a draw, winning moves and losing moves. At such a level, we might even discover some opening lines that would give a forced win for white (what I call "golden lines"). So to answer that question we need first to answer the question : how many total possible chess positions do we have ?

A first answer can be found in wikipedia :

http://en.wikipedia.org/wiki/Shannon_number

So, our mathematiciens, estimate it roughly to be equal to 64! / 32!(8!)²(2!)⁶, or roughly 10⁴³.

First we have to mention that this number corresponds to the exact number of possible position of 32 chess pieces (16 black + 16 white) on the chess board. However, there are all the intermediate possible piece combinations : 31 pieces on the board, 30 pieces down to only two kings on the board. From this point of view, we can think that this number is under-estimated.

On the other hand, this number does not take into consideration all the forbidden type of positions. Below a list of them :
1) Two kings cannot be adjacent.
2) Pawns do not exist on the first and last rank.
3) Bishops do only exist on half of the board.
4) Some pawn configurations are not possible, for instance a position where all 8 white pawns are located on 7th rank and all 8 black pawns are located on the 2nd rank. This is, I think, the part that is the most difficult to assess.

We can redo the same calculation that Shannon did. We will first start with the calculation of the space used by the bishops. They can only exist on half the board (64/2=32) :

Pos.Bishops = (32!/30!) * (32!/30!) = 32*31*32*31

There are 4 bishop units in total. For pawns, we will assume that all the bishops are limiting the space of existence of the pawns. That is to say, that none of the bishops is on the first and last rank. This is already an approximation, which reduces a bit the number of possibilities. Therefore, the pawn space of existence, becomes 48 (from 2th rank till 7th = 6*8) minus the four squares occupied by bishops : 48-4=44. In the case of pawns, we have to exclude all the dual positions, this is why we divide the result by 8! for white pawns and 8! for black pawns. In this calculation, we did not take into account remark 4) above because it adds a lot of complexity.

Pos.Pawns = (44!/28!) / (8!*8!) = (44*43*42*41*40*39*38*37)*(36*35*34*33*32*31*30*29)/(8!*8!)

Finally, the last piece with space of existence limitations is the king. We have now 64 minus four squares occupied by bishops minus 16 squares occupied by pawns equal 44 squares remaining for the king to choose from. The second king can only be placed in squares that are not neighboring the first king. Therefore, we will have :

Pos.Kings = 44 * (44-9)

Finally for the rest of the pieces, all the 42 remaining squares are free and can be used without exception. Each time duals have to be taken out :

Pos.Queens= 42*41
Pos.Knights= (40*39*38*37) / (2*2)
Pos.Rooks = (36*35*34*33) / (2*2)

Therefore, the total number of legal chess positions, assuming 8 pawns for black and white; 1 queen for black and white; 2 knights, 2 rooks and 2 bishops for black and white, is :


Chess Possible 32 pieces = Pos.Bishops x Pos.Pawns x Pos.Kings x Pos.Queens x Pos.Knights x
Pos.Rooks
= 2.71 x 10³⁹

This is already ten thousand times less than Shannon !
There are many possibilities for position including less pieces : for 31 pieces, we have already 10 possible piece combination (32 pieces - 1 black pawn or 1 white or 1 black bishop or 1 white bishop or 1 black rook or 1 white rook or 1 black knight or 1 white knight or black queen or white queen). For every of these piece combination, the total number of possible chess positions will decrease. For instance, if we have 32 pieces without 1 white rook :

Pos.Rooks = (36*35*34) / (2)

The total number of positions decreases to 1.64 x 10³⁸ , which sixteen times less.
So the sum of all the variations with 31 pieces, will result in an order of magnititude of 1 x 10³⁹
For 30 pieces, there will be even more piece combinations, but because we have less pieces, there are also less possible chess positions. Without getting in all the detailed calculations, we can presume that the sum of all the additional positions coming from less pieces than 32, we will not exceed 10⁴⁰ possible chess positions.

Another question araises : how relevant are these positions ? Because many of them will never occur in real chess games although they are fully legal. See my post about chess 960, where I show some of other possible starting positions that would allow to explore this large part that does never happen in classical chess. Very roughly, we can guess that the number of chess possible positions based on the standard starting position is in the range of 10²⁰ to 10³⁰.

Now, let's estimate the total amount of memory needed for storing a 32-men tablebases :

A 6-men tablebase, requires about 1000 GB = 8 x 10¹² bits (see here for details). The number of chess positions in a 6-men tablebase is smaller than 64!/58! = 64*63*62*61*60*58 = 3.10¹². We can deduce a ratio of 10bits/position. With such a ratio, 32-men tablebases will require about 10⁴¹ bits to be stored. This also means that we need to increase our current storing capabilities by 10^41-12 = 10²⁹ assuming that 1000 GB is a typical storage capability today.

Now we have to take a look at what is called "Moore's law".




Gordon Moore is the co-founder of Intel, the current biggest semiconductor corporation in the world. This law states that every two years, the density of transistors on our chips is doubled. This law would be better called Intel's law, because Intel has been driving and maintaining this speed of transistor densification. It is not clear how Moore's law will do when the semiconductor industry will reach to atomic scale (after nanotechnology, angstr-technology). It is also possible that due to some new technology, moore's law would be accelerated.

Assuming Moore's law will continue to be applicable as it has already been for the last 40 years : since 2 power 99 is about 10²⁹, we can deduce that we will 99 x 2 years to reach that increase in storage capacity. Therefore :

By year 2200, 32-men tablebases will be available and the DNA of chess will be totally and finally decrypted.

See you then!