本文へ移動
myowchick

最善手を選ぶと毎回同じペアが出る

毎週の雑談ペアを決めるコードを書いた。誰と誰を組ませたいかを点数にして、合計がいちばん高い組み方を選ぶ。書き上げて何度か動かしたら、毎回まったく同じペアが出てきた。入力が同じなら最善手も同じなんだから当たり前で、バグではない。困ったのは、最善手が複数あるときにどれを選ぶかを何も決めていなかったこと。結局、決定的な探索のいちばん奥に乱数を注すことになった。

ツールは雑談ペア作成に置いてある。以下はsrc/lib/tools/pair-randomizer.tsの話。

何度引いても同じペアが出る

シャッフルを潰した状態（並べ替えなしと同じ結果になる生成器を渡す）で、6名・履歴なしのまま1,000回引いた実測。

no-shuffle distinct results over 1000 runs: 1 [ 'AB CD EF' ]

6名の組み方は15通りある。そのうち1通りしか出てこないうえ、出てくるのは名簿の並び順のまま先頭から2人ずつという、いちばん芸のない並びだった。履歴が空なら15通りは全部同点なので、探索は最初に見つけた同点をそのまま返していただけだ。

3つの軸を1本のスコアに畳む

組み合わせの良さは3つの軸で決めている。まだ組んでいない、組んだ回数が少ない、前回から間が空いている。この順で効かせたい。

const NEVER_MATCHED_SCORE = 1_000_000
const PAIR_COUNT_WEIGHT = 10_000
const DAY_WEIGHT = 1

function scorePair(pairKey, historySummary, now) {
  const summary = historySummary.get(pairKey)

  if (summary === undefined) {
    return NEVER_MATCHED_SCORE
  }

  const elapsedDays =
    summary.lastMatchedAt === null
      ? 0
      : Math.floor((now.getTime() - summary.lastMatchedAt) / MILLISECONDS_PER_DAY)

  return elapsedDays * DAY_WEIGHT - summary.count * PAIR_COUNT_WEIGHT
}

やりたいのは（未経験か, 回数の少なさ, 日数）のタプルを頭から比べる辞書式順序で、それを桁の違う重みで1つの数に潰している。グループのスコアはメンバー全員ぶんのペアの合計、全体のスコアはグループの合計。探索はこの1つの数の最大化として書ける。

桁は繰り上がる

タプル比較を桁で代用すると、下の桁が積み上がって上の桁を食う瞬間が必ずある。境界がどこかを実測した。

4名（2組）で、合計2回・0日前の組み方と、合計3回・T日前の組み方をぶつける。

T=4999日前: AB|CD          ← 回数の少ないほうが勝つ
T=5000日前: AB|CD, AC|BD   ← 同点。乱数しだいで両方出る
T=5001日前: AC|BD          ← 回数の多いほうが勝つ

1回ぶんの差は10,000点。それを2組ぶんの日数で割ると5,000日で、計算どおりの位置で引っくり返った。

厄介なのは、この境界が組の数で割られること。同じ実験を16名（8組）でやると1,250日まで下がる。

T=1249日前 → P（合計8回・0日前）
T=1250日前 → 同点
T=1251日前 → Q（合計9回・T日前）

1,250日は3年5ヶ月ほど。毎週続けているチームなら普通に届く長さだ。「回数の少なさを日数より優先する」は、履歴が古びるほど怪しくなる約束だった。ここは今のところ直していない。8組ぜんぶが1,250日ぶん古い状態で、回数1回ぶんの差より日数を採るのが明確に間違いだとも言い切れないので、境界を知ったうえで放っている。

未経験ペアの優先のほうは頑丈だった。1,000,000点を日数で食い切るまで倒れない。

AC・BD が 3,652 日前（約10年前）に 1 回 → AB|CD
AC・BD が 1,009,999 日前（約2765年前）に 1 回 → AB|CD
AC・BD が 1,010,001 日前（約2765年前）に 1 回 → AC|BD

未経験の1,000,000点と1回ぶんの10,000点を足した1,010,000日で入れ替わる。ここまで余裕があれば桁の分離として成立している。

200万通りを1,632局面に潰す

16名を2人組にする分け方は15!! = 2,027,025通りある。総当たりで並べるには多すぎるが、全部を別々に数える必要はない。

探索は「残っている単位のうち、いちばん若い通し番号を含むグループを1つ選ぶ」を繰り返す形にしてある。単位というのは固定ペアを2人でひとかたまりにしたもので、固定が無ければ1人が1単位。いちばん若い番号を必ず含めるという縛りが、同じグループの集合を順番違いで数え直すのを止める。

そのうえで、局面は「残っている単位のビット」と「まだ作れる大きいグループの残り数」だけで決まる。この2つを番号に潰して配列に控える。

const memoKey = unitMask * memoStride + largerLeft
const memoized = memo[memoKey]
if (memoized !== undefined) {
  return memoized
}

文字列キーのMapではなく生の配列にしてあるのは、unitMaskが最大でも2 ** 16 - 1で、そのまま添字になるから1。

