# 100手で人間の癖を学ぶ — Hedgeアルゴリズムとオンライン学習

## 人間はランダムになれるか

Are You Random は、0 か 1 のボタンを 100 回押して AI に予測されないかを競うゲームだ。AI はプレイヤーの入力をリアルタイムで観察しながら次の手を予測し続け、最後にスコアが出る。

スコアは AI の予測確率の log loss をもとに計算される。各ステップで AI が「次は 1」と確率 p で予測したとき、実際の入力が 1 なら損失は -log(p)、0 なら -log(1-p) だ。これを全ステップで平均した値を log(2) で割り、0〜100 に正規化したものがランダム度スコアになる。

avg_log_loss = (1/T) × Σ -log(p_actual_t)
randomness_score  = min(avg_log_loss / log(2), 1) × 100

AI が常に 50/50 で迷っていれば平均 log loss は log(2) になりスコアは 100。確信を持って正解し続けるほど損失が下がりスコアも下がる。AI が「外した回数」ではなく「どれだけ迷っていたか」を測っている点が肝で、たまたま外れただけの予測と、最初から五分五分だった予測は別物として扱われる。

この記事では、そのゲームを裏で動かす予測エンジンの仕組みを解説する。LLM でも深層学習でもない、古典的なオンライン学習がベースになっている。

## バッチ学習ではない

機械学習の文脈でよく語られるのはバッチ学習だ。大量のデータを用意して、モデルを訓練して、本番に載せる。Are You Random の予測器はそのアプローチを一切取らない。

プレイヤーが 0 か 1 を一手押すたびに、その結果をすぐに学習へ反映する。次の手を予測し、正誤が判明し、重みを更新する。これがオンライン学習の本質であり、このゲームで唯一選べる戦略でもある。なぜなら、ゲーム開始前に「このプレイヤーの手」のデータなど、どこにも存在しないからだ。

## 18 の予測器

予測エンジンは一枚岩ではない。18 個の予測器がそれぞれ独自の仮説に基づいて次の手を予測する。

最も単純なのは定数予測器で、常に 0 または常に 1 を返す。極端に偏ったプレイヤーへの対策だ。RepeatExpert は「人は同じ手を繰り返しがちだ」という仮説で直前の入力をそのまま予測に使い、FlipExpert はその逆、「切り替えたくなる」癖を突く。

RunLengthExpert はもう一段深い。「同じ値が 3 回続いたあと、人は切り替えることが多い」といった連続長ごとの傾向を学習する。連続長 n のとき継続した回数と切り替えた回数を別々に記録し、次の手の確率を推定する。KT 平滑化も適用されるため、出現していない連続長でも破綻しない。

AlternationExpert は直近 6 手が交互パターン（010101…）になっていれば、その継続を予測する。BalanceExpert は 0 と 1 の偏りを tanh 関数でソフトに見て、少ない方を予測する。「均衡させようとする」という心理的な癖を狙っている。PeriodExpert は周期長 2〜6 のパターンを検出し、次が一致するかどうかを返す。

より洗練されているのが ContextExpert だ。直前 k 手のパターンを見て次を予測する k 次マルコフモデルで、k=1 から k=6 まで 6 種類が走っている。「001 の次は高確率で 1 が来る」といった具合に、プレイヤー固有の文脈的な癖を蓄積していく。初期重みが他の予測器の 2 倍に設定されているのも、この予測器を主力として扱っているからだ。

## 重みの指数的更新

18 の予測器が出した予測を、どう一つの答えに統合するか。ここで Hedge アルゴリズムが登場する。

各予測器には重みが割り当てられている。各予測器の予測確率を重み付き平均して最終的な予測を出し、真の答えが判明したあと、外れた予測器の重みを指数的に削る。

loss_i  = -log( p_i(x_t) )
w_i    ← w_i × exp(-η × loss_i)   // η = 0.5

「外れたら罰則」というシンプルな規則だが、指数関数を使った減衰が効く。わずかにずれた予測より、高い確信度で大きくはずした予測のほうが重みを激しく削られる。ゲームが進むにつれ、そのプレイヤーに「合っている」予測器だけが生き残る構造だ。

理論的な裏付けもある。オンライン学習の regret 理論によれば、T 手後の Hedge の累積損失は最良の予測器の損失に対して O(√(T log N)) の誤差しか生まない（N は予測器数）。100 手・18 予測器なら、その上界は十分に小さい。

## KT 平滑化という工夫

ContextExpert の内部には Krichevsky-Trofimov 平滑化が組み込まれている。

ある文脈に対して「1 が来た回数 n1、0 が来た回数 n0」を記録しておき、次の確率をこう計算する。

P(next=1 | context) = (n1 + 0.5) / (n0 + n1 + 1.0)

n1 も n0 もゼロのとき、単純な頻度推定では 0/0 で破綻する。KT 平滑化はそこに疑似カウント 0.5 を加えることで、初期状態でも 0.5（五分五分）を返せるようにしている。

この 0.5 という値は恣意的ではない。情報理論的に、最悪ケースの冗長性を最小化する Jeffreys 事前分布から導かれる定数だ。直感的には「何も知らないなら半々」という以上の意味がある。

## 100 手という短さの中で

面白いのは、このアルゴリズムが「たった 100 手」という非常に短い系列を前提にしている点だ。

k=6 の ContextExpert は 64 種類の文脈を追うが、100 手では多くの文脈が一度も現れない。それでも KT 平滑化のおかげで破綻せず、バックオフ（k 次で見つからなければ k-1 次に落とす）で補完する。短い系列の中でなるべく早く有力な予測器へ収束させるための工夫が、設計のあちこちに散りばめられている。

## 確信度という補助情報

ゲーム中、UI には AI の確信度が 0〜100% で表示される。計算式はシンプルだ。

confidence = |P(next=1) - 0.5| × 2

P(next=1) が 0.5 のとき確信度は 0（五分五分）、0 か 1 に完全に傾けば 1（100%）になる。 Hedge の重みがまだ分散していてどの予測器も優位でない序盤は確信度が低く、特定の予測器に重みが集中してくると上がっていく。プレイヤーは確信度の変化を見ることで、自分の癖が読まれ始めているかどうかを間接的に観察できる。

もっとも、確信度が高い = AI が正解するとは限らない。高確信度でも外すことはある。重みが収束した予測器の仮説が間違っていれば、それだけ大きく罰則を受けて重みが崩れる。その揺り戻しもまた Hedge の設計どおりだ。

## イソモーフィックな予測器

予測ロジックはクライアントとサーバーで完全に共有されている。ゲーム中の予測と確信度の表示はブラウザ上で動くが、ゲーム終了後に送信された 100 手の入力列をサーバーが同じロジックで最初から再計算し、スコアを確定する。

クライアント側の「暫定スコア」はあくまで表示用に過ぎない。サーバーが正しく再計算できる理由は、予測器が同一のコードで、かつ入力列さえあれば完全に再現可能なステートレスな決定論的アルゴリズムだからだ。乱数もなく、外部状態への依存もない。

この設計はスコア改ざん対策にもなっている。クライアントがどんなスコアを自己申告しても、サーバー再計算の結果と食い違えばそちらを採用する。ロジックの一元化と不正対策が、同一コードを共有するという一つの判断から同時に達成されている。