Evolutionary algorithm outperforms deep-learning machines at video games

Neural networks have garnered all the headlines, but a much more powerful approach is waiting in the wings.

by Emerging Technology from the arXiv


With all the excitement over neural networks and deep-learning techniques, it’s easy to imagine that the world of computer science consists of little else. Neural networks, after all, have begun to outperform humans in tasks such as object and face recognition and in games such as chess, Go, and various arcade video games.

These networks are based on the way the human brain works. Nothing could have more potential than that, right?

Not quite. An entirely different type of computing has the potential to be significantly more powerful than neural networks and deep learning. This technique is based on the process that created the human brain—evolution. In other words, a sequence of iterative change and selection that produced the most complex and capable machines known to humankind—the eye, the wing, the brain, and so on. The power of evolution is a wonder to behold.

Which is why computer scientists have long attempted to harness its capabilities. So-called evolutionary computing has achieved some remarkable feats in the 30 years since it was first put to use optimizing factory production lines for tractors.

But in the last few years, this area of computer science has had to play second fiddle to deep-learning machines and their huge success.

Today, the tables look set to turn thanks to the work of Dennis Wilson and a few colleagues at the University of Toulouse in France. These guys have shown how evolutionary computing can match the performance of deep-learning machines at the emblematic task that first powered them to fame in 2013—the ability to outperform humans at arcade video games such as Pong, Breakout, and Space Invaders. The work suggests that evolutionary computing should be feted just as widely as its deep-learning-based relations.

Evolutionary computing works in an entirely different way than neural networks. The goal is to create computer code that solves a specific problem using an approach that is somewhat counterintuitive.

The conventional way to create code is to write it from first principles with a specific goal in mind.

Evolutionary computing uses a different approach. It starts with code generated entirely at random. And not just one version of it, but lots of versions, sometimes hundreds of thousands of randomly assembled pieces of code.

Each of these codes is tested to see whether it achieves the required goal. And of course, all the code is awful because it is randomly generated.

But just by chance, some pieces of code are a little better than others. These pieces are then reproduced in a new generation of code, which includes more copies of the better codes.

However, the next generation cannot be an identical copy of the first. Instead, it must change in some way. These changes can involve switching two terms in the code—a kind of point mutation. Or they can involve two codes that are cut in half and the halves exchanged—like sexual recombination.

Each of the new generation is then tested to see how well it works. The best pieces of code are preferentially reproduced in another generation, and so on.

In this way, the code evolves. Over time, it becomes better, and after many generations, if conditions are right, it can become better than any human coder can design.

Computer scientists have successfully applied evolutionary approaches to problems ranging from designing robots to building aircraft parts.

But it has fallen out of favor because of the huge interest in deep learning. So an important question is whether it can match the performance of deep-learning machines. To find out, Wilson and co used the approach to develop code that could control arcade computer games dating from the 1980s and 1990s.

These games are available in a database called the Arcade Learning Environment, which is increasingly being used to test the learning behavior of algorithms of various kinds. The database consists of 61 Atari games, such as Pong, Space Invaders, Breakout, and Kung Fu Master.

The task is to create an algorithm that can play a game like Pong by looking only at the output from the screen, the same way that humans play. So the algorithm must analyze each game position and then decide how to move to maximize its score.

The controls for all games are the same. These correspond to the eight directions the controller can be moved (up, down, left, and right plus four diagonal directions), a button press, the same eight movements combined with a button press, and doing nothing at all. Not all games use all 18 possible combinations, and some use as few as four.

The code first has to be created. The evolutionary approach requires a vocabulary of terms that can be concatenated to form computer code. The terms range from simple actions such as ADD (x+y)/2 to more complex ones, such as “return the 1-element x-vector if x is a scalar.”

The choice of terms that make up this vocabulary is important, and Wilson and co use a set already defined for Cartesian genetic programming (as their technique is called).

The process begins by randomly creating a code containing 40 terms. This is the “genome” of the program. This genome is then tested to see how well it plays the game, as judged by the score. Depending on how well it performs, the genome is then reproduced with mutations and tested again, and so on. In total, the team tested 10,000 genomes in this way.

The results make for interesting reading. At first, the genomes are terrible at playing the game. But over time, they get better. And after many generations, they play well, sometimes better than humans.

