こんばんわ、おはようございます。最近は田んぼと狩りを交互に行き来する日々です。谷脇です。
この記事はTech KAYAC Advent Calendar 2020の8日目の記事です。昨日に引き続きやっていきます。
これまでのあらすじ
- eスポーツ大会を誰でも！かんたんに！開ける！参加できる！Tonamelでダブルエリミネーション形式を実装しました
- ついでにシングルエリミネーション形式も変えたので、まずそこでキレイにトーナメント表を組むときのアルゴリズムの話をしました
というわけで、今日は「圧縮と展開」と「ダブルエリミネーション敗者サイドの組み方」についての話をしていきます。
圧縮と展開
きれいなトーナメント表は出来ましたが、前のトーナメント表には出来て、このトーナメント表には出来ないことが生じました。Tonamel内ではシード編集と呼ばれる機能で、あえて偏りをもたせたトーナメント表を作成する機能です。
前のシングルエリミネーションではBYEがあったので、BYEとの入れ替えを繰り返すと偏りをもたせたトーナメント表を作成することが出来ました。しかし新しいシングルエリミネーションでは、初期状態にBYEは存在しません。というわけで、編集時に前のシングルエリミネーションと同様になるようにしました。私はこれを"展開"と言っています。また、展開できるんだから元に戻さないといけません。それもTonamelで出来ます。私は"圧縮"と呼んでいます。
これも詳細なアルゴリズムは避けますが、そんなにキレイではなく様々なケースごとに分岐したりやることを変えるような泥臭いやつです。
泥臭いやつにはバグがつきもの。というわけでテストも書いています。テストは圧縮と展開の前後で同じ結果になるかどうかなどを見ていたり、圧縮の結果をgraphvizのDOT形式で保存しておいて、修正で圧縮の内容が変化したときにテストがコケるようになっています。Golden Testingというやつです。
また、結果を目視で確認できるように、テストでgraphvizでレンダリングしたグラフをsixelで表示できるようにしています。
圧縮と展開があることでこんな極端なトーナメント表も組めてしまいます。
敗者サイドの組み方
さて、本丸のダブルエリミネーションです。ダブルエリミネーションはシングルエリミネーションの拡張として実装しています。ですが、簡単な拡張で済んだわけではなく、開発期間中に3回書き直しています。ダブルエリミネーションもまた"本質的に難しい"機能だったからです。
ダブルエリミネーション形式の必要条件は「1度までなら負けられる」ですが、「同じ相手と出来るだけ当たらないようにする」というのも十分条件としてあります。敗者サイドで同じ相手との2度目の対戦が起こってしまうことをDouble Jeopardyと呼びます。この言葉はベータ期間中にお問い合わせ経由でユーザさんに教えてもらいました。当時はDouble Jeopardyを防ぐ仕組みはありましたが、言葉を知らずに実装しているのが手探り感満載なのを演出しております...。言葉がわからんとググれないんですよねえ...。サーベイ不足というのもありますが、実装当時は発明するしか無いという感じでした。
まず初めに「同じ相手と出来るだけ当たらないようにする」仕組みとして実装した手法は、対戦の組み合わせのグラフ上での距離関数を実装した上で、距離関数をコストにしたときにラウンドごとに組み合わせのコストの合計が最大になるように、焼きなまし法で組み合わせ探索を行う方法でした。大体いい感じの結果にはなるのですが、焼きなまし法は乱択アルゴリズムなので、敗者サイドを生成するごとに結果がブレてしまうことがありました。ブレずに収束させようとして試行回数を増やすと時間が余計にかかってしまうのが難点なのと、特定のケースで組み合わせを調整をしたいときに、距離関数をいじるしか手法がないので、他のケースまで影響が及んでしまうのも難しい点でした。
2つ目の実装は、世間のダブルエリミネーションのトーナメント表を見ながらひたすらケースごとに実装していく泥臭いものです。人のトーナメント表でも上から割り当てていくような、単純なものではなく、勝者サイド上での対角線で割り当てていくなどの工夫をする必要がありました。
さらに人数が多いともっと複雑に入れ替えています。
さらに、ではない中途半端な人数だと、敗者サイド1回戦に勝者サイド1回戦だけではなく勝者サイド2回戦の人たちも混ざってきます。
さらにさらに、特定のケースでは、勝者サイド2回戦の敗者を中途半端に2回戦に回すことになります...。
この辺を地道に地道に潰していきました。
3度目の書き換えは、すべてのケースを実装した時点でぐちゃぐちゃになっていたので、整理するためにリファクタリングしたことでした。
偏りがあるトーナメント表での敗者サイド
さてここまででよかったね、となるのですが、Tonamelは勝者サイドのトーナメント表で極端に偏ったトーナメント表を作れるのでした。さてどうしたものか...。
悩んだ末取った手段としては、偏った勝者サイドトーナメント表を展開して人トーナメントにした上で、敗者サイドを生成し、勝者サイドと敗者サイドを両方に圧縮をかけることで、解決しました。
ただ、世間でこういった事例を私は見つけたことがないので、この手法が正解かはわかりません。トーナメント表にこだわりを持つ方は是非Tonamelを使用してフィードバックをサイトのお問合せフォームなどからください。
まとめ
- Tonamelのシングルエリミネーション形式を再実装した
- そういえばシングルエリミネーションの切り替えはオンラインでやったのですが、これも色々考えることがあったのでまた別の機会に
- Tonamelのダブルエリミネーション形式を新規実装した
- 敗者サイドの実装詳細が知りたい方は...君も面白法人になるんだよ...
- 頭を使ったり脳筋で殴ったり、大変でした
感情的には最高のものが作れたと思いつつ、理性的にはまだまだ機能的に足りない点がたくさんあるので、今回やったことをベースにどんどん発展させていきたいですね。
明日も誰かが書きます！
