# From Requirements to Source Code: Evolution of Behavioral Programs
## 4 Method
### Grammar  
We use grammar-based GP to evolve the program. The grammar is mostly domain-independent (except for the terminal set) and utilizes the repetitive nature of a behavioral program. The structure of a general behavioral program is illustrated in Figure 1. The program consists of contextual data, represented as a set of entities, queries on these entities, and context-dependent behaviors, each bound to a single query. For example, in Listing 2, there are two types of entities--cell and line. The queries are Cell.Any and Line.Any, and each of the context-dependent b-threads is bound to one of these queries. We recall that for generating strategy b-threads, additional queries and behaviors are required (Cell.Sides, Cell.Corners, etc.). In the following experiments we want evolution to find both the b-threads and all context queries, including Cell.Any and Line.Any. We note that a context query is essentially defined as a set of entities. For example, Cell.Any is a set of nine sets, each containing a single cell entity. Similarly, Line.Any is a set of eight sets (three rows, three columns, and two diagonals), each containing three cell entities in a line. Thus, the queries in our grammar are parameterized by the size of the internal sets. The grammar is presented in Listing 4; it is divided into two parts: a general grammar for any COBP programs, and specific terminals for tic-tac-toe. The general grammar can be generalized even more, e.g., by allowing multiple requests or by allowing _waitFor_ and _request_ in the same synchronization statement. Nevertheless, this grammar is general enough for our task and, from our experience with COBP, it is popular in programs as well. The specific grammar for tic-tac-toe is also general, in the sense that it only defines the entities and events that were defined by the rule b-threads. In addition, this part of the grammar configures the maximal possible priority and the maximal number of queries, behaviors per query, and entities. These values act as estimations that help evolution by placing boundaries on the size of the individuals. ```
1//AgeneralgramforCOBPprograms:
2 Bprogram\(\rightarrow\)Query\({}^{1\ldots\textit{MaxQueries}}\)
3



The player alternated between playing first and playing second in order to prevent evolution from succumbing to a bias, since the first player has an advantage because it has the opportunity to make more moves in a single game. Further, we alternated between players that do not lose and and random players because playing only against the first type of players did not allow the generated programs to learn how to win games. In addition, playing only against random players did not allow the generated programs to learn how to block the opponent from winning. Given these 100 games, the fitness function was

\[f=50\cdot\phi(\frac{wins}{missed\_wins+wins})+50\cdot\phi(\frac{blocks}{missed\_ blocks+blocks})-deadocks\]

\[\phi(x)=\frac{1-e^{-x}}{1-e^{-1}}\]

\(deadlocks=\) Number of times the individual did not request any action. \(wins/block=\) Number of wins/blocking opponent from winning. \(missed\_wins/missed\_blocks=\) Number of times that the individual missed an opportunity to win/block the opponent from winning. The first two parts take into account how decisively the generated program won when given the opportunity, and how decisively it blocked the enemy from winning when possible. Additionally, to complete the game (i.e., reach a tie or a win), the individual must request for at least one event that is not blocked, whenever it is the turn of the O player. To address this, we added a penalty part to the fitness that reduces one point for each non-completed game. Finally, to push evolution further, we used fitness pressure (denoted by \(\phi\)) for each of the two parts. Thus, the fitness values were in the range of \([-100,100]\). ### Genetic Operators

Our design of the genetic operators is based on two observations. First, generally speaking, b-threads may be correlated in several ways.