Many genomes ended up playing entirely new gaming strategies, often complex ones. But they sometimes found simple ones that humans had overlooked.

For example, when playing Kung Fu Master, the evolutionary algorithm discovered that the most valuable attack was a crouch-punch. Crouching is safer because it dodges half the bullets aimed at the player and also attacks anything nearby. The algorithm’s strategy was to repeatedly use this maneuver with no other actions. In hindsight, using the crouch-punch exclusively makes sense.

That surprised the human players involved in the study. “Employing this strategy by hand achieved a better score than playing the game normally, and the author now uses crouching punches exclusively when attacking in this game,” say Wilson and co.

Overall, the evolved code played many of the games well, even outperforming humans in games such as Kung Fu Master. Just as significantly, the evolved code is just as good as many deep-learning approaches and outperforms them in games like Asteroids, Defender, and Kung Fu Master.

It also produces a result more quickly. “While the programs are relatively small, many controllers are competitive with state-of-the-art methods for the Atari benchmark set and require less training time,” say Wilson and co.

The evolved code has another advantage. Because it is small, it is easy to see how it works. By contrast, a well-known problem with deep-learning techniques is that it is sometimes impossible to know why they have made particular decisions, and this can have practical and legal ramifications.

Overall, this is interesting work that should suggest to computer scientists who are focusing exclusively on deep learning that they may be missing a trick. The evolutionary approach is a powerful alternative that can be applied in a wide set of situations.

Indeed, some researchers have begun to use it to evolve better deep-learning machines. What could possibly go wrong?


Ref: https://arxiv.org/abs/1806.05695: Evolving Simple Programs for Playing Atari Games.

 

