⼤規模な計算資源の強いゲームプレイへの貢献
美添 ⼀樹

九州⼤学 情報基盤研究開発センター 教授
2022年4⽉8⽇ αxSCシンポジウム「ゲームとスーパーコンピュータ」
https://www.cc.kyushu-u.ac.jp/scp/users/news/2021/523.html

頭の良い機械を作りたいという夢は昔からあった
The Turk (トルコ⼈) 1770年〜1854年
チェスを指すオートマタ(機械⼈形)

2

コンピュータ
DeepBlue (IBM)

チェス世界チャンピオン
対Kasparov (ロシア)
1997年
チェス対戦
DeepBlue勝利
ゲーム⽊探索チェス専⽤チップ
利⽤のスパコン（今から⾒ると⼒任せ）

Copyright 2007, S.M.S.I., Inc.
Owen Williams, The Kasparov Agency.

3

AlphaGo vs プロ囲碁棋⼠

AlphaGo

Google Deep Mind 社
が開発した囲碁プログラム
2016年3⽉
イ・セドル（元世界最強）に4勝1敗で勝利
2017年1⽉
ネット上でトップ棋⼠に60連勝(ハンドル名 Master)2017年5⽉
柯潔（現世界最強）に3連勝
2017年10⽉
囲碁のルールだけから学習した
AlphaGo Zero が AlphaGo を上回る
2017年11⽉
AlphaZero 同⼿法で将棋とチェスも最強に

4

念のため: ゲーム⽊探索

5

ゲーム⽊探索の2つの⽅法
その1, 最後まで読み切る

その2, 評価関数を使う

詰将棋

局⾯五⽬並べスコア

がんばって良い評価関数を作る? ? ? ?

どうぶつ
しょうぎ

チェッカー

どの⼿が良いのか︖

6

その1, 最後まで読み切る

読み切れるゲーム、無理なゲーム
三⽬並べ
765

どうぶつしょうぎ
246,803,167

チェッカー
5✕1020

ゲームの
局⾯数

読み切れる
オセロ
1028

チェス
1041

将棋
1069

囲碁
10170

読み切れない注意: これは合法局⾯の数（の推定）⼿順を考慮するとさらに⼤きい（主に千⽇⼿の影響）

7

つまり評価関数が必要
minimax探索 + ⼿作り評価関数の成功例は多数存在する

αβ探索(minimax探索 + αβ枝刈)
先⼿はスコア最⼤化
後⼿はスコア最⼩化

5050

熟練の開発者の⼿によるいわば「芸術品」

チェッカー

47

1994年にチャンピオンに勝利
CHINOOK vs Tinsley
50

7047

67

オセロ

1997年にチャンピオンに勝利
Logistello vs 村上
50

2470

25

47

15

探索順序

探索を途中で打ち切り評価関数の値を⽤いる

6765

チェス

1997年にチャンピオンに勝利
IBM DeepBlue vs Kasparov8機械学習の時代

機械学習による評価関数の成功例（引⽤は初出の論⽂ではない）[Tesauro, Gerald 1995] "Temporal Difference Learning and TD-Gammon"

TD-gammon

1992年 強化学習＋NNによるバックギャモンプログラム[Buro 1995] ”Logistello: A Strong Learning Othello Program”

オセロ

1997年にチャンピオンに勝利
Logistello vs 村上[Hoki, Kaneko 2014] ”Large-Scale Optimization for Evaluation Functions with Minimax Search”

将棋

2005年 Bonanza method
現在は⼈間よりかなり強い

9bonanza method

学習による評価関数
棋譜データからの機械学習による評価関数
主に2つ⽅法がありうる
1, 勝敗 / 形勢を推測する
2, 最善⼿を予測する
ここではまだ深層学習の話題ではなく、より単純なモデル

基本的なアイデアある局⾯ p の特徴ベクトル𝑓(𝑝)それぞれの特徴の重み𝒘

ある局⾯ p の評価 e(p,w)
𝑒 𝑝, 𝒘 = 2 𝒘𝒊 𝑓! (𝑝)!

将棋における「特徴」と「重み」の例
⾶⾞がある（特徴）x ⾶⾞の価値（重み）
⽟と⾦銀が特定の配置にある x その重み
10bonanza method

重みの次元と学習⼿順
駒の価値

13通り

⽟と駒⼀つの位置関係

81 x 駒の種類 x 80
合法⼿と対称性より 60,876

⽟と王と駒⼀つの位置関係

81 x 80 x 駒の種類 x 79
合法⼿と対称性より 2,425,950

⽟とそれ以外の駒⼆つの位置関係

81 x 駒の種類 x 80 x 駒の種類 x 79
合法⼿と対称性より 44,222,454

訓練例の全局⾯につき、浅い探索を⾏って候補⼿を選ぶ

収束するまで右の⼿順をプロの着⼿との不⼀致を数える
繰り返す
詳細は省略

⽬的関数の偏微分に基づいて重みを更新する

これはあくまで⼀例でもっと⼤量の特徴量を⽤いる例も存在する
𝑒 𝑝, 𝒘 = 2 𝑤! 𝑓! (𝑝)!

f, wの次元が数百万〜数億最初のbonanzaの学習はPentium 4 のマシンで90⽇計算時間が強さに変換される時代
新たな枠組みとして機械学習による評価関数 + αβ探索
「⼯芸品」から「⼯業⽣産品」へ
11

囲碁の評価関数は作れるか︖
良い評価関数は、正確で⾼速でないといけない

駒の価値のような⼿がかりがないオセロの隅ほど特徴のある場所がない

深層学習以前は囲碁の評価関数を作れた⼈は居なかった
途中で終局図を予想するのも困難

12コンピュータの画像認識
ILSVRCImagenet large Scale
Visual Recognition Challenge
プログラムによる画像認識の精度を競う

⽝と猫を⾒分けるくらいは余裕[K. He et al. 2015, Microsoft Research Asia]

2014年 ⼈間（⾮専⾨家）を超える精度を達成（Google と Microsoft）

13

DCNN: Deep Convolutional Neural Network
dog 0.94
cat 0.03
aircraft 0.01
ship 0.01

フィルタをたくさん重ねると、複雑な形状を検知できる
個々のフィルタは他純な操作に対応（輪郭線抽出とかぼかしとか）

画像認識では例えばここの数値が⾼いと猫、と⾔うのが特定されている (by google)
https://googleblog.blogspot.jp/2012/06/using-large-scale-brain-simulations-for.html

Microsoft の ResNet は 152層 [K. He et al. 2016]（注︓1,202層まで実験されているが、最⾼精度は152層） 「猫顔ニューロン」

14画像認識の⼿法で着⼿予測
囲碁は19x19の画像

アマ⾼段者の棋譜約17万局から学習

盤⾯から画像を⽣成し、「⽝」「猫」などの代わりに次に打つ場所を予測
予測精度57-60%（通常の画像はRGBの3枚、AlphaGo Zero では下図の17枚） アマ5段が試したら50%程度
この図は9路盤だが、実際は19路盤である

⿊の位置

⽩の位置

過去7⼿の⿊/⽩の位置

⼿番 (0なら⽩番)
15

policy network

value network「着⼿予測」と「形勢評価」

policy network は局⾯の着⼿確率を予測[Silver, Huang et al. 2016] Fig. 1b

⼈間の棋譜からの教師あり学習で実現可能
最新のGPUなら1枚で数週間︖
1つの対局の約200⼿全てが教師例(棋譜数 x 約200 の教師例)

value network は局⾯の勝率を予測

