diff options
| -rw-r--r-- | evolver/evolver.cpp | 361 | ||||
| -rw-r--r-- | include/lib94/lib94.hpp | 15 | ||||
| -rw-r--r-- | lib94/core.cpp | 97 | ||||
| -rw-r--r-- | makefile | 26 | ||||
| -rw-r--r-- | readme.txt | 19 | ||||
| -rw-r--r-- | tabulator-mpi/mpi.txt | 15 | ||||
| -rw-r--r-- | tabulator-mpi/source.cpp | 214 | ||||
| -rw-r--r-- | tabulator/tabulator.cpp | 159 |
8 files changed, 274 insertions, 632 deletions
diff --git a/evolver/evolver.cpp b/evolver/evolver.cpp deleted file mode 100644 index fb80d4f..0000000 --- a/evolver/evolver.cpp +++ /dev/null @@ -1,361 +0,0 @@ -#include <lib94/lib94.hpp> -#include <filesystem> -#include <algorithm> -#include <iostream> -#include <cstdlib> -#include <fstream> -#include <sstream> -#include <mpi.h> - -constexpr size_t max_good_warriors = 100; -constexpr int rounds_per_matchup = 100; -constexpr int steps_to_tie = 1000000; - -constexpr lib94::instruction background_instruction = { - .op = lib94::DAT, .mod = lib94::F, - .amode = lib94::DIRECT, .bmode = lib94::DIRECT, - .anumber = 0, .bnumber = 0 -}; - -lib94::warrior *warrior_to_beat; -int comm_rank, comm_size; - -std::filesystem::path output_dir; - -std::vector<lib94::warrior *> seed_warriors; - -void head_main(); -void child_main(); - -int main(int argc, char **argv) { - - MPI_Init(&argc, &argv); - - MPI_Comm_rank(MPI_COMM_WORLD, &comm_rank); - MPI_Comm_size(MPI_COMM_WORLD, &comm_size); - - if (comm_size < 2) { - std::cerr << "you need at least two processes." << std::endl; - return 1; - } - - if (argc < 4) { - if (comm_rank == 0) - std::cerr << "usage: " << argv[0] << " <warrior to beat> <output directory> <seed 1> <seed 2> ..." << std::endl; - return 2; - } - - 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; - } - - if (warrior_to_beat == 0) { - if (comm_rank == 0) - std::cerr << "could not read file " << argv[1] << std::endl; - return 4; - } - - output_dir = argv[2]; - - for (int i = 3; i < argc; ++i) { - - 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(); - - else - child_main(); - - return 0; - -} - -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()); - } -}; - -void head_main() { - - std::cout << "\x1b""7\x1b[?47h\x1b[2J" << std::flush; - - std::vector<scored_warrior> warriors; - for (lib94::warrior *const &w : seed_warriors) - warriors.push_back({.score = -1, .w = w}); - - int *warrior_counts = new int[comm_size]; - - int round = 1; - - while (true) { - - std::cout << "\x1b[1;1Hhead node: sending warriors\x1b[0K" << std::flush; - - int warrior_count = warriors.size(); - MPI_Bcast(&warrior_count, 1, MPI_INT, 0, MPI_COMM_WORLD); - - for (scored_warrior &sw : warriors) { - std::vector<uint8_t> 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 (round == 1) { - for (scored_warrior &sw : warriors) - delete sw.w; - warriors.clear(); - } - - 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; - } - } - - std::sort(warriors.begin(), warriors.end()); - - std::filesystem::path out_path = output_dir / (std::to_string(round) + ".red"); - - 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); - } - - 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 << "\x1b[0J" << std::flush; - - out_file.close(); - - 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); - } - - size_t good_warriors = std::min(max_good_warriors, warriors.size()); - - for (size_t i = good_warriors; i < warriors.size(); ++i) - delete warriors[i].w; - - warriors.resize(good_warriors); - - ++round; - - } - -} - -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; -} - -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; - } - - 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; - - } - -} - -void mutate(lib94::warrior *w) { - do - mutate_step(w); - while (rand() % 2 == 0); -} - -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; -} - -void child_main() { - - srand(time(0)); - - std::vector<scored_warrior> warriors; - - while (true) { - - int warrior_count; - MPI_Bcast(&warrior_count, 1, MPI_INT, 0, MPI_COMM_WORLD); - - if (warrior_count == 0) { - MPI_Finalize(); - exit(0); - } - - warriors.resize(warrior_count); - - std::cout << "\x1b[" << (comm_rank + 1) << ";1Hchild node " << comm_rank << ": receiving warriors\x1b[0K" << std::flush; - - 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::cout << "\x1b[" << (comm_rank + 1) << ";1Hchild node " << comm_rank << ": mutating warriors\x1b[0K" << std::flush; - - for (scored_warrior &sw : warriors) - mutate(sw.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); - } - - std::cout << "\x1b[" << (comm_rank + 1) << ";1Hchild node " << comm_rank << ": waiting for other child nodes\x1b[0K" << std::flush; - - MPI_Gather(&warrior_count, 1, MPI_INT, 0, 0, 0, 0, MPI_COMM_WORLD); - - for (scored_warrior &sw : warriors) { - std::vector<uint8_t> 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); - } - - for (scored_warrior &sw : warriors) - delete sw.w; - - warriors.clear(); - - } - -} diff --git a/include/lib94/lib94.hpp b/include/lib94/lib94.hpp index 71ec68e..9b4147c 100644 --- a/include/lib94/lib94.hpp +++ b/include/lib94/lib94.hpp @@ -6,6 +6,7 @@ #include <string> #include <vector> #include <deque> +#include <mpi.h> #include <set> #ifndef LIB94_CORE_SIZE @@ -22,7 +23,8 @@ namespace lib94 { //it has to be at least big enough to represent LIB94_CORE_SIZE squared, //since it is used as an intermediate for all of the instructions, //including in particular MUL. - typedef int_least32_t number_t; + typedef int32_t number_t; + #define LIB94_MPI_NUMBER_T MPI_INT32_T enum opcode : uint8_t { DAT, MOV, ADD, SUB, @@ -162,10 +164,17 @@ namespace lib94 { //convenience method - calls clear_core(background), then init_round(warriors, count, //offsets, shuffle), then single_step<false> until either one warrior remains or that - //has been called rounds_to_tie times. if one warrior remains, returns the pointer to + //has been called steps_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); + const warrior *do_round(const instruction &background, const warrior *const *warriors, size_t count, const number_t *offsets, bool shuffle, long steps_to_tie); + + //runs every possible offset and turn order using do_round. + //asserts that total length is not more than core size. + //should be called from everyone in a communicator. + //assumes comm ranks go from 0 to comm size - 1. + template <bool print_progress> + void tabulate_mpi(const instruction &background, const warrior *w1, const warrior *w2, long steps_to_tie, int &w1_wins_out, int &w2_wins_out, int &rounds_out, MPI_Comm communicator); } diff --git a/lib94/core.cpp b/lib94/core.cpp index 5bbe00f..790205e 100644 --- a/lib94/core.cpp +++ b/lib94/core.cpp @@ -1,8 +1,10 @@ #include <lib94/lib94.hpp> #include <functional> #include <algorithm> +#include <iostream> #include <cassert> #include <random> +#include <mpi.h> namespace lib94 { @@ -319,13 +321,13 @@ namespace lib94 { template const warrior *single_step<true>(); template const warrior *single_step<false>(); - const warrior *do_round(const instruction &background, const warrior *const *warriors, size_t count, const number_t *offsets, bool shuffle, long rounds_to_tie) { + const warrior *do_round(const instruction &background, const warrior *const *warriors, size_t count, const number_t *offsets, bool shuffle, long steps_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) + for (long i = 0; i < steps_to_tie; ++i) if (single_step<false>() != 0) { --warriors_left; if (warriors_left == 1) @@ -336,4 +338,95 @@ namespace lib94 { } + template <bool print_progress> + void tabulate_mpi(const instruction &background, const warrior *w1, const warrior *w2, long steps_to_tie, int &w1_wins_out, int &w2_wins_out, int &rounds_out, MPI_Comm communicator) { + + assert(w1->instructions.size() + w2->instructions.size() <= LIB94_CORE_SIZE); + + std::vector<number_t> w2_offsets; + for (number_t i = w1->instructions.size(); i + w2->instructions.size() <= LIB94_CORE_SIZE; ++i) + w2_offsets.push_back(i); + + int comm_size; + int comm_rank; + + MPI_Comm_size(communicator, &comm_size); + MPI_Comm_rank(communicator, &comm_rank); + + if constexpr (print_progress) + if (comm_rank == 0) + for (int i = 0; i < comm_size; ++i) + std::cerr << '\n'; + + int actual_count = w2_offsets.size(); + int per_process = (actual_count - 1) / comm_size + 1; + + w2_offsets.resize(per_process * comm_size); + for (int i = actual_count; i < per_process * comm_size; ++i) + w2_offsets[i] = LIB94_CORE_SIZE + 1; + + std::shuffle(w2_offsets.begin(), w2_offsets.end(), prng); + + number_t *recv_buffer = new number_t[per_process]; + MPI_Scatter(w2_offsets.data(), per_process, LIB94_MPI_NUMBER_T, recv_buffer, per_process, LIB94_MPI_NUMBER_T, 0, communicator); + + int wins[2] = {0, 0}; + + const warrior *w1_first_warriors[2] = {w1, w2}; + number_t w1_first_offsets[2] = {0, 0}; + + const warrior *w2_first_warriors[2] = {w2, w1}; + number_t w2_first_offsets[2] = {0, 0}; + + int last_percent = -1; + + for (int i = 0; i < per_process; ++i) + if (recv_buffer[i] != LIB94_CORE_SIZE + 1) { + + if constexpr (print_progress) { + int percent = i * 100 / per_process; + if (percent != last_percent) { + std::cout << "\x1b[" << comm_size - comm_rank << "A\x1b[3G"; + std::cout << "worker " << comm_rank + 1 << ": " << percent << "%\x1b[0K"; + std::cout << "\x1b[" << comm_size - comm_rank << "B\x1b[1G"; + std::cout << std::flush; + } + } + + w1_first_offsets[1] = recv_buffer[i]; + const warrior *w = do_round(background, w1_first_warriors, 2, w1_first_offsets, false, steps_to_tie); + if (w == w1) + ++wins[0]; + else if (w == w2) + ++wins[1]; + + w2_first_offsets[0] = recv_buffer[i]; + w = do_round(background, w2_first_warriors, 2, w2_first_offsets, false, steps_to_tie); + if (w == w1) + ++wins[0]; + else if (w == w2) + ++wins[1]; + + } + + + if constexpr (print_progress) { + std::cout << "\x1b[" << comm_size - comm_rank << "A\x1b[3G"; + std::cout << "worker " << comm_rank + 1 << ": complete\x1b[0K"; + std::cout << "\x1b[" << comm_size - comm_rank << "B\x1b[1G"; + std::cout << std::flush; + } + + int win_sums[2]; + + MPI_Allreduce(wins, win_sums, 2, MPI_INT, MPI_SUM, communicator); + w1_wins_out = win_sums[0]; + w2_wins_out = win_sums[1]; + rounds_out = actual_count * 2; + + } + + template void tabulate_mpi<true>(const instruction &background, const warrior *w1, const warrior *w2, long steps_to_tie, int &w1_wins_out, int &w2_wins_out, int &rounds_out, MPI_Comm communicator); + template void tabulate_mpi<false>(const instruction &background, const warrior *w1, const warrior *w2, long steps_to_tie, int &w1_wins_out, int &w2_wins_out, int &rounds_out, MPI_Comm communicator); + } @@ -1,26 +1,20 @@ -CPP_ARGS = -std=c++20 -O2 -Wall -Wextra -Iinclude -ggdb +# https://github.com/open-mpi/ompi/issues/5157 +CPP_ARGS = -std=c++20 -O2 -Wall -Wextra -Iinclude -ggdb $(shell mpic++ --showme:compile) -DOMPI_SKIP_MPICXX +MPI_LD_ARGS = $(shell mpic++ --showme:link) GTKMM_CPP_ARGS = $(shell pkg-config --cflags gtkmm-4.0) GTKMM_LD_ARGS = $(shell pkg-config --libs gtkmm-4.0) -# https://github.com/open-mpi/ompi/issues/5157 -MPI_CPP_ARGS = $(shell mpic++ --showme:compile) -DOMPI_SKIP_MPICXX -MPI_LD_ARGS = $(shell mpic++ --showme:link) - -default: bin/bench bin/evolver bin/tabulator-mpi +default: bin/bench bin/tabulator clean: rm -r obj bin bin/bench: obj/bench/main.o obj/bench/bench_window.o obj/bench/core_widget.o obj/lib94.o @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} $^ ${MPI_LD_ARGS} -o $@ + g++ ${CPP_ARGS} $^ ${MPI_LD_ARGS} ${GTKMM_LD_ARGS} -o $@ -bin/tabulator-mpi: obj/tabulator-mpi/source.o obj/lib94.o +bin/tabulator: obj/tabulator/tabulator.o obj/lib94.o @mkdir -p $(dir $@) g++ ${CPP_ARGS} $^ ${MPI_LD_ARGS} -o $@ @@ -31,14 +25,6 @@ obj/bench/%.o: bench/%.cpp @mkdir -p $(dir $@) g++ -c ${CPP_ARGS} ${GTKMM_CPP_ARGS} $^ -o $@ -obj/evolver/%.o: evolver/%.cpp - @mkdir -p $(dir $@) - g++ -c ${CPP_ARGS} ${MPI_CPP_ARGS} $^ -o $@ - -obj/tabulator-mpi/%.o: tabulator-mpi/%.cpp - @mkdir -p $(dir $@) - g++ -c ${CPP_ARGS} ${MPI_CPP_ARGS} $^ -o $@ - obj/%.o: %.cpp @mkdir -p $(dir $@) g++ -c ${CPP_ARGS} $^ -o $@ @@ -30,22 +30,7 @@ To open bench, just run bin/bench after building as above. The "tabulator" program runs every possible pairing of warriors from a selection against each other with every possible separation and turn order, and then shows the number of wins of each warrior against each other warrior in a table format. The column header -is the winner, and the row header is the loser. This program uses MPI to run batches of these rounds in different processes, and -communicate the results back to a head process. +is the winner, and the row header is the loser. This program uses MPI to run this across multiple processes. To run all of the included warriors against each other, run - mpirun bin/tabulator-mpi warriors/*.red - -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 experimental "evolver" program attempts to create warriors who are good against a particular other -warrior via a process similar to genetic evolution. I may or may not attempt to improve it in the future. - -The evolver takes an arbitrary number of input warriors as "seeds". To evolve a warrior against Dwarf, using -all of the included warriors as seeds, and storing the outputs from each round in a directory named output, run - mpirun bin/evolver warriors/dwarf.red output warriors/*.red - -As with tabulator, evolver requires at least two processes, and you will have to oversubscribe if you only have one core. + mpirun bin/tabulator warriors/*.red diff --git a/tabulator-mpi/mpi.txt b/tabulator-mpi/mpi.txt deleted file mode 100644 index 9ee7ff4..0000000 --- a/tabulator-mpi/mpi.txt +++ /dev/null @@ -1,15 +0,0 @@ -message tag 0: - head -> worker - four ints: - warrior 1 index - warrior 2 index - start round - end round (exclusive, 0 for exit) - -message tag 1: - worker -> head - four ints: - warrior 1 index - warrior 2 index - w1 wins against w2 - w2 wins against w1 diff --git a/tabulator-mpi/source.cpp b/tabulator-mpi/source.cpp deleted file mode 100644 index f7fe54f..0000000 --- a/tabulator-mpi/source.cpp +++ /dev/null @@ -1,214 +0,0 @@ -#include <lib94/lib94.hpp> -#include <iostream> -#include <fstream> -#include <sstream> -#include <cstdio> -#include <vector> -#include <mpi.h> - -const int default_rounds_per_chunk = 250; -const int steps_to_tie = 1000000; - -int error(std::string msg, int rank) { - if (rank == 0) { - std::cerr << msg << std::endl; - return 1; - } - return 0; -} - -int main(int argc, char **argv) { - - MPI_Init(&argc, &argv); - - int rank; - int size; - - MPI_Comm_rank(MPI_COMM_WORLD, &rank); - MPI_Comm_size(MPI_COMM_WORLD, &size); - - if (size < 2) - return error("this must be run under mpi with at least two processes.", rank); - - std::vector<std::string> filenames = {}; - int rounds_per_chunk = default_rounds_per_chunk; - - for (int i = 1; i < argc; ++i) { - if (atoi(argv[i]) > 0) - rounds_per_chunk = atoi(argv[i]); - else - filenames.push_back(argv[i]); - } - - if (filenames.size() == 0) - return error("no files specified.", rank); - if (filenames.size() == 1) - return error("only one file specified.", rank); - - int count = filenames.size(); - lib94::warrior **warriors = new lib94::warrior *[count]; - for (int i = 0; i < count; ++i) { - std::ifstream file(filenames[i]); - if (!file) - return error("could not open " + filenames[i] + ".", rank); - std::stringstream stream; - stream << file.rdbuf(); - try { - warriors[i] = lib94::compile_warrior(stream.str()); - } - catch (const lib94::compiler_exception &ex) { - return error("could not compile " + filenames[i] + ": " + ex.message + " on line " + std::to_string(ex.source_line_number) + ".", rank); - } - } - - //w1 * count + w2 - int *placements = new int[count * count]; - for (int i = 0; i < count; ++i) - for (int j = 0; j < count; ++j) { - int p = LIB94_CORE_SIZE - warriors[i]->instructions.size() - warriors[j]->instructions.size() + 1; - if (p <= 0) - return error(filenames[i] + " and " + filenames[j] + " do not fit in core together.", rank); - placements[i * count + j] = p; - } - - if (rank == 0) { - - std::cerr << "\x1b""7\x1b[?47h\x1b[2J" << std::flush; - - //w1 * count + w2 - int *wins_array = new int[count * count]; - for (int i = 0; i < count * count; ++i) - wins_array[i] = 0; - - for (int i = 0; i < count; ++i) - for (int j = 0; j < count; ++j) { - if (i == j) - continue; - int rounds = placements[i * count + j]; - for (int r = 0; r < rounds; r += rounds_per_chunk) { - int e = std::min(r + rounds_per_chunk, rounds); - - MPI_Status status; - int buffer[4]; - MPI_Recv(buffer, 4, MPI_INT, MPI_ANY_SOURCE, 1, MPI_COMM_WORLD, &status); - int source = status.MPI_SOURCE; - - wins_array[buffer[0] * count + buffer[1]] += buffer[2]; - wins_array[buffer[1] * count + buffer[0]] += buffer[3]; - - buffer[0] = i; - buffer[1] = j; - buffer[2] = r; - buffer[3] = e; - MPI_Send(buffer, 4, MPI_INT, source, 0, MPI_COMM_WORLD); - - std::cerr << "\x1b[" << source << ";1Hworker " << source << ": " << warriors[i]->name << " vs " << warriors[j]->name << " rounds " << r + 1 << " to " << e << " of " << rounds << ".\x1b[0K" << std::flush; - } - } - - for (int i = 1; i < size; ++i) { - MPI_Status status; - int buffer[4]; - MPI_Recv(buffer, 4, MPI_INT, MPI_ANY_SOURCE, 1, MPI_COMM_WORLD, &status); - int source = status.MPI_SOURCE; - - wins_array[buffer[0] * count + buffer[1]] += buffer[2]; - wins_array[buffer[1] * count + buffer[0]] += buffer[3]; - - buffer[3] = 0; - MPI_Send(buffer, 4, MPI_INT, source, 0, MPI_COMM_WORLD); - std::cerr << "\x1b[" << source << ";1Hworker " << source << ": complete.\x1b[0K" << std::flush; - } - - std::cerr << "\x1b[?47l\x1b""8"; - - int col_width = 13; - for (int i = 0; i < count; ++i) - if ((int)warriors[i]->name.size() > col_width) - col_width = (int)warriors[i]->name.size(); - - printf(" %*s", col_width, ""); - for (int i = 0; i < count; ++i) - printf(" | %*s", col_width, warriors[i]->name.c_str()); - putchar('\n'); - for (int k = 0; k < col_width + 2; ++k) - putchar('-'); - for (int i = 0; i < count; ++i) { - putchar('+'); - for (int k = 0; k < col_width + 2; ++k) - putchar('-'); - } - putchar('\n'); - for (int j = 0; j < count; ++j) { - printf(" %*s", col_width, warriors[j]->name.c_str()); - for (int i = 0; i < count; ++i) - if (i == j) - printf(" | %*s", col_width, ""); - else - printf(" | %5d / %5d%*s", wins_array[i * count + j], placements[i * count + j] * 2, col_width - 13, ""); - putchar('\n'); - } - - } - - else { - - lib94::instruction core_background = { - .op = lib94::DAT, - .mod = lib94::F, - .amode = lib94::DIRECT, - .bmode = lib94::DIRECT, - .anumber = 0, - .bnumber = 0 - }; - - int buffer[4] = { 0, 0, 0, 0 }; - MPI_Send(buffer, 4, MPI_INT, 0, 1, MPI_COMM_WORLD); - - while (true) { - - MPI_Recv(buffer, 4, MPI_INT, 0, 0, MPI_COMM_WORLD, 0); - if (buffer[3] == 0) - break; - - auto w1 = warriors[buffer[0]]; - auto w2 = warriors[buffer[1]]; - int start_offset = w1->instructions.size(); - int w1_wins = 0; - int w2_wins = 0; - - const lib94::warrior *const wlist[2] = { w1, w2 }; - int offsets[2] = {}; - - for (int round = buffer[2]; round < buffer[3]; ++round) { - - offsets[1] = start_offset + round; - lib94::clear_core(core_background); - lib94::init_round(wlist, 2, offsets, false); - - for (int step = 0; step < steps_to_tie; ++step) { - auto lost = lib94::single_step<false>(); - if (lost == w1) { - ++w2_wins; - break; - } - if (lost == w2) { - ++w1_wins; - break; - } - } - - } - - buffer[2] = w1_wins; - buffer[3] = w2_wins; - MPI_Send(buffer, 4, MPI_INT, 0, 1, MPI_COMM_WORLD); - - } - - } - - MPI_Finalize(); - return 0; - -} diff --git a/tabulator/tabulator.cpp b/tabulator/tabulator.cpp new file mode 100644 index 0000000..60cd680 --- /dev/null +++ b/tabulator/tabulator.cpp @@ -0,0 +1,159 @@ +#include <lib94/lib94.hpp> +#include <iostream> +#include <fstream> +#include <sstream> +#include <cstdio> +#include <vector> + +const int steps_to_tie = 1000000; + +int error(std::string msg, int rank) { + if (rank == 0) { + std::cerr << msg << std::endl; + return 1; + } + return 0; +} + +constexpr lib94::instruction background_instruction = { + .op = lib94::DAT, .mod = lib94::F, + .amode = lib94::DIRECT, .bmode = lib94::DIRECT, + .anumber = 0, .bnumber = 0 +}; + +int main(int argc, char **argv) { + + MPI_Init(&argc, &argv); + + int rank; + int size; + + MPI_Comm_rank(MPI_COMM_WORLD, &rank); + MPI_Comm_size(MPI_COMM_WORLD, &size); + + lib94::seed_prng(time(0) + rank); + + std::vector<std::string> filenames = {}; + + for (int i = 1; i < argc; ++i) + filenames.push_back(argv[i]); + + if (filenames.size() == 0) + return error("no files specified.", rank); + if (filenames.size() == 1) + return error("only one file specified.", rank); + + int count = filenames.size(); + lib94::warrior **warriors = new lib94::warrior *[count]; + for (int i = 0; i < count; ++i) { + try { + warriors[i] = lib94::compile_warrior_from_file(filenames[i]); + } + catch (const lib94::compiler_exception &ex) { + return error("could not compile " + filenames[i] + ": " + ex.message + " on line " + std::to_string(ex.source_line_number) + ".", rank); + } + if (!warriors[i]) + return error("could not open " + filenames[i] + ".", rank); + } + + int **wins_against = new int *[count]; + for (int i = 0; i < count; ++i) + wins_against[i] = new int[count]; + + int **rounds_against = new int *[count]; + for (int i = 0; i < count; ++i) + rounds_against[i] = new int[count]; + + for (int i = 0; i < count; ++i) + for (int j = i + 1; j < count; ++j) { + + const lib94::warrior *w1 = warriors[i]; + const lib94::warrior *w2 = warriors[j]; + + if (rank == 0) + std::cout << "running " << w1->name << " vs " << w2->name << "..." << std::endl; + + int w1_wins, w2_wins, rounds; + lib94::tabulate_mpi<true>(background_instruction, w1, w2, steps_to_tie, w1_wins, w2_wins, rounds, MPI_COMM_WORLD); + + if (rank == 0) + std::cout + << "results:\n " << w1->name << ": " << w1_wins << "\n " + << w2->name << ": " << w2_wins << "\n ties: " + << (rounds - w1_wins - w2_wins) << "\n\n"; + + wins_against[i][j] = w1_wins; + wins_against[j][i] = w2_wins; + + rounds_against[i][j] = rounds; + rounds_against[j][i] = rounds; + + } + + if (rank == 0) { + + unsigned column_width = 0; + unsigned name_width = 0; + for (int i = 0; i < count; ++i) + if (warriors[i]->name.size() > name_width) { + name_width = warriors[i]->name.size(); + column_width = name_width; + } + + unsigned number_width = 0; + for (int i = 0; i < count; ++i) + for (int j = 0; j < count; ++j) + if (i != j) { + unsigned width = std::to_string(rounds_against[i][j]).size(); + if (width > number_width) + number_width = width; + if (width * 2 + 3 > column_width) + column_width = width * 2 + 3; + } + + for (int i = 0; i < count; ++i) + warriors[i]->name.insert(0, column_width - warriors[i]->name.size(), ' '); + + std::string spaces, dashes; + spaces.resize(column_width, ' '); + dashes.resize(column_width, '-'); + + std::string first_spaces; + first_spaces.resize(name_width, ' '); + std::cout << ' ' << first_spaces; + for (int i = 0; i < count; ++i) { + std::cout << " | " << warriors[i]->name; + } + + std::string first_dashes; + first_dashes.resize(name_width, '-'); + std::cout << "\n-" << first_dashes; + for (int i = 0; i < count; ++i) + std::cout << "-+-" << dashes; + std::cout << "-\n"; + + for (int i = 0; i < count; ++i) { + std::string name = warriors[i]->name; + name.erase(0, column_width - name_width); + std::cout << ' ' << name; + for (int j = 0; j < count; ++j) + if (i == j) + std::cout << " | " << spaces; + else { + std::string num = std::to_string(wins_against[j][i]); + std::string den = std::to_string(rounds_against[j][i]); + num.insert(0, number_width - num.size(), ' '); + den.insert(0, number_width - den.size(), ' '); + std::string content = num + " / " + den; + content.insert(0, column_width - content.size(), ' '); + std::cout << " | " << content; + } + std::cout << '\n'; + } + + } + + MPI_Finalize(); + return 0; + +} |