March 25, 2014
How deep can brute force dive?
Without any good reason, i just can't stop myself from fearing the day when machines will completely solve the chess puzzle from the beginning move. Are they close to calculate everything?
Hopefully not yet. Even though the strongest PC processor today is far behind Deep Blue 1997's power, many free engines manage to play much stronger than it thanks to better evaluation algorithms.
What is the limit then, if they would be forced to calculate every possibility, in other words if they would use pure brute force instead of selective search, giving up elliminating non sense variations?
Let's assume an average of 3 minutes thinking time per move which represents tournament time controls and an average of 30 possible legal moves in each half move (ply) to calculate how far machines can look ahead:
Deep Blue @ 200 million nodes per second:
Max analysis depth: log (200 Mnodes * 180 sec) / log (30) = 7,15 plies!
Stockfish @ 25 million nodes per second:
Max analysis depth: log (25 Mnodes * 180 sec) / log (30) = 6,54 plies!
Obviously still not enough. In both cases machines can't even look 4 full moves ahead!
Now, i calculate how much time would Deep Blue need to calculate all possible variations up to 25 plies ahead, remembering that strongest recent engines reach this depth easily on a modern pc today:
(30^25) / 200Mn / 3600 / 24 / 365 = 1.34 * 10 ^ 21 years
Hmm. Too long for an opponent to wait.
This time let's be more reasonable with 20 plies depth and 20 possible moves per ply:
(20^20) / 200Mn / 3600 / 24 / 365 = 1.66 * 10 ^ 10 years
At least the second result can be sizeable by human mind: 16.6 billion years. The conclusion is that we must still postpone the brute force projects.
Machines don't see everything yet and we won't live enough to witness that.
Subscribe to: Post Comments (Atom)
Post a Comment