https://www.human-competitive.org/call-for-entries
May 27, 2022 — Deadline for entries (consisting of one TEXT file, PDF files for one or more papers, and possible "in press" documentation (explained below). Please send entries to goodman at msu dot edu


The TEXT file must contain the following 11 items.


1. the complete title of one (or more) paper(s) published in the open literature describing the work that the author claims describes a human-competitive result;


From Requirements to Source Code: Evolution of Behavioral Programs




2. the name, complete physical mailing address, e-mail address, and phone number of EACH author of EACH paper(s);


Roy Poliansky, roypoli@post.bgu.ac.il, Department of Software and Information Systems Engineering, Ben-Gurion University, Beer-Sheva 8410501, Israel, +972-74-7795116


Moshe Sipper, sipper@bgu.ac.il, Department of Computer Science, Ben-Gurion University, Beer-Sheva 
8410501, Israel, +972-8-6477880


Achiya Elyasaf, achiya@bgu.ac.il, Department of Software and Information Systems Engineering, Ben-Gurion University, Beer-Sheva 8410501, Israel, +972-74-7795116




3. the name of the corresponding author (i.e., the author to whom notices will be sent concerning the competition);


Moshe Sipper




4. the abstract of the paper(s);


Automatically generating executable code has a long history of arguably modest success, mostly limited to the generation of small programs of up to 200 lines of code, and genetic improvement of existing code. We present the use of genetic programming (GP) in conjunction with context-oriented behavioral programming (COBP), the latter being a programming paradigm with unique characteristics that facilitate automatic coding. COBP models a program as a set of behavioral threads (b-threads), each aligned to a single behavior or requirement of the system. To evolve behavioral programs we design viable and effective genetic operators, a genetic representation, and evaluation methods. The simplicity of the COBP paradigm, its straightforward syntax, the ability to use verification and formal-method techniques to validate program correctness, and a program comprising small independent chunks all allow us to effectively generate behavioral programs using GP. To demonstrate our approach we evolve complete programs from scratch of a highly competent O player for the game of tic-tac-toe. The evolved programs are well structured, consisting of multiple, explainable modules that specify the different behavioral aspects of the program and are similar to our handcrafted program. To validate the correctness of our individuals, we utilize the mathematical characteristics of COBP to analyze program behavior under all possible execution paths. Our analysis of an evolved program proved that it plays as expected more than 99% of the times.






5. a list containing one or more of the eight letters (A, B, C, D, E, F, G, or H) that correspond to the criteria (see above) that the author claims that the work satisfies;


B, E, F, G


(B) The result is equal to or better than a result that was accepted as a new scientific result at the time when it was published in a peer-reviewed scientific journal.


(E) The result is equal to or better than the most recent human-created solution to a long-standing problem for which there has been a succession of increasingly better human-created solutions.


(F) The result is equal to or better than a result that was considered an achievement in its field at the time it was first discovered.


(G) The result solves a problem of indisputable difficulty in its field.




6. a statement stating why the result satisfies the criteria that the contestant claims (see examples of statements of human-competitiveness as a guide to aid in constructing this part of the submission);


Most work on code evolution focuses on genetic improvements of existing code or on code evolution of small modules, such as methods elaborated in Section 2 of our paper. We are aware of no attempt at generating *from scratch* a *complete program* for a non-trivial task, i.e., a program with several modules, each corresponding to a different aspect of the desired behavior. In this work, we evolve source code for high-quality tic-tac-toe players. While tic-tac-toe may seem simple, creating a complete program *from scratch* to play the game is highly complicated. 


We are the first to use Context-Oriented Behavioral Programming (COBP) in an evolutionary setting. COBP is a software development and modeling paradigm, designed to allow users to program reactive systems in a natural and intuitive manner that is aligned with how humans perceive the system requirements. COBP programs consist of multiple independent modules, each aligned with a single behavioral aspect of the system, e.g., a requirement or a strategy. At run-time, these components are interwoven into a cohesive behavior that is consistent with all components.


A COBP program has unique characteristics that makes it an excellent candidate for code evolution: 1) Repetitive structure, which allows for a simple representation of a program as an abstract syntax tree (AST); 2) small independent components that are easier to change and adjust, since in many cases breaking one component has little effect on the rest; and 3) synthesis, formal reasoning, and verification algorithms can be used to evaluate a generated program’s performance.


We have gone beyond genetic improvement (GI) into what might be called genetic generation (GG). The generated source code is modular, where each module is explainable and resembles human COBP programs for tic-tac-toe. 


To sum up, we have a new scientific result (B), it rivals human solutions (E), it is an achievement in the field of automated software generation (F), and we solve a difficult problem (G). 




7. a full citation of the paper (that is, author names; title, publication date; name of journal, conference, or book in which article appeared; name of editors, if applicable, of the journal or edited book; publisher name; publisher city; page numbers, if applicable);
Poliansky, R.; Sipper, M.; Elyasaf, A. From Requirements to Source Code: Evolution of Behavioral Programs. Appl. Sci. 2022, 12, 1587. 
Open-access link: https://doi.org/10.3390/app12031587 




8. a statement either that "any prize money, if any, is to be divided equally among the co-authors" OR a specific percentage breakdown as to how the prize money, if any, is to be divided among the co-authors;


Any prize money, if any, is to be divided equally among the co-authors.




9. a statement stating why the authors expect that their entry would be the "best," and


First, and foremost, we believe we are the first to demonstrate the evolution of programs from scratch, using a paradigm that has several additional advantages. This is perhaps an important step forward in the field of automated code generation.


Overall, it is apparent that testing is the most dominant evaluation parameter for fitness calculation in this field; however, with our algorithm, formal methods and verification techniques can also be used to evaluate the correctness of COBP programs, due to inherent mathematical properties.


Our evolved programs are well structured, consisting of multiple modules that are explainable and similar to our handcrafted program. Thus, another strength of our approach is the ability to understand the generated programs. Due to the simple and repetitive structure of the evolved behavioral programs, we were able to observe that evolved individuals ultimately exhibited similar behavior to a handcrafted program. This understandability is a clear advantage over previous methods.




10. An indication of the general type of genetic or evolutionary computation used, such as GA (genetic algorithms), GP (genetic programming), ES (evolution strategies), EP (evolutionary programming), LCS (learning classifier systems), GI (genetic improvement), GE (grammatical evolution), GEP (gene expression programming), DE (differential evolution), etc.


GP (genetic programming)




11. The date of publication of each paper.  If the date of publication is not on or before the deadline for submission, but instead, the paper has been unconditionally accepted for publication and is “in press” by the deadline for this competition, the entry must include a copy of the documentation establishing that the paper meets the "in press" requirement.


Published: 2 February 2022