スイスドローのマッチングを、Python+NetworkXでおこなう話
近況 ブログの執筆をしようと思っていたのですが、早1か月が経ってしまいました。 その間、知人に頼まれてポケモンカードゲームの大会運営プラットフォームを作っていました。 UI・UXの知識があんまりないので、利用者に快適に用いてもらえるものを作るのが結構難しいです。勉強しなければ... Pythonでのスイスドローのマッチングの実装 さて、今回はその中で利用した、スイスドロー形式の大会の対戦マッチングの方法について解説したいと思います。 用いるもの Python 3.7, NetworkX 2.2 スイスドローのマッチングは、グラフ理論の「最小重み最大マッチング問題」と呼ばれる問題に当てはめて解くことができます。 参考リンク： 組合せ最適化 - 典型問題と実行方法 組合せ最適化 - 典型問題 - 重みマッチング問題 この問題も、PythonのライブラリNetworkXを使うと簡単に解くことができます。 実装の手順 ①プレイヤーをノードとしてグラフ上に配置 ②すべての未対戦の組み合わせの2ノード間に、【勝ち点の差の絶対値等】を-1倍した数値を重みとしたエッジを作成する。 (【】の中身は、大会ごとに異なると思いますので各自変えてください。なお、勝ち点→オポネントのようにタイブレイカーを導入したい場合は、後のものを十分小さい値にして重みに足し合わせればうまく行くはずです。) ③NetworkXの、「 networkx.algorithms.matching.max_weight_matching (maxcardinality=True)」を用いて、重みの合計が最大になる組み合わせを求める。 （NetworkXには最大重み(最大)マッチング問題を解く関数しか用意されていないので、②では重みを-1倍しています。） ④おわり 特に難しい点はないので、サンプルコードは用意していません。 なお、重みをそのまま用いると上位層と下位層での重みの差の扱いが同じになってしまいます。 上位層でできるだけ階段マッチングを発生させないよう、重みを2乗(した後で-1倍)してから用いると良いかもしれないです。 間違っている部...