着⼿予測よりも⼤量のデータが必要
同じ対局の局⾯は類似している
そのまま使うと過学習する(棋譜数 x 1 の教師例)(実際は1はちょっと極端だが）16

⾃⼰対戦で棋譜⽣成→学習
Deep Learningの問題点
データが⼤量に必要理想的な解決策

プロ棋⼠を1万⼈雇⽤してひたすら対局させる（無理）AlphaGo の解決策
まずプロ棋⼠の⼿を予測するDNNを⽤意
それを強化学習でちょっと強くする（アマ5段程度）
それを使って3,000万局対局させ、1局から1局⾯採取
それを元に Deep Learning で Value Network 作成
17

AlphaGo 初期バージョン

policy-net + value-net + MCTS
着⼿予測で枝刈り

Monte-Carlo Tree Search を⽤い、value-net の評価 (予測勝率) の⾼い⽅へ探索⽊を伸ばす
なお、初期バージョンはNN以外にサンプリング (rollout) も併⽤

このバージョンが、元世界ランク1位の囲碁棋⼠
イ・セドルに4勝1敗で勝利 (2016年3⽉)

18AlphaGo Zero⼈間の棋譜を全く使わない“Zero” からの学習
深い探索で⾃⼰対戦した結果を予測するようにモデルを訓練（基本のアイデアは単純）

⾃⼰対戦による強化学習
膨⼤な計算資源
しかし⾃⼰対戦の規模が巨⼤
学習の各ステップで25,000局の⾃⼰対戦 (1⼿0.4秒)(1GPUなら20⽇ぐらい)
最終的に40⽇間で2千9百万回の⾃⼰対戦を⾏う(1GPUなら 25,000⽇ぐらい)前のバージョンの AlphaGoに対して 100戦全勝
⼈間に負けた記録は無し
19

20

訓練の計算量

最近の⾃然⾔語モデルにはAlphaGo Zero を超える物も有名なグラフですが、https://openai.com/blog/ai-and-compute/
AlexNet to AlphaGo Zero: A 300,000x Increase in Compute
AlphaGoZero

Megatron-Turing NLG
GPT-3

AlphaGo Zero 等の強化学習の場合、単にモデルとデータが⼤規模な場合とは異なりシミュレーション (⾃⼰対戦)が⼀番時間がかかる
21探索も並列化の対象「早さは強さ」。以下はプロに勝利した例
チェス専⽤チップ搭載スーパーコンピュータ(今から⾒ると⼒任せ)IBM Deep Blue
[対Kasparov 1997]

普通の計算機・普通のネットワーク
だが効率よい並列化（プログラミングの芸術だと思います）

GPS将棋[第2回電王戦 2012]

Monte-Carlo Tree Searchを並列化
176GPUを使⽤(対1ノード版の勝率 75%)

AlphaGo[対イ・セドル 2016]22

Monte-Carlo Tree Search (MCTS)
確率的な探索アルゴリズム。強化学習と共通の理論的背景を持つ
通常の探索アルゴリズム

50

65

30

Monte-Carlo Tree Search

Upper Confidence Bound [Auer+2002]
MCTS [Coulom2006]

節点の評価値は“確率”
サンプリングや機械学習で確率を得る
確率同⼠を⽐較して探索

100 70
節点の評価値はスカラー⼤⼩⽐較で探索
2003 nicolas p. rougier (CC BY-SA 4.0)

元々、囲碁の研究から⽣まれた⼿法
ゲーム以外でも⾮常に多彩な応⽤あり
AlphaGo も利⽤している

23

並列探索の難しさ
radfbeghcikjlnom

単純に分割すると計算負荷が不均等になり⼤規模な並列化は不可能

探索空間が巨⼤な時は何らかの枝刈りが必須
枝刈りがあると並列化は難しくなる

012

324

並列 Monte-Carlo Tree Search
テクニカルすぎるので省略。鍵となるテクニックの名称は下図参照
並列囲碁プログラム mp-fuego (50 node vs 1 node で48勝2敗)
化合物探索 (逐次2560分 対 256並列10分がほぼ同性能)
実装は MPI_Iprobe を使った技巧的なプログラムで、かなり複雑
K. Yoshizoe, A. Kishimoto, T. Kaneko, H. Yoshimoto, Y. Ishikawa. “Scalable Distributed Monte-Carlo Tree Search.” SoCS 2011.
X. Yang, T. Kr Aasawat, K. Yoshizoe. “Practical Massively Parallel Monte-Carlo Tree Search Applied to Molecular Design.” ICLR 2021.

ハッシュ駆動並列化

深さ優先変形&Hash table for each worker
000111011101

W0&
O1011000110110

O1=2F2
O1

c2101001001101

W3c2&111110111101

F2W2

C1010011101101

C1W1

0

1

2

3

C3

c2

C1
F2

s2

n2

N325

ゲームAIの進歩の意義
囲碁・将棋・チェスを含む多くのゲームで⼈類を超えた「完璧に精確なシミュレータ上で計算実験をひたすら⾏うことでより良い解を発⾒する」というアプローチと⼀般化したい

機械学習＋探索＋HPC
これは強⼒なツールなのでゲーム以外にも応⽤すべき様々な数値シミュレーションの技術を活⽤し、多くの最適化問題を解きたい

Cl

N
N
O

Cl

DeepMind に機械学習メインでは太⼑打ちできないし…

ClN
F

O
F

⼿始めに化合物探索とか…

2003 nicolas p. rougier (CC BY-SA 4.0)26新規化合物探索
薬になりそうな
分⼦量の⼩さい物

何らかの「スコア」が⾼い化合物を発⾒したい
チェス
1045

これを AlphaGo ぽい
⼿法で解く

化合物
1060

囲碁
10170

2003 nicolas p. rougier (CC BY-SA 4.0)

全探索を⾏うには探索空間が広すぎる
2003 nicolas p. rougier (CC BY-SA 4.0)

27

ChemTS: AlphaGo for ChemistryMonte-Carlo
Tree Search
化合物を網羅する空間を探索

F

N

O
c=C

Csn

F

シミュレーションで「スコア」を計算しフィードバック

ClN

Cl

N
O

RNN (イメージ)

ClN
FOF既存の計算化学のツールを利⽤
Gaussian や RDKit

有望な化合物をサンプリング この化合物を⽰す

O=C(Nc1cc(Nc2c(Cl)cccc2NCc2ccc(Cl)cc2Cl)c2ccccc2c1OC(F)F)c1cccc2ccccc12

化合物データベースで訓練した DNN
化合物を⽰す⽂字列を出⼒
ChemTS: An Efficient Python Library for de novo Molecular Generation.
X. Yang, J. Zhang, K. Yoshizoe, K. Terayama, K. Tsuda. STAM 2017
Practical Massively Parallel Monte-Carlo Tree Search Applied to Molecular Design
X. Yang, T. Kr Aasawat, K. Yoshizoe. ICLR 2021

28

化合物の探索空間を⽂字列で表現(SMILES: Simplified Molecular-Input Line-Entry System)

OWater (H and single bond omitted)

O=C=O

Carbon dioxide

N#N

Nitrogenc1=cc=cc=c1

Benzene (c1 and c1 connect)[Cu+2].[O-]S(=O)(=O)[O-]

Copper sulfate

ONONHOO

Cc3ccc(c2nc(CCCCO/N=C(CCC(O)=O)c1ccccc1)c(C)o2)cc3
以下の⽂法規則によって定義されるそれぞれの記号は元素・結合・リングの情報を⽰す
Atom: {C, c, o, O, N, F, [C@@H], n, -, S,Cl, [O-],[C@H], [NH+],[C@], s, Br, [nH], [NH3+], [NH2+],[C@@], [N+], [nH+], [S@], [N-], [n+],[S@@], [S-], I, [n-], P, [OH+],[NH-], [P@@H], [P@@], [PH2],[P@], [P+], [S+],[o+], [CH2-], [CH-], [SH+], [O+], [s+], [PH+], [PH], [S@@+] }Bonds: {/,=, \# }Ring: {1,2,3,4,5,6,7,8,9}
Branch: {(, )}29AlphaGo
Cl

N
NO

Cl
N
F

Cl

ChemTS (我々の研究)

O=C(Nc1cc(Nc2c(Cl)cccc2NCc2ccc(Cl)cc2Cl)
c2ccccc2c1OC(F)F)c1cccc2ccccc12

OF

CNN (ResNet)
による画像認識
囲碁の局⾯のサンプリング(rollout)

RNN (GRU) による⽂字列処理RNN によるサンプリング(rollout)

勝敗による報酬

計算化学シミュレータの結果に基づく報酬

Monte-Carlo Tree SearchMonte-Carlo Tree Search O(P-UCT)(vanilla UCT)FNc=CFCsn30

囲碁も化合物も枝刈り探索
rootFc=CCNOSFClc

N

確率に基づいて探索空間を枝刈り
31新規化合物の発⾒並列探索で⾼速にスコアの⾼い化合物を発⾒（ただし単純なベンチマークスコア）
X. Yang, T. Kr Aasawat, K. Yoshizoe. “Practical Massively Parallel Monte-Carlo Tree Search Applied to Molecular Design.” ICLR 2021

並列探索で実際に新たな蛍光有機分⼦を発⾒（これは共著者に頼り切りですが）(Gaussian16 を⽤いた DFTシミュレーションによるスコアを利⽤)

M. Sumita, K. Terayama, N. Suzuki, S. Ishihara, R. Tamura, M. K. Chahal, D. T. Payne, K. Yoshizoe, K. Tsuda,"De novo creation of a naked eye–detectable fluorescent molecule based on quantum chemical computation and machine learning",
Science Advances, 10.1126/sciadv.abj3906

32

計算資源→ゲームの強さ→︖名⼈
⼿作りの評価関数-

様々な⼆⼈ゲーム
その他探索問題

機械学習で評価関数- オセロ、将棋など

Deep Learning
画像認識など探索の進歩

Monte-Carlo Tree Search(強化学習などが背景)︖︖︖探索︖︖︖名⼈
リアルタイムゲーム、タンパク質、戦闘機操縦
化合物、…
33