A Faster Jigsaw Solving Algorithm 104
mikejuk writes "Andrew Gallagher at Cornell University in Ithaca, New York has improved the standard approach to automated jigsaw solving by copying what humans do in finding groups of pieces that best match and working outwards from there. With a speed of 10,000 pieces per 24 hours, it can solve large puzzles. Not only that, but the type of jigsaw it solves is more difficult than the usual in that the pieces are square and can be placed in any orientation. It is so good it can even solve problems consisting of a number of mixed up pieces without being told how many or their dimensions. Of course, as well as having fun beating humans at another recreational pastime, the technique could be used to unscramble shredded documents, as per the recent DARPA challenge."
Re:Progress. (Score:4, Insightful)
Re:Progress. (Score:3, Insightful)
I'm a lowly technician. So long as there are printers, someone has to go around the rooms clearing paper jams and putting new cartridges in.
Well then, your job should be safe for quite some time, as "paperless" office ranks right up there with IPv6.
Re:Progress. (Score:4, Insightful)
I find it sad that people actually think AI or any sort of AI is actually present here, or improving when they read about things like this.
There is no intelligence here. Nothing. There's no guesswork, only statistics, rigorously calculated and applied the same every single time. It's a heuristic. It's programmed. It's immutable. It's basically a targeted improvement on a naive brute-force algorithm.
That's *not* how intelligence works. To be honest, the nearest thing to "intelligence" we've had recently is the Kinect, but only because it was based on a genetic algorithm at one point and tweaked incessantly. And even that is more brute-force and dedicated processors than anything else.
There has NEVER been, in the whole field of AI, a logical leap to join two abstract concepts. There has never been discovery or invention (no matter how minor) on the same scale as even a pigeon. No machine ever worked out something that it wasn't told how to do DOWN TO THE LETTER.
This is not AI. Your science fiction is, and for the foreseeable future still will be, just that - fiction. There's nothing a computer does today that isn't just 60's theory and ideas applied with a sufficiently large amount of processing power to come up with pretty predictable results that do not approach AI. Yes, eventually, brute-force will allow us to come to resemble intelligence but it will not be intelligence, and brute-force is the most expensive thing to apply to a problem like that (and, strangely, own our intelligence is the cheapest!).
Literally, the closest we get is genetic algorithms and lettings things just run off on their own, and we're pretty sure even that's just an illusion and not crossed the line into something we would consider actual intelligence. There's an example of a GA put to work on a chip design to distinguish two frequencies of input. When the input is of one frequency, it activates one output, when the input is of another frequency, it activates another. The GA "evolved" through generations based only on selection for those criteria and ended up with ingenious solution that took years of analysis to understand fully.
But even that isn't "intelligence", so much as blind luck and brute-force. No machine, for the next 50-100 years at least, will be able to hold even quite a boring conversation with you (go look at the transcripts of Turing Test entries from as far back as you can and now - improvement but still no magic insight that makes it seem human unless you're terminally stupid). It certainly won't have a consistent or reasoned opinion. And certainly not one that it come to by itself and wasn't just a case of it picking a contrary / popular opinion deliberately.
Prove me wrong, by all means, but sci-fi is for the TV. I still can't get my phone to recognise my voice on a simple phrase 8 times out of 10 and that has vast quantities of brute-force, previous patterns, pattern-matching code and statistics to work from. Sure, it *looks* impressive and intelligent when you say "Where is the post office?" and it analyses the waveform to think you said "post office" with 85% certainty and then stick that into a basic search to see what comes up in the local area. But it's NOT understanding what you said. Not by a long shot. If I'd said "Where's the post? Office?", it will get it completely, 100% absolutely wrong and I can't teach it to get it right even the same amount of the time that any trained animal would.
This is not AI. Please stop thinking it is. It's pseudo-related at best.
Very disappointing. (Score:4, Insightful)
Here every edge has a color distribution and another edge of another tile with matching distribution. The fundamental solution was proposed originally in a Perry Mason novel by Erle Stanley Gardener. (As reported by Donald Knuth in his book/manual on TeX ). Perry Mason asks Paul Drake to find the two rentals by the same person just half an hour apart. Paul Drake says, "there are thousands of rental records, I would never find the match in time". Perry Mason says, "Nah. Just sort all the records by name, and look for duplicates".
Sorting by name, is grandiloquently called "Lexicographic Ordering" in comp sci. Create a lexicographic value for the color distribution on each edge, sort it by that order and look for duplicates. Here areas of uniform color would get multiple duplicates and one has to prune the tree. That is where these guys claim to have made some improvement. It is a nice problem I would give to some master's students learning heavy duty scientific computing. But I think shape matching has a lot more potential in developing antibodies and medicines.
Time complexity? (Score:2, Insightful)
"With a speed of 10,000 pieces per 24 hours" is not useful. What is the time complexity?