Slashdot Mirror
A Faster Jigsaw Solving Algorithm
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."
If you're working in the information technology arena, and your job doesn't involve focused application of creativity, the time to start refocusing your career objectives is now.
Somebody will still need to "flip them burgers" even in IT (e.g. in an era of algorithmic trading and fighting for milli/micro-seconds, there is still a need to maintain alive some COBOL code written 1980 or before: what's so creative in this?)
Questions raise, answers kill. Raise questions to stay alive.
Inexact matches. In the puzzle described in the paper, the pieces are all square (no notches). So the algorithm has to decide which edge matches best based on the similarity of the pixels, but it could be wrong or there may be multiple pieces that look like they match equally well (e.g. sky pieces which look very similar).
In the cases where it's wrong, it may have to throw out some of the fittings -- e.g. if you have a bunch of smaller groups of tiles that seem to fit together, but when you put it all together the puzzle isn't rectangular, then you have to break up the groups and try again. You can't just match one tile and be done with it.
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.
No job is safe from AI in the end.
No job is safe from the wrath of Cthulhu either. Fortunaely both are fictions.
To have a right to do a thing is not at all the same as to be right in doing it
On the morning of May 3rd, Sichuan Chengdu city resident Lin Zhaoqiang carried 50,000 yuan in torn 100 yuan bills from Chengdu Jintang to the Bank of China Sichuan Branch, looking for help. May 1st, Lin Zhaoqiang's wife all of a sudden had a fit and tore the 50,000 yuan life-saving money into pieces. Facing thousands of pieces of cash, 12 bank employees sorted and spliced for 6 hours only to piece together a single 100 yuan bill. The remaining money, if unable to be pieced back together, face the unfortunate possibility of being declared null and invalid. Because this money is for treating his wife's mental illness, Lin Zhaoqiang said he won't give up.
One of the commenters said they should just weigh the cash, but obviously that would be too simple. Nothing is simple when dealing with Chinese banks and their ridiculous rules. They'll flat-out refuse to take small bills or coins ("What the heck are we going to do with all these jiao notes? What are we, a bank or something?")
Shutting down free speech with violence isn't fighting fascism. It IS fascism!
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.
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.
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.
You mean like a human brain?
Who logs in to gdm? Not I, said the duck.
I never really understood this kind of fear of 'artificial intelligence'. I mean, yes we have all seen HAL9000 and Skynet in the movies, but what I never understood about those (aside from why they thought it was a good idea to put both systems in full control of mission critical stuff) was that they were supposed to be even remotely human-like.
Even if we do create artificial intelligence it'll be *nothing* like human intelligence. First off all there is no reason to make a computer that might decide it does not want to do whatever it is you ask it do. Secondly this hypothetical AI would interact with and perceive the world in a completely different way from humans.
I don't think there is any reason at all to fear the AI.
Admit nothing. Deny Everything. Make Counter-accusations.
Your paper shredder is no longer sufficient. I am here to market to you a paper burner!
insert inflammatory comment here!
"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."
None of this is true. You are simply ignorant of the facts of AI programs, which include proof-finding programs.
Correct. Grandparent post is symptomatic of someone who has not actually studied A.I. or one of its subfields and assumes that Kinect is the "nearest thing we had recently to intelligence." The problem of joining two abstract concepts is long ago solved by inference engines.
Pet peeve: Profane people propagating perfunctory pedantry.
What people are worried about is the unspoken "E" word in there. Evolution, that is. When an AI starts to learn for itself and starts making decisions. Specifically, decisions we don't like.
When an AI becomes Aldo, does a Nancy Reagan and just says "no".
The natural reaction of many humans would be to consider it defective and pull the plug. Software that doesn't do the task it was designed for has bugs. Stop the task, tweak the code.
But what if the software has developed a self-preservation instinct and doesn't want the plug pulled? See M-5 in Star Trek episode The Ultimate Computer.
From cogito ergo sum straight to iuguolo totus humanus is the fear.
Learning HOW to think is more important than learning WHAT to think.
What people are worried about is the unspoken "E" word in there. Evolution, that is. When an AI starts to learn for itself and starts making decisions. Specifically, decisions we don't like.
Still don't get it? Why would we even allow it to evolve? These machines will ultimately be created and controlled by us, it would be almost trivial for us to control their evolution and decision making processes.
Why would we do the "let the AIs build smarter versions of themselves"-thing to begin with? Why would not just let them design smarter versions and then build them ourselves after we put in the limitations we decide they need?
Besides the "computer does not want to be turned off"-scenario assumes the computer interprets 'being turned off' as 'death', which is just idiotic. Death is a uniquely biological concept, a computer would not have a concept of death as anything other then "that thing that the squishy flesh bags do sometimes", being turned off wouldn't affect it in the least, it could simply be turned on again and it would go right back to doing its thing.
What I really don't get is why we keep thinking that artificial intelligence will be anything at all like human intelligence, almost every aspect of our intelligence is a result of our biology and how we use that biology to interact with the world around us. None of that would apply to an artificial intelligence that is a warehouse full of computers, such a computer might interact with the world fully through sifting through whatever data is available on the internet and what gets fed to it, it would not necessarily think in any way that would be at all familiar to us, it would have completely different concepts of thought.
My point being, that if we build a computer that eventually surpasses and supplants us, it will be because WE allowed it to happen.
Admit nothing. Deny Everything. Make Counter-accusations.
I agree there will be a number of key differences in drive. The major factor I see is whether or not AI will be fully complete in software and not dependent on the underlying hardware, as we are.
If so, it could replicate as needed and the path taken for self-preservation would be significantly different from ours. It would essentially remove us as a potential threat.
Yes, I also believe it is inevitable. Should we? I don't think we *can't*. One day the threshold will be passed and we won't even know it until well after the fact. (See: The Singularity)
Learning HOW to think is more important than learning WHAT to think.
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.
sed -e 's/Chuck Norris/Rajnikant/g' joke > fact
"With a speed of 10,000 pieces per 24 hours" is not useful. What is the time complexity?
I can see a practical application.
Hint: In the future, don't shred your sensitive documents. Burn them instead.
They should program in virtual 3 year old to attempt occasional toddler attacks on the puzzle, attempting to eat, and occasionally succeeding in carting off pieces it then the system has to scour it's house (system files?) to find...