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

2021 年 12 月 23 日katsura

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

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

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

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

概要
作ったもの
どうやって作ったか
1. 問題定義
2. 最適解探索のためにやったこと
オプションモードの実装
1. 送迎会モード
2. ２チームモード
サンプルコード
最後に

作ったもの

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

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

どうやって作ったか

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

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

問題定義

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

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

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

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

１．ランダムな部屋割をn個作成し、一番良いものを選ぶ（乱択アルゴリズム）

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

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

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

２．ランダムに席の交換を行い、部屋割を良くしていく（焼きなまし法）

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

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

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

３．チューニング

ここまで実装したところで動かしたところ、１・２を上手く組み合わせることで、最も理想的な部屋割（スコア＝０）を見つけることが出来ました。

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

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

オプションモードの実装

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

送迎会モード

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

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

２チームモード

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

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

サンプルコード

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

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

|-- css
|   `-- style.css
|-- index.html
`-- js
    |-- main.js
    |-- time_table.js
    `-- time_table_controller.js

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

js/time_table.js

export class TimeTable {
    /** @type {number} 部屋数 */
    room_num = 0

    /** @type {number[]} 部屋ごとの人数 */
    room_members_num = []

    /** @type {Object}} 通し番号のIDから、部屋ID・席IDへのマッピング */
    id_2_place = {}

    /** @type {Object} 部屋割りのメイン情報 */
    table = {}

    /** @type {Object} 一時退避用 */
    old_table = {}

    /** @type {Object}  メンバーの名前一覧 */
    member_label = {}

    /**
     * 
     * @param {*} max_member_num 参加者全員
     * @param {*} core_member_num 必須メンバー
     * @param {*} room_max_member_num 部屋の最大人数 
     * @param {*} max_time 部屋割りの数（席替え回数＋１）
     */
    constructor(
        max_member_num = 16,
        core_member_num = 1,
        room_max_member_num = 4,
        max_time = 5,
    ) {
        this.init(max_member_num, core_member_num, room_max_member_num, max_time)
    }
    init(
        max_member_num = 16,
        core_member_num = 1,
        room_max_member_num = 4,
        max_time = 5,
        has_team = false,
        team1_num = 8,
    ){
        this.max_member_num = max_member_num
        this.core_member_num = core_member_num
        this.room_max_member_num = room_max_member_num
        this.max_time = max_time
        this.has_team = has_team
        this.team1_num = team1_num
        this.initRoomNum();
        this.initTable();
    }
    // 部屋ごとの人数の初期化
    initRoomNum() {
        // 部屋の数
        this.room_num = Math.ceil(this.max_member_num / this.room_max_member_num)
        // 部屋ごとの人数
        this.room_members_num = []
        for (let r = 0; r < this.room_num; r++) {
            if (this.room_num * (this.room_max_member_num - 1) + r < this.max_member_num) {
                this.room_members_num.push(this.room_max_member_num)
            } else {
                this.room_members_num.push(this.room_max_member_num - 1)
            }
        }
        let i = 0
        for (let r = 0; r < this.room_num; r++) {
            for (let m = 0; m < this.room_members_num[r]; m++) {
                this.id_2_place[i] = {"r": r, "m": m}
                i++
            }
        }
    }
    // 部屋割用のテーブルの初期化
    initTable() {
        this.table = []
        for (let t = 0; t < this.max_time; t++) {
            let rooms = []
            let member_id = 0
            for (let r = 0; r < this.room_num; r++) {
                let room = []
                for (let m = 0; m < this.room_members_num[r]; m++) {
                    room.push(member_id)
                    member_id++
                }
                rooms.push(room)
            }
            this.table.push(rooms)
        }
    }
    // メンバーの名前を改行区切りで読み込み
    setMemberLabelFromCSV(csv_text){
        for (let m = 0; m < this.max_member_num; m++) {
            this.member_label[m] = `メンバー${(m + 1)}`
            if (m  {return item != ""})
        for (let i = 0; i < csv.length; i++ ){
            if (csv[i] != ""){
                this.member_label[i] = csv[i]
            }
        }
    }
    // スコアを計算
    calcScore() {
        const pairs = Array(this.max_member_num)
        this.team_duplicate_count = Array(this.max_member_num)
        this.member_duplicate_count = Array(this.max_member_num)
        const scores = Array(this.max_member_num)
        for (let m = 0; m < this.max_member_num; m++) {
            pairs[m] = Array(this.max_member_num).fill(0)
            this.team_duplicate_count[m] = 0
        }

        // メンバー同士が何回同じ部屋になったかをカウント
        for (let t = 0; t < this.max_time; t++) {
            for (let r = 0; r < this.room_num; r++) {
                for (let m1 = 0; m1 < this.room_members_num[r] - 1; m1++) {
                    for (let m2 = m1 + 1; m2 < this.room_members_num[r]; m2++) {
                        const m1_id = this.table[t][r][m1]
                        const m2_id = this.table[t][r][m2]
                        pairs[m1_id][m2_id]++
                        pairs[m2_id][m1_id]++
                    }
                }
            }
        }

        // ２チームモードで同じチームの人が同じ部屋になった回数をカウント
        if (this.has_team === true) {
            const center = (this.team1_num - 0.5)
            for (let t = 0; t < this.max_time; t++) {
                for (let r = 0; r < this.room_num; r++) {
                    for (let m1 = 0; m1 < this.room_members_num[r] - 1; m1++) {
                        for (let m2 = m1 + 1; m2 < this.room_members_num[r]; m2++) {
                            const m1_id = this.table[t][r][m1]
                            const m2_id = this.table[t][r][m2]
                            if (Math.sign(m1_id - center) * Math.sign(m2_id - center) == 1) {
                                this.team_duplicate_count[m1_id]++;
                                this.team_duplicate_count[m2_id]++;
                            }
                        }
                    }
                }
            }
        }

        let score = 0
        for (let m1 = 0; m1 < this.max_member_num; m1++) {
            let core_ratio = 1
            if (m1 < this.core_member_num) {
                // 歓送迎会補正
                core_ratio = 100
            }
            // 被り値を元にスコアを計算
            this.member_duplicate_count[m1] = 0
            for (let m2 = 0; m2 < this.max_member_num; m2++) {
                score += Math.max(pairs[m1][m2] - 1, 0) * Math.max(pairs[m1][m2] - 1, 0) * core_ratio
                this.member_duplicate_count[m1] += Math.max(pairs[m1][m2] - 1, 0) * Math.max(pairs[m1][m2] - 1, 0) * core_ratio
            }

            // 2チーム補正
            if (this.has_team === true) {
                score += (this.team_duplicate_count[m1] * this.team_duplicate_count[m1])
            }
        }
        return score
    }
    // 1. 乱択アルゴリズムでランダムに配置
    generateByRandom1(){
        for (let t = 0; t < this.max_time; t++) {
            this.table[t][0][0] = 0
        }
        let id = 1
        for (let t = 0; t < this.max_time; t++) {
            for (let m = 1; m = this.max_member_num) {
                    id = 1
                }
            }
        }

        for (let t = 0; t  { return this.table[t][0].includes(val) == false })
            let n = rest.length
            for (let r = 1; r < this.room_num; r++) {
                for (let m = 0; m < this.room_members_num[r]; m++) {
                    let k = Math.floor(Math.random() * n);
                    let member_id = rest.splice(k, 1)[0]
                    n--
                    this.table[t][r][m] = member_id
                }
            }
        }
    }
    // 2. 焼き鈍し法でスコア改善する変更を探索
    random2oneStep() {
        let t = Math.floor(Math.random() * this.max_time)
        let k1 = Math.floor(Math.random() * (this.max_member_num - 1)) + 1
        let k2 = Math.floor(Math.random() * (this.max_member_num - 1)) + 1
        if (k1 == k2) {
            return
        }
        this.swapMember(t, k1, k2)

        this.calcScore()
        let score = this.calcScore()
        if (score  (new Date()).getTime()){
            this.generateByRandom1ms(200)
            let before_score = this.calcScore();
            for (let i = 0; i  (new Date()).getTime()) {
            for (let i = 0; i < min_steps; i++) {
                this.generateByRandom1()
                let score = this.calcScore()
                if (score  (new Date()).getTime()) {
            for (let i = 0; i < min_steps; i++){
                this.random2oneStep()
            }
            if (this.best_score == 0){
                return;
            }
        }
    }
    // 十分な結果が得られなかった場合に、追加の探索を実行するためのメソッド
    additionalSearch(){
        let before_score = this.calcScore();
        for (let i = 0; i < 10; i++) {
            this.generateByRandom2ms(500)
            const after_score = this.calcScore();
            if (before_score == after_score) {
                break;
            }
            before_score = after_score
        }
    }

    // 以降は各種値の取得など
    getMemberLabel(m){
        if (m < this.core_member_num) {
            return "★" + this.member_label[m]
        } else {
            return this.member_label[m]
        }
    }
    getMemberDuplicateCount(m){
        return this.member_duplicate_count[m]
    }
    getMaxMemberNum(){
        return this.max_member_num
    }
    getMaxTime(){
        return this.max_time
    }
    getRoomNum(){
        return this.room_num
    }
    getRoomLabel(r){
        const base = String.fromCharCode(65 + r % 26)
        if (r / 26 < 1) {
            return base
        } else {
            return base + (Math.floor(r / 26) + 1)
        }
    }
    getTable(t, r){
        return this.table[t][r]
    }
}

js/time_table_controller.js

import { TimeTable } from './time_table.js'

export class TimeTableController {
    constructor(){
        this.time_table = new TimeTable()
        this.element_id = "#time_table_result_0"
    }
    init(){
        this.setupEvents();
    }
    setupEvents(){
        this.time_table.setMemberLabelFromCSV($("#member_label_csv").val())
        this.clearTable()

        $('#generate_auto').click(() => {
            this.parseSettings()
            this.clearTable()
            window.setTimeout(() => {
                this.time_table.generateAuto()
                this.refresh()
                $('#additional_search').removeClass('reveal')
            }, 50);
        })
        $('#additional_search').click(() => {
            this.clearTable()
            window.setTimeout(() => {
                this.time_table.additionalSearch()
                this.refresh()
            }, 50);
        })
    }
    parseSettings(){
        this.time_table.init(
            parseInt($("#max_member_num").val()),
            parseInt("0" + $("#has_core_member:checked").val()),
            parseInt($("#room_max_member_num").val()),
            parseInt($("#max_time").val()),
            $("#has_team:checked").val() == 1,
            parseInt($("#team1_num").val()),
        )
        this.time_table.setMemberLabelFromCSV($("#member_label_csv").val())
    }
    refresh() {
        const element = this.getRootElement()
        element
            .empty()
            .append(`<div><span data-tooltip="0に近いほど良い部屋割です">
            スコア<i class="question circle outline icon"></i></span>：${this.time_table.calcScore()}</div>`)
            .append(this.getResultTableElement())
            .append(this.getTimeTableElement())
    }
    clearTable() {
        const element = this.getRootElement()

        element.empty()
    }
    getRootElement() {
        return $(this.element_id)
    }
    getTimeTableElement() {
        const element = $('<div></div>')
        for (let t = 0; t < this.time_table.getMaxTime(); t++) {
            element.append(this.getRoomsElement(t))
        }
        return element
    }
    getRoomsElement(t) {
        const element = $('<div class="ui"></div>')
        element.append(`<div class="ui horizontal section divider">${t + 1}回目</div>`)
        const rooms_element = $(`<table class="ui vertically grid room"></table>`)
        for (let r = 0; r < this.time_table.getRoomNum(); r++) {
            const row = $(`<tr class="row"></tr>`)
            row.append(`<th class="one wide column">${this.time_table.getRoomLabel(r)}</th>`)
            for (let m = 0; m < this.time_table.getTable(t, r).length; m++) {
                const member = this.time_table.getTable(t, r)[m]
                row.append(`<td class="three wide column">${this.time_table.getMemberLabel(member)}</td>`)
            }
            rooms_element.append(row)
        }
        element.append(rooms_element)
        return element
    }
    getResultTableElement() {
        const element = $('<table class="ui celled table"></table>')
        const tr1 = $(`<tr></tr>`)
        const tr2 = $(`<tr></tr>`)
        for (let m = 0; m < this.time_table.getMaxMemberNum(); m++) {
            tr1.append(`<th>${this.time_table.getMemberLabel(m)}</th>`)
            tr2.append(`<td>${this.time_table.getMemberDuplicateCount(m)}</td>`)
        }
        return element.append(tr1).append(tr2)
    }
}

js/main.js

import { TimeTableController } from './time_table_controller.js'

$(() => {
    let time_table_controller = new TimeTableController()
    time_table_controller.init()

});

index.html

<!DOCTYPE html>
<html>

<head>
    <meta charset="utf-8" />
    <title>zoom部屋シミュレーション</title>
    <script src="https://code.jquery.com/jquery-3.6.0.slim.min.js"
        integrity="sha256-u7e5khyithlIdTpu22PHhENmPcRdFiHRjhAuHcs05RI=" crossorigin="anonymous"></script>
    <script src="https://cdnjs.cloudflare.com/ajax/libs/semantic-ui/2.4.1/semantic.min.js"
        integrity="sha512-dqw6X88iGgZlTsONxZK9ePmJEFrmHwpuMrsUChjAw1mRUhUITE5QU9pkcSox+ynfLhL15Sv2al5A0LVyDCmtUw=="
        crossorigin="anonymous" referrerpolicy="no-referrer"></script>
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/semantic-ui/2.4.1/semantic.min.css"
        integrity="sha512-8bHTC73gkZ7rZ7vpqUQThUDhqcNFyYi2xgDgPDHc+GXVGHXq+xPjynxIopALmOPqzo9JZj0k6OqqewdGO3EsrQ=="
        crossorigin="anonymous" referrerpolicy="no-referrer" />
    <link rel="stylesheet" href="css/style.css">
    <script type="module" src="./js/main.js"></script>
</head>

<body>
    <div class="ui container">
        <h1>Zoom部屋割探索ツール</h1>
        <div class="ui  segment">
            <button id="generate_auto" class="ui primary basic button">部屋割を新規探索</button>
            <button id="additional_search" class="ui primary basic button reveal" data-tooltip="より良いスコアを探す時はこちら押して下さい。">追加探索</button>
            <div class="ui form">
                <div class="fields">
                    <div class="field">
                        <label>参加者一覧
                        </label>
                        <textarea id="member_label_csv"></textarea>
                    </div>
                    <div class="field">
                        <label>参加人数</label>
                        
                        <label>ルームの最大人数</label>
                        
                        <label>開催回数</label>
                        
                    </div>
                    <div class="field">
                        <label data-tooltip="メインの主賓が1人いる場合、その人のメンバーの被りを無くすのを優先します">
                            歓送迎会モード
                            <i class="question circle outline icon"></i>
                        </label>
                        <div class="ui checkbox">
                            
                            <label></label>
                        </div>
                    </div>
                    <div class="field">
                        <label data-tooltip="２つのチーム合同のZoom飲み会の場合。同じチームの人同士がなるべく一緒にならないようにします">
                            ２チームモード
                            <i class="question circle outline icon"></i>
                        </label>
                        <div class="ui checkbox">
                            <label></label>
                        </div>
                        <label>1チーム目の人数</label>
                        
                    </div>
                </div>
            </div>
        </div>
        <div id="time_table_result_0" class="ui segment">
            <h3 class="ui header">
                部屋割
            </h3>
            <div class="ui attached segment">
                <div class="ui horizontal section divider">１回目</div>

                <div class="ui vertically grid room">
                    <div class="row">
                        <div class="one wide column">A</div>
                        <div class="three wide column">メンバー1</div>
                        <div class="three wide column">メンバー2</div>
                        <div class="three wide column">メンバー3</div>
                        <div class="three wide column">メンバー4</div>
                    </div>
                </div>
            </div>
        </div>
    </div>

</div>

css/style.css

body {
    background-color: #DBCDAF;
    color:  #41466B;
}
th{
    background-color: #41466B;
    color: white;
}
.room tr.row:nth-child(odd) .column{
    background-color: #41466B;
}
.room tr.row:nth-child(even) .column{
    background-color: #6689B0;
}
.room tr>.column{
    color: white;
    border: white solid 0.5px;
    padding: 1em;
    
}
.ui.room>.row{
    padding-bottom: 0px;
    padding-top: 0px;

}