In the comments the author of the article refers to a paper[1] that describes the system (Ludi) that they're using. They came up with 57 aesthetics criteria which they used on games played by humans and compared the scores on the criteria to the human judgements.
Based on this they picked the 16 best criteria and generated games. The fitness function is a score based on the criteria after n amount of automated playthroughs.
These generated games tested by humans and they found that the aesthetics criteria and human judgements correlated significantly.
Besides these criteria (they do not describe all criteria in depth but I assume some might be leaning towards being subjective in regards to the programmers preferences) they also add a restriction to how long the planning of a move for a game can take (15 seconds) and discarding the game if it surpasses this. Which as you say can be seen as designing the search space, but the results indicate that they've come up with a way to effectively measure the "fun" factor of the games they came up with.
Based on this they picked the 16 best criteria and generated games. The fitness function is a score based on the criteria after n amount of automated playthroughs. These generated games tested by humans and they found that the aesthetics criteria and human judgements correlated significantly.
Besides these criteria (they do not describe all criteria in depth but I assume some might be leaning towards being subjective in regards to the programmers preferences) they also add a restriction to how long the planning of a move for a game can take (15 seconds) and discarding the game if it surpasses this. Which as you say can be seen as designing the search space, but the results indicate that they've come up with a way to effectively measure the "fun" factor of the games they came up with.
[1] http://www.cameronius.com/cv/publications/ciaig-browne-maire...