From 9778e5c1298c8888214725f968badcbab516ea82 Mon Sep 17 00:00:00 2001 From: Benji Dial Date: Fri, 7 Jun 2024 01:11:49 -0400 Subject: redo evolver, add warrior serialization / deserialization to library --- evolver/evolver.cpp | 487 +++++++++++++++++++++++++++++----------------------- 1 file changed, 276 insertions(+), 211 deletions(-) (limited to 'evolver') diff --git a/evolver/evolver.cpp b/evolver/evolver.cpp index 5e649da..fb80d4f 100644 --- a/evolver/evolver.cpp +++ b/evolver/evolver.cpp @@ -2,294 +2,359 @@ #include #include #include +#include #include -#include -#include -#include +#include +#include -const lib94::warrior *warrior_to_beat; +constexpr size_t max_good_warriors = 100; +constexpr int rounds_per_matchup = 100; +constexpr int steps_to_tie = 1000000; -constexpr int score_rounds = 50; -constexpr int rounds_to_tie = 1000000; -constexpr int warriors_per_generation = 100; - -struct winfo { - lib94::warrior w; - int score; +constexpr lib94::instruction background_instruction = { + .op = lib94::DAT, .mod = lib94::F, + .amode = lib94::DIRECT, .bmode = lib94::DIRECT, + .anumber = 0, .bnumber = 0 }; -std::vector current_generation; -int generation_number; +lib94::warrior *warrior_to_beat; +int comm_rank, comm_size; -std::default_random_engine prng; +std::filesystem::path output_dir; -//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); -} +std::vector seed_warriors; -//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); -} +void head_main(); +void child_main(); -//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; -} +int main(int argc, char **argv) { -void random_warrior(lib94::warrior &w) { + MPI_Init(&argc, &argv); - std::uniform_int_distribution length_dist(1, 10); - int length = length_dist(prng); - w.instructions.resize(length); + MPI_Comm_rank(MPI_COMM_WORLD, &comm_rank); + MPI_Comm_size(MPI_COMM_WORLD, &comm_size); - 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); + if (comm_size < 2) { + std::cerr << "you need at least two processes." << std::endl; + return 1; } - 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; + if (argc < 4) { + if (comm_rank == 0) + std::cerr << "usage: " << argv[0] << " ..." << std::endl; + return 2; + } - case 3: - case 4: - random_numbers(w.instructions[instr], -instr - 1, w.instructions.size() - instr); - break; + try { + warrior_to_beat = lib94::compile_warrior_from_file(argv[1]); + } + catch (const lib94::compiler_exception &ex) { + if (comm_rank == 0) + std::cerr + << "syntax error on line " << ex.source_line_number + << " of " << argv[1] << ":\n " << ex.message << std::endl; + return 3; + } - case 5: - random_numbers(w.instructions[instr]); - break; + if (warrior_to_beat == 0) { + if (comm_rank == 0) + std::cerr << "could not read file " << argv[1] << std::endl; + return 4; + } - case 6: - random_instruction(i); - random_numbers(i, -instr - 1, w.instructions.size() + 1 - instr); - w.instructions.insert(w.instructions.cbegin() + instr, i); - break; + output_dir = argv[2]; - case 7: - random_instruction(i); - random_numbers(i, -instr - 2, w.instructions.size() - instr); - w.instructions.insert(w.instructions.cbegin() + instr + 1, i); - break; + for (int i = 3; i < argc; ++i) { - case 8: - case 9: - if (w.instructions.size() > 1) - w.instructions.erase(w.instructions.cbegin() + instr); - break; + try { + seed_warriors.push_back(lib94::compile_warrior_from_file(argv[i])); + } + catch (const lib94::compiler_exception &ex) { + if (comm_rank == 0) + std::cerr + << "syntax error on line " << ex.source_line_number + << " of " << argv[i] << ":\n " << ex.message << std::endl; + return 3; + } + if (seed_warriors.back() == 0) { + if (comm_rank == 0) + std::cerr << "could not read file " << argv[i] << std::endl; + return 4; } } -} + if (comm_rank == 0) + head_main(); -void crossover(const lib94::warrior &a, const lib94::warrior &b, lib94::warrior &c) { + else + child_main(); - std::uniform_int_distribution b_offset_dist(0, a.instructions.size()); - int b_offset = b_offset_dist(prng); + return 0; - 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); +struct scored_warrior { + int score; + lib94::warrior *w; + bool operator <(const scored_warrior &other) const { + return score > other.score || (score == other.score && w->instructions.size() < other.w->instructions.size()); + } +}; - 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); +void head_main() { - c.org = a.org; + std::cout << "\x1b""7\x1b[?47h\x1b[2J" << std::flush; -} + std::vector warriors; + for (lib94::warrior *const &w : seed_warriors) + warriors.push_back({.score = -1, .w = w}); -const lib94::instruction background = { - .op = lib94::DAT, - .mod = lib94::F, - .amode = lib94::DIRECT, - .bmode = lib94::DIRECT, - .anumber = 0, - .bnumber = 0 -}; + int *warrior_counts = new int[comm_size]; -int main(int argc, char **argv) { + int round = 1; - prng.seed(time(0)); + while (true) { - 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; - } + std::cout << "\x1b[1;1Hhead node: sending warriors\x1b[0K" << std::flush; - 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; - } + int warrior_count = warriors.size(); + MPI_Bcast(&warrior_count, 1, MPI_INT, 0, MPI_COMM_WORLD); - std::filesystem::path output_dir(argv[2]); + for (scored_warrior &sw : warriors) { + std::vector serialization; + lib94::serialize_warrior(sw.w, serialization); + int serialization_length = serialization.size(); + MPI_Bcast(&serialization_length, 1, MPI_INT, 0, MPI_COMM_WORLD); + MPI_Bcast(serialization.data(), serialization_length, MPI_UINT8_T, 0, MPI_COMM_WORLD); + } - if (std::filesystem::exists(output_dir)) { - std::cerr << output_dir << " already exists." << std::endl; - return 1; - } + if (round == 1) { + for (scored_warrior &sw : warriors) + delete sw.w; + warriors.clear(); + } - if (!std::filesystem::create_directories(output_dir)) { - std::cerr << "could not create " << output_dir << '.' << std::endl; - return 1; - } + std::cout << "\x1b[1;1Hhead node: waiting for child nodes\x1b[0K" << std::flush; + + MPI_Gather(warrior_counts, 1, MPI_INT, warrior_counts, 1, MPI_INT, 0, MPI_COMM_WORLD); + + for (int i = 1; i < comm_size; ++i) { + std::cout << "\x1b[1;1Hhead node: receiving warriors from child node " << i << "\x1b[0K" << std::flush; + for (int j = 0; j < warrior_counts[i]; ++j) { + int score; + MPI_Recv(&score, 1, MPI_INT, i, 0, MPI_COMM_WORLD, 0); + int serialization_length; + MPI_Recv(&serialization_length, 1, MPI_INT, i, 0, MPI_COMM_WORLD, 0); + uint8_t *buffer = new uint8_t[serialization_length]; + MPI_Recv(buffer, serialization_length, MPI_UINT8_T, i, 0, MPI_COMM_WORLD, 0); + warriors.push_back({.score = score, .w = lib94::deserialize_warrior(buffer)}); + delete[] buffer; + } + } - 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; - } + std::sort(warriors.begin(), warriors.end()); - int last_best_score = 0; + std::filesystem::path out_path = output_dir / (std::to_string(round) + ".red"); - while (true) { + int total_score = 0; + for (const scored_warrior &sw : warriors) + total_score += sw.score; + + std::cout << "\x1b[" << (comm_size + 2) << ";1Hmin/avg/max score from round " << round << ":\n " + << (float)(warriors[warriors.size() - 1].score * 100) / (rounds_per_matchup * 2) << "% / " + << (float)(total_score * 100) / (warriors.size() * rounds_per_matchup * 2) << "% / " + << (float)(warriors[0].score * 100) / (rounds_per_matchup * 2) << "%\x1b[0K\n\nbest was:\n"; + + std::ofstream out_file(out_path); + if (!out_file) { + std::cout << "\x1b[?47l\x1b""8" << std::flush; + std::cerr << "could not open file " << out_path << std::endl; + int zero = 0; + MPI_Bcast(&zero, 1, MPI_INT, 0, MPI_COMM_WORLD); + MPI_Finalize(); + exit(5); + } - std::shuffle(current_generation.begin(), current_generation.end(), prng); + out_file << ";author evolver\n;name evolved\n"; + out_file << ";score was " << (float)(warriors[0].score * 100) / (rounds_per_matchup * 2) << "%\n"; + out_file << "org " << warriors[0].w->org << '\n'; + std::cout << " org " << warriors[0].w->org << "\x1b[0K\n"; + for (const lib94::instruction &i : warriors[0].w->instructions) { + out_file << lib94::instruction_to_string(i) << '\n'; + std::cout << " " << lib94::instruction_to_string(i) << "\x1b[0K\n"; + } - std::cout << "generation " << generation_number << ". " << std::flush; + std::cout << "\x1b[0J" << std::flush; - int best_score = 0; - const lib94::warrior *best_w = ¤t_generation[0].w; + out_file.close(); - int total_score = 0; + if (warriors[0].score == rounds_per_matchup * 2) { + std::cout << "\x1b[?47l\x1b""8completed in " << round << " rounds\n"; + int zero = 0; + MPI_Bcast(&zero, 1, MPI_INT, 0, MPI_COMM_WORLD); + MPI_Finalize(); + exit(0); + } - for (winfo &wi : current_generation) { + size_t good_warriors = std::min(max_good_warriors, warriors.size()); - if (wi.score == -1) { + for (size_t i = good_warriors; i < warriors.size(); ++i) + delete warriors[i].w; - const lib94::warrior *ws[2] = { warrior_to_beat, &wi.w }; - int score = score_rounds; + warriors.resize(good_warriors); - 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; - } + ++round; - wi.score = score; + } - } +} - if (wi.score > best_score) { - best_score = wi.score; - best_w = &wi.w; - } +void randomize_in_range(lib94::instruction &instr, int min, int max) { + instr.op = (lib94::opcode)(rand() % 16); + instr.mod = (lib94::modifier)(rand() % 7); + instr.amode = (lib94::mode)(rand() % 8); + instr.bmode = (lib94::mode)(rand() % 8); + instr.anumber = (rand() % (max - min + 1) + min + LIB94_CORE_SIZE) % LIB94_CORE_SIZE; + instr.bnumber = (rand() % (max - min + 1) + min + LIB94_CORE_SIZE) % LIB94_CORE_SIZE; +} - total_score += wi.score; +void randomize(lib94::instruction &instr) { + instr.op = (lib94::opcode)(rand() % 16); + instr.mod = (lib94::modifier)(rand() % 7); + instr.amode = (lib94::mode)(rand() % 8); + instr.bmode = (lib94::mode)(rand() % 8); + instr.anumber = rand() % LIB94_CORE_SIZE; + instr.bnumber = rand() % LIB94_CORE_SIZE; +} - } +void mutate_step(lib94::warrior *w) { + + if (w->instructions.size() == 0) { + bool in_range = rand() % 2 == 0; + lib94::instruction instruction; + if (in_range) + randomize_in_range(instruction, 0, 0); + else + randomize(instruction); + w->instructions.push_back(instruction); + return; + } - std::cout << "average / maximum score " << (double)total_score / current_generation.size() << " / " << best_score << ". " << std::endl; + int rand_inclusive = rand() % (w->instructions.size() + 1); + int rand_exclusive = rand() % w->instructions.size(); + bool in_range = rand() % 2 == 0; + + switch (rand() % 4) { + + //org + case 0: + w->org = rand_exclusive; + return; + + //insert + case 1: + w->instructions.insert(w->instructions.cbegin() + rand_inclusive, (lib94::instruction){}); + if (w->org > rand_inclusive) + ++w->org; + rand_exclusive = rand_inclusive; + //FALLTHRU + + //modify + case 2: + if (in_range) + randomize_in_range(w->instructions[rand_exclusive], -rand_exclusive, w->instructions.size() - rand_exclusive - 1); + else + randomize(w->instructions[rand_exclusive]); + return; + + //remove + case 3: + w->instructions.erase(w->instructions.cbegin() + rand_exclusive); + if (w->org > rand_exclusive) + --w->org; + return; - 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); +void mutate(lib94::warrior *w) { + do + mutate_step(w); + while (rand() % 2 == 0); +} - if (!file) { - std::cerr << "could not open " << file_path << '.' << std::endl; - return 1; - } +int score(const lib94::warrior *w) { + int the_score = 0; + const lib94::warrior *const warriors[2] = {warrior_to_beat, w}; + for (int i = 0; i < rounds_per_matchup; ++i) { + const lib94::warrior *winner = lib94::do_round(background_instruction, warriors, 2, 0, true, steps_to_tie); + if (winner == 0) + ++the_score; + else if (winner == w) + the_score += 2; + } + return the_score; +} - 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'; +void child_main() { - file.close(); + srand(time(0)); - if (best_score == score_rounds * 2) { - std::cout << "perfect score reached." << std::endl; - return 0; - } + std::vector warriors; - } + while (true) { - ++generation_number; + int warrior_count; + MPI_Bcast(&warrior_count, 1, MPI_INT, 0, MPI_COMM_WORLD); - std::vector new_warriors; - new_warriors.reserve(current_generation.size() + 2); + if (warrior_count == 0) { + MPI_Finalize(); + exit(0); + } - new_warriors.push_back({.w = *best_w, .score = best_score}); + warriors.resize(warrior_count); - std::uniform_int_distribution score_at_least(best_score > score_rounds ? score_rounds : 0, best_score > score_rounds ? score_rounds * 2 + 1 : score_rounds); + std::cout << "\x1b[" << (comm_rank + 1) << ";1Hchild node " << comm_rank << ": receiving warriors\x1b[0K" << std::flush; - for (const winfo &wi : current_generation) - if (wi.score >= score_at_least(prng)) - new_warriors.push_back(wi); + for (int i = 0; i < warrior_count; ++i) { + int serialization_length; + MPI_Bcast(&serialization_length, 1, MPI_INT, 0, MPI_COMM_WORLD); + uint8_t *buffer = new uint8_t[serialization_length]; + MPI_Bcast(buffer, serialization_length, MPI_UINT8_T, 0, MPI_COMM_WORLD); + warriors[i].w = lib94::deserialize_warrior(buffer); + delete[] buffer; + } - std::uniform_int_distribution warrior_dist(0, new_warriors.size() - 1); + std::cout << "\x1b[" << (comm_rank + 1) << ";1Hchild node " << comm_rank << ": mutating warriors\x1b[0K" << std::flush; - do { + for (scored_warrior &sw : warriors) + mutate(sw.w); - lib94::warrior w1 = new_warriors[warrior_dist(prng)].w; - lib94::warrior w2 = new_warriors[warrior_dist(prng)].w; + for (size_t i = 0; i < warriors.size(); ++i) { + std::cout << "\x1b[" << (comm_rank + 1) << ";1Hchild node " << comm_rank << ": scoring warriors " << (float)(i * 100) / warriors.size() << "%\x1b[0K" << std::flush; + warriors[i].score = score(warriors[i].w); + } - mutate(w1); - mutate(w2); + std::cout << "\x1b[" << (comm_rank + 1) << ";1Hchild node " << comm_rank << ": waiting for other child nodes\x1b[0K" << std::flush; - lib94::warrior w; - crossover(w1, w2, w); - w.name = "g" + std::to_string(generation_number) + "w" + std::to_string(new_warriors.size() + 1); + MPI_Gather(&warrior_count, 1, MPI_INT, 0, 0, 0, 0, MPI_COMM_WORLD); - new_warriors.push_back({.w = w, .score = -1}); + for (scored_warrior &sw : warriors) { + std::vector serialization; + lib94::serialize_warrior(sw.w, serialization); + int serialization_length = serialization.size(); + MPI_Send(&sw.score, 1, MPI_INT, 0, 0, MPI_COMM_WORLD); + MPI_Send(&serialization_length, 1, MPI_INT, 0, 0, MPI_COMM_WORLD); + MPI_Send(serialization.data(), serialization_length, MPI_UINT8_T, 0, 0, MPI_COMM_WORLD); + } - } while (new_warriors.size() < warriors_per_generation); + for (scored_warrior &sw : warriors) + delete sw.w; - current_generation = std::move(new_warriors); + warriors.clear(); } -- cgit v1.2.3