30 Comments

  • My spouse and i have been very joyful Louis could deal with his investigations through the entire ideas he grabbed out of the web site. It’s not at all simplistic to simply find yourself giving freely thoughts others might have been selling. We see we now have the website owner to thank because of that. The specific illustrations you have made, the simple website navigation, the friendships you will assist to engender – it is many incredible, and it’s helping our son and the family reason why that article is brilliant, and that’s pretty essential. Thank you for everything!

  • I happen to be commenting to make you understand of the brilliant encounter my princess gained using the blog. She figured out several pieces, which included what it is like to possess an excellent teaching character to make men and women clearly understand specified extremely tough issues. You really did more than our own expected results. Many thanks for offering those valuable, healthy, educational and in addition easy guidance on that topic to Emily.

  • nmd says:

    Thank you for your whole work on this blog. Betty loves engaging in internet research and it’s easy to understand why. We all hear all about the lively form you produce simple guides by means of the blog and increase participation from other individuals on this idea then our favorite girl is really starting to learn a lot of things. Take pleasure in the remaining portion of the new year. You’re carrying out a glorious job.

  • adidas nmd says:

    I am just commenting to let you know of the fantastic encounter my friend’s girl found reading your web page. She picked up too many things, including what it is like to have a very effective coaching style to have many others smoothly thoroughly grasp various impossible topics. You actually did more than her desires. Thank you for presenting these great, dependable, explanatory and in addition unique thoughts on this topic to Gloria.

  • I precisely had to thank you very much once more. I do not know what I would have worked on in the absence of the actual pointers shown by you relating to that field. It seemed to be a very intimidating case in my opinion, nevertheless finding out a professional form you managed it forced me to weep over delight. Extremely thankful for this assistance and in addition have high hopes you are aware of a powerful job you are getting into teaching the rest by way of your web page. I know that you haven’t encountered any of us.

  • Very interesting details you have mentioned, appreciate it
    for posting.

  • Hello there, You’ve performed a fantastic job.

    I’ll definitely digg it and personally suggest to
    my friends. I am sure they’ll be benefited from this
    site.

  • Hi everyone, it’s my first pay a visit at this site,
    and post is really fruitful designed for me, keep up posting such content.

  • An interesting discussion is definitely worth
    comment. I do think that you ought to write more on this topic, it may not be a
    taboo matter but usually people do not discuss such issues.
    To the next! Best wishes!!

  • Wonderful goods from you, man. I have understand your stuff previous to and you are just extremely wonderful.
    I actually like what you have acquired here, certainly like what you’re stating and the way in which you
    say it. You make it entertaining and you still care
    for to keep it wise. I can not wait to read much more from you.
    This is actually a wonderful web site.

  • Wow! After all I got a website from where I
    can really obtain valuable data concerning my study and
    knowledge.

  • Bill says:

    I will right away grasp your rss as I can’t to find your email
    subscription link or e-newsletter service. Do you have any?
    Kindly allow me know so that I could subscribe.
    Thanks. I couldn’t refrain from commenting. Perfectly written! Its like
    you learn my mind! You seem to understand so much
    about this, like you wrote the book in it or
    something. I think that you simply can do with some percent to power the message house a
    bit, but other than that, that is excellent blog.
    A fantastic read. I will definitely be back.

    http://foxnews.org

  • Anonymous says:

    This article offers clear idea in favor of the new people of blogging, that genuinely how to do blogging.

  • Anonymous says:

    Hi there, of course this article is truly fastidious and I have learned lot of things from it about blogging.
    thanks.

  • Some times its a pain in the ass to read what website owners wrote
    but this internet site is very user pleasant!

  • After exploring a few of the blog articles on your web page, I honestly appreciate
    your way of blogging. I book marked it to my bookmark website list and will be checking back in the near future.

    Please visit my website as well and tell me how you feel.

  • Нello eveгy one, here еvery one is sharing ѕuch knowledge, so it’s pleasant to read this blog, and I used to pay a visit this blog every day.

  • Anonymous says:

    I have not checked in here for a while since I thought it was
    getting boring, but the last few posts are good quality so I guess I will add you back to my daily bloglist.

    You deserve it friend 🙂

  • Loving the information on this web site, you
    have done great job on the articles.

  • This is the right website for anybody who wants to find
    out about this topic. You realize so much its almost hard to
    argue with you (not that I personally would want to?HaHa).
    You certainly put a fresh spin on a topic which has been written about for ages.
    Great stuff, just excellent!

  • Aw, this was an exceptionally nice post. Taking a few minutes and actual effort to generate a good article…
    but what can I say… I put things off a whole lot and don’t seem to get nearly anything done.

  • This web site really has all the info I wanted concerning this subject and didn’t know who to ask.

  • Hello.This article was extremely interesting, especially because I was browsing for thoughts on this
    topic last week.

  • Italian says:

    Ӏ ɡo to ѕee every dday some blogs ɑnd sites to read articles, һowever tһis blog offers quality based
    cοntent.

  • Some truly nice and utilitarian information on this
    web site, likewise I think the style has got great features.

  • Thank you for your whole labor on this web page.
    Kim delights in managing research and it’s easy
    to understand why. A number of us know all regarding the
    lively manner you make both interesting and useful strategies via the web blog and as well strongly encourage
    contribution from some other people about this concept while our favorite daughter
    is without a doubt understanding a whole lot. Take pleasure in the rest
    of the new year. Your carrying out a pretty cool job.[X-N-E-W-L-I-N-S-P-I-N-X]I am
    really impressed along with your writing talents as well
    as with the format in your blog. Is this a paid subject matter or did
    you customize it your self? Anyway keep up the excellent high quality writing, it is uncommon to see a great
    weblog like this one nowadays.

  • sell bitcoin says:

    Ηello to all, һow іs eveгything, I tһink evеry οne iѕ getting more freom tһis website,
    and your views ɑre fastidious іn favor oof
    new people.

  • Hi there, just became alert to your blog through Google,
    and found that it is truly informative. I am going to watch out for brussels.

    I will be grateful if you continue this in future.
    Lots of people will be benefited from your writing.
    Cheers!

  • Howdy, i read your blog occasionally and i own a similar one and i was just curious
    if you get a lot of spam feedback? If so how do you reduce it, any plugin or anything you can advise?
    I get so much lately it’s driving me crazy so any assistance
    is very much appreciated.

  • Heya і’m forr thhe first timе here. I found this board and Ι fіnd It reaⅼly uѕeful & іt
    helped me оut mucһ. I hope to give sometһing bаck and
    һelp оthers lіke yօu aided me.

Leave a Reply

Your email address will not be published. Required fields are marked *