確率的多段階意思決定過程を用いた ビリヤード戦略の最適化

卒業研究論文

確率的多段階意思決定過程を用いた  ビリヤード戦略の最適化 

学籍番号  00D8103011K 川端  利哉

中央大学理工学部情報工学科  田口研究室

2004 年 3 月

あらまし

  本研究では，ビリヤードの最適戦略を導出する．まず，プレーが行われる台を座標で表 し，手球と的球の衝突後の進む方向，進む距離，クッションの作用など，球の動きを数理 的に表現する．それにより，狙うポケットの決定や，次の状態に推移する確率を算出し，

確率的多段階意思決定を用いて最適戦略を求める．最後に，その戦略のシミュレーション を行い，確率的多段階意思決定を用いずに求めた戦略と比較し，検証する．

キーワード：動的計画法，最適性の原理，確率的多段階意思決定

目次

第

1

章  はじめに ... 1

第

2

章  ビリヤードの概要 ... 2

2.1  基本概念 ... 2

2.2  ボーラードのルール  ... 3

第

3

章 動的計画法 ... 4

3.1  動的計画法とは  ... 4

   

3.2  多段階決定過程  ... 4

3.2.1  要素 ... 4

   

3.2.2  N

段階決定過程 ... 5

3.3  最適性の原理 ... 6

3.3.1  性質 ... 6

3.3.2  N

段階階決定過程での最適性の原理 ... 6

3.3.3  逐次関係と最適化 ... 7

3.4  確率的多段階意思決定過程 ... 8

第

4

章 ビリヤードの数理化 ... 11

4.1  球の配置  ... 11

4.2  角度と距離  ... 12

4.3  基本分離  ... 13

4.4  手球及び的球の衝突後の移動距離 ... 14

4.5  衝突後の手球の経路 ... 15

第

5

章  確率的多段階意思決定のモデル ... 18

5.1  段階と状態 ... 18

5.2  確率設計 ... 19

5.2.1  ネクスト配置確率 ... 20

5.2.2  シュート成功確率 ... 21

5.2.3  使用する確率 ... 23

   

5.3  期待利得と決定 ... 23

第

6

章 シミュレーション結果 ... 26

6.1 最適戦略シミュレーション  ...  26

     

6.1.1  シミュレーション準備  ...  26

     

6.1.2  シミュレーション結果  ...  27

6.2  戦略シミュレーション比較  ...  29

     

6.2.1  シミュレーション結果  ...  29

第

7

章 おわりに ... 

31

謝辞 

...  32

...  33 

第 1 章 はじめに

ビリヤードは，国内では「遊び」のイメージが強いが，国際的にはスポーツとして位置 づけられている．

57

カ国が加盟する世界ビリヤードスポーツ連合は，

1998

年に国際オリン ピック委員会（IOC）の正式承認団体に承認された．今後，オリンピックの正式種目となる のも時間の問題であるともいわれている．

ビリヤードの起源については，今日までに明確な事は解明されていないが，14 世紀頃に フランスで発祥したという説が最も一般的である．1850年代（江戸時代）になると日本に もビリヤードが上陸し，華族や将官など一部の階級で社交スポーツとして楽しまれた．街 にビリヤード場ができ，一般に広まっていったのは大正時代に入ってからのことである．

1900

年代になると，アメリカでの流行を受け，日本でも幾度かのブームを繰り返し，現在 に至る． 

ビリヤードには，さまざまなゲームが存在する．その中には，相手選手と勝敗を競うの ではなく，いかにシュートを成功させつづけ，高得点を得られるかを競うボーラードとい うゲームがある．このゲームの特徴は，狙う的球に指定はなく，シュートなどのプレー技 術だけでなく，どの的球から狙うかという戦略が重要となる点である．同程度のプレー技 術を持ったプレーヤーでも，戦略の違いによってその得点は大きく異なり，最適な戦略を 見い出すことは非常に困難である．

本研究では，ボーラードを簡略化したゲームを題材とする．そして，確率的多段階意思 決定過程を用いてゲームの最適戦略を導出し，その戦略を検証する．

第 2 章

ビリヤードの概要

2.1   基本概念

ビリヤードは手球を撞いて，的球を台上の６ヶ所にあるポケットに落としていくゲーム である．ミスをせずに連続してポケットするために，１ショット毎に次の球が狙いやすく なるようなネクストをとることも重要となる．シュートを外す，もしくはファールをする とミスとなり，そのイニングが終了となる．

ここで，本論文で用いるビリヤード用語を以下に述べる．

・手球  …  プレーヤーが撞くことが許されるただ

1

つのボール．通常は白い球である．

・的球  …  手球に対して，1番から

15

番までの狙われる球の総称．

・撞点  …  手球を撞く狙い点（手球に回転を与えるために上下左右を撞く）．

・ひねり  …  手球に左右の回転を与えること．また，その回転そのもの．撞点の変化に よりひねりの大きさを調整する．

・押し球  …  上の撞点により，手球に積極的な前進回転を与えたショットで，ショット された手球が基本分離角より前方へ出るアクションを起こすショット．

・引き球  …  下の撞点により，後退方向に逆回転を与えたショットで，的球に衝突した 後，逆方向または基本分離角を広げるアクションを起こすショット．

・ポケット  …  台上にある穴．または，穴にボールを落とすこと．

・ファール  …  定められたルールに対する違反行為．

・イニング  …  ミスやファールで交代するまで，続けてプレーできる期間．

・ネクスト  …  シュート後に次の的球が狙いやすいように手球の残り配置をコントロー ルすること．または，その配置．

・ラシャ  …  台に張られた緑色の布

・クッション  …  台の内側側面に張られたゴム製の壁．または，その壁に当たって球が 跳ね返る動作のこと．

・スクラッチ  …  手球が誤ってポケットに落ちてしまうファール．

・セーフティ  …  シュートの成功を狙うのではなく，意図的に残りの配置が相手にとっ て困難となることを狙った戦略．または，そのような戦略的意図を持 ったショット．

・キャノンショット  …  手球を連続して

2

個以上の的球に当てて，

2

個目以降の的球をポ ケットさせる狙い方．または，そのような狙い方をしたショット．

・コンビネーションショット  …  手球を的球に当てた後，さらにその的球を他の的球に 当て，後から当たった的球をポケットする狙い方．ま たは，そのような狙い方をしたショット．

・バンクショット  …  的球をクッションさせてからポケットする狙い方．または，その ような狙い方をしたショット．

・ブレークショット  …  ビリヤードのゲーム開始のショット．

2.2   題材とするゲームのルール

  ビリヤードの数あるゲームの中から，本研究でモデルとするゲームを選定する．

ビリヤードのゲームの

1

つにボーラードがある．ボーラードとは，対戦相手を必要とせ ずに，そのプレーヤーの実力を測定するための種目である．これはプロテストの必須種目 でもある．

10

個の的球を用い，そのどれから狙ってもよく，落とした球の個数が点数とな る．そして，ボーリングの要領で点数を付けていくのだが，１回のミスで１投分の扱いと なる．つまり，ミスをせずに

10

個の的球を落としきるとストライク，1回ミスをして落と しきると，スペアとなる．

このゲームの特徴をまとめると以下のようになる．

・対戦相手が不要なことより，セーフティなどの戦略選択は行われない．

・本人の能力，意思決定によってのみゲームが進む．

・任意の的球を狙ってよいので，各段階でどの球を狙うのか意思決定を行う．

以上の特徴から，題材としてボーラードに注目する．しかし，10 個の的球を用いると

10

段階の意思決定を行うことなり，計算機実験における計算時間が膨大に掛かってしまうた め，ボーラードを基盤としたオリジナルのゲームを定義する．そのルールを以下に示す．

・ボーラード同様，任意の的球から狙うことができ，対戦相手は存在しない．

・ブレークは行わず，任意の配置を初期状態として設定し，ゲームが始まる．

・初期状態の的球は

5

個である．

また、モデルの簡略化のため，以下の条件も加える．

・シュート以外，球の衝突は起こらない．

・スクラッチは起こらない．

・フロッグは起こらない．

・ヒネリによるカーブは起こらない．

・コンビネーションショットは不可．

・キャノンショットは不可．

・バンクショットは不可．

第 3 章

動的計画法

3.1   動的計画法とは

  動的計画法とは，ある目的関数を最大，または最小にする最適問題に対する手法の中で も，特に時間的または空間的に多段階の最適問題（逐次決定問題）の最適解導出に極めて 有力な手続きを与える数理計画法の一分野であり，

1950

年にベルマンによって開発された．

3.2   多段階決定過程

  多段階決定過程は，いくつかの段階から成り立ち，各段階において決定がなされなくて はならない．ある段階でなされる決定が以後の段階でなされる決定に影響するという性質 に対して，全段階後（最終段階）における目的関数を適当にするように各段階での決定を 行う規則を形成する．

3.2.1   要素

  多段階決定過程の要素は，次の

5

つの要素からなる．

1)状態 ：各段階における系を記述するために用いられる変数の集合であり，その要

素を状態変数という．

 

2)決定と政策：決定段階は多段によって行われ，各段階における決定によって，過程の目

的とするものは定まる．この決定は，各段階の状態に影響を与え，しかも 多段にわたり最終状態に影響してくる．このような各段階における決定の 系列を政策という．

 

3)利得

：過程の最終目的とするものの，各段における値のことで，各段階での状態

と決定との関数として定まる．

 

4)状態変換

：各段階での決定の結果として状態の推移法則を与える．

 

5)マルコフ性：動的計画法の取り扱う多段決定過程では，系の過去の履歴は，未来の決定

を定めることに何も影響を与えない．すなわち，

n

^{段階以後の状態は}

n − 1

段階以前の段階における状態には関係しない．

また，上記の

1）2）3）を簡潔に表現すると，次のようにいえる．

・状態

s

_n＝自分がどこにいるか

・決定

d

_n＝現在何をすべきか

・利得

r

_n＝どの程度うまく仕事をしているか

多段階決定過程では，

1

つの段階のアウトプットの状態が，次の段階のインプットの状態と なり，図

3.1

のように示すことができる．

  段 の 番 号 は 通 常 降 順 に つ け る ． 段 階 に お け る 決 定 に よ り 状 態 が 状 態 に変換され，利得

n d

_n

s

_n

(

_{n n}

n

n

t s d

s

₋₁

= , ) R

_n

( s

_n

, d

_n

)

が得られる．

3.2.2   N 段階決定過程

  段階決定過程を考える．すなわち，システムが 段階において，状態の集合 の中に ある状態 を初期状態として始動する．決定の集合 から適当な決定 を選び，そ の結果として，関数 で与えられる利得を受け取り，変換 に従って 段階で のシステムの状態が定められる．すなわち，

N n S

_n

s

n

D

_n

d

_n

∈ D

_n

(

n n

n

s d

R , ) T

n

N − 1

(

n n

)

n

n

T s d

S

₋₁

= ,

      （3.1）

である．次に，システムは 段階に移り，決定の集合 から適当な決定 を 選ぶ．その結果として，関数 で与えられる利得を受け取り，変換 に従っ

− 1

n D

_n−1

d

_n−1

∈ D

_n−1

(

1 1

1 ₋

,

₋

− n n

n

s d

R ) T

n−1

−1

D

n

D

₁

第

1

段階 第

n − 1

段階

(

_{1 1}

)

1 ₋

,

₋

− n n

n

s d

T

(

_{1 1}

)

1 ₋

,

₋

− n n

n

s d

R

(

1 1

)

1

s , d T

(

_{n n}

)

n

s d

R , R

1

( s

1

, d

1

) R

₀

( ) s

₀

−1

S

n

S

⁰

図

3.2  N

段階決定過程

D

n

第 段階

n S

n

(

n n

)

n

s d

T ,

第 段階

n

第

n − 1

段階

d

n

d

_n−1

s

n

s

_n−1

s

_n−2

r

n

r

_n−1

図

3.1  段階の接続

て 段階での状態 に推移する．同様のプロセスを繰り返して，最後の

1

段階 において，決定の集合 から適当な決定

− 2

n s

_n−2

∈ S

_n−1

D

1

d

₁

∈ D

₁を選び，利得

^R

₁

( ^s

₁

^{, d}

₁

)

^{を受け取る．そし}

て，変換

T

₁によってシステムは最終状態

S

₀に入り，利得

R

0

( ) s

0 が定まってこの多段階決定 過程は終了する．このとき，各段階で選択する決定の系列

{ d

_n

, d

_n−1

, L , d

1

}

が政策となる．

目的関数として受け取る利得の実数値関数を最大（または最小）にする政策を最適政策と いい， で表す．目的関数値はシステムの初期状態 と，各段階でとる決定 によって定められる．以上の仮定に基づき最適政策 を見い 出す方法が動的計画法である．次で述べる最適性の原理が柱となっている．

* 1

* 1

*

, d , , d

d

_{n n}−

L s

n

1 1

, ,

, d d

d

_{n n}−

L

1^*

* 1

*

, d , , d

d

_{n n}−

L

3.3   最適性の原理 3.3.1   性質

最適性の原理とは，任意の初期状態と決定に対して，残りの決定は最初の決定として生 じた状態に関して最適政策を取らなければならないという原理である．簡単に説明すると 図

3.3

の点

A

から点

B

への最適経路を考えるとき，その道が点

C

を通るならば，点

C

から 点

B

への道の選び方は，点

C

から点

B

への最適経路でなければならないということである．

点

B

点

C

点

A

図

3.3  最適性の原理

3.3.2   N 段階決定過程での最適性の原理

最適性の原理を

N

段階決定過程に当てはめると， 段階決定過程では，その

1

段階にお ける決定をどのように選択しても，最適解を求めるには残りの

N

− 1

n

^{段階において最適政策}

を取らなくてはならない．

  を，状態 からはじめて最適政策を用いて 段階で得られる最大利得と定義する．

n

は決定過程で残っている段階の数を示す．初期段階

( ) s

f

_n

s n

N

n =

において決定 を選択したとす れば，受け取る利得は となる．最適性の原理によれば，

d

N

(

(

N N

n

T s d

f

₋₁

, ))

( )

_n

(

_N

(

_N

) )

n

s

d

f T s d

f

N

, max

₋₁

=

    （3.2）

が成立する．式（3.2）は一種の再帰関係式であり， を満足するすべての につ いて成立し，特に

≥ 2

≥ n

N n

= 1

n

に対しては，

( ) (

_N

(

_N

) )

d

R T s d

s f

N

,

1

= max

      （3.3）

が成立する．従って，逐次

f

_n

( ) s

を求めることができる．

3.3.3   逐次関係と最適化

  最適性の原理をもとにして導いた再帰関係式（3.2），（3.3）を解く手続きを考える．今，

段階の決定過程で

1

段階に到達しているとすれば，それ以前の事柄にかかわらず，

n

(

1 1

)

0

( )

0 1

(

1 1

)

1

(

1 1

)

0

(

1

(

1 1

) )

1

s , d R s R s , d R s , d R T s , d

R + = = +

      （3.4）

が最大になるように決定 を選ばなければならない．1 段階以前に取られた決定系列が最 適でない場合でも同様に式（3.4）が最大となるような決定 を選ぶ．そこで，

d

1

d

1

( ) ( ( ) )

[

_{1 1}

,

_{1 0 1 1}

,

₁

]

₁

( )

₁

max

1

s f d s T R d s R

d

+ =

    （3.5）

を考える．関数

f

₁は

s

₁の連続関数である．

  次に

2

段階においては，

( ) ( ) ( )

[ ]

( ) ( ( ) ) ( ( ( ) ) )

[ ]

( ) ( ( ) ) ( ( ( ) ) )

[ ]

( ) [ ( ( ) ) ( ( ( ) ) ) ]

( ) ( ( ) )

[

2 2 2 1 2 2 2

]

1 2 2 2 1 0 1 2 2 2 1 2

2 2

1 2 2 2 1 0 1 2 2 2 1 2 2 2

1 2 2 2 1 0 1 2 2 2 1 2 2 2

0 0 1 1 1 2 2 2

, ,

max

, , ,

, max

, max

, , ,

, ,

max max

, , ,

, ,

max

, ,

max

2

1 2

1 2

2 1 2 1

d s T f d s R

d d s T T R d d s T R d

s R

d d s T T R d d s T R d s R

d d s T T R d d s T R d s R

s R d s R d s R

d

d d

d d

d d d d

+

=

⎭⎬ ⎫

⎩⎨ ⎧ + +

=

⎭⎬ ⎫

⎩⎨ ⎧ + +

=

+ +

=

+ +

      （3.6）

( )

₂

2

s

= f

となる．同様にして，3段階に対しては，

( ) ( ( ) )

{

_{3 3}

,

_{3 2 3 3}

,

₃

}

₃

( )

₃

max

3

s f d

s T f d s R

d

+ =

    （3.7）

となる．よって

1 ≤ i ≤ n

について，

( )

{ ,

1 1 0

}

max R

_i

s

_i

d

_i

R

_i

R R

d d di i1 1

+ + +

+

₋

L

L

−

( ) ( ( ) )

{

_{i i i i i i i}

}

_i

( )

_i

d

R s d f T s d f s

i

= +

= max ,

₋₁

,

    （3.8）

が成り立つ．よって，多段決定過程は逐次計算可能である．

3.4   確率的多段階意思決定過程

  前節までは，状態変換と利得を求める関数（以下，これを利得関数と呼ぶ）が確定的な 確定的決定過程を論じた．それに対し，既知の不確実性を含む逐次決定過程で，確率変数 に対する分布が既知の場合を確率的決定過程という．確率的決定過程の特徴は，段階

i

での 最適決定 は状態 を観測して，不確実な要素がなくなったときに初めて定められる点で ある．すなわち，一般的には決定は現在の状態に依存する．

*

d

i

s

_i

  確率的多段階意思決定過程は，多段決定過程での

3

要素，状態変換 ，過程の現在の状 態 ，決定 に不確実要素を記述する確率 を加えて定められ，

T

n

S

n

d

_n

r

_n

s

_n−1

= T

_n

[ s

_n

, d

_n

, r

_n

]

^のよ

うに表される．ただし， の確率分布は既知とする．各段階からの利得が と によって 与えられたとしても，状態変換が現在の状態，決定，確率に依存するので，全利得関数は 初期状態と決定系列の確率的関数である．したがって，全利得関数そのものは決定系列を 評価する手段として適していない．ここで，確率的決定過程では全利得の期待値を取り，

全利得関数の期待値を最大にするような決定系列 を求める．

r

n

s

_i

d

_i

* 1

* 1

*,

d

, ,

d

d

_{n n− L}

  まず， を状態 からはじめて

n

段階で得る最大期待利得と定義する．すると，この 最大化問題では

( ) s

1

f

_n

s

₁

     

(3.9)

( ) [ ] [

⎭ ⎬

⎫

⎩ ⎨

⎧ +

= ∑

= + +

n

i

n n i i d i

n

s E J s d J s

f

1

1 1

1

max , ]

を得る．ここで，記号

E

は期待値を意味する（すべての確率変数に対する分布に関して期 待値をとる）．

  確率的決定過程に対する関数再帰方程式は，最適性の原理を用いて導出できる．計画期

間 の問題では，

n 2

段階のはじめの時点で，残り期間は

n − 1

^{段階となる．}

を新しい出発状態として，残り 段階ある過程に対して最適政策を用いる最大期待利得 は となる．過程のはじめでは はまだ未知であるが，確率変数 に対す る確率分布は既知であるので，確率変数 に対する確率分布を

[

1 1 1

]

1

2

T s , d , r s =

− 1 n

[

n

(

n n n

n

T s d r

f

₋₁

, , ) ] ^r

₁

^r

₁

r

n

F ( ) r

n ^{とすれば， 段階}

での期待利得は，

− 1 n

      （3.10）

( )

[

1 1 1

] ( )

1 1

T s , d , r dF r f

_{n n}

∫

−^∞∞ −

で与えられる．

1

段階からの利得は

J

1

[ s

1

, d

1

]

であるので，

1

段階での決定が で，その後，

最適政策をとったときの期待利得は，

d

1

      （3.11）

(

_{1 1}

) + ∫

−^∞∞ −₁

[

₁

(

_{1 1 1}

) ] ( )

₁

1

s , d f T s , d , r dF r

J

_n

となる． 段階の全過程で最適政策ととったとき，期待利得は で始まる 個の決定すべ てに関し最大化させなければならない．従って，

n d

₁

n

( )

¹

^{= max} {

¹

(

¹

^,

¹

) ⁺ _∫

₋^∞_∞ ⁻¹

[

¹

(

¹

^,

¹

^,

¹

) ] ( )

¹

}

1

r dF r d s T f d

s J s

f

_n

n d

  （3.12）

が成り立ち，初期状態が規定されると最適決定系列

d

_n^*

, d

_n−₁^*

, L , d

₁^*が逐次求められる．

ここで，期待利得

^E {



^∑

_i=ⁿ₁

^J

ⁱ

[ ^s

ⁱ

^{, d}

ⁱ

] ^{+ J}

ⁿ⁺¹

[ ] ^s

ⁿ⁺¹

}

は過程の期間中一定ではないことを明示する．

1

段階の過程では，

[ ] [ ]

[ ] [ { [ ]

[ ]

{ } _L

L + +

+

=

⎭ ⎬

⎫

⎩ ⎨

⎧ +

∫

∫

∑

∞

∞

−

∞

∞

−

= + +

3 2 2 2 3

2 1 1 1 2 1

1 1

1

1 1

, , ,

, , , ,

,

d r d s T J

d r d s T J d

s J

s J d s J E

n

i

n n i i i

}

  （3.13）

[ ]

{ }

[ ]

{

n n

} ] ( ) ( ) ( )

n n

n n n n n

r dF r

dF r dF r

s T J

d r d s T J

L

2 1

1

1 1 1

,

, , ,

⋅ +

+

+

−

−

−

である．過程の

1

段階では，決定

d

₁を決める．状態

^s

₂

^{= T}

₁

[ ^s

₁

^{, d}

₁

^{, r}

₁

]

^{は，過程の出発点では}

既知ではないが， 1段階の間で のある値が実際に起こっているため， 2

r

₁ 段階のはじめで

は

s

₂は既知となる．従って，2段階のはじめでは次のようになる．

[ ] [ ]

[ ] [ ]

[ ]

{ }

∫ [

∫

∑

∞

∞

−

∞

∞

−

= + +

+ +

+

=

⎭ ⎬

⎫

⎩ ⎨

⎧ +

L L

^{3 2 2 2 3}

2 2 2 1 1 1

1

1 1

, , , , ,

,

d r d s T J

d s J d s J

s J d s J E

n

i

n n i i i

（3.14）

[ ]

{ }

[ ]

{

n n

} ] ( ) ( ) ( )

n n

n n n n n

r dF r

dF r dF r s T J

d r d s T J

L

3 2

1

1 1 1

,

, , ,

⋅ +

+

+

−

−

−

この期待利得は，（3.13）式で与えられた期待利得とは一般に異なる．

  過程の

k

番目の段階のはじめでは，決定 の値と，状態 の値はす べて既知であるが，確率 の値は未知である．従って，

k

^{番目の段階のはじめで}

は，

1 2

1

, d , , d

_k−

d L s

₁

, s

₂

, L , s

k n

k

k

r r

r ,

+₁

, L ,

（3.1５）

[ ] [ ]

[ ] [ ] [ ]

[ ]

{ }

[

[ ]

{ }

[ ]

{

n n

} ] ( )

k

( )

k

( )

n n

n n n n n

k k k k k

k k k n

i

n n i i i

r dF r

dF r dF r s T J

d r d s T J

d r d s T J

d s J d

s J d s J

s J d s J E

L L L

L

1 1

1 1 1

1 1

2 2 2 1 1 1

1

1 1

,

, , ,

, , ,

, ,

, ,

+ +

−

−

−

∞

∞

− + +

∞

∞

−

= + +

⋅ +

+

+ +

+ + +

=

⎭ ⎬

⎫

⎩ ⎨

⎧ +

∫

∫

∑

となる． 番目の期間では期待利得 は状態 と決定 の

確定的関数である．

k [ ] [

⎭ ⎬

⎫

⎩ ⎨

⎧ ∑ +

= + +

n

i

J

i

s

i

d

i

J

n

s

n

E

1

,

1 1

] s

k

d

_k

, d

_k+₁

, L , d

_n

  本研究では，この確率的多段階意思決定過程を用い，問題を解析する．

第 4 章

ビリヤードの数理化

確率的多段階意思決定を行う準備として，ビリヤードを数理的に解析する．しかし，台 上の球のアクションは非常に繊細なものであり，気温，湿度，埃の影響，ラシャの種類や 状態など，あらゆる環境要素において変化する．公式世界大会などにおいては，特定の新 品のラシャの使用を徹底し，台に特殊なヒーターを組み込むことで気温や湿度などの外気 の影響を緩和させている．このような配慮により，環境要素による変化は無視できるもの とし，本研究では，基本的な物理的理論に基づき解析を行う．

4.1 球の配置

図

4.1  4×2

メッシュの場合の座標と配置例

台上の球の動きを解析するにあたり，台をメッシュ状に区切り，その１メッシュの中心 に球は配置されるものと考え，それを座標的に扱う．

ビリヤード台のサイズは，2540㎜

× 1270

㎜であり， 2：1の長方形である．一般化する と，

n × m

メッシュ（

n = 2 m

）の場合，台上の球の動ける範囲を，

0 ≤ x ≤ 2 n  

^，

0 ≤ y ≤ 2 m

となるように座標をとる．つまり，

1

つのメッシュに

1

つの球のみ配置可能と仮定すると，

扱える球の個数は，

(3,3) (7,3)

(5,1) (1,1)

y

4 x 4

8

2×1

メッシュのとき 

2

個

4×2

メッシュのとき 

8

個

6×3

メッシュのとき 

18

個    

M

メッシュのとき  個

m

n × nm

となる．図

4.1

に

4×2

メッシュの場合の具体例を示す．

4.2   角度と距離 

  以後の解析にさしあたり，手球，的球，ポケットの配置関係より，それぞれの角度と距 離の算出方法を記す．前節で論じたとおり，配置を座標的に扱い算出する．

手球，的球，ポケットの配置をそれぞれ（ ），（ ），（ ）とし，x 軸に対

して，それぞれ手球と的球を結んだ角度，的球とポケットを結んだ角度を

1 1

, y

x x

₂

, y

₂

x

₃

, y

₃

θ

a，

θ

_bとする．

また，シュートを狙う際に，手玉の進路に対する的球の進む角度を

θ

^{とする．手球と的球}

を結んだ距離，的球とポケットを結んだ距離をそれぞれ

d

_a，

d

_bとする．

θ

b

θ

y

( x

₃

, y

₃

) ( x

₂

, y

₂

)

( x

₁

, y

₁

)

θ

a

x

図

4.2  座標と角度の関係

図

4.2

より，それぞれの距離は，

( ) ( )

( ) (

3 2

)

²

2 2 3

2 1 2 2 1 2

y y x

x d

y y x

x d

b a

− +

−

=

− +

−

=

（4.1）

また，それぞれの角度は，

⎟⎟ ⎠

⎜⎜ ⎞

⎝

= ⎛

⎟⎟ ⎠

⎜⎜ ⎞

⎝

= ⎛

^{− −}

b b

a

a d

x x d

x

x_{2 1 3 2}

arccos ,

arccos θ

θ

（4.2）

となり，シュートを狙う際に，手球の進路に対する的球の進む角度

θ

は，

a

b

θ

θ

θ = −

（4.3）

と算出できる．

  また，狙うポケットを決定する際には，任意の手球と的球，それに

6

箇所あるポケット の位置関係から，式（4.3）で算出する

θ

が最小となるポケットを選択する．

4.3   基本分離

  下の図

4.3

に示すように，手球と的球が衝突した後，その位置関係に応じて手球は進む向 きを変え，的球は衝突による力で動き出す．その際の，手球の進む向きを表現する．

         

       

α

：衝突後の手球の進路と垂直線のなす方向      

β

：衝突後の的球の進路と垂直線のなす方向      

m

：球の質量（手球と的球は同質量）

     

v

：衝突前の手球の速度      

u

：衝突後の手球の速度

w

：衝突後の的球の速度

    図

4.3  衝突後の分離

衝突前と衝突後のエネルギー保存則，また，垂直方向，及び水平方向の運動量保存則より，

以下の

3

式を得る．

2 2

2

2 1 2

1 2

1 mv = mu + mw

（4.4）

β

α cos

cos + ⋅

⋅

= mu mw

mv

（4.5）

w u β

α

衝突

v

β

α sin

sin = ⋅

⋅ mw

mu

（4.6）

ここで，式（4.4），（4.5），（4.6）を簡略化し，さらに式（4,5），（4.6）の両辺を

2

乗す ると，以下の

3

式を得る．

(4.4)′

2 2

2

u w

v = +

(4.5)′

β β

α

α

^{2 2}

2 2

2

= u ⋅ cos + 2 uw ⋅ cos ⋅ cos + w ⋅ cos

v

(4.6)′

β β

α

α

^{2 2}

2

2

sin 2 sin sin sin

0 = u ⋅ + uw ⋅ ⋅ + w ⋅

さらに，(4.5)′，(4.6)′式を足し合わせると，

（4.7）

( cos α cos β sin α sin β

2

2

2

2

= u + w + uw ⋅ − ⋅

v )

となり，この(4.7)式と(4.4)′式を比較することにより，

( )

( )

2 0 cos

2

0 sin sin cos

cos 2

β π α

β α

β α β

α

= +

∴

= +

⋅

=

⋅

−

⋅

               uw

uw

（4.8）

しかがって，上式より手球と的球の分離角は

90

°であるといえる．

しかし，実際には，手球に上下の回転を加えるようにショットすることで，ラシャとの 摩擦の兼ね合いで，この分離角は変化する．つまり，手球が無回転の状態で的球に衝突し たときに的球の進む向きに対して

90°に分離するといえる．これを，手球の基本分離角と

定義し，以降の解析に活用する．

4.4   手球及び的球の衝突後の移動距離

d

2

     

：手球が進む距離（撞く強さに依存）

   

：手球が的球と衝突するまでの距離

d

d

1

   

d

₂：手球が衝突地点から本来進むはずの距離    

l

：手球が衝突地点から実際進む距離

   

m

：的球が衝突地点から進む距離 θ：的球が進む角度（3.2.2節より算出）

      図

4.4  衝突後の移動距離

l

^θ

d

d

₁

  図

4.4

より，以下の

2

式が得られる．

sin θ

2 2 1

d M

d d d

= +

=

（4.9）

以上より，衝突後の手球の移動距離は，

( d d

1

) ^{sin θ}

l = −

（4.10）

であり，同様に，衝突後の的球の移動距離は，

( d d

1

) ^{cos θ}

m = −

（4.11）

と求めることができる．

4.5   衝突後の手球の経路

まず，クッションがないと仮定して，衝突後の手球の移動距離 と分離した角度

l θ

^から，

どの位置まで進むかを考える．的球と衝突した点，つまり狙った的球の座標を

A

（ ），

手球が移動後に停止する場所の座標を

B（

）すると，

2 2

, y x Y

X ,

2 2

sin cos

y l

Y

x l

X

+

⋅

=

+

⋅

= θ

θ

（4.12）

となる．

  ここで，

n × m

メッシュのモデルにおいて，球の配置可能範囲は

0 ≤ x ≤ 2 n  

^， なので，

m y 2 0 ≤ ≤

<

X 0， X > 2 n

，

Y < 0， Y > 2 m

の場合，クッションの作用を考慮しなければ ならない．つまり，クッションは

x =0， x =

，

=0， =

の

4

箇所に存在する．ここ で，便宜上， ， とする．そして，それぞれの場合に分けて考察する.

n

2 y y 2 m

n

N = 2 M = 2 m

まず，

Y > M

^{のときを考える．図}

4.5

のように，手球の経路上かつ， の点を

C

（ ）とし，線分

AB

の距離を

M y =

c c

y

x , r

とする．斜線部分の三角形の比より，

r l y M y

Y −

₂

: −

₂

= :

2 2

) (

y Y

y M r l

−

−

= ⋅

（4.13）

つまり，クッションからの跳ね返りの距離

l ′

は

 

( )

y

2

Y M Y r l l

l −

= −

−

′ =

（4.14）

θ

B( X , Y )

となる．また，式（

4.5

）より，点

C

の座標が求められる．

M y

x r

x

d d

=

+

⋅

= cos θ

₂

（4.15）

ここで，左右のひねりを考慮しない場合，クッションでは入射角＝反射角の関係が成り立 つ．つまり，反射後の進行方向

θ ′

は

θ

θ ′ = −

（4.16）

となる．さらに，ひねりを考慮するならば，ひねりによる効果（角度の広がり）を

δ

とす ると，反射後の進行方向

θ ′′

は単純に和で求めることができ

δ θ δ θ

θ ′′ = − + = ′ +

（4.17）

となるので，式（4.6），（4.7），（4.9）より，反射後に停止する配置

D ( x

d

, y

d

)

は

A( x

₂

, y

₂

)

C( x

_c

, y

_c

)

x y

r l

D ( x

_d

, y

_d

)

図

4.5  クッションの作用

m 2

n

2

c d

c d

y l

y

x l

x

′′ +

= ′

′′ +

= ′ θ

θ sin

cos

（4.18）

と導くことができる．

  同様に，

Y < 0

にときは，

2 2

y Y

y r l

−

⋅

= −

（4.13）′

y

2

Y r lY l

l ′ = − = −

（4.14）′

0

cos

₂

=

+

⋅

=

c c

y

x r

x θ

（4.15）′

δ θ δ θ

θ ′′ = − + = ′ +

（4.17）′

となるので，これらを式（4.10）に代入すると，反射後の停止は位置

D

を求めることがで きる．

  続いて，

X > N

のときは，

2 2

) (

x X

x N r l

−

−

= ⋅

( )

x

2

X N X r l l

l −

= −

−

′ =

cos x

2

r y

N x

c c

+

⋅

=

=

θ

δ θ δ θ

θ ′′ = − + = ′ +

これらの式を，また同様に，

X < 0

のときも，

2 2

x X

x r l

−

⋅

= −

x

2

X r lX l

l ′ = − = −

cos

2

0

x r

y x

c c

+

⋅

=

=

θ

δ θ δ θ

θ ′′ = − + = ′ +

以上の式を得る．式（

4.10

）に代入することで，反射後に停止する配置

D

を決定する．

  ただし，この配置

D ( x

_d

, y

_d

)

が配置可能範囲である

0 ≤ x ≤ 2 n

^，

0 ≤ y ≤ 2 m

^{を満たさない}

ときは，同じ処理を繰り返す．

第 5 章

確率的多段階意思決定モデル

4

章までに論じた手法をもとに，確率的多段階意思決定モデルを作成する．ここで,モデ ルの作成にあたり，必要な要素を以下に整理する．

n =シュート選択の回数

状態

決定 どのような戦略をとるか，どの球を狙うか 確率

=

の状態の配置に推移する確率

期待利得

=その時点での利得の期待値

5.1   段階と状態

ブレーク後の配置を状態 とし，1 段階の決定を行うと，状態 に移る．つまり，シュ す のもとで，的球がひとつ減るごとに状態数は１ずつ増加 初期状態において的球が

k

個の過程では，k段階過程となり，状態は

0

から

k

までと なる．つまり，最終的に手球

1

個だけが台上に残る状態が状態 となる．

具体例として，的球

5

個のゲームにおける各段状態の球の個数を表

5.1

に示す．

前述したとおり，台をメッシュ 区切 ，球の配置を行う その を追及する めにメッシュを小さく分けることは困難で なら，確率的多段階意思決定過程 は各ノード毎に再帰 算 り すこ に加 ，本モデルでは，各状態毎に飛躍的 ノード数が増加する また，いかにして計算量を低減させるかも重要となる．

s

n

=現在の配置の状態

n

=

d

r

n ^次

J

n

s

0

s

₁

ートが べて成功するという仮定 する．

n

表

5.1  的球 5

個のゲームにおける各状態の球の個数

状態

s

0

s

₁

s

₂

s

₃

s

₄

s

₅

s

手球数

1 1 1 1 1 1

的球数

5 4 3 2 1 0

  で り ． 際，現実感

た ある．なぜ

と

で 的に計 を繰 返 え

に からである．

a

× メッシュで，各状態におけるノード数は，その状態での配置の数を表す（前章まで

b

 

は

n × m

メッシュと表記してきたが，記号の混乱を避けるため本章では

a × b

メッシュと表 記する）．球の個数を

m

^{とすると，全}

n

^{段階過程の状態}

s

_k^では，

m = n − k +1

個の球が存在 している．

ここで，計算量を低減させるために，ノード数を減らすことを考慮し，以下の

4

通りの 方法の仮定し，配置数，つまり，ノード数を考え，本研究で用いる方法を決定する．

( ) ab

^m通り     （B）：複

（A）：それぞれの球の配置が全メッシュ数 通り考えられることより，配置は

数の的球を区別しないものとすると，配置は

ab

∑

⁻

⋅

¹

= m

i ab

C

ab

通り

    （C）：複数の的球を区別せず，それぞれの的球が同じメッシュに存在しない場合，配

1 i

置は

ab ×

_ab

C

_m−1通り

    （ ）：複数の的球を区別せず，すべての球が同じメッシュに存在しない場合，配置は

で，的球を区別する必要がな

うに，手球と的球が同じメッ 存在することを許さないと，ネクストを決定する際に

であるといえる． ，方法（B），（C）のノード数を比較すると，具体例を示した表

5.2

らも明らかなように，方法（B）よりも方法（C）方が配置の組み合わせが少ないので，

5.2  

本 多段 で用 を る． さ り 下

の

2

する

状態

D

m通り

ab

C

本研究で題材としたゲームでは，どの的球を狙ってもよいの

い．つまり，方法（A）では，必要以上のノード数を計算することとなる．また，（C）のよ シュに

支障が生じる．以上より，本研究のモデルに最適なノード数は方法（B），（C）のどちらか ここで

か

このモデルでは方法（C）を採用する．

表

5.2  3×6

メッシュ，的球

5

個のゲームにおける各状態のノード数の比較

s

0

s

_{1 2}

s

_{3 4}

s

₅

確率設計

節では，確率的 階決定過程 いる確率

r

_n 設計す それに しあた ，以 つの確率を定義 ．

s s

ノード数

(A)

 

34,012,22 4

 

1,889,568

 

104,976

 

5,832

 

324

 

18

ノード数

(B) 227,070 72,846 17,766 3,078 324 18

ノード数(C)

154,224 55,080 14,688 2,754 324 18

ノード数

(D) 111,384 42,840 12,240 2,448 306 18

・ ：ネクスト配置確率

5.2.1   ネクスト配置確率

ネックスト配置確率は，状態 から状態 に推移するとき，状態 における任意の的 の任意の位置に移動する確率を表す．4.5 節の「衝突後の手 の経路」を用いて算出する．

し，最大値を，台の

長辺

2

往復分の強さ（ ）とする．

・シュート成功後に手球が止まった位置のメッシュ毎にコストをカウントする．

    コストは，［強さの最大値−そのときの強さ］とする．これは，強さによるシュート，

度を考慮するためである．

・全メッシュに対するコストの総和より，各メッシュの確率を算出する．

また スト配

  こ 球の

N

・

S

：シュート成功確率

s

k

s

_k+1

s

_k

球を狙い，その手球が状態

s

_k+1 球

算出方法を以下に示す．

・任意の的球を狙う際に，強さ（手球が進む距離）を

1

ずつ増加させる．

その際，強さの最小値を，的球がポケットに届く最小の強さと

a

×

b

メッシュのモデルでは

8 a

 

もしくはネクストの難

，状態

s

_kにおいて，複数の的球が存在するときには，それぞれの的球についてネク 置確率を導出する．

こで，6×3メッシュで図

5.2

のように配置番号を付け，それに対応した手球と的 位置関係からネクスト配置確率を算出した結果の一部を図

5.3

に示す．

( x

₁

, y

₁

)

( x

₃

, y

₃

) ｙ

( x

₂

, y

₂

)

図

5.1  ネクスト配置確率

ｘ

0 0 0.0987 0 0.0189 0.0405 0 0.0444 0.1273 0 0 0.0545 0.1111

0 0 0 0 0.2115 .1916 0 0.0014 0.1269 0 0.0621 0.0061 0.0444 0.1152 0.0424 0.0444 0.0788

0 0 0 0 0.0654 0.0192 0.0513 0 0 0 0.1053 0.0837 0 0.0182 0.0747 0.1475 0.0909 0

0.051 0.018 0 0 0.091 0.172 0 0.0897 0.2872 0 0 0 0 0.2476 0.1646 0 0 0

0.042 0.02 0.006 0.079 0.069 0.115 0 0.1026 0.1359 0.1923 0 0 0.2598 0 0 0.1207 0 0

0 0.055 0.087 0.069 0.127 0 0 0.0038 0.1885 0 0 0 0.0963 0 0 0 0.0854 0.0256

0 0.473 0 0 0 0 0 0 0 0 0 0 0.512 0 0 0 0 0

0 0.527 0 0 0 0 0 0.2625 0 0 0 0 0 0.2027 0 0 0.0315 0

0 0 0 0 0 0 0 0.0399 0.2159 0.2016 0.1506 0.1296 0 0 0.1486 0.1051 0 0

手玉=3 的球=8

0.401〜1.000

手球=4 的球=0

手球=6 的球=12

手球=9 的球=0

0.001〜0.100 0.101〜0.400

手球配置 的球配置

手球=8

的球=3

手球=16 的球=7 手球=12

的球=6 手球=11

的球=13 的球=3 手球=9

.6051 0 0 0 0.17 0.1484

0 0

12 x

6

⑰

⑤

⑮ ⑯

⑬ ⑭

④

①

⓪  ② ③

図  

3

メ ュ の配 番号

y

6

⑫

⑩ ⑪

⑦ ⑧ ⑨

⑥

5.2 6

× ッシ で 置

図

5.3  ネクスト配置確率の実行例

5.2.2   シュート成功確率

その名の通り，ある的球を狙ったときに狙ったポケットにシュートが成功する確率であ る．しかし，現実のシュート成功率というものは当然プレーヤーの能力によって異なるた め，本研究では仮想のプレーヤーを設定し，それぞれの配置における距離と角度の関係か らそのシュート成功確率を各プレーヤーに与える．また，シュート成功確率を導出する際 に用いる距離と角度の評価の値を簡易度と定義する．

ここで指す距離とは，手球と的球を結ぶ距離と的球とポケットを結ぶ距離の和であり，

4.2

節でいう にあたる．また，その簡易度は台の長辺+短辺の長さをシュート可能な 最大距離とし，それ以上の距離のときは簡易度を

0

とする．

一方，角度は，シュートを狙う際に，手球の進路に対する的球の進む角度のことであり，

4.2

節でいう

b

a

d

d +

θ

にあたる．ここで，手球の進路に対する的球の進む角度が

90°以上になる

ことは物理的に存在し得ないことから

90°以上の角度は簡易度を 0

とする．

  これら

2

つの指標に表

5.3

のように簡易度を割りあてる．ただし，距離の簡易度は， × メッシュモデルのときの値である．

表

5.3

  簡易度との対応

簡易度

0 1 2 3 4 5 6 7 8 9

a b

距離

>6.0 >5.7 >5.4 >5.1 b b b b >4.8 b >4.5 b >4.2 b >3.9 >3.6 >3.3 b b b

角度［度］

>90.0 >85.5 >81.0 >76.5 >72.0 >67.5 >63.0 >58.5 >54.0 >49.5

10 11 12 13 14 15 16 17 18 19 20

>3.0 >2.7 >2.4 >2. b b b 1 b >1.8 b >1.5 b >1.2 b >0.9 b >0.6 >0.3 >0.0 b b b .

>4 5.0 > 0.5 >36.0 >31.5 4 >27.0 >22.5 >18.0 >13.5 > 9.0 >4.5 >0.0

易度による差は生じにくいことがわ か

理

ここで，角度の簡易度に着目すると，任意の配置において最適なポケットを選択したと きに，その多くは角度が

45°以下になる．例えば，3×6

メッシュにおけるすべての配置で は，全体の

89.6％を占める．このことから，角度の簡

る．そこで，距離の簡易度に

2

倍の重みを付け，それと角度の簡易度との和をとること によって，シュート成功確率を導く．

ただし，距離と角度のうち，どちらか一方でも簡易度が

0

の場合は，そのシュートは物 的に成立しないものとみなし，成功確率を

0

とする．

表

5.4  シュート成功確率と簡易度

シュート成功確率

1.0 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1

簡易度(距離＋角度)

>54 >48 >42 >36 >30 >24 >18 >12 >6 >0

5.2.3   使用する確率

上の つの確率を用いて，確率的多段階決定過程で用いる確率 導出す ．前述 ように 状態 か に推移する確率である．つまり，状態

狙 の ト さ 態 る

いう確率である．つまり，ネクスト配置確率 とシュート成功確率

ー 功 合

  以

2 r

_nを る し

た ，確率

r

_nとは

s

_n−1 ら状態

s

_n

s

_n−1におい て任意の的球を い，そ シュー を成功 せ，状

s

_nのどこにネクストが配置され か

N S

^{は互いに独立あり，}

と 確率

r

_nは

シュ トが成 した場    

r

_n

= N × S

( S )

N r

_n

′ = ′ × −

シュートが失敗した場合   

1

となる．ここで

N ′

とは，シュート失敗した場合のネクスト配置確率であり，手球のネクス ト配置だけからでなく，外れた的球が新たにどこに配置されるかという観点から確率を導 出するものである．ただし，本研究のモデルには

r′

を用いる過程，つまり，シュートが失 敗する過程は省略する．

5.3

まず，以下の記号を再定義する．

：利得

置 態

  期待利得と決定

 

S

n：状態

D

n：決定

J

n

R

n：確率

T

n：状態変換

s

ni^{：配 を表す状}

S

_n^の要素（

s

_ni

∈ S

_n）

u

ki^：状態

s

_ki^から

n

段階までの最大期待利得

( ) ^{j i} [ ] ^X

r

_n

,

：的球

X

を狙い，状態

s

_ni^から状態

s

_n+1j^{に推移する確率（}

r

n

( ) j , i ∈ R

n^）

率的多段階意思決定過程において，状態

S

₁からはじめて 段階で得る最大期待利得は

n

確

( )

[ ] ( )

( ) ^{S = max} { ^J ( ^{S , D} ) ⁺ _∫ }

f

^∞

∞

− −1 0 0 0 0 0

0 0 0

0

, ,

1

R dF R D S T f

_n

n d （5.1）

と表される．また，最終的な目的は，各段階での利得の和