From 6c439e8b57f1cc3efef154b5032e86d068de261e Mon Sep 17 00:00:00 2001 From: Kjetil Orbekk Date: Mon, 10 Aug 2015 15:52:52 -0400 Subject: New scheduling algorithm in C++. --- scheduling/scheduling.cc | 265 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 265 insertions(+) create mode 100644 scheduling/scheduling.cc diff --git a/scheduling/scheduling.cc b/scheduling/scheduling.cc new file mode 100644 index 0000000..bd1f6bb --- /dev/null +++ b/scheduling/scheduling.cc @@ -0,0 +1,265 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +using std::string; +using std::vector; +using std::map; + +int kIterations = 1000000; + +vector Split(const string& message, char deliminator) { + std::istringstream stream(message); + vector result; + string tmp; + while (std::getline(stream, tmp, deliminator)) { + result.emplace_back(tmp); + } + return result; +} + +struct Player { + Player(const string id, const int rank, const int desired_games) + : id_(id), rank_(rank), desired_games_(desired_games) {} + Player() = default; + Player(const Player& other) = default; + Player& operator=(const Player& other) = default; + + string id_; + int rank_; + int desired_games_; + + string DebugString() const { + std::ostringstream output; + output << "Player(id=" << id_ << ", rank=" << rank_ + << ", desired_games=" << desired_games_ << ")"; + return output.str(); + } + + string ToString() const { + std::ostringstream output; + output << id_ << " (" << std::abs(rank_) << (rank_ > 0 ? 'd' : 'k') + << ")"; + return output.str(); + } +}; + +std::unique_ptr ParsePlayer(const vector& data, int round) { + const int kPlayerTokens = 7; + if (data.size() < kPlayerTokens) { + return nullptr; + } + string id = data[0]; + std::istringstream rank_stream(data[2]); + int rank; + rank_stream >> rank; + char sign; + rank_stream >> sign; + if (sign != 'k' && sign != 'd') { + return nullptr; + } + if (sign == 'k') { + rank = -rank; + } + std::istringstream desired_games_stream(data[3 + round]); + int desired_games; + desired_games_stream >> desired_games; + return std::unique_ptr(new Player(id, rank, desired_games)); +} + +int RankDifference(const Player& p1, const Player& p2) { + int r1 = p1.rank_; if (r1 < 0) { r1++; } + int r2 = p2.rank_; if (r2 < 0) { r2++; } + return std::abs(r1 - r2); +} + +bool LegalMatch(const Player& p1, const Player& p2) { + return RankDifference(p1, p2) < 10; +} + +template +vector> GenerateMatches( + GeneratorT generator, + vector players) { + std::list> possible_matches; + for (int i = 0; i < players.size(); i++) { + for (int j = 0; j < players.size(); j++) { + // X vs. y and y vs. x is the same match. Also excludes x vs. x. + Player* p1 = &players[i]; + Player* p2 = &players[j]; + if (i < j && LegalMatch(*p1, *p2)) { + possible_matches.emplace_back(std::tuple(i, j)); + } + } + } + + vector> result; + while (!possible_matches.empty()) { + std::uniform_int_distribution distribution( + 0, possible_matches.size() - 1); + int i = distribution(generator); + auto it = possible_matches.begin(); + std::advance(it, i); + Player* p1 = &players[std::get<0>(*it)]; + Player* p2 = &players[std::get<1>(*it)]; + possible_matches.erase(it); + + if (p1->desired_games_ && p2->desired_games_) { + result.push_back(std::tuple(p1->id_, p2->id_)); + p1->desired_games_--; + p2->desired_games_--; + } + } + return result; +} + +double Score(const map& players, + const vector> matches) { + double score = 0.0; + for (const auto& match : matches) { + const Player& p1 = players.at(std::get<0>(match)); + const Player& p2 = players.at(std::get<1>(match)); + double rankScore = 500 - 10 * pow(RankDifference(p1, p2), 1.5); + score += rankScore; + } + return score; +} + +struct Match { + Player white_; + Player black_; + double komi_; + int handicap_; + + string ToString() const { + std::ostringstream stream; + stream << white_.ToString() << " vs. " << black_.ToString(); + stream << " (komi: " << komi_; + if (handicap_) { + stream << "; H" << handicap_; + } + stream << ")"; + return stream.str(); + } + + string TabSeparated() const { + std::ostringstream stream; + stream << white_.id_ << "\t"; + stream << black_.id_ << "\t"; + if (handicap_) { + stream << "H" << handicap_ << "\t"; + } else { + stream << "None\t"; + } + stream << komi_; + return stream.str(); + } +}; + +template +Match CreateMatch(GeneratorT generator, const Player& p1, const Player& p2) { + Player white; + Player black; + double komi = 0.0; + int handicap = 0; + + if (p1.rank_ == p2.rank_) { + std::bernoulli_distribution distribution(0.5); + komi = 7.5; + if (distribution(generator)) { + white = p1; + black = p2; + } else { + white = p2; + black = p1; + } + } else { + komi = 0.5; + if (p1.rank_ > p2.rank_) { + white = p1; + black = p2; + } else { + white = p2; + black = p1; + } + if (RankDifference(p1, p2) > 1) { + handicap = std::min(9, RankDifference(p1, p2)); + } + } + return {white, black, komi, handicap}; +} + +int main() { + const int kRound = 1; + vector players; + + string line; + while (std::getline(std::cin, line)) { + std::unique_ptr player = ParsePlayer(Split(line, '\t'), kRound); + printf("%s\n", player->DebugString().c_str()); + if (player) { + players.emplace_back(*player); + } else { + printf("Failed to parse player: %s\n", line.c_str()); + } + } + + // Needed by Score(). + map playerMap; + for (const Player& player : players) { + playerMap[player.id_] = player; + } + + // Generate randomized pairings and pick the best one. + vector> best_matches; + double best_score = std::numeric_limits::lowest(); + for (int i = 0; i < kIterations; i++) { + if (i && i % (kIterations / 10) == 0) { + printf("%.2f%% done\n", 100.0 * i / kIterations); + } + std::random_device rd; + std::mt19937 generator(rd()); + auto matches = GenerateMatches(generator, players); + double score = Score(playerMap, matches); + if (score > best_score) { + best_score = score; + printf("Iteration(%d): New best score(%.3f)\n", i, score); + best_matches = matches; + } + } + + // Designate colors, handicap, komi, and print a sorted list of matches. + vector finalized_matches; + for (auto pair : best_matches) { + std::random_device rd; + std::mt19937 generator(rd()); + const Player& p1 = playerMap[std::get<0>(pair)]; + const Player& p2 = playerMap[std::get<1>(pair)]; + finalized_matches.emplace_back(CreateMatch(generator, p1, p2)); + } + auto match_comparator = [](const Match& m, const Match& n) -> bool { + return (m.white_.rank_ + m.black_.rank_) > + (n.white_.rank_ + n.black_.rank_); + }; + std::sort(finalized_matches.begin(), finalized_matches.end(), + match_comparator); + + std::ostringstream export_filename; + export_filename << "matches_r" << kRound << ".tsv"; + std::ofstream export_file; + export_file.open(export_filename.str()); + for (const Match& match : finalized_matches) { + printf("%s\n", match.ToString().c_str()); + export_file << match.TabSeparated() << "\n"; + } +} -- cgit v1.2.3