メモ化がどれだけ効いているかを、局面数を数える版に差し替えて測った（2人組・固定ペアなし）。

人数完全マッチングの総数探索した局面数検討したグループ候補
81054397
10945103332
1210,3952531,076
14135,1356373,361
162,027,0251,63210,226

8名では2.4倍しか得をしていないのが、16名では1,242倍になる。局面数の上限は残りメンバーの部分集合の数、つまり2 ** nで頭打ちなので、(n - 1)!!とは伸び方が違う。

同点は引き直した並び順で崩す

createPairingは探索へ入る前にメンバーのIDをシャッフルして、通し番号を振り直す。

// 同点の組み合わせが複数あるときにどれを選ぶかを、毎回ここで引き直す。
// これをしないと、同じ入力からはいつも同じ組み方しか出てこない
const orderedIds = shuffle(
  members.map((member) => member.id),
  randomInt,
)
const indexOf = new Map(orderedIds.map((memberId, index) => [memberId, index]))

探索はこの通し番号だけで動く。スコアの計算にも比較にも手を入れていない。変わるのは同点になったときの決着だけだ。

if (score === current.score && compareIndexes(candidateUnits, current.unitIndexes) >= 0) {
  return current
}

同点なら通し番号の列が小さいほうを残す。番号がシャッフル済みなので、これが「引き直した並び順で先に来るほう」になる。

6名・履歴なしで60,000回引いた実測。

distinct matchings: 15 / expected 15
expected per matching: 4000
AE BD CF 4074 6.79%
AD BC EF 4067 6.78%
AC BD EF 4050 6.75%
（中略）
AC BE DF 3948 6.58%
AF BC DE 3937 6.56%
AF BD CE 3934 6.56%
chi-square (df=14, 5% crit 23.68): 7.94

15通りが全部出て、最大6.79%・最小6.56%。カイ二乗は7.94（自由度14、5%点は23.68）なので、一様と見ていい。

一様になるのは偶然ではない。履歴が空なら全ペアが同点で、探索は毎回「残りのいちばん若い番号」と「その次に若い番号」を組ませる。シャッフルした並びの先頭から2人ずつ切っているだけで、これはランダムな完全マッチングの作り方そのものだ。

履歴が入れば同点の幅は狭まる。8名で3回ぶんの履歴を積んだあと2,000回引いたら14通りだった。最高スコアは1つでも、そのスコアを出す組み方はたいてい複数ある。乱数はそこだけを崩している。

16名で止めた理由

上限はMAX_MEMBERS = 16にしてある。上限を外したコピーで測った時間がこれ（Node 24、固定ペアなし、11回の中央値）。

人数2人組3人組4人組
120.3ms1.0ms1.9ms
141.1ms11.3ms28.6ms
163.0ms59.3ms47.8ms
1813.9ms68.6ms902.6ms
2027.5ms776.5ms1,256.7ms

2人組はまだ余裕がある。落ちるのは3人組と4人組で、グループ1つを作るのに単位を3つ4つ選ぶぶん候補が膨らむ。16名の最悪が59.3msなら押しても気にならないが、18名は4人組で900msを超えて、押した瞬間に固まったように見える。上限はここで切った。

固定ペアを入れると単位が減るので、探索は逆に軽くなる。16名・4人組の実測。

固定ペア単位数時間
0組1650.3ms
1組1516.7ms
2組145.2ms
4組120.6ms

制約を足すほど遅くなりそうなものだが、この形の探索では制約が探索空間を削る側に回る。

一巡するまでの回数

最後に、未経験ペア優先が実際どれだけ効くかを測った。毎週1回ペアを作り、結果を履歴に積み直すのを、全ペアが1度ずつ揃うまで繰り返す。300回ぶんの平均。

人数全組数履歴あり理論下限毎回シャッフルするだけ
6155.14回5回15.4回
8287.17回7回26.7回
10459.21回9回37.5回
126611.22回11回51.1回

8名なら300回中248回が7回で一巡した。7回は総当たり戦の理論下限で、これ以上は詰められない。毎回シャッフルするだけだと平均26.7回、悪い回は66回かかった。3倍以上の差がある。

まとめ

  • 複数の評価軸を桁の違う重みで1本に畳むのは書きやすいが、組数ぶん足し合わせる設計だと下の桁が繰り上がってくる。境界は割り算で出るし、実測でも確かめられる
  • 全探索でも局面をビットで持って控えれば、200万通りが1,632局面まで潰れる
  • 最善手を選ぶ探索は決定的で、同点をどう崩すかを決めていないなら、それは何も決めていないのと同じ。通し番号を引き直してから探索に入れば、スコアの計算にも比較にも触らずに同点だけ壊せる

Footnotes

  1. この持ち方だと単位数が32を超えた時点で1 << unitIndexが壊れる。上限を16名にしてあるので届かないが、伸ばすならBigIntか配列に持ち替えることになる。 ↩

← 一覧へ戻る