A command-line game about evolution and information retrieval.
In this game, you play a god who controls the environment of a strange world where the only species is boolean queries.
Their evolutionary fitness depends on their match with a specific random sentence from a corpus of unique sentences (the "language" of this world).
The goal is to evolve a population of boolean queries that match this sentence well before the rounds are over.
You do not know the sentence.
You also cannot manipulate the queries directly, only indirectly via selection pressure, mediated by specific evolutionary actions.
If your population of queries dies out, you lose.
After the installation procedure, the following requirements should be satisfied:
- Elasticsearch 7.10.1-1
- Python 3.9.6
- elasticsearch (pip) 7.14.0
Enter the project directory.
Install Python dependencies:
make setup
Install Elasticsearch, and enable and start the server, per instructions on their website for your OS.
It should look something like this:
$ sudo systemctl enable elasticsearch.service
$ sudo systemctl start elasticsearch.service
Without any custom configuration, this initializes an index server on http://localhost:9200 by default. This game assumes the default configuration per default.
Check all options:
./evolve-a-query.py -h
If you have swi-prolog installed, you can rebuild the language file via:
make language.txt
Run:
./evolve-a-query.py language.txt
... to run the game on the provided language file. It contains variations of Noam Chomsky's famous nonsensical sentence "colorless green ideas sleep furiously", generated by a PROLOG Definite Clause Grammar. All sentences in this file follow the same syntactic structure and make more or less sense, literally.
You can also use your own language file. Just remember: one sentence per line.
Elasticsearch is used as the indexing engine. It also computes the score, or fitness, of each query against the secret target sentence.
The game starts with one single query, initialized with a single random positive term. From this seed query, you must evolve a healthy population of queries that match the secret target sentence well.
This is what a query looks like:
1. 0.123456 [+ideas +furiously -colorful -wake]
The first column (1.) indicates its rank among all queries in the population.
The second column (0.123456) indicates its current matching score against the target sentence.
"+"-prefixes indicate positive terms. They must be in the target sentence for the whole query to match.
"-"-prefixes indicate negative terms. They must not be in the target sentence for the whole query to match.
In each round, you can inspect:
- the vocabulary,
- the current population of queries,
- their scores against the secret target sentence,
- and the average score across the population.
The goal is to maximize the average population score. This means that you must both evolve strong queries and eliminate the weak queries.
Each round allows you to select one of the following evolutionary actions on the population:
Love Is In The Air
... but for now just clone each query once, doubling the population size.
The Weak Shall Perish
Remove all queries whose scores match the worst score.
Deus Ex Machina
Remove random queries from the population.
Gamma Party
Apply random mutations throughout the population. For each query, either a term will be removed or a random new term will be added with a random prefix (+/-).
This Town Is Too Small For The Both Of Us
Remove duplicate queries.
Then the selected action is applied to the population and new queries and scores are computed.
Tipp for beginners: First create a population of clones, then apply mutations, then remove the bad mutations.
The game ends after the specified number of rounds, of when your population dies out because your selective pressure was a tad to harsh.
Run unit tests with pytest via:
make test
- Save highscores in SQLite database.
- Extend evolutionary actions.
- Parameterize evolutionary actions.
- Implement sexual reproduction of queries (for action "Love Is In The Air").
- Implement more complex search than via boolean queries. Requires more sophisticated evolutionary actions.
- Increase complexity of sentences, with corresponding linguistic preprocessing.
- Extend unit tests.
- Untangle existing unit tests: one test per call.
- Replace repeat pattern for testing random operations with mockups.
- Add pydoc documentation to methods.
Update Python requirements:
pipreqs .
Use virtual environment:
python3 -m venv evolve-a-query
source evolve-a-query/bin/activate