Dirt wrote:Uri Blass wrote:The project is of course nonsense but I am not sure that it is impossible to solve chess.
I agree, but I don't think it can be solved this century. I doubt it ever
will be solved, whether we can or not. Only so much effort should be put into solving a game.
Fully agreed as well. Let me add a few thoughts on it.
- IF the number of legal chess positions (NULP) is like O(10^46), and
- IF only 1% of these were actually reachable from the initial position of standard chess (but I doubt that, I believe it is more like 10-20%), and
- IF we had K computers available (let's call them "cluster nodes" in this context) where each cluster node gets a different opening position to solve (comparable to "distributed perft") and has "a lot of cores", and
- IF each cluster node can perform a fast state-of-the-art optimized parallel alpha-beta search with, say, 100 Mnps and only needs the theoretical minimum of nodes given by alpha-beta as 2 * sqrt(N) (which is hard to achieve when no "unsafe" pruning or reduction methods are available as in this case), and
- IF we can find phantastic speedup methods on the global level (not local for a cluster node) like a world-wide distributed hash table or an efficient algorithm to reuse cluster nodes for remaining work if they finish earlier than others, that are good for a total speedup factor of, say, 100, and
- IF we have a perfectly working replacement concept to replace defective cluster nodes on the fly and immediately resume work without any significant loss of information, and
- IF there are enough money and other resources around to do all as written above,
THEN the total time T in years until we are done derives from the number of cluster nodes K as follows:
One year has about 3 * 10^7 seconds, so one cluster node with 100 Mnps would be able to search 3 * 10^15 positions per year which would cover 4.5 * 10^30 positions per year based on the "perfect alpha-beta search" assumption. So for 10^44 reachable positions and with my mystical total speedup factor of 100 we would have something like
T = (10^42) / (K * 4.5 * 10^30) = 2.222 * 10^11 / K
so that we could expect a solution within T = 80 years for K = 2.5 * 10^9 cluster nodes.
With a lot of IF's. And even if someone comes up with another mystical speedup factor of 2500 then it's still 10^6 cluster nodes calculating day by day, 24/7 for 80 years, while also wasting LOTS of energy and money.
A more realistic formula with less "mystical" assumptions might be somewhere around this:
T = 10^14 / K
In my calculations above the major limiting parts seem to be
1) the required hardware and
2) the assumption that there is nothing better than "perfect alpha-beta" to address the problem.
Obviously we don't know today how 1) will evolve in future but we may well assume that hardware improvements are good for a small constant factor at most, like factor 2 every N years.
As to 2), as long as there is no fundamentally better approach than alpha-beta for searching a chess tree this will remain the key argument why solving chess most probably will not happen within the next few centuries at least.
Sven