1. "Evolving QWOP Gaits" 2. V. Scott Gordon 5340 Shelato way, Carmichael, CA 95608, USA gordonvs@ecs.csus.edu 916-978-0117 Steven Ray 4900 12th ave, Sacramento, CA 95820 stevenlray@gmail.com 512-845-9374 Laurent Vaucher 1, allee Erik Satie, 95520 Osny, France laurentvaucher@gmail.com (+33)964127219 3. V. Scott Gordon 4. QWOP is a popular Flash game in which a human player controls a sprinter in a simulated 100-meter dash. The game is notoriously difficult owing to its ragdoll physics engine, and the simultaneous movements that must be carefully coordinated to achieve forward progress. While previous researchers have evolved gaits using simulations similar to QWOP, we describe a software interface that connects directly to QWOP itself, incorporating a genetic algorithm to evolve actual QWOP gaits. Since QWOP has no API, ours detects graphical screen elements and uses them to build a fitness function. Two variable-length encoding schemes, that codify sequences of QWOP control commands that loop to form gaits, are tested. We then compare the performance of SGA, Genitor, and a Cellular Genetic Algorithm on this task. Using only the end score as the basis for fitness, the cellular algorithm is consistently able to evolve a successful scooting strategy similar to one most humans employ. The results confirm that steady-state GAs are preferred when the task is sensitive to small input variations. Although the limited feedback does not yet produce performance competitive with QWOP champions, it is the first autonomous software evolution of successful QWOP gaits. 5. G,H 6. QWOP is an extraordinarily difficult online game for humans, and most humans are unable (or barely able) to complete a QWOP race. Our system not only was able to evolve a gait that completes a QWOP race every time, it does so using considerably less sensory feedback than a human. Humans are able to adjust their gait based on visually assessing the configuration of the runner. By contrast, our system utilizes only the final score, without any real-time feedback of the runner's orientation. This is equivalent to what a blind human would need to accomplish. Although our system does not yet run as fast as the QWOP world champion ("sighted") humans, we have been unable to find any evidence of a successful completion of QWOP by a blind human. Therefore, we propose that our "blind" system not only defeats blind humans, it also challenges and does better than most sighted humans. We reference item G because completing an actual online QWOP race is indisputably difficult, and we are the first to solve it using a computer. We reference item H because QWOP is a widely-played online game intended solely for humans and for which sanctioned competition occurs. 7. S. Ray, V. Gordon, and L. Vaucher. "Evolving QWOP Gaits", to be presented at the 2014 Genetic and Evolutionary Computation Conference (GECCO-2014), Vancouver, BC Canada There is also an online video showing the evolution of our successful blind QWOP gait at: http://www.youtube.com/watch?v=eWxFI3NHtT8 We received permission from Bennett Foddy, the creator of QWOP, to publish the QWOP screenshots in our paper, and to post the video of our evolved QWOP gait on YouTube. 8. Any prize money, if any, is to be divided equally among the co-authors. 9. Naturally, I am hesitant to compare our work against other works that I haven't yet seen. However, I have perused many of the previous years' winners, and note that an "honorable mention" Humie was awarded in 2005 to a system that also evolves gaits (Hornby, et al). What sets our study apart from that one, is that our application is situated firmly within the domain of a human competition, and that our system interacts and competes directly in the online human game without any accomodation whatsoever for its being a machine. The actual online QWOP website has no way of discerning that our system is a machine when it plays. Thus, our system is more purely and obviously "human competitive" than perhaps many submissions. Furthermore, since all learning took place within the online QWOP game itself (fitness was determined through actual competition), the system learns via the same process that a human would need to learn - through actual practice in the QWOP online game itself. Evolution took approximately 20 hours of actual game play. 10. We used a Cellular Genetic Algorithm.