Paterson's Worms Solved by Number-Crunching

An anonymous reader writes "Thirty years ago, Martin Gardner described Paterson's Worms to the world. Just recently, Benjamin Chaffin, one of the designers of the Pentium 4 chip, managed to trace a couple trillion steps of the 'unsolved' worms, and has pretty much solved all but two of them."

Worms?

Did somebody say worms [wormsinsand.org]?

Chaffin solves Patterson's Worms...

Sounds painful...

Of course, my first reaction was

...how the hell did he have the patience to step through "a couple trillion" lines of code in a worm???

Then I read the article. These worms, then - they're basically more complex versions of the Game of Life, right?

trippy

After reading the article, I'm left scratching my head about what this really means and how it might be useful in every day life.

The obvious answer is that the worms are psychodelic. Those are some "trippy ass worms", as can be concluded from the illustrations in the article. Those worms are on acid.

Or...

Another great background for that monitor that can do 30000x40000.

Worms and computers

A good overview can be found in
B. Hayes "In search of the optimal scumsucking bottomfeeder", American Scientist vol. 91, no. 5 pp392-396 (2003)

It is my belief that...

Brute force is killing thought. We do not learn from randomly testing cases. The scientific method has degraded to the point of oblivion.
Apparently, Frank Herbert was wrong. Brute force is the mind killer, not fear.

Re:It is my belief that...

Brute force is killing thought. We do not learn from randomly testing cases.

It is an interesting point you bring up, but I think there is a lot we can learn from brute force approaches to problem solving. Your mind, in a sense, employs brute force approaches to many of its tasks. It just so happens that the billions of cycles happen in parallel rather than in serial, and the algorithms are a bit different than the ones we're used to.

When you read this post, aside from thinking how brilliant it is, various small parts of your mind are frantically pattern matching millions of visual features simultaneously, and your "attention" is focusing a higher level consciousness onto part of that field, at which point millions of more patterns are being matched against the results of that first run, where you see letters and words, and those get matched against millions of words you've seen before, etc. etc. Brute force is everywhere around you. It is thought.

Re:It is my belief that...

nah...
evidence indicates that it is not brute force that the mind uses, but rather hueristic pattern matching, followed by brute force. There is a huge difference.
It also allows for some rather incredible pattern matching and unbelievably stupid mistakes on the part of humans.

One of the more interesting things is that humans don't search for an exact fit when doing pattern recognition, they go for a "good enough" condition. (Rembeber teh atrilce on raeidng?) This actually allows for more rapid processing, but opens the door for some pretty stupid mistakes.

On the whole, though, the human mind is an incredible processor. It is also non-binary, since many nerves can exist in many different states, some of which are qualitative, and it is non-linear, and parrallel! Branches, forks, etc., are quite common, and each nerve connects to a LOT of other nerves.

Re:It is my belief that...

Brute force, aka trial-and-error, is what drives evolution. Brute force created the human brain, your mind, and thought.

Other sites

There are more pictures at Benjamin Chaffin's page. [williams.edu]
There is more information on the games and rules at Sven's page [accessv.com], that includes a comparison of Chaffin's notation to Gardner's and a comparison of Worms to the Game of Life. [math.com]

Brute Force

This isn't much of a solution, in particular he can only say that some worms "appear infinite" and he couldn't prove that two worms were identical except for being rotated by 180 degrees. While his programs would be useful to an individual studying the worms to try form conjectures regarding symmetry and halting they should not be confused with real solutions. Understanding should be the first aspect to any solution.

There's an executable...

Here's an executable for Linux that draws worm tracks. Also some animated GIF's of the trail being drawn.

Martin Gardner is my hero

I devoured his columns as a boy. His simple, clear writing style made it easy to understand very sophisticated concepts. Today, I aspire to write like he did.

He is getting on in years and it's been awhile since I've seen anything new from him (either on math or junk science, his other favorite topic). His collection, The Night is Large is a great overview of his work.

