Solving problems with brute force (plus secret sauce)

I recently found myself flipping through Feng Shu’s book entitled Behind Deep Blue, after reading an article by him in the IEEE Spectrum. This got me thinking about the role of, and sufficiency of, brute force in solving difficult problems.

His IEEE Spectrum article is based on the premise that brute force search is sufficient, in conjunction with powerful hardware, to conquer difficult open problems such as the game of Go. In that article he goes as far as to say that even things like Monte Carlo methods are irrelevant and the game is all about more computation.

However, when I read his book, I see a more nuanced approach. By the time they were up against Kasparov, they had all sorts of things going for them – in addition to basic search algorithms. Among other things, they had specialized evaluation functions that had the benefit of expertise from several grandmasters. And over 15 years, they had put in all sorts of subtle tweaks before the system did what it was supposed to. So, it did have some secret sauce – although the main course was, undoubtedly, brute force computation on specialized hardware.

I am actively interested in this issue because a similar decision is called for in applications I am currently thinking about – involving humanoid robots. A consensus is emerging that the right way to get at interesting behaviors with humanoid robots is to take a data-driven approach to mimic human activities, and perhaps actively improve from randomized experiments – without wasting too much effort in trying to understand the structure (such as the way a control engineer would). I am in agreement about the role of learning but I am sceptical about dogmatically staying away from analysis. Instead, my feeling is that certain key design insights – based on a deep understanding of the task (using suitable mathematical abstractions that are invariant with respect to quantitative details) – would go a long way towards tangibly useful behaviors, in the same way that the grandmasters played an important role for chess. Of course, the question is always that of where the boundary lies…

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s