fixedpoint.jp

2020-05-13

Viterbiアルゴリズムの簡潔な説明

FFmpegのドキュメンテーションに含まれている、Viterbi algorithmの簡潔な説明が分かりやすい。隠れマルコフモデルの隠れ状態の列を推定するアルゴリズムにしてはemission matrixに関する部分が省略されているが、そのおかげで動的計画法の側面が明確になっている。

2020-05-10

乱択ニム型ゲームで先手が勝つ確率について

次に挙げるルールにのっとったニム型ゲームには、先手に必勝法がある。

• それぞれ1から100までの数字が書かれた100個の石からなる山がある。
• 2人のプレーヤーが先手と後手に分かれ、交互に山から石を書かれた数字の順に取っていく。
• 各プレーヤーの各手番につき、少なくとも1個、多くとも6個の石を取る。
• 100が書かれた石を取った方を勝ちとする。

このゲームはピーター・フランクルのらくらく数学パズル塾 (朝日文庫)で紹介されているパズルと同じものである。そのよく知られた必勝法は以下のとおりである。

• 最初に先手が2つの石を取る。
• 以降、後手が\(x\)個の石を取った場合、次に先手は\(7 - x\)個の石を取る。

これに従うと、\(100 = 2 + 7 * 14\)であることから、先手が29手目で常に勝利することができる。このため、このゲームは先後どちらになるかで勝敗が決まってしまう退屈なゲームである。

そこで、各手番でプレーヤーが取る個数をランダムに選ぶようにルールを改変するとどうなるであろうか？つまり、各手番で(公平な)6面体サイコロを1つ振り、出目の数だけ石を取ることにする。この改変版を乱択ニム型ゲームと呼ぶことにする。さて乱択ニム型ゲームで先手が勝つ確率はどのくらいだろうか？要は、各手番のサイコロの出目を足していき、奇数番目の手でその和が100に達する確率がどのくらいになるか、という問題である。ただし、勝ちの手番では取る石の数字が100を越えることも許す(例えば、6の目が16手連続で出続けて(\(6 * 16 = 96\))、さらに17手目も6が出た場合(\(96 + 6 = 102\))、先手の勝ちとする)。

計算機で疑似乱数を生成させてこのゲームをシミュレーションしてみると、先手も後手もほぼ同程度の頻度で勝ったり負けたりするように見える。つまりほぼ1/2の確率で先手が勝つように見える。しかし正確なところは分からない。

正確に確率を計算するために、まずいくつかの定義を準備する。自然数\(n\)に対し、それぞれ1から\(n\)までの数字が書かれた\(n\)個の石からなる山を用いて、\(n\)が書かれた石を取った方を勝ちとする乱択ニム型ゲームを\(G_n\)と呼ぶ。\(G_n\)で先手が勝つ確率を\(p_n\)と呼び、後手が勝つ確率を\(q_n\)と呼ぶ。すなわち、今求めたいのは\(p_{100}\)である。\(p_1 = 1\)は明らか。さらに、\(G_n\)において先手が最初の手番で出した目に応じて、残りの進行全体を\(k < n\)なる\(G_k\)と同一視できる。例えば\(G_{100}\)で先手最初の手番に5が出た場合、残りの進行全体は\(G_{95}\)と同一視できる。このとき、同一視した\(G_{95}\)における後手の勝ちが、元の\(G_{100}\)における先手の勝ちを意味する。\(n\)が小さい場合:\begin{align}q_2 &= \frac{p_1}{6}; \\q_3 &= \frac{p_1 + p_2}{6}; \\q_4 &= \frac{p_1 + p_2 + p_3}{6}; \\q_5 &= \frac{p_1 + p_2 + p_3 + p_4}{6}; \\q_6 &= \frac{p_1 + p_2 + p_3 + p_4 + p_5}{6}; \\q_7 &= \frac{p_1 + p_2 + p_3 + p_4 + p_5 + p_6}{6}.\end{align}\(q_k = 1 - p_k\)を代入して解くと\[p_n = \left( \frac{5}{6} \right)^{n-1} \qquad (1 \leq n \leq 7)\]が得られる。ただ\(p_n\)がこのように幾何級数的であるのはここまでで、一般の\(n\)については\[p_n = \frac{1}{6} \sum_{i=1}^6 q_{n-i} \qquad (n \geq 7)\]が成り立っている。\(q_k = 1 - p_k\)を代入すると\[p_n = 1 - \frac{1}{6} \sum_{i=1}^6 p_{n-i} \qquad (n \geq 7)\]と\(p_k\)だけからなる式にできる。特に、\[p_n = \frac{p_{n-7} + 5 p_{n-1}}{6} \qquad (n \geq 8)\]こうして、以下のRacketプログラムで\(p_{100}\)が正確に計算できることになる。

#lang racket
(require srfi/1)

(define (p n)
  (let lp ((i 1)
           (ls '(1)))
    (cond ((>= i n)
           (car ls))
          ((< i 7)
           (lp (+ i 1)
               (cons (* 5/6 (car ls)) ls)))
          (else
           (lp (+ i 1)
               (cons (/ (+ (seventh ls) (* 5 (car ls))) 6)
                     (take ls 6)))))))

(define p100 (p 100))
p100 ; => 54443218649389348716498209861047618553904558871554859532791938833224449355325/108886437250011817682781711193009636756190618412159145257178661061582856912896
(exact->inexact p100) ; => 0.5000000002239345

結局\(p_{100}\)は\(\frac{1}{2}\)よりわずかながら大きい。

Archives