Anway, it's a pleasure just to see his name and know that people are still pursuing the topics he wrote about.

-- Brian

Whoa - I went to school with him

Ben and I were on the track and XC team together at Williams. He was a year ahead of me. I knew that he worked at Intel, but hadn't kept in touch.

Run this on Big Mac

from the article Currently my grid is about 1.57 million points on a side

If he's saying that the 2 worms hit the end of the 1.57million^2 grid, in a non-repeating pattern, that's pretty neato. We must know where it ends! Put it on Big Mac, make the grid bigger, and call it iWorms.

Multi-player worms game; anyone remember?

A long time ago, I had a mult-player game based on this: each player would have a different colored worm, and if a worm encountered a configuration it hadn't seen before, it would prompt it's player for what to do in that situation; the game wrapped top/bottom and left/right (set on a torus), so it couldn't go on forever. It was sort of psychedelic watching the different colors spread and writhe over the screen,, and interesting to see how your rules interacted with the rules of the other players' worms. Really fun, for such a simple game.

I wonder...

I wonder what these worm trail pictures tell us about the Pentium 4 design. Can anyone identify the 64 bit extensions?

Fractals

Has anyone noticed how similar these worms look to fractal pictures? julia sets worms example #57 [accessv.com]

Encryption...?

Strange Idea, but, what about using this in encryption for pseudo-random number generation?

It's obviously simple to implement, but requires exponential processor/mem usage to generate each successive generation of pattern's. Would this be effective? would the reduced keyspace be better or worse than the computational requirements?

Could a mathematician please explain...

... how the rules are supposed to be followed? I've read Ed Pegg's page [maa.org] as well as the AccessV page, but when working through the patterns [accessv.com] I get stuck at '2 5 1 0'; instead of getting a 180 degree rotation of '2 1 0 4' I get an infinite pattern.

I was trying to take the first possible move available (e.g. for 2 1 0 4, try 2, then 1, then 0, then 4) but it's apparently not what I should be doing...

Thanks!

The graphics...

Yeah, it's a bitching about the graphics of the page.

Would if have been too much work to put separators in the first graphic? The thing is confusing enough, but made more so by leading the person to think that it is one long pattern with six different worms doing their own thing.

Oh no

Oh great, another worm? Where do I get the patch from this time?

Rules Explanation

This is great but it took a long time to figure out the rules since the description is so horrible. Well I got this far so good luck!

For 104015 as drawn here is the list of decisions. Basically it seems that every time the worm comes across a point with an eaten segment attached to it, the worm takes the next rule as a new decision, then draws a segment, and then goes back to the first rule in the list (which makes it try to start drawing a hexagon again). However I have to say that Pegg's coloring is rather arbitrary, that lone green segment in the middle stumped me for a while! Also the way decisions are made is not intuitive.

111111 black hexagon
Hit hexagon starting point, pick rule #2 which is a "0".
0 go straight one segment in red.
Go back to start of program, now use rule #1:
111 draw three more red segments using that rule.
Hit the black hexagon again, pick rule #3 (a "4") unclear yet whether it is picked because it is next in order or because the rules #1 and #2 can't be used. But considering next decision, I believe it is because it is next in order:
4 turn two hours to left and draw first blue segment. Then go back to beginning of program.
1111 draw four more blue segments until black hexagon is hit again.
Hit hexagon, pick rule #4 (a "0").
0 draw first yellow segment straight ahead. Then go back to beginning of program
1 draw second yellow segment.
Hit a vertex of the black hexagon, but we can crash through for some reason. So we keep drawing segments with rule #1 which should be in yellow but is green in the drawing:
11 draw two more segments
Hit the blue hexagon so pick rule #6 (a "5").
5 turn two hours to left and draw another green segment. Then go back to beginning of program with rule #1:
1111 draw more green segments
Hit blue hexagon again. Rule #1 doesn't do the job so rule #2 (a "0"):
0 go straight ahead drawing a single green segment. Then back to beginning of program with rule #1:
1 turn right and draw a single green segment.
Hit black hexagon, so pick next rule. All the rules are useless but the last rule #6 (a "5"):
5 turn left and draw a single green segment. Then go back to beginning of program and rule #1:
1 turn right and draw a single green segment.
Now we hit the black and red hexagons so another decision is to be made and we are into magenta which I won't follow.

