March 25, 2014

How deep can brute force dive?

Programs playing at over 3000 elo is not rare at all today. Although the progress is mainly based on much smarter evaluation alghoritms, especially positional vs material, there's a little bit of help from stronger processors with multi cores and lots of threads too. We've come to a time we talk about 8, 16 cores and up to 64 threads on a single machine.

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.

No comments:

Post a Comment