Zoom飲みの振り分けツールを作成した話

katsura

こんにちは、プロダクトエンジニアリング部の katsura です。
みなさん、Zoom 飲み会やってますか?
先日、私の会社でも、技術系メンバーで Zoom 飲み会をしました。

Zoom 飲み会をしていて困ること、それは部屋割です。
たくさんの人が同じ Zoom の部屋にいても、しゃべらない人が出てきてしまいます。
1部屋の人数が少ないと、部屋のメンバーみんながしゃべれますが、同じメンバーとばかり話すことになってしまいます。

そこで、先日のZoom飲み会では、4人部屋を4つ作り、時間制で席替え(部屋割りの変更)していくことにしました。
「これで、いろんなメンバーとおしゃべりできる!」っと思ったのですが、うまい部屋割を作ることが難しく、同じ人と何度も同じ部屋になるケースがあったり、一度も同じ部屋にならないケースが出たりしてしまいました。

そのネタを飲み会内で話したところ、人力で最適なうまい部屋割を探すの難しいならプログラムやらせれば良いんじゃない?という話になり、面白そうだったので Zoom の部屋割を探すツール作ってみることにしました。

作ったもの

実際に作成した社内ツールの実行結果はこの様になっています。

これにより、全ての社員と1度だけ同じ部屋になる、最適な部屋割を探す事ができました。

どうやって作ったか

さて、ここから、Zoom 部屋割探索ツールをどのように作成したのかについて、説明していきたいと思います。

ちなみに、筆者は競技プログラミングには詳しくないので、競技プログラミングをやったことのある人からすると、少し物足りない点があったり、問題定義の仕方に違和感を感じる部分があるかもしれませんが、ご了承いただけると幸いです。

問題定義

今回のZoomの部屋割り探索問題について、以下のように問題定義しました

  • 参加メンバーは16人とします
  • Zoomの1部屋の人数は4人で、合計4部屋とします。
  • メンバーはいずれかの部屋に割り振られるものとします
  • 飲み会中は4回席替え(部屋割変更)を行うことにします。
  • 以下の計算で計算されるスコア(被り値)を0に近づけることを目標にします
    • あるメンバーAから見た時、他とメンバーBと同じ部屋になった数を countA,B をします
      • ※例:AとBの人が1度も同じ部屋にならなかった場合は0、AとBの人が1度だけ同じ部屋になった場合は1,AとBが2回同じ部屋になった場合は2となる
    • A・Bの組み合わせの被り値 scoreA,B=(max(countA,B – 1, 0))2  とする
      • 例1:AとBが1回も同じ部屋にならなかった場合は0
      • 2:AとBが1回同じ部屋になった場合は0
      • 例3:AとBが2回同じ部屋になった場合は1
      • 例4:AとBが3回同じ部屋になった場合は4
      • 例5:AとBが4回同じ部屋になった場合は9となる
      • ※二乗しているのは、同じ人と同じ部屋になる回数をなるべく減らしたいという気持ちを反映させるためです。
    • 各メンバー組み合わせの scoreの 合計を score_sum とし、この値を0に近づけることを目標とします

最適解探索のためにやったこと

今回は乱択アルゴリズム焼きなまし法を活用し、最適な部屋割を探すことにしました。

1.ランダムな部屋割をn個作成し、一番良いものを選ぶ(乱択アルゴリズム)

まず、最初に 乱択アルゴリズム の考えに則り、ある程度よい部屋割を探すことにしました。
今回の場合は、ランダム作成した部屋割n個を作成し、その中から1番スコアがよい部屋割を採用することにしました。
ランダムな部屋割なので、最適な部屋割を見つけられる確率は低いですが、実装は容易ですし、数をこなせばそこそこ良いパターンまでは見つけられるので、今回採用しました。

ランダムな部屋割の作成には、フィッシャーとイェーツによる手法 を参考にしつつ実装しました。
具体的には、部屋割が決まっていない人を1名ランダムに選び、空いている席の先頭に配置するというのを繰り返すだけです。

これにより、人が考える部屋割りと同じぐらい良い部屋割を探すことは出来ました。

2.ランダムに席の交換を行い、部屋割を良くしていく(焼きなまし法)

次に、 焼きなまし法 を参考にしつつ、1で見つけた部屋割を改良していく処理を実装しました。
焼きなまし法とは、ランダムにパラメータを変化させ、良い状態に変化した場合のパラメータを見つけていく手法のことです。
今回のケースでは、ランダムに席を交換していき、より良い部屋割にしていく手法を実装しました。

具体的には以下のような流れです

  1. ランダムに2席を選択
  2. 2名の席を交換した場合のスコアを計算
    1. 交換の方がスコアが良い場合は、元に戻す
    2. 交換の方がスコアが良い場合は、交換を確定する
  3. 1~2をm回実行する

3.チューニング

ここまで実装したところで動かしたところ、1・2を上手く組み合わせることで、最も理想的な部屋割(スコア=0)を見つけることが出来ました。

そこで、nやmの値をどう決めるかについて検討してみることにしました。
ただ、参加人数などのパラメータ数によって最適な値は変わって来るので、条件ごとのnやmを決めるのは大変です。
また、nやmの値によっては何分も待たされる可能性がありますし、何分も待ってまで最適な解を見つけるニーズも少ないなということもあり、nやmの具体的な値を決めるのは微妙そうでした。

今回のツールでは『最適値を見つけられるnやm決める』というのはやめて、『そこそこの時間でそこそこの結果を探す』という方向でチューニングすることにしました。
最終的な実装としては、『5秒以内で見つけられた中で最も良い結果を表示する』という時間ベースの実装を採用しています。

オプションモードの実装

実際の利用を考えたところ、他にも欲しい機能が出てきたので、実際には以下の機能の実装も行いました。

送迎会モード

指定したメンバーの被りをなるべく減らすモードです。
「新しく入ってきた人には、なるべく色んな人と話してほしい!」というシーンを想定して作成しました。

指定したメンバーに関するスコアだけ100倍にすることで、指定したメンバーがなるべく色んな人と組み合わさるような実装になっています。

2チームモード

同じチームの人同士が同じ部屋になるべくならないような組み合わせを優先してくれます。
「2チーム合同でZoom飲みするんだから、普段話さない人と話したい!」というシーンでの利用を想定して作成しました。

同じチームの人同士が同じ部屋になった場合に追加のスコアを加算することで、同じチームの人が同じ部屋になりにくいよう工夫しています。

サンプルコード

これらを元に、実際に実装したのが下記のコードとなります。

以下のように配置することを前提とした関係となっています。

Plain Text

サンプルコードはクリックすると展開されます。

js/time_table.js
JS
time_table.js
js/time_table_controller.js
JS
time_table_controller.js
js/main.js
JS
main.js
index.html
Plain Text
index.html
css/style.css
CSS
style.css

最後に

今回は、乱択アルゴリズムや焼きなまし法という、普段の業務ではあまり利用しないアルゴリズムを活用しプログラムを作成してみました。業務や趣味のプログラムばかり作っていると、どうしても使うツールやアルゴリズムが偏りがちですので、たまにはこういうネタ的なツールも作ってみるのも良いかと思いました。

katsura

Posted by katsura