It still seems wierd how decisions are made and maybe following magenta for yourself will tell you how the recursion is supposed to be done. Personally I would rather see some pseudo code since it is difficult to tell which of the two "0" rules is being chosen.

does this take other things into account?

Like... the pitter-patter of rain, moisture in the soil, ground vibrations cause by other things, like nearby animals, fishermen, etc?

Oh yeah, that screensaver

I always wondered what the screensaver had to do with worms. Now I know - it's a simulation of worms eating food in 1969, or something. I guess I still don't know. Damn you computer scientists, and your weird algorithms!

uhh

what?

Moo

Martin Garnder is rather intelligent. Yet, he is also a pompous fool. If you read his books, his arrogance is astounding, and only what he believes is sensical. This shows up in some of his preferatory remarks and explanations. But, he is good at some things. While the Aha! books are mildly reprehensible (for the aforementioned reasons) their thought-provoking comments outweigh them many times over.

Re:worms?

C64? Why would you associate that game with the C64? I'm certain that the most primitive version was on the SNES, way out of the C64's league.

Only game called Worms on the C64 would have been the crappy efforts of BASIC coders creating Snake clones.

Re:Who......

Who cares? Anybody who wants to be even further discouraged that all the low-hanging fruit in mathematics was plucked a hundred years ago, and that the possibility of finishing grad school in mathematics is diminishing to zero. If you want to teach college mathematics, you have to first somehow produce some sort of results leading to a Ph.D. It's not like you just "go to school" and take classes and finish according to some well-defined plan, the way high school or undergrad college works. You are expected to find some interesting and new idea. Which is so difficult in the field of mathematics anymore that it's totally depressing.

Re:Next Task, Chess

Well about computers and chess, you could start with this discussion [slashdot.org] here on /. two weeks ago...

Re:John Conway and the complexity of life

Life is very similar to "worms" but is actually much simpler.

Yes it's the same Conway. And Life is certainly NOT much simpler than worms. if anything it is much more complex. Both start with a simple set of rules that lead to complex patterns, but with worms there is only a point at any one time, and the patterns are only in it's past history and the changes it has made to it's landscape, a landscape that is consumed. But life and it's variants have multiple points of dynamic change each move (generation). It can show motion in multiple locations and multiple directions at once. It shows beauty and patterns both in it's history and in it's current generation. Conway's game of life, in it's many variations, is actually more complex than worms.

Worms does look more novel, particularly in that it is usually played on a triangular or hexagon grid work, while life is usually played on a square cellular structure. By life is not limited to a 2-d squale cellular structure and more than wormes is limited to a hexagon based structure. Life could certainly be played on a hexagon cell board, as well as many other cell arangements. I expect the main reason life is predominately seen on a square cell arangement is simply because Y by Y arrays lend themself very well to playing life in software, and it is still a complex game on a simple square cellular universe.

Re:Next Task, Chess

In short, no. There are more outcomes of chess then there are particles in the known universe. see the other reply for the previous discussion on chess.

Re:THE ANSWER IS......FORTY TWO

perhaps it is...six times nine?

Nope. 6 * 9 = 54. That's The question for a differend universe.

Re:worms?

For the record, there was a game called "Worms?" for the C=64 and Atari by Electronic Arts in 1983. It was the game described in the article, where you would tell worms what to do when they encountered a "novel" situation in terms of their hex grid. Unfortnately I can't find a link.

Nothing to do with the "Worms" games that came out for PC and various consoles later.