チーム分けアルゴリズム

始めに

人狼のwebゲームを作っていたら、ランダム配役が必要になりました。

そこで簡単に作ったランダム配役(チーム分け)アルゴリズムをメモしときます。

1000人以下の人数ならまあ動くと思います。

コード紹介

人狼の配役で必要なことは、

• 市民や人狼等の役職の人数(ルール決めでプレイヤーが設定してくれる)。
• 上に基づくランダムなチーム分け。

今回は、簡易化のために、市民と人狼のランダム配役のアルゴリズム(JavaScript版)を紹介します。

ただし、同じようにループを増やすだけで、役職が増えたときにも対応できます。

/* 役振り */
var roles = [];
for(var i = 0; i < n; i++)
{
    roles.push(-1);
}

/* 市民 */
for(var i = 0; i < nCiv; i++)
{
    var a = Math.floor(Math.random()*1027);
    var a2 = a%n;
    while(roles[a2] != -1)
    {
        if(a2+1 >= n)
        {
            a2 = 0;
        }
        else
        {
            a2 += 1;
        }
    }
    roles[a2] = 200; //市民の役職番号
}

/* 人狼 */
for(var i = 0; i < nWerewolf; i++)
{
    var a = Math.floor(Math.random()*1027);
    var a2 = a%n;
    while(roles[a2] != -1)
    {
        if(a2+1 >= n)
        {
            a2 = 0;
        }
        else
        {
            a2 += 1;
        }
    }
    roles[a2] = 300; //人狼の役職番号
}

• n: プレイヤーの合計人数
• nCiv: 市民の人数
• nWerewolf: 人狼の人数
• つまり、n = nCiv + nWerewolf
• 200: 市民を示す
• 300: 人狼を示す

このコードを実行すると、roles[]のなかに、ランダムな順番でnCiv個の200とnWerewolf個の300が入ります。

アルゴリズム解説

今回は、あまり効率は良くないが簡単に書けるアルゴリズムなので、理解するのは非常に簡単です。

最初のループでroles[n]の全ての要素に-1を入れています。

つまり、-1が入っている要素はまだ役職が割り振られていないことを示します。

次に、

var a = Math.floor(Math.random()*1027);
var a2 = a%n;

をすることで、a2に0以上n-1以下のランダムな数字を割り当てます。
(1027のところはnよりかなり大きい数字であればなんでも良い(10n以上が好ましい))

その下の処理で、roles[a2]に役職が未割り当て(-1)なら割り当て、

割り当ててある場合は、0以上n-1以下の間で未割り当ての要素を見つけるまで次の要素へ進むという処理をしてあります。

これで各役職につき、その人数分ループしてあげればroles[]に全ての役職がランダムに割り振られます。

役職の数がn個、1役職割り振るのに最大でn-1回ループします。

つまり、このアルゴリズムはO(n^2)の処理速度ということになります。

最後に

このアルゴリズムはO(n^2)の処理速度でした。

あまり効率が良いとは言えませんが、人狼のプレイはせいぜい10人程度なので、十分高速と言えます。

もし1000人以上の人数をチーム分けしようと思うと、1000^2 = 1,000,000ループと処理が非常に遅くなってきます。

これ以上の人数をチーム分けしたい方は、別のアルゴリズムを使う必要がありそうです。

逆に少人数ならば、理解しやすく簡単に書けるこのアルゴリズムでも良いでしょう。