Space-State Complexity

Researchers estimated there are roughly 10⁴³ space states in Chess. That means if you have a machine with memory space proportional to 10⁴³ units, you can solve Chess. As a result, you will always play the best moves, and will never lost a game combating with either the smartest human or the quickest computer in universe. However, imagine how large a number with 43 zeros behind is! Building such a monster computer is far beyond our physical world.

In a paper in 1950 [1], Shannon used a quite simple estimate, 64! | 32! 8!² 2!⁸ = 4.63*10⁴², to describe the number of legal states in Chess when all pieces are on board. However, if we consider that every bishop can only stay in one of 32 grids, the estimate can be improved to: (60! | 28! 8!² 2!⁸)*(32*31)², that is 2.99*10⁴¹.

What is the state complexity of Chinese Chess then? The best estimate we knew before is 10⁴⁵. Simply by a causal estimate, we could reach such a result, and not surprisingly, it is greatly over-estimated. Therefore, I carefully calculated legal states in Chinese Chess, and I am quite happy to announce a much closer estimate: 8.73*10³⁹.

Please be noted that the result is still an estimate of the number of legal states in Chinese Chess. There are some states that are still included in our estimation.

1. The states when bishop and pawn in the same side occupy the same position.
2. The illegal states when two kings facing directly to each other.
3. The ending states, where one side loses because of no moves.

States in Situation 1 are against rules, and those in Situation 2 are illegal. They should be eliminated from calculation. However, we may argue the number of them is less than 10³⁹ (Actually it is not hard to calculate, but may be too bored to do so. And as a result, the codes will be illegible and yet do not make count sense. I wisely avoid implementing this part to keep myself still sober :-P). The states in Situation 3 are all leaf states having no descendant states. The number of such states may have a surprising percentage in the whole legal states. Anyway, they are still legal states. Hence when taking Situation 1 and 2 into account, we believe the number of legal states in Chinese chess is O(8*10³⁹).

Considering some further thinking:

1. For every state, it can be divided into 2 sub-state: either in the turn for black side to move or for red side to move.
2. State isomorphism. For example, vertical mirror state through column 5 and isomorphic states by exchanging white pieces and black pieces.

Luckily, they only reduce the space complexity by a factor of a little smaller than 2. Therefore, I seriously raise my new findings:
The space-state complexity in Chinese Chess is O(4*10³⁹)