Space-State Complexity
Researchers
estimated there are roughly 1043 space states in Chess. That
means if you have a machine with memory space proportional to 1043
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 2!8 =
4.63*1042, 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 2!8)*(32*31)2, that is 2.99*1041.
What is the state complexity of
Chinese Chess then? The best estimate we knew before is 1045.
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*1039.
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.
- The states when bishop and
pawn in the same side occupy the same position.
- The illegal states when two
kings facing directly to each other.
- 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
1039 (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*1039).
Considering some further
thinking:
- 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.
- 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*1039)
|