From ecbb0627092bf4e77cf211b0b7632f0d2448d025 Mon Sep 17 00:00:00 2001 From: Benji Dial Date: Thu, 28 Dec 2023 21:49:47 -0500 Subject: add convenience methods and (experimental) evolver --- evolver/evolver.cpp | 296 ++++++++++++++++++++++++++++++++++++++++++++++++ include/lib94/lib94.hpp | 11 ++ lib94/core.cpp | 17 +++ lib94/warrior.cpp | 15 +++ makefile | 6 +- readme.txt | 8 ++ 6 files changed, 352 insertions(+), 1 deletion(-) create mode 100644 evolver/evolver.cpp diff --git a/evolver/evolver.cpp b/evolver/evolver.cpp new file mode 100644 index 0000000..5e649da --- /dev/null +++ b/evolver/evolver.cpp @@ -0,0 +1,296 @@ +#include +#include +#include +#include +#include +#include +#include +#include + +const lib94::warrior *warrior_to_beat; + +constexpr int score_rounds = 50; +constexpr int rounds_to_tie = 1000000; +constexpr int warriors_per_generation = 100; + +struct winfo { + lib94::warrior w; + int score; +}; + +std::vector current_generation; +int generation_number; + +std::default_random_engine prng; + +//sets random opcode, modifier, and modes +void random_instruction(lib94::instruction &instr) { + std::uniform_int_distribution opcode_dist(lib94::DAT, lib94::NOP); + std::uniform_int_distribution modifier_dist(lib94::A, lib94::I); + std::uniform_int_distribution mode_dist(lib94::IMMEDIATE, lib94::B_INCREMENT); + instr.op = (lib94::opcode)opcode_dist(prng); + instr.mod = (lib94::modifier)modifier_dist(prng); + instr.amode = (lib94::mode)mode_dist(prng); + instr.bmode = (lib94::mode)mode_dist(prng); +} + +//sets random numbers +void random_numbers(lib94::instruction &instr) { + std::uniform_int_distribution number_dist(0, LIB94_CORE_SIZE - 1); + instr.anumber = number_dist(prng); + instr.bnumber = number_dist(prng); +} + +//sets random numbers within a range; left_limit and right_limit are assumed to be >= -LIB94_CORE_SIZE +void random_numbers(lib94::instruction &instr, std::make_signed_t left_limit, std::make_signed_t right_limit) { + std::uniform_int_distribution> number_dist(left_limit, right_limit); + instr.anumber = (number_dist(prng) + LIB94_CORE_SIZE) % LIB94_CORE_SIZE; + instr.bnumber = (number_dist(prng) + LIB94_CORE_SIZE) % LIB94_CORE_SIZE; +} + +void random_warrior(lib94::warrior &w) { + + std::uniform_int_distribution length_dist(1, 10); + int length = length_dist(prng); + w.instructions.resize(length); + + for (int i = 0; i < length; ++i) { + random_instruction(w.instructions[i]); + //allow numbers to point up to one instruction before or after warrior + random_numbers(w.instructions[i], -i - 1, length - i); + } + + std::uniform_int_distribution org_dist(0, length - 1); + w.org = org_dist(prng); + +} + +void mutate(lib94::warrior &w) { + + std::uniform_int_distribution case_dist(0, 9); + + while (true) { + + std::uniform_int_distribution instr_dist(0, w.instructions.size() - 1); + int instr = instr_dist(prng); + + lib94::instruction i; + + switch (case_dist(prng)) { + + case 0: + return; + + case 1: + case 2: + random_instruction(w.instructions[instr]); + break; + + case 3: + case 4: + random_numbers(w.instructions[instr], -instr - 1, w.instructions.size() - instr); + break; + + case 5: + random_numbers(w.instructions[instr]); + break; + + case 6: + random_instruction(i); + random_numbers(i, -instr - 1, w.instructions.size() + 1 - instr); + w.instructions.insert(w.instructions.cbegin() + instr, i); + break; + + case 7: + random_instruction(i); + random_numbers(i, -instr - 2, w.instructions.size() - instr); + w.instructions.insert(w.instructions.cbegin() + instr + 1, i); + break; + + case 8: + case 9: + if (w.instructions.size() > 1) + w.instructions.erase(w.instructions.cbegin() + instr); + break; + + } + + } + +} + +void crossover(const lib94::warrior &a, const lib94::warrior &b, lib94::warrior &c) { + + std::uniform_int_distribution b_offset_dist(0, a.instructions.size()); + int b_offset = b_offset_dist(prng); + + std::uniform_int_distribution b_start_dist(b_offset, std::min(a.instructions.size(), b_offset + b.instructions.size())); + int b_start = b_start_dist(prng); + + std::uniform_int_distribution b_end_dist(b_start, std::min(a.instructions.size(), b_offset + b.instructions.size())); + int b_end = b_end_dist(prng); + + c.instructions.resize(a.instructions.size()); + std::copy(a.instructions.cbegin(), a.instructions.cbegin() + b_start, c.instructions.begin()); + std::copy(b.instructions.cbegin() + b_start - b_offset, b.instructions.cbegin() + b_end - b_offset, c.instructions.begin() + b_start); + std::copy(a.instructions.cbegin() + b_end, a.instructions.cend(), c.instructions.begin() + b_end); + + c.org = a.org; + +} + +const lib94::instruction background = { + .op = lib94::DAT, + .mod = lib94::F, + .amode = lib94::DIRECT, + .bmode = lib94::DIRECT, + .anumber = 0, + .bnumber = 0 +}; + +int main(int argc, char **argv) { + + prng.seed(time(0)); + + if (argc != 3) { + std::cerr << "please call this with the path to a warrior to beat followed by the path to a directory to store the outputs." << std::endl; + return 1; + } + + try { + warrior_to_beat = lib94::compile_warrior_from_file(argv[1]); + } + catch (const lib94::compiler_exception &ex) { + std::cerr << "error compiling " << argv[1] << ": " << ex.message << " on line " << ex.source_line_number << '.' << std::endl; + return 1; + } + + if (!warrior_to_beat) { + std::cerr << "could not open " << argv[1] << '.' << std::endl; + return 1; + } + + std::filesystem::path output_dir(argv[2]); + + if (std::filesystem::exists(output_dir)) { + std::cerr << output_dir << " already exists." << std::endl; + return 1; + } + + if (!std::filesystem::create_directories(output_dir)) { + std::cerr << "could not create " << output_dir << '.' << std::endl; + return 1; + } + + generation_number = 1; + current_generation.resize(warriors_per_generation); + for (int i = 0; i < warriors_per_generation; ++i) { + random_warrior(current_generation[i].w); + current_generation[i].w.name = "g1w" + std::to_string(i + 1); + current_generation[i].score = -1; + } + + int last_best_score = 0; + + while (true) { + + std::shuffle(current_generation.begin(), current_generation.end(), prng); + + std::cout << "generation " << generation_number << ". " << std::flush; + + int best_score = 0; + const lib94::warrior *best_w = ¤t_generation[0].w; + + int total_score = 0; + + for (winfo &wi : current_generation) { + + if (wi.score == -1) { + + const lib94::warrior *ws[2] = { warrior_to_beat, &wi.w }; + int score = score_rounds; + + for (int i = 0; i < score_rounds; ++i) { + const lib94::warrior *winner = lib94::do_round(background, ws, 2, 0, true, rounds_to_tie); + if (winner == warrior_to_beat) + --score; + else if (winner != 0) + ++score; + } + + wi.score = score; + + } + + if (wi.score > best_score) { + best_score = wi.score; + best_w = &wi.w; + } + + total_score += wi.score; + + } + + std::cout << "average / maximum score " << (double)total_score / current_generation.size() << " / " << best_score << ". " << std::endl; + + if (best_score > last_best_score) { + + last_best_score = best_score; + + std::filesystem::path file_path = output_dir / (std::to_string(generation_number) + ".red"); + std::ofstream file(file_path); + + if (!file) { + std::cerr << "could not open " << file_path << '.' << std::endl; + return 1; + } + + file << ";author evolver\n;name " << best_w->name << "\n;score = " << best_score << " / " << score_rounds * 2 << "\norg " << best_w->org << '\n'; + for (const lib94::instruction &i : best_w->instructions) + file << lib94::instruction_to_string(i) << '\n'; + + file.close(); + + if (best_score == score_rounds * 2) { + std::cout << "perfect score reached." << std::endl; + return 0; + } + + } + + ++generation_number; + + std::vector new_warriors; + new_warriors.reserve(current_generation.size() + 2); + + new_warriors.push_back({.w = *best_w, .score = best_score}); + + std::uniform_int_distribution score_at_least(best_score > score_rounds ? score_rounds : 0, best_score > score_rounds ? score_rounds * 2 + 1 : score_rounds); + + for (const winfo &wi : current_generation) + if (wi.score >= score_at_least(prng)) + new_warriors.push_back(wi); + + std::uniform_int_distribution warrior_dist(0, new_warriors.size() - 1); + + do { + + lib94::warrior w1 = new_warriors[warrior_dist(prng)].w; + lib94::warrior w2 = new_warriors[warrior_dist(prng)].w; + + mutate(w1); + mutate(w2); + + lib94::warrior w; + crossover(w1, w2, w); + w.name = "g" + std::to_string(generation_number) + "w" + std::to_string(new_warriors.size() + 1); + + new_warriors.push_back({.w = w, .score = -1}); + + } while (new_warriors.size() < warriors_per_generation); + + current_generation = std::move(new_warriors); + + } + +} diff --git a/include/lib94/lib94.hpp b/include/lib94/lib94.hpp index 63f862e..0766af7 100644 --- a/include/lib94/lib94.hpp +++ b/include/lib94/lib94.hpp @@ -147,6 +147,17 @@ namespace lib94 { template const warrior *single_step(); + //convenience method - reads the contents of a file and then calls compile_warrior. + //if the file cannot be read, returns a null pointer. see comment on compile_warrior. + warrior *compile_warrior_from_file(std::string path); + + //convenience method - calls clear_core(background), then init_round(warriors, count, + //offsets, shuffle), then single_step until either one warrior remains or that + //has been called rounds_to_tie times. if one warrior remains, returns the pointer to + //that warrior. if a tie is reached, returns a null pointer. this asserts that the call + //to init_round returns true. see comment on init_round. + const warrior *do_round(const instruction &background, const warrior *const *warriors, size_t count, const number_t *offsets, bool shuffle, long rounds_to_tie); + } #endif diff --git a/lib94/core.cpp b/lib94/core.cpp index bec793b..5bbe00f 100644 --- a/lib94/core.cpp +++ b/lib94/core.cpp @@ -319,4 +319,21 @@ namespace lib94 { template const warrior *single_step(); template const warrior *single_step(); + const warrior *do_round(const instruction &background, const warrior *const *warriors, size_t count, const number_t *offsets, bool shuffle, long rounds_to_tie) { + + clear_core(background); + assert(init_round(warriors, count, offsets, shuffle)); + size_t warriors_left = count; + + for (long i = 0; i < rounds_to_tie; ++i) + if (single_step() != 0) { + --warriors_left; + if (warriors_left == 1) + return get_next_warrior(); + } + + return 0; + + } + } diff --git a/lib94/warrior.cpp b/lib94/warrior.cpp index a744cb8..b803d6d 100644 --- a/lib94/warrior.cpp +++ b/lib94/warrior.cpp @@ -2,6 +2,7 @@ #include #include #include +#include #include #include #include @@ -760,4 +761,18 @@ namespace lib94 { } + warrior *compile_warrior_from_file(std::string path) { + + std::ifstream file(path); + if (!file) + return 0; + + std::stringstream stream; + stream << file.rdbuf(); + file.close(); + + return compile_warrior(stream.str()); + + } + } diff --git a/makefile b/makefile index 704421f..637c7b0 100644 --- a/makefile +++ b/makefile @@ -7,7 +7,7 @@ GTKMM_LD_ARGS = $(shell pkg-config --libs gtkmm-4.0) MPI_CPP_ARGS = $(shell mpic++ --showme:compile) -DOMPI_SKIP_MPICXX MPI_LD_ARGS = $(shell mpic++ --showme:link) -default: bin/bench bin/tabulator-mpi +default: bin/bench bin/evolver bin/tabulator-mpi clean: rm -r obj bin @@ -16,6 +16,10 @@ bin/bench: obj/bench/main.o obj/bench/bench_window.o obj/bench/core_widget.o obj @mkdir -p $(dir $@) g++ ${CPP_ARGS} $^ ${GTKMM_LD_ARGS} -o $@ +bin/evolver: obj/evolver/evolver.o obj/lib94.o + @mkdir -p $(dir $@) + g++ ${CPP_ARGS} $^ -o $@ + bin/tabulator-mpi: obj/tabulator-mpi/source.o obj/lib94.o @mkdir -p $(dir $@) g++ ${CPP_ARGS} $^ ${MPI_LD_ARGS} -o $@ diff --git a/readme.txt b/readme.txt index 618a3ca..ffb5eac 100644 --- a/readme.txt +++ b/readme.txt @@ -38,3 +38,11 @@ To run all of the included warriors against each other, run Note that tabulator expects at least two processes (one head process and at least one worker). If you only have one core, you may run mpirun -np 2 --oversubscribe bin/tabulator-mpi warriors/*.red + +=== evolver === + +The "evolver" program attempts to create warriors who are good against a particular other warrior via a process similar to genetic +evolution. It is highly experimental and does not always work. I may or may not attempt to improve it in the future. + +To evolve a warrior against the included Epson warrior, with the outputs from each round stored in a directory named output, run + bin/evolver warriors/epson.red output -- cgit v1.2.3