Information Structure and Mathematical Analysis of Amusement Game -Part 1- Markov Model for “Reviving the Dead” Game
Wataru MOGI, Masaaki SHINOHARA and Keitaro HIDAKA
遊戯 遊戯
遊戯 遊戯ゲームの ゲームの ゲームの ゲームの情報構造 情報構造 情報構造 情報構造と と と数理分析 と 数理分析 数理分析 数理分析
―
―
―
―(((その(そのその1)その )))起死回生起死回生起死回生・起死回生・・・大逆転大逆転大逆転大逆転ゲームのマルコフモデルゲームのマルコフモデルゲームのマルコフモデルゲームのマルコフモデル――――
(財)計量計画研究所 ○茂木 渉 日大生産工 篠原 正明 青山学院大(院) 日高 啓太郎
1. はじめにはじめにはじめにはじめに
パチンコ,パチスロ,ボードゲーム,PCゲーム等 の遊戯ゲームの1つである「起死回生・大逆転ゲーム」
について,動作遷移を(有限)マルコフ連鎖として モデル化し,ゲーム終了までの平均試行回数の分析 ならびに関連する頻度分析を行う.
2. 起死回生起死回生起死回生起死回生・・・・大逆転大逆転大逆転ゲーム大逆転ゲームゲームゲーム
ゲーム開始状態をS,終了状態をTとすると,図1 に示す動作遷移図となる.
S 1 2 3 N−1 N T
図 図 図
図1:::: 起死回生起死回生起死回生起死回生・・・・大逆転大逆転大逆転大逆転ゲームのゲームのゲームのゲームの動作遷移図動作遷移図動作遷移図動作遷移図
○iは第i回の試行状態を表し,「ハズレ」では第i +
1回の試行状態○i+1 へ,「アタリ」では第1回の試
行状態○1へ遷移する.又,土壇場の試行状態○Nで「ハ ズレ」が出ると,終了状態Tへ移行し,ゲーム終了で ある.ここで,○i での「アタリ」の確率をpi (1 ≤ i ≤ N) とするとき,起死回生・大逆転ゲームでは通常pi = p (1
≤ i ≤ N−1),pN = q,で,pは小さく(例えば,0.01),
qは大きく(例えば,0.5)設定する.
Sが誕生,Tが死滅,○i →○i+1 の遷移が加齢と考
えれば,「アタリ」は1才○1への若返りを意味し,さ らに最後の土壇場○Nでは,その若返りの確率qが大き くなっている.これが,ゲーム名「起死回生・大逆 転ゲーム」の由来である.
3. マルコフモデルマルコフモデルマルコフモデルマルコフモデル
図1の動作遷移図に遷移確率を記入したマルコフ
連鎖を図2に示す.
S 1 2 3 N−1 N T
1.0 1 –p1 1 –p2 1 –p3 1 –pN−1 1 –pN
p1 p2 p3 pN−1 pN
図 図 図
図2:::: 起死回生起死回生起死回生起死回生・・・・大逆転大逆転大逆転大逆転ゲームのマルコフモデルゲームのマルコフモデルゲームのマルコフモデル ゲームのマルコフモデル
4. 平均値特性平均値特性平均値特性平均値特性
x(i)を状態iの平均試行回数とすると,以下の関係式
が成立する.
) 1 ( ) 1 ( )
(i = −p−1 x i−
x i 2≤i≤N+1 (1)
) 0 ( ) ( )
1 (
1
x j x p x
N
j
j +
=∑
=
(2)
) 1 ( ) 0
( =x N+
x (3)
但し,x(0) = x(S), x(N + 1) = x(T)である.又,(1)を詳細 に表現すると以下の通りである.
−
= +
−
=
−
=
−
=
) ( ) 1 ( ) 1 (
) 3 ( ) 1 ( ) 4 (
) 2 ( ) 1 ( ) 3 (
) 1 ( ) 1 ( ) 2 (
3 2 1
N x p N
x
x p x
x p x
x p x
N
M M
(4)
従って,
pN
N N x
x −
= + 1
) 1 ) (
(
−日本大学生産工学部第43回学術講演会(2010-12-4)−
― 119 ― 7-37
) 1 )(
1 (
) 1 ) (
1 (
−1
−
−
= +
−
N
N p
p N N x
x M
) 1 ( ) 1 )(
1 (
) 1 ) (
4 (
4
1 p
p p
N x x
N
N − −
−
= +
− L
) 1 )(
1 ( ) 1 )(
1 (
) 1 ) (
3 (
3 4
1 p p
p p
N x x
N
N − − −
−
= +
− L
) 1 )(
1 )(
1 ( ) 1 )(
1 (
) 1 ) (
2 (
2 3 4
1 p p p
p p
N x x
N
N − − − −
−
= +
− L
) 1 )(
1 )(
1 )(
1 ( ) 1 )(
1 (
) 1 ) (
1 (
1 2 3 4
1 p p p p
p p
N x x
N
N − − − − −
−
= +
− L
を得る.すなわち,(5)式となる.
) 1 )(
1 ( ) 1 )(
1 (
) 1 ) (
(
1
1 i i
N
N p p p
p
N i x
x − − − −
= +
+
− L
N i≤
1≤ (5)
ゲーム全体としてゲーム開始から終了までの平均 停留回数(=平均ゲーム長)をTとするならば,(3)式 においてx(0) = x(N + 1) = 1.0とし,(6)式においてTを 評価する.
∑
=
= N
j
j x T
1
)
( (6)
起死回生・大逆転ゲームのパラメータpi = p (1 ≤ i ≤
N−1),pN = qを代入すると,次式(7)を得る.
∑−
= −
= − 1
0(1 ) 1 1
1 N
j
q j
T q
−
−
−
= − 1
) 1 (
1 1 1 1
p N
p q
p (7)
例えば,N = 20, p = 0.05, q = 10/19とすると,(8)を得る.
78 .
≒71
T (8)
5. 頻度特性頻度特性頻度特性頻度特性
図3に起死回生・大逆転モデルのz-変換マルコフモ
デル(シグナルフローグラフ)を示す.(1),(2)に関し てz-変換後の関係式を以下に示す(但し,z-変換後の x(i)について同じ記号を使用).
S 1 2 3 N−1 N T
1.0 1 –p1 1 –p2 1 –p3 1 –pN−1 1 –pN
p1 p2 p3 pN−1 pN
z z z z z
図 図図
図3: 起死回生起死回生起死回生起死回生・・・・大逆転大逆転大逆転大逆転ゲームのゲームのゲームのゲームのz-変換変換変換変換シグナルフロシグナルフロシグナルフロシグナルフロ ー
ーー ーグラフグラフグラフグラフ
) 1 ( ) 1 ( )
(i = −p−1 zxi−
x i 2≤i≤N+1 (9)
) 0 ( ) ( )
1 (
1
zx j zx p x
N
j
j +
=∑
=
(10)
(9),(10)を変形して,(11)式で定まるS-T間のz-変換利
得GST(z)を求める.
) S ( ) ( ) T
( GST z x
x = (11)
ここで,S-T間のシグナルフローグラフ利得GST(z)は
以下の再帰関係式によっても求めることができる.
1 )
0(z =
P (12)
−
= −
−
= −
−
= −
−
−
z p z P
z zP z p
P
z p z P
z zP z p
P
z p z P
z zP z p
P
N N
N N
N 1 ( )
) ( ) 1 ) ( (
) ( 1
) ( ) 1 ) ( (
) ( 1
) ( ) 1 ) ( (
1 1 2 1
1 2 2
1 0
0 1 1
M
(13)
) ( )
ST(z P z
G = N (14)
(13)式の再帰関係式は(15)で表現できる.
z p z P
z zP z p
P
i i
i i
i 1 ( )
) ( ) 1 ) ( (
1 1
−
−
−
= − 1≤i≤N (15)
例えば,N = 3, p1 = p2 = p, p3 = qとすると(図4),以 下を得る.
― 120 ―
p z z p
P −
= − 1
) 1 ) (
1( (16)
pz z P
z zP z p
P 1 ( )
) ( ) 1 ) ( (
1 1
2 −
= − (17)
) ( )
( 3
ST z P z
G =
qz z P
z zP q
) ( 1
) ( ) 1 (
2 2
−
= − (18)
(17)に(16)を代入し,(17)を(18)に代入すると,(19)を
得る.
3 2 2
3 2
ST 1 (1 ) (1 )
) 1 ( ) 1 ) (
( pz p pz p qz
z q z p
G − − − − −
−
= − (19)
S 1 2 3 T
1.0 1 –p 1 –p 1 –q
p p q
図 図 図
図 4: N = 3, p1 = p2 = p, p3 = qのシグナルフローグラフのシグナルフローグラフのシグナルフローグラフのシグナルフローグラフ
(19)式の分子において,z3の係数は経路S→○1→○2→
○3→Tの経路利得積,分母においてzの係数は○1の自 己閉路,z2の係数は閉路○1→○2→○1,z3の係数は閉 路○1→○2→○3→○1の閉路利得積に対応しているこ とがわかる.
又,GST(z) = Σai ziと展開した時のaiが試行回数= iで
SからTへ到達する頻度を表しているので,(20)を得
る.
3 2 2
3 2
GT 1 (1 ) (1 )
) 1 ( ) 1 ) (
( pz p pz p qz
z q z p
G − − − − −
−
= −
+L + +
=a3z3 a4z4 a5z5 (20)
ここで,a3, a4, a5,…は以下の通りである.
− +
−
−
=
−
−
=
−
−
=
M
) ) 1 ( )(
1 ( ) 1 (
) 1 ( ) 1 (
) 1 ( ) 1 (
2 2
5
2 4
2 3
p p p
q p a
p q p a
q p a
(21)
一般のNで,pi = p (1 ≤ i ≤ N−1), pN = qの場合(22)と一 般のNとpiの場合(23)のS-T間シグナルフローグラフ
利得GST(z)を以下に示す.
N N N
N
qz p pz
p pz p pz
z q z p
G 2 2 3 1
1
ST 1 (1 ) (1 ) (1 )
) 1 ( ) 1 ) (
( −
−
−
−
−
−
−
−
−
−
−
= −
L
− + −
−
−
= −
∑−
=
−
−
N N N
i
i i
N N
qz p pz p
z q p
) 1 ( )
1 ( 1
) 1 ( ) 1 (
1
1
1
1 (22)
−
−
−
−
−
−
−
−
−
−
−
−
−
= −
− N N N
N N
z p p p
p
z p p p z p p z p
z p p
z p G
) 1 ( ) 1 )(
1 (
) 1 )(
1 ( ) 1 ( 1
) 1 ( ) 1 )(
1 ) (
(
1 2
1
3 3 2 1 2 2 1 1
2 1 ST
L
L L
∑ ∏
∏
=
−
=
=
−
−
−
=
N
i
i i i
j j N
i
N i
z p p
z p
1 1
1 1
) 1 ( 1
) 1
( (23)
6. シミュレーションシミュレーションシミュレーションシミュレーション
0 10000 20000 30000 40000 50000 60000 70000 80000 90000 100000
0 100 200 300 400 500 600
図 図図
図5: 到達回数累積分布到達回数累積分布到達回数累積分布到達回数累積分布((((N = 20, p = 0.05, q = 10/19,,, , ゲーム
ゲームゲーム
ゲーム回数回数回数=10万回回数 万回万回)万回)))
0 2000 4000 6000 8000 10000 12000 14000 16000 18000 20000
0 100 200 300 400 500 600
図 図図
図6: 到達回数頻度分布到達回数頻度分布到達回数頻度分布到達回数頻度分布((((N = 20, p = 0.05, q = 10/19,,, , ゲーム
ゲームゲーム
ゲーム回数回数回数=10万回回数 万回万回)万回)))
― 121 ―
7. おわりにおわりにおわりにおわりに
「起死回生・大逆転ゲーム」をマルコフ連鎖として モデル化し,シグナルフローグラフ技法を用いて各 種統計分析を行った.シミュレーション値と理論値 は合致した.
付録 付録付録
付録1 シグナルフローグラフのシグナルフローグラフのシグナルフローグラフのS-T間利得シグナルフローグラフの 間利得間利得間利得 GSTにににに関関関する関するするするMason公式公式公式公式
シグナルフローグラフは信号流れ線図ともよばれ,
制御工学,電気工学,通信工学などの分野において,
対象をネットワーク表現して解を求める生産現場生産現場生産現場生産現場にににに 密着
密着密着
密着したしたした問題解決手法である.生産現場した 生産現場生産現場の生産現場のの技術者の技術者技術者な技術者 どが,連立方程式を直接解く代わりに,問題の特質 をネットワーク表現し,問題の構造面を反映した陽 表現解(トポロジー公式とも呼ばれる)を導くこと ができる.連立方程式の数値解法が非常に容易とな った今日では,シグナルフローグラフを用いた求解 法はほとんど使われていないようだ.陽表現解(ト ポロジー公式)を与えるMason公式を以下に説明す る.
∑
= kPk∆k ∆
GST (A1.1)
但し,Δ=1 − (すべてのループゲインの和)+(すべて
の2つの点疎なループのゲイン積の和) − (すべての3
つの点疎なループのゲイン積の和)+(すべての4つ の点疎なループのゲイン積の和) − ・・・・
Pk = k番目のS-T間単純パスのパスゲイン
Δk = k番目のS-T間単純パスを開放除去したシグ
ナルフローグラフのΔ 付録
付録付録
付録2 Mathematicaによるによるによる理論解による理論解理論解理論解
一般のNの場合((22)式または(23)式)でもGST(z) をΣai ziと級数展開できれば,試行回数= iでSからTへ 到達する頻度を得ることが可能である.iが大きくな ると手計算による展開は困難になるが,Mathematica を用いることで容易に展開が可能である.その方法 を以下に示す.使用する関数は次の3つである.
Series[ f(x), {x, x0, n} ]
f(x)のx = x0に関するn次までの級数展開.
Coefficient[ f(x), x, i ]
多項式 f(x)のxiの係数を返す.
For[ i = α, i <= β, i++, f(x) ]
初期条件i = α,停止条件i <= βとしてf(x)を 繰り返し,ループの最後にiを1つインクリ メントする.
これらを組み合わせた,(22)式の級数展開を得るため のプログラムと,その実行画面,及び結果の理論頻 度分布を以下に示す(但し,mは展開を打ち切る次
数,>>> dataはファイル名「data」というファイルにj
での値を追加出力することを意味する).
For[ j = 1, j <= m, j++, Coefficient[ Series[「(22)式」, {z, 0, m} ], z, j ] >>> data ]
図 図図
図A1: Mathematicaでのでのでのでの実行画面実行画面実行画面実行画面
0 0.02 0.04 0.06 0.08 0.1 0.12 0.14 0.16 0.18 0.2
0 100 200 300 400 500 600
図 図 図
図A2: 到達回数頻度分布到達回数頻度分布到達回数頻度分布到達回数頻度分布((((理論値理論値理論値理論値))))
ところで,最初のピーク値は試行回数i = 20で出現し,
その頻度値a20は以下で与えられるが,図A2の理論値 と一致する.
1787 . 0 ) 19 / 9 ( ) 95 . 0
( 19
20= ≒
a (A2.1)
― 122 ―