Tagged: Game theory Toggle Comment Threads | Keyboard Shortcuts

  • richardmitnick 9:38 am on December 28, 2020 Permalink | Reply
    Tags: "The Lasting Lessons of John Conway’s Game of Life", , Game theory, Mathematical exotica,   

    From The New York Times: “The Lasting Lessons of John Conway’s Game of Life” 

    From The New York Times

    Dec. 28, 2020
    Siobhan Roberts


    Fifty years on, the mathematician’s best known (and, to him, least favorite) creation confirms that “uncertainty is the only certainty.”

    In March of 1970, Martin Gardner opened a letter jammed with ideas for his Mathematical Games column in Scientific American. Sent by John Horton Conway, then a mathematician at the University of Cambridge, the letter ran 12 pages, typed hunt-and-peck style.

    Page 9 began with the heading “The game of life.” It described an elegant mathematical model of computation — a cellular automaton, a little machine, of sorts, with groups of cells that evolve from iteration to iteration, as a clock advances from one second to the next.

    Dr. Conway, who died in April, having spent the latter part of his career at Princeton, sometimes called Life a “no-player, never-ending game.” Mr. Gardner called it a “fantastic solitaire pastime.”

    The game was simple: Place any configuration of cells on a grid, then watch what transpires according to three rules that dictate how the system plays out.

    Birth rule: An empty, or “dead,” cell with precisely three “live” neighbors (full cells) becomes live.

    Death rule: A live cell with zero or one neighbors dies of isolation; a live cell with four or more neighbors dies of overcrowding.

    Survival rule: A live cell with two or three neighbors remains alive.

    With each iteration, some cells live, some die and “Life-forms” evolve, one generation to the next.

    Among the first creatures to emerge was the glider — a five-celled organism that moved across the grid with a diagonal wiggle and proved handy for transmitting information. It was discovered by a member of Dr. Conway’s research team, Richard Guy, in Cambridge, England. The glider gun, producing a steady stream of gliders, was discovered soon after by Bill Gosper, then at the Massachusetts Institute of Technology.

    John Horton Conway, investigating “Life” in 1974. Credit: Kelvin Brodie/The Sun News Syndication.

    “Because of its analogies with the rise, fall and alterations of a society of living organisms, it belongs to a growing class of what are called ‘simulation games,’” Mr. Gardner wrote when he introduced Life to the world 50 years ago with his October 1970 column.

    Life swiftly eclipsed Dr. Conway’s many other mathematical accomplishments, and he came to regard his missive to Mr. Gardner as “the fatal letter.”

    The Game of Life motivated the use of cellular automata in the rich field of complexity science, with simulations modeling everything from ants to traffic, clouds to galaxies. More trivially, the game attracted a cult of “Lifenthusiasts,” programmers who spent a lot of time hacking Life — that is, constructing patterns in hopes of spotting new Life-forms.

    To mark the 50th anniversary, the ConwayLife.com community — which hosts the LifeWiki, with more than 2,000 articles — created an Exploratorium, a large, explorable stamp-collection pattern.

    Patterns that didn’t change one generation to the next, Dr. Conway called still lifes — such as the four-celled block, the six-celled beehive or the eight-celled pond. Patterns that took a long time to stabilize, he called methuselahs.

    The tree of Life also includes oscillators, such as the blinker, and spaceships of various sizes (the glider being the smallest).

    In 2018, there was a much-celebrated discovery of a special kind of spaceship, the first elementary knightship, named Sir Robin. Made of hundreds of cells, it moves two cells forward and one sideways every six generations. It was discovered by Adam P. Goucher, a British algorithmist, building on an earlier partial find by Tomas Rokicki, a developer of Golly, a program for exploring the distant future of large Life patterns.

    And the hunting party continues. In September, Pavel Grankovskiy, of Russia, discovered the Speed Demonoid spaceship. In December, John Winston Garth, of Alabama, discovered the Doo-dah spaceship. Both are contenders for pattern of the year, in what has been a good year for new Life discoveries.

    Life ultimately became way too popular for Dr. Conway’s liking. Whenever the subject came up, he would bellow, “I hate Life!” But in his final years he learned to love Life again. He narrated a documentary, with the working title “Thoughts on Life,” by the Brooklyn-based mathematician and filmmaker Will Cavendish, exploring the deterministic Game of Life versus the Free Will Theorem, a result Dr. Conway proved with his Princeton colleague Simon Kochen.

    “I used to go around saying, ‘I hate Life,’” Dr. Conway says in the film. “But then I was giving a lecture somewhere, and I was introduced as ‘John Conway, Creator of Life.’ And I thought, ‘Oh, that’s quite a nice way to be known.’ So I stopped saying ‘I hate Life’ after that.”

    Recently, some of Life’s most steadfast friends reflected upon its influence and lessons over half a century.

    Credit: The Martin Gardner Literary Interests/Special Collections, Stanford University Libraries.

    Bill Gosper

    — Mathematician and programmer, Stanford, Calif.

    Life is the world’s most wholesome computer game! True, it used to be dangerously addicting to some of us, but not so much now that nearly all of the theoretically possible gun and oscillator periods have been found. It took 40 years to find the coveted Snark, a stable pattern that reflects gliders 90 degrees.

    But there are still open questions: for example, what spaceship vector velocities are possible, or what constructions are possible with glider collisions. A startling recent theorem states that any construction, no matter how large, can be accomplished with a reverse caber-tosser built from a certain fixed number of gliders — that number was 32, but as of September it is now down to 17.

    These days it has become harder and harder for an amateur to find a newsworthy pattern without fancy software and hardware. Perhaps Life can remain a gateway drug, luring newcomers into the effectively inexhaustible universe of different Lifelike rules.

    Brian Eno

    — Musician, London

    I first encountered Life at the Exploratorium in San Francisco in 1978. I was hooked immediately by the thing that has always hooked me — watching complexity arise out of simplicity.

    Life ought to be very predictable and boring; after all, there are just three simple rules that determine the position of some dots on a grid. That really doesn’t sound very interesting until you start tweaking those rules and watching what changes.

    Life shows you two things. The first is sensitivity to initial conditions. A tiny change in the rules can produce a huge difference in the output, ranging from complete destruction (no dots) through stasis (a frozen pattern) to patterns that keep changing as they unfold.

    The second thing Life shows us is something that Darwin hit upon when he was looking at Life, the organic version. Complexity arises from simplicity! That is such a revelation; we are used to the idea that anything complex must arise out of something more complex. Human brains design airplanes, not the other way around. Life shows us complex virtual “organisms” arising out of the interaction of a few simple rules — so goodbye “Intelligent Design.”

    Melanie Mitchell

    — Professor of complexity, Santa Fe Institute

    Given that Conway’s proof that the Game of Life can be made to simulate a Universal Computer — that is, it could be “programmed” to carry out any computation that a traditional computer can do — the extremely simple rules can give rise to the most complex and most unpredictable behavior possible. This means that there are certain properties of the Game of Life that can never be predicted, even in principle!

    In this moment in time, it’s important to emphasize that inherent unpredictability — so well illustrated in even the simple Game of Life — is a feature of life in the real world as well as in the Game of Life. We have to figure out ways to flourish in spite of the inherent unpredictability and uncertainty we constantly live with. As the mathematician John Allen Paulos so eloquently said, “Uncertainty is the only certainty there is, and knowing how to live with insecurity is the only security.” This is, I think, Life’s most important lesson.

    Credit: The Martin Gardner Literary Interests/Special Collections, Stanford University Libraries.

    Daniel Dennett

    — Professor of philosophy, Tufts University

    I use the Game of Life to make vivid for my students the ideas of determinism, higher-order patterns and information. One of its great features is that nothing is hidden; there are no black boxes in Life, so you know from the outset that anything that you can get to happen in the Life world is completely unmysterious and explicable in terms of a very large number of simple steps by small items. No psionic fields, no morphic resonances, no élan vital, no dualism. It’s all right there. And the fact that it can still support complex adaptively appropriate structures that do things is also important.

    In Thomas Pynchon’s novel “Gravity’s Rainbow,” a character says, “But you had taken on a greater and more harmful illusion. The illusion of control. That A could do B. But that was false. Completely. No one can do. Things only happen.”

    This is compelling but wrong, and Life is a great way of showing this.

    In Life, we might say, things only happen at the pixel level; nothing controls anything, nothing does anything. But that doesn’t mean that there is no such thing as action, as control; it means that these are higher-level phenomena composed (entirely, with no magic) from things that only happen.

    Credit: Kjetil Golid.

    Credit: Kjetil Golid.

    Susan Stepney

    — Professor of computer science, University of York, England

    In the Artificial Life community, Life is a foundational piece of work. It sits in the background, influencing the way people think of life “in silico.”

    Life probably maintains its interest for two reasons. One is that the whole field of cellular automata is very important, because computationally it can be used to model so many different things — for example, physical systems from fluid dynamics to coupled magnetic spins to chemical reaction-diffusion systems.

    The other reason is that it’s just cool and pretty and great to look at. When you speed it up, it flows and boils and bubbles; it actually comes to look alive.

    I did some work with students looking at Life on a Penrose tiling grid, rather than the square grid. I wanted to know whether it was the rules or the grid that was the important thing. We found some interesting oscillating patterns and snakelike patterns. Basically, what we showed is that there is something in those rules; the rules are producing the interesting dynamics. Penrose Life still generates interesting behaviors, even in a different environment.

    A Penrose Life oscillator known as “The Bat.” Credit: Animation by Susan Stepney.

    Stephen Wolfram

    — Scientist and C.E.O., Wolfram Research

    I’ve wondered for decades what one could learn from all that Life hacking. I recently realized it’s a great place to try to develop “meta-engineering” — to see if there are general principles that govern the advance of engineering and help us predict the overall future trajectory of technology. One can look at microprocessors or airplanes, but they involve all sorts of details of physics and materials. In Life there’s 50 years of “engineering development,” just applied to configurations of bits. It’s the purest example I know of the dynamics of collective human innovation.

    Bert Chan

    — Artificial-life researcher and creator of the continuous cellular automaton “Lenia,” Hong Kong

    Although the Game of Life is not the proudest invention of Conway, according to himself, it did have a big impact on beginner programmers, like me in the 90s, giving them a sense of wonder and a kind of confidence that some easy-to-code math models can produce complex and beautiful results. It’s like a starter kit for future software engineers and hackers, together with Mandelbrot Set, Lorenz Attractor, et cetera.

    Life enthusiasts have discovered or engineered many wonderful patterns inside Life. Some of the most amazing ones are a digital clock, a simulation of Life inside Life, and self-replicators. The engineering is so ingenious and delicate that a single mistake of misplacing one cell among perhaps a million cells will make the whole machine fail. On the other hand, when I was investigating Lenia — a continuous extension of Life — I found that its patterns are fundamentally different from those in Life. Lenia patterns are fuzzy, thus not easy for engineering (they are mostly evolved instead), but are harder to destroy. Although having the same root, Life and Lenia have nearly opposite nature: designed versus organic, precise versus adaptive, fragile versus resilient.

    These are interesting findings in research, but if we think about our everyday life, about corporations and governments, the cultural and technical infrastructures humans built for thousands of years, they are not unlike the incredible machines that are engineered in Life. In normal times, they are stable and we can keep building stuff one component upon another, but in harder times like this pandemic or a new Cold War, we need something that is more resilient and can prepare for the unpreparable. That would need changes in our “rules of life,” which we take for granted.

    Credit: Bert Chan.

    Rudy Rucker

    — Mathematician and author of Ware Tetralogy, Los Gatos, Calif.

    When Life started out, we didn’t yet have the notion of mathematical chaos. The unfolding of the successive generations of a Game of Life board is completely deterministic. If you start with the same setup, you always get the same outcomes. The odd thing is that, even though the results of a given game of Life start-position are predetermined, there is no easy shortcut to predict these outcomes. You just have to run the damn thing through all its steps.

    That’s what chaos is about. The Game of Life, or a kinky dynamical system like a pair of pendulums, or a candle flame, or an ocean wave, or the growth of a plant — they aren’t readily predictable. But they are not random. They do obey laws, and there are certain kinds of patterns — chaotic attractors — that they tend to produce. But again, unpredictable is not random. An important and subtle distinction which changed my whole view of the world.

    William Poundstone

    — Author of The Recursive Universe: Cosmic Complexity and the Limits of Scientific Knowledge, Los Angeles, Calif.

    The Game of Life’s pulsing, pyrotechnic constellations are classic examples of emergent phenomena, introduced decades before that adjective became a buzzword.

    Fifty years later, the misfortunes of 2020 are the stuff of memes. The biggest challenges facing us today are emergent: viruses leaping from species to species; the abrupt onset of wildfires and tropical storms as a consequence of a small rise in temperature; economies in which billions of free transactions lead to staggering concentrations of wealth; an internet that becomes more fraught with hazard each year. Looming behind it all is our collective vision of an artificial intelligence-fueled future that is certain to come with surprises, not all of them pleasant.

    The name Conway chose — the Game of Life — frames his invention as a metaphor. But I’m not sure that even he anticipated how relevant Life would become, and that in 50 years we’d all be playing an emergent game of life and death.

    Dr. Conway in his Princeton office in 1993.Credit: Dith Pran/The New York Times.

    See the full article here .


    Please help promote STEM in your local schools.

    Stem Education Coalition

  • richardmitnick 11:24 am on December 7, 2020 Permalink | Reply
    Tags: "Saurabh Amin- Striving to make our infrastructure safer", , , Control theory; machine learning and robotics., Game theory, Infrastructure, Mathematical systems theory,   

    From MIT News: “Saurabh Amin- Striving to make our infrastructure safer” 

    MIT News

    From MIT News

    Systems engineer and MIT professor Saurabh Amin focuses on making transportation, electricity, and water infrastructure more resilient against disruptions. Credit: Gretchen Ertl.

    Early on in his studies, starting in India and then in the U.S., Saurabh Amin became fascinated by bringing principles from mathematical systems theory to bear on the real-world systems that we all rely on — in particular, transportation, electricity, and water infrastructure — and how to make them more resilient.

    As the types of disruptions facing these systems, from natural disasters to security attacks, become more frequent and diverse, a proactive approach to monitoring and controlling these systems becomes all the more important.

    Amin started to work on infrastructure systems as an undergraduate at the Indian Institute of Technology at Roorkee, India’s oldest technology institute. Citing other alumni who came before him and contributed to important civil engineering projects around the world, he says, “I was fortunate to study there. I think our curriculum actually had a very good balance” between real-world engineering applications and theoretical understanding of core concepts.

    Inspired by this balance of theory and applications, Amin decided to study transportation systems at the University of Texas at Austin for his masters. He then earned his PhD in systems engineering at the University of California at Berkeley, where he delved into control theory, machine learning, and robotics — areas that have all come together in his more recent research. He now applies these tools to his analyses of different failure mechanisms and pathways, including how to guard infrastructure systems against problems caused by aging, natural disasters, or deliberate malicious action.

    “There are a lot of commonalities among these networks — they are built and operated by human actors, but their functionality is governed by physical laws. So, that is what drives me forward,” Amin says.

    He seeks “to develop a rigorous theoretical foundation of the resilience of infrastructures, to come at it from different angles, and to understand which kind of network failures are difficult or easy to analyze, or to defend against.”

    Amin received an offer for an assistant professor position at MIT while he was still finishing his doctoral work at Berkeley. He had met his wife, Richa Sharma, under MIT’s Great Dome during an earlier research visit at the Institute, where she was completing a doctorate in chemical engineering. But just as he was about to move to Cambridge, she received a postdoc position at Lawrence Berkeley Laboratory.

    “So we exchanged zip codes for a couple of years, before she moved back here again,” he says. Sharma now works at Schlumberger Doll Research on developing new sensor technologies with a specific focus on carbon dioxide. Both share a strong interest of using technology to develop more sustainable solutions. They now have two children, a girl and a boy, ages 6 and 3.

    Amin joined the MIT faculty in 2012. “Coming to MIT from Berkeley, they are somewhat different cultures, but very similar academic environments for cross-disciplinary research,” he says. In 2019, Amin earned tenure in the Department of Civil and Environmental Engineering, where he teaches classes including 1.208 (Resilient Networks) and 1.020 (Engineering Sustainability: Analysis and Design). Recently, he launched a new first-year discovery subject, 1.008 (Engineering Solutions to Societal Challenges).

    His research at MIT has continued to apply principles of systems theory, including game theory and optimization, to determine the best ways to maintain resiliency in systems. “The angle which I have pursued is of applied theory, applied in the sense that I draw my hypotheses and models, which are in these areas of transportation, electricity, and water,” Amin says. “Then I consider various kinds of failure situations, from attacks to failures resulting from natural events or disasters.”

    In 2020, Amin started to pursue two new collaborative projects: one on pandemic-resilient urban mobility and another on hurricane-resilient smart grid operations.

    To assess such correlated disruption scenarios, he finds ways to abstract these problems into mathematical representations, using methods developed in systems and control theory, optimization, and game theory. That then allows him to use tools developed by these disciplines to develop new ways to understand the potential failure mechanisms in infrastructure systems and propose solutions to plan for and respond to them.

    Part of the analysis involves studying the best ways of allocating limited resources when restoring vital water, power, and transportation systems, for example after a hurricane or earthquake has caused multiple simultaneous failures over a wide area. Key questions include: Where are the key points where sensor systems should be installed, and which shutoffs and switches can best provide system resilience under different scenarios? What type of response capabilities are needed to restore the system functionality as quickly as possible?

    Using game theory in this work, he says, “to me is a nice interplay between the way in which the humans, as operators of infrastructures and users of infrastructures, or even as the attackers to these infrastructures, would behave and interact with this network. And how, on the other hand, the sensing and control systems, which is a more of an automated part, not the human part, can be implemented to make it more robust.”

    This approach of marrying control theory and optimization and game theory principles with traditional civil engineering systems is what brought Amin to his current position. “The reason why I got the job at MIT, I think, was because of this new approach to cyber-enabled infrastructure resilience that I wanted to develop,” he says.

    In integrating these disciplines, “I need to be rigorous in terms of the mathematical proofs that these disciplines provide, and in terms of the performance guarantees that we must provide even under the face of disruptions. Importantly, these guarantees also need to be translated back to something implementable, which is of direct value to the operators or the managers of infrastructures and the large number of users who rely on the services offered by them.”

    “Being able to make small steps to address this challenge, by way of teaching and research, is what excites me about my job the most,” he says.

    See the full article here .

    Please help promote STEM in your local schools.

    Stem Education Coalition

    MIT Seal

    The mission of MIT is to advance knowledge and educate students in science, technology, and other areas of scholarship that will best serve the nation and the world in the twenty-first century. We seek to develop in each member of the MIT community the ability and passion to work wisely, creatively, and effectively for the betterment of humankind.

    USPS “Forever” postage stamps celebrating Innovation at MIT.

    MIT Campus

Compose new post
Next post/Next comment
Previous post/Previous comment
Show/Hide comments
Go to top
Go to login
Show/Hide help
shift + esc
%d bloggers like this: