Þ ï Â § ç é æ s g t â ² x w B · ß ` h & Ï*¨ O q f w ° A

1,a) 2 1,b)

(P-UCT )

Support Vector Machine (SVM)

1.

1.1

[9]

[2]

1

Waseda University2

ZENRIN DataComa) [email protected]) [email protected]

1.2

[2]

[4]

(MOGA)

MOGA

[3]

[6]

( )

― 854 ―

「マルチメディア，分散，協調とモバイル(DICOMO2019)シンポジウム」令和元年7月

© 2019 Information Processing Society of Japan

[5,10,11]

UCB1

UCB1

UCB1

UCB1

1.3

UCT

(P-UCT )

P-UCB1

P-UCB1 UCB1

Support Vector Machine (SVM) [12]

1.4

(1)

(2) P-

UCB1 P-UCB1

(a)

(b)

1:

(3) 4

[2]

― 855 ―© 2019 Information Processing Society of Japan

1:

1.875

3.000

2.

2.1

G = (V,E)

V

E

L = {l1, l2, . . . , lk}vs ∈ V

eu ∈ E

vs ∈ V lat lng z

Lvisible ⊆ L

lt ct

h PP ct

1

PP

eu ∈ E et sl

cr hr w

*1 et

sl

cr

1. 1 1(a)

1(b)

9 {v1, v2, . . . , v9} 10

{e1, e2, . . . , e10} 6

{e11, e12, . . . , e16} 2 {l1, l2}w

l1 {pp1, pp2, pp3, pp4} l2 {pp5, pp6, pp7, pp8}�

*1

2:

2.2

H = {h1, h2, . . . , hn} u

like(hn)

like(hn) /

2

2 2 h1 (

) h2 ( ) 2 h1

u h2 u

2.3

1 ( ). G = (V,E)

vs ∈ V vg ∈ V

2. 3

vs

vg


3:

�

3.

(P-UCT )

2

(i)

(ii)

(i) SVM

SVM 2

/ 2

2 SVM

(ii)

UCT

P-UCB1

P-UCB1

P-UCT

3.1

Phase 1–Phase

3

Phase 1 :

SVM

20

Phase 2 :

vs ∈ V vg ∈ V

vs vnow ∈ V

0

Phase 3 :

5

(Step 1)

vnow

P-UCB1

vselect

(Step 2)

vselect

vg ( )

(Step 3)

SVM 20

0 ≤ rwselect ≤ 1 (rwselect

)

(Step 4)

rwselect vselect P-UCB1

vselect 1

(Step 5)

(Step 1) (Step 4)

(Step 4) vselect

N (Step 1)

vselect vnow vnow vg

vnow

3. 4

(Phase 1)

vnow

(Phase 2 4(a)) vnow 2

P-UCB1

(Phase 3-Step 1 4(b))

(Phase 3-Step 2 4(c))

SVM 20


(a) Phase 2 : (b) Phase 3-Step 1 : (c) Phase 3-Step 2 :

(d) Phase 3-Step 3 : (e) Phase 3-Step 4 : (f) Phase 3-Step 5 :

4:

0 ≤ rwj ≤ 1

(Phase 3-Step 3 4(d)) rwj

P-UCB1 v1

1

(Phase 3-Step 4 4(e))

N

(Phase 3-Step 5 4(f)) �

3.2 P-UCB1

P-UCB1 UCB1 [10]

vj ∈ V 3.1

0 P-UCB1

1

P-UCB1(vj) = Xj +

√2 log n

nj(1)

Xj

nj n

n nj

vnow 0

Xj 2


5:

Xj =

nj∑k=1

rwj(k)

nj(2)

rwj(k) vj k

P-UCB1 2

(i) ( )

(ii)

P-UBC1 ( )+( )

3.3

[2]

[8]

20

(A)

1.

2.

( )

vg

5

{v1, v4, v7, v8}4 v1(= vs) v2 1

v4 {v3, v5} 2

v7 {v5, v6} 2

9

3.

[1] 8

22.5

(B)

4.

ct

5.

ct

6.

ct

7.

ct

8.

w

true

9.

w

true

(C)

10.

sl

11.

sl

12.

sl


(a) (b)

6:

13.

sl

14.

sl

15.

sl

16.

sl

17.

sl

(D)

18.

[7]

1

19.

ct 1

1

20.

ct 1

1

SVM /

2 2

SVM SVM

C = 1 γ = 0.1

4.

Python3

22 23 8

6

4.1

(1)–(5)

(1)

15 ( 5 10

)

( )

300m–1000m


2:

A B C D E F G H

10 0 0 0 3 0 2 2 0 0.875

20 0 2 4 3 2 1 4 3 2.375

30 4 4 4 4 0 1 4 3 3.000

[2] 2 4 4 0 0 2 1 2 1.875

(2)

( )

( )

(3)

SVM

2

SVM 10 20 30

( 10

5 )

(4)

0 1 2 3 4 5

0 4

(5)

[2]

5

4.2

2 4.1 Step

2 ( ) A–H

10 0.875 20

2.375 30 3.000

[2] 1.875

A 7– 10

10 20

0

30

4

2

7: ( 10) A

8: ( 20) A

20 30


9: ( 30) A

10: [2] A

5.

P-UCT

( ) SVM

22 23

8

10 0.875

20 2.375 30 3.000

1.875

20 30

[1] , , “,”

, vol. 7, no. 2, pp. 11–20, 2002.

[2] , , , “,” A,

vol. 87, no. 1, pp. 132–139, 2004.

[3] , , “,”

21, p. 51. , 2005.

[4] , , , , , “

,”(ITS), vol. 2006, no. 22 (2006-ITS-024), pp. 31–38, 2006.

[5] , “ -,” , vol. 49, no. 6, pp. 686–693,

2008.

[6] , “ ,”25

, p. 165. , 2009.

[7] , , , , ,, “

,”2014 , vol. 2014, pp. 102–107, 2014.

[8] , , , , ,, , “

,”, pp. 1–10, 2015.

[9] , “ ,” 2018,http://www.soumu.go.jp/johotsusintokei/whitepaper/ja/h30/html/nd252110.html.

[10] C. B. Browne, E. Powley, D. Whitehouse, S. M. Lu-cas, P. I. Cowling, P. Rohlfshagen, S. Tavener, D. Perez,S. Samothrakis, and S. Colton, “A survey of monte carlotree search methods,” IEEE Transactions on Computa-tional Intelligence and AI in Games, vol. 4, no. 1, pp.1–43, 2012.

[11] R. Coulom, “Efficient selectivity and backup operatorsin monte-carlo tree search,” in Proc. International Con-ference on Computers and Games, pp. 72–83, Springer,2006.

[12] N. Cristianini, J. Shawe-Taylor et al., An Introductionto Support Vector Machines and Other Kernel-BasedLearning Methods, Cambridge University Press, 2000.


Documents

Þ ï Â § ç é æ s g t â ² x w B · ß ` h & Ï*¨ O q f w ° A