simont: A picture of me in 2016 (Default)
simont ([personal profile] simont) wrote2005-05-12 10:36 am

Thoughts on thoughts (II)

I said in my last entry that I'd been inspired to reflection as a result of adding two new games to my puzzle collection, and then I proceeded to comment on something that had been brought to my attention by the first of those games. Here's something that was brought to my attention by the second.

The second of my new games is ‘Twiddle’: a tile rearrangement game in much the style of Rubik's cube, and well suited to much the same kind of solution strategy, which is to put as much of the puzzle in place as you can do simply and then resort for the rest to rote-learned move sequences that (for example) cyclically rearrange three pieces or flip two upside down.

For any puzzle of this type, there's a theoretical ‘God's Algorithm’ for solving it, which can take any position and always find the shortest sequence of moves that return that position to the start state. Normally the set of possible positions is too large to actually analyse this by computer, but for several of the simpler forms of Twiddle it actually turned out to be feasible on a normal desktop PC, so I hacked up some software and gave it a go.

The results are really scary. It turns out, for example, that Twiddle in the default state can always be solved in at most eleven moves (and there are very few positions actually requiring that many; a randomly chosen position is much more likely to take seven or eight). But when I started solving Twiddle puzzles, my move sequence for permuting three pieces took longer than that on its own!

So one obvious question to ask of God's Algorithm, once you have an implementation of it for a particular puzzle, is ‘so if it takes me fourteen moves to permute three pieces and you say anything can be done in at most eleven, you tell me how I can permute three pieces more efficiently’. So I asked that, and it told me – and I kicked myself. The shortest move sequences for simple transformations like this are not magical weirdness; they're obvious things that could have been constructed using the normal mathematical tools one uses to construct Rubik-puzzle operators. They just happen to apply the same techniques more efficiently than I did.

(Asking God's Algorithm to solve a completely scrambled grid, however, is without question magical weirdness. It's really crazy to watch. You can't mentally keep track of where every piece is going, unless your brain is somewhat roomier than mine. You can just about watch the pieces on the top row get put into the right places, and when you do that it doesn't look too different from a human approach to putting the same pieces in place – except that at the moment the top row is finished, mysteriously the rest of the grid suddenly seems to be in order as well. It's creepy.)

What this exercise brought home to me is just how bad the human brain (or at least my brain :-) is at doing things really well. We as a race are staggeringly good at finding ways to do something at all: we've managed to survive and achieve total dominance on this planet in spite of (a) enormous razor-toothed ravening killing machines, (b) insidious deadly organisms much too small to see, (c) countless types of beast which can move faster than us, fly, or otherwise get to food before we do, (d) a rather haphazard trial-and-error body design, (e) natural disasters, ice ages etc, (f) each other, (g) miscellaneous. And we've done this in spite of having intrinsic strength, speed, stamina, stealth and/or armament disadvantages compared to most of the wildlife we've been competing with for survival; our ability to find solutions to problems is without question a trump card that beats all of that lot into a cocked hat.

But it seems to me that we don't solve any of these problems particularly well. Efficiency, optimality and the like are things we strive for desperately hard over centuries or millennia. Finding the best solution to a problem is something the human brain is badly suited for and other approaches can do better: most of the things we have so far trained computers to do for us (add up, play chess, control complex aircraft etc), they turn out to be able to do better than we can.

To some extent this is just me. I know I personally don't have much talent for, or find much satisfaction in, finding better solutions to an existing problem when I could be finding a new problem to solve instead. I can just about cope if I'm given a clear efficiency criterion to meet (‘solve this problem using at most the amount of memory in this computer’), because that way I can use that criterion to begin the process of ruling out possible approaches. But saying ‘just make this better, by any means necessary’ is almost the definition of tedium to me unless I happen to catch sight of an utterly obvious improvement. (Which I will do sometimes, but once the obvious ones are dealt with I have little patience with searching for the less obvious.) In addition, I think I have the stereotypical mathematician's attitude to some extent: to exclaim ‘Ah, a solution exists!’ and go back to bed. For some kinds of problem, once you know it can be done in principle, actually doing it is just boring grunt-work. (But for other kinds of problem, the grunt work is the fun bit: I'm temperamentally a hands-on actually-build-things programmer rather than a blue-sky computer science research type.)

But also, I wonder if this reflects another aspect of the evolutionary pressure under which we evolved. Just as strength, speed, stamina, stealth and nasty pointy teeth all turned out to be much smaller advantages in the long run than a problem-solving brain, I wonder if it might also be the case that we don't need to be able to find the best solutions to problems, because just like physical prowess it's another specialism which can be defeated by a sufficiently determined generalist. I wonder if a species which devoted more brain-space to doing things efficiently at the expense of losing a bit of the flexibility and adaptability of the human brain might have lost out to us just as the sabre-toothed tigers did. The rival tribe over the hill knows how to make flint axes sharper than we can? No matter, because while they were sitting there sharpening things, we were inventing leather body armour. Their hunters can track a food animal and have a 40% better chance of actually catching it than ours? But we've invented farming, so we don't even need to bother any more. And so on.

Then again, I do know that other people are better at optimising things than I am. There are people in my group at work who excel at finding a new and different 0.5% or 1% improvement to the performance of our tools, every week or every two weeks, and over the course of a year those tiny percentages add up impressively. And where I tend to make major decisions based on simple qualitative grounds (if I do it this way it will enable this in future which I like the sound of), I know that ideally I would be making decisions based on overall cost (yes, but it'll also take three times as long and I'll never actually turn out to get any benefit from it); and I know that some people can do that well, or at least better, and that they tend to be the people who succeed in areas like business. (In fact, sometimes I think this is one of the reasons I shy away from business and prefer to work in free software, where counting the cost of things tends to be less of an issue.) So perhaps this is all unnecessarily me-centric, and the paragraph of evolutionary theory above is just a specious moral justification for my personal intellectual limitations.

Anyone have any thoughts? Am I right to think humans as a whole tend to be good at qualitative problem solving and less good at quantitative optimisation? Or am I right to suspect that that's just me trying to excuse my own limitations? Or do some (or most) people function equally well in either mode and the interesting distinction is somewhere else? Or is the question meaningless, and what I see as two substantially different modes of thought are in fact more similar than they feel?

pm215: (Default)

[personal profile] pm215 2005-05-12 09:51 am (UTC)(link)
the paragraph of evolutionary theory above is just a specious moral justification

I'm always kind of suspicious of this, since I think you can construct a cod-evolutionary argument for just about any aspect of human behaviour or physiology...

rmc28: Rachel in hockey gear on the frozen fen at Upware, near Cambridge (Default)

[personal profile] rmc28 2005-05-12 09:53 am (UTC)(link)
I think I'm definitely in the camp of "make a solution that works" rather than "make a perfect solution". Frex, we need a dining room table that folds, not a perfect one (that argument went on sporadically for nearly 2 years but has now been solved); Keith offered to build me a perfect bed, but I got bored of waiting and bought a less-perfect one.

But then I can get wound up by people doing what seems to me obviously sub-optimal things that "work", like unsorted bookshelves, and washing up/cleaning teeth while leaving the tap running.

[identity profile] mooism.livejournal.com 2005-05-12 09:57 am (UTC)(link)
I think people are satisfied with a “good enough” solution, and while we generally aim for perfection, we don’t cry when we don’t achieve it. After all, no-one *needs* better than “good enough”.

Some people get hung up with doing things faster or more precisely than ever before, but then some people get hung up on painting something exactly the right shade of green — seeking perfection is for the purposes of beating sexual rather than natural selection.

[identity profile] cartesiandaemon.livejournal.com 2005-05-12 10:22 am (UTC)(link)
It could make sense. The example I remember is a dog on a beach non-opposite a stick in the sea. It doesn't run in a straight line, it tries to minimise the time to get the stick. But it doesn't do it perfectly, just good enough. It sounds like there's a lot of problems where ingrained rules of thumb can take you most of the way there, but anytjhing more ocmplicated requires analysis and just isn't practical when being chased by a tiger.

But here it sounds like a limitation of memory. I don't know exactly how your algorithm works, but presumably some sort of tree search, which my brain just can't handle, so the *only* way I can do it is to find a route I can take baby steps along using algorithms I can remember.

[identity profile] songster.livejournal.com 2005-05-12 10:41 am (UTC)(link)
It's the joke about the two guys chased up a tree by a bear - one puts on running shoes. You don't need to outrun the bear, just outrun the competition.

Evolution doesn't proceed by finding optima, it proceeds by finding incremental improvements. These should home in on local optima, but these are unlikely to be global optima (e.g. the backwards vertebrate eye). Also, the enviroment and the definition of "better" is continually changing.

[identity profile] ex-lark-asc.livejournal.com 2005-05-12 10:44 am (UTC)(link)
(a) enormous razor-toothed ravening killing machines, (b) insidious deadly organisms much too small to see, (c) countless types of beast which can move faster than us, fly, or otherwise get to food before we do, (d) a rather haphazard trial-and-error body design, (e) natural disasters, ice ages etc, (f) each other, (g) miscellaneous

*applause* you're on form today :)

defeated by a sufficiently determined generalist

THat's so a journal title/nameline :)

I do think the brain is better at just finding a solution than it is at finding the best one. Mostly because finding any kind of solution frees you up to do other things like farm, hunt, pay the rent &c - we're amazingly good jugglers really :)

[identity profile] claroscuro.livejournal.com 2005-05-12 10:54 am (UTC)(link)
Am I right to think humans as a whole tend to be good at qualitative problem solving and less good at quantitative optimisation

I tend to be reasonably good at bodging together solutions needed urgently so they work. They might not be pretty, but they work. This in areas ranging from bike repair to emotional crises to website design.

On the other hand, I am also an optimiser. I always want to fiddle with things I can make more efficient. The main exception to this is people, who I have no desire to change. I have found, however, that many people will look at me blankly and say "Why do you want to fix this, it works, doesn't it?" when I suggest re-designing their filing system, sorting their equipment for efficient and effective use and access, improving the performance of their website or database, etc.

It actually doesn't matter how trivial the task is, I hate having to do it inefficiently. I've left a trail of re-designed stuff behind me in the last few years as I have temped around Cambridge: spreadsheets and paper filing systems, storage cupboards, protocols, processes.

Personally, I suspect I'm lazy. Just in a rather specialised, invest-more-initial-effort sort of a way.
pm215: (Default)

[personal profile] pm215 2005-05-12 11:07 am (UTC)(link)
many people will look at me blankly and say "Why do you want to fix this, it works, doesn't it?"

It's largely in response to this kind of person that I've developed a tendency to resist the implementation of 'good enough' bodge solutions; they make it harder than you might think to do the Right Thing later on...

[identity profile] ptc24.livejournal.com 2005-05-12 11:36 am (UTC)(link)
Personally, I suspect I'm lazy. Just in a rather specialised, invest-more-initial-effort sort of a way.

How are you for impatience and hubris?
ext_8103: (Default)

[identity profile] ewx.livejournal.com 2005-05-12 01:09 pm (UTC)(link)
What makes you think that the insidious deadly organisms much too small to see aren't going to win in the long run?
ext_8103: (Default)

[identity profile] ewx.livejournal.com 2005-05-12 01:29 pm (UTC)(link)
There's a moral hazard associated with betting against the survival of the human race, in any case.
ext_8103: (Default)

[identity profile] ewx.livejournal.com 2005-05-12 01:48 pm (UTC)(link)
You could set up an inevitable and unavoidable impending planetary doom, then collect on the bet and enjoy your ill-gotten gains in the intervening time.
ext_8103: (Default)

[identity profile] ewx.livejournal.com 2005-05-12 01:59 pm (UTC)(link)
It might unavoidable but could fail to happen for reasons outside your control, or an inevitable event that you could personally avoid. Or possibly I was just using repetition for emphasis.
ext_44: (games)

[identity profile] jiggery-pokery.livejournal.com 2005-05-12 04:30 pm (UTC)(link)
I know you're talking about real life rather than puzzles, but you may well be interested in, and enjoy solving, the class of puzzles which are purely about optimisation. See http://www.otuzoyun.com/puzzledesign/index.html and the puzzles submitted for previous years' competitions.

As to how to go about solving a general optimisation puzzle, er... beats me!

*deliberately ignores the interesting questions in your last para*
ext_44: (pattern)

[identity profile] jiggery-pokery.livejournal.com 2005-05-13 06:22 am (UTC)(link)
Well, I bumped into him at least once or twice, and I was at Oxford! :-)

Do you still have contact with him? (Heck, is he on LJ?) If so, try to get him to book the World Puzzle Championships week in his diary before other things fill the week up: October 12th-17th.

[identity profile] oneplusme.livejournal.com 2005-05-12 05:36 pm (UTC)(link)
Possibly this is just my personal experience (as anyone who knows me well will attest, I have an appallingly flaky memory), but I think part of the problem is that human brains simply aren't built for brute force.

We can make a computer search the entirety of a given problem space, and it may well come up with a better solution than any human (and more quickly). This is, I'd contend, because computers do not suffer from boredom and have memories vastly more reliable than ours when it comes to large data sets. Vast matrices simply don't fit well into a human brain. That said, of course, brains are remarkably good at ignoring things, which is often a very good way to get a solution.

(This seems like an appropriate point for a nice illustrative quote on from John McCarty (http://www-formal.stanford.edu/jmc/newborn/newborn.html):
In 1965 the Russian mathematician Alexander Kronrod said, "Chess is the Drosophila of artificial intelligence." However, computer chess has developed much as genetics might have if the geneticists had concentrated their efforts starting in 1910 on breeding racing Drosophila. We would have some science, but mainly we would have very fast fruit flies.
)

This also ignores the fact that brains are also good at inventing computers to do brute force on their behalf. That, I think, is where the adaptability part becomes a win - it allows brains to bootstrap to higher levels of complexity by creating and using the appropriate tools (writing; abaci; computers) to extend their capabilities.

[identity profile] oneplusme.livejournal.com 2005-05-12 05:37 pm (UTC)(link)
(And damnit, my "h" key sucks.)

[identity profile] mtbc100.livejournal.com 2005-05-12 06:43 pm (UTC)(link)
I tend to like to do an interative thing of doing something that works, realising how it could have been better, then redoing it.

[identity profile] tombee.livejournal.com 2005-05-14 07:12 am (UTC)(link)
I think you're largely correct, because primarily humans work through complex problems by constructing stories. Quant optimisation as implemented by machine is the complementary opposite to this intelligence.

Typically: we endeavour to understand as much of the problem as we want to/ need to/can/ justify by tedious cost-benefit analysis or other meta-picture, thus reducing the solution set to a manageable (and communicable, if you're lucky) space. This remaining solution set gets over to a computer- using a rock to do our thinking for us. (Or, increasingly, to an underling with a computer.)

In this context, business and human optimisation can still be seen as being story driven; "The ape who attained tribal status by spotting a very small inefficiency in the bread-making process" is THE all-time best-seller- but in order to do this you typically have to know "the story of the ape who made bread"... and this may prove to be quite complicated after sufficiently many apes have had a hand at improving it already.

IMO the more interesting question is the previous musing on musing: why there's an inherent difference (if there is) between brains that are good at multitasking and ones that are good at doing one hard thing at once.

As to:

And we've done this in spite of having intrinsic strength, speed, stamina, stealth and/or armament disadvantages compared to most of the wildlife we've been competing with for survival; our ability to find solutions to problems is without question a trump card that beats all of that lot into a cocked hat

Personally, I'm a good deal more suspicious of comments about specious moral justification made by dragons.

This is an optimisation problem of a sort of course; brains trade against strength and speed because there's only so much blood to go around. However, humans do have some other vital strengths: Hands (which had to evolve, hand in hand, with the brain): Long flexible levers, and considerable stamina over long distance. For example, I know for a fact that you yourself once ran a cross country race faster than 8 other people.

[identity profile] tombee.livejournal.com 2005-05-14 02:40 pm (UTC)(link)
What does this indicate? bugger all, obviously.

On the other hand, how many of your year could you hand-on-heart say were definitely fully human? I can only think of one, and even he was convinced that x was equivalent to 3.