2022/10/18

サイエンスカフェ in 静岡

第157話

ゲーム⼈⼯知能の進歩

2022年 9⽉29⽇
電気通信⼤学
保⽊邦仁

⾃⼰紹介
学⽣のころ
⼤学︓

もう誰も勝てない
ボナンザ完結編︕

東北⼤学（宮城県仙台市）

所属学会︓ ⽇本化学会、分⼦科学研究会
マグノリア

現在
職業︓

電気通信⼤学（東京都調布市）

専⾨︓

ゲーム⼈⼯知能
ヒューリスティック探索、機械学習

所属︓

電気通信⼤学 情報・ネットワーク⼯学専攻
情報数理⼯学プログラム

所属学会︓ 情報処理学会、⼈⼯知能学会

12022/10/18

本講義ではゲーム⼈⼯知能の発展の経緯を振り返り、科学技術に対する興味・関⼼を引き出す
少々難しい話題も含みます
どうぞお付き合いください

グランドチャレンジ

(アポロ11号、Wikipedia)2

2022/10/18

チェス(チェス、Wikipedia)

トルコ人（18世紀のチェスマシン）(トルコ⼈、Wikipedia)32022/10/18

IBM ディープ・ブルー (1996 - 1997)

CMU のチェス AI 研究者が IBM リサーチへ
元世界チャンピオンに勝ち越し
同社の広告塔 (スーパーコンピュータなど)

難易度

⼆⼈ゼロ和完全情報ゲーム（2000年ごろ）
五⽬並べ (Allis, 1994)
チェッカー(Schaeffer et al., 2007)

ここまで解ける • 後退解析
• 証明数探索
オセロ (Buro, 2002)• Alpha-beta 探索• 精緻な評価関数
ここまで⼈間に勝てる

チェス (Campbell et al., 2002)
将棋

囲碁
将棋・囲碁の⼈⼯知能はいつ⼈間に勝てるのか4

2022/10/18

そのころの⼈⼯知能 (AI)
• 「貼り付けた図がピョンピョン
⾶ぶのを何とかしたい」• 「質問の意味が分かりません」• ググググッと下から登場しシステムがクラッシュ

AIは余計な技術

マイクロソフト社

ソネットエンタテイメント社

コンピュータ将棋の進歩• 計算機の性能• 探索アルゴリズム• ⼤規模な機械学習52022/10/18

ゲーム⽊と探索(終端Maxプレイヤ
プレイヤ
Max

現状況

0 (ゲームの値)

Min プレイヤ
プレイヤ
Min
ミニマックス戦略

最善応⼿系列01まで探索しきれる場合)

10−1

10−1利得

このようにして最適戦略が求まる

ゲーム⽊と探索 (続き)(終端まで探索しきれない場合)
近似的な最適戦略

32

1Max プレイヤ

1Min プレイヤ

0−13点

機械学習で近似関数を得る

−2
評価値

6

2022/10/18

機械学習
信濃川

未知河川の流路延⻑

幹線流路延⻑ (km)既知のデータから a と b を決定
未知のデータを予測

利根川

400
300

𝑦

200
100

𝑎𝑥

𝑏

淀川

0
0

5,000 10,000 15,000 20,000

データはゲーム記録から採取
流域⾯積 (km2)• ゲーム状況 (駒の配置など)図︓主な河川（総務省統計局、平成26年度）• 着⼿
未知河川の流域⾯積• 勝敗

機械学習の成功例（１）
バックギャモンの勝敗の予測
勝率（出⼒）
三層ニューラルネットワーク

強化学習法

各升での駒の個数（⼊⼒）
世界チャンピオンと同等レベルの強さを獲得（Tesauro, 1995）
Backgammon, Wikipedia, 20187

2022/10/18

機械学習の成功例（２）回帰分析によりオセロの結果を予測
­1.0点

0.3点

1.3点

­2.5点

図︓オセロ評価関数（合計­1.9点）

世界チャンピオンに勝った（Buro, 2002）
Reversi, Wikipedia, 2018

Bonanza の評価関数

⽟を含む３駒全通りに対する値付け

４３点
－９０点
－１点

１３点

2008年ソースコード公開
将棋 AI の性能が向上

82022/10/18

将棋⼈⼯知能 対 ⼈間

• 2007年 Bonanza 対渡辺明⻯王
 ⼈⼯知能:評価関数の機械学習
 ⼈間:
トップレベルのプロ棋⼠
 ⼈⼯知能敗北

⽇本将棋連盟、棋⼠データベース、2021

将棋⼈⼯知能 対 ⼈間

• 2007年 Bonanza 対渡辺明⻯王
 ⼈⼯知能:評価関数の機械学習
 ⼈間:
トップレベルのプロ棋⼠
 ⼈⼯知能敗北

⽇本将棋連盟、棋⼠データベース、2021• 2010年あから対清⽔市代⼥流王将
 ⼈⼯知能︓
約200台の計算機使⽤ ⼈間:
通算タイトル獲得数歴代１位
 ⼈⼯知能勝利

あから棋⼠が分散並列環境と初めて対峙
⽇本将棋連盟、⼥流棋⼠データベース、2021

92022/10/18

ボンクラ―ズ対⽶⻑邦雄永世棋聖 (2012)• 2011年コンピュータ将棋選⼿権で優勝• Bonanza を参考にして作成
⼈間が対コンピュータ戦略をとる

⼈間プレイヤー側の第⼀⼿△６⼆⽟の意味は︖

異種格闘戦, 東京, 1976
レスリング (アントニオ猪⽊)
キックが得意ボクシング (モハメド・アリ)
パンチが得意図︓アントニオ猪⽊は１ラウンド、ほとんど寝転がった15ラウンド（最終ラウンド）まで決着つかず、引き分け

10

2022/10/18• 怪しげな駒の運びでインファイトを回避、防衛ラインを築く• コンピュータは⾶⾞を往復させて⼿待ちの繰り返し• ⼈間側は引き分けにする権利を得ていたかのように⾒えたが、その後接近戦になった。

将棋⼈⼯知能 対⼈間• 2007年 Bonanza 対渡辺明⻯王
 コンピュータ: 評価関数の機械学習 ⼈間側:
トップレベルのプロ棋⼠
⽇本将棋連盟、 コンピュータ敗北
棋⼠データベース、2021• 2010年 あから対清⽔市代⼥流王将 コンピュータ︓ 約200台の計算機使⽤
 ⼈間側 ︓
通算タイトル獲得数歴代１位
 コンピュータ勝利
⽇本将棋連盟、⼥流棋⼠データベース、2021• 2012年 Bonkras 対⽶⻑永世棋聖
 ⼈間側: 対コンピュータ戦略使⽤ コンピュータ勝利

以降、⼈間側が普通にやっては勝ちにくくなっていく
⽇本将棋連盟、• 計算機の性能制限
棋⼠データベース、2021• 同⼀計算機・プログラムの事前貸し出し11

2022/10/18

⼆⼈ゼロ和確定完全情報ゲーム（2014年ごろ）

難易度

五⽬並べ(Allis, 1994)

チェッカー (Schaeffer et al., 2007)
ここまで解ける(Buro, 2002)• 後退解析
• 証明数探索オセロ
囲碁の⼈⼯知能はいつ⼈間に勝てるのか
チェス(Campbell et al., 2002)• Alpha-beta 探索
ここまで⼈間に勝てる• 精緻な評価関数
将棋 (Hoki, Kaneko, JAIR, 2014)

囲碁

その頃の AI• 「ワード」と「貼り付けた図がピョンピョン⾶ぶ」でグーグル検索• 検索結果の⼀番上が「WORDでマイクロソフト社
図が思った位置に移動できない」• 教えて︕goo のベストアンサーに⾏き、「アンカー表⽰」と 「アンカーの段落固定」の解説にたどり着く

相当いいところまで技術が発達している

122022/10/18

コンピュータ囲碁の進歩• 計算機の性能• 探索アルゴリズム• 深層学習①モンテカルロ法による地の認識（１９９０年代）
着⼿可能な交点に等確率で着⼿双⽅の⽯を打ち上げ切る
同じことを何度も繰り返す
平均を取る
沢⼭の結果の平均を取ると、それらしい結果が得られる棋⼒の⼤幅な向上は容易ではないと思ったが、実はこの⽅法には新たな展開があった
図︓乱数を⽤いてゲームを何度も試⾏する様⼦

13

2022/10/18

モンテカルロ⽊探索(Kocsis, 2006)
着⼿⼿番

モンテカルロ法の性能が向上
勝ちやすい着⼿を重点的に試⾏

2/50/10/2

2/30/11/1

⽊構造にまとめる

負
け負
け

勝
ち負
け

勝
ち

1/20/1負
け

負
け

勝
ち

負
け

1/1

勝
ち

②深層学習による⼿番の評価
線形重み和関数𝑢 𝒙 =𝑤

𝑤 𝑥𝑤𝑥𝑤 𝑥𝑤 𝑥𝑤 𝑥𝑤 𝑥𝑤 𝑥𝑤 𝑥𝑤 𝑥𝑥 𝑥 𝑥𝑥 𝑥 𝑥𝑥 𝑥 𝑥

計算の順⽅向重み係数wiは囲碁のデータから決定

𝑢 𝒙𝑤 ,⋯,𝑤

図︓碁盤と特徴変数 𝑥𝑥 ,⋯,𝑥
図︓フィルタ。画像処理（ぼかし、シャープ化）に応⽤例あり

142022/10/18

囲碁の評価関数の⼀部（１ユニット分）

𝑓 𝑢𝑢
図︓活性化関数

19x19の各要素に対する演算

𝑓 𝑢

max 0, 𝑢

活性化関数
異なるフィルタを他の⾯に適⽤畳み込み

異なるフィルタを他の⾯に適⽤同じフィルタを⼀⾯（19x19）に適⽤

畳み込みニューラルネット
ワークによる囲碁の⼿番評価
評価値

10層以上

畳み込み⼤量の重み係数を⾃動調整• GPU を使⽤
• ⼤量のデータ（囲碁の棋譜）棋⼒の⼤幅な向上は容易ではないと思ったが、モンテカルロ法との相性がすこぶる良かった。
100個以上152022/10/18

Google DeepMind アルファ碁（2016）• 囲碁 AI 研究者がディープマインド社に⾏った• 2016年にイ・セドルに勝ち越した• 同社の⼈⼯知能技術の⾼さを強く印象づけた

⼆⼈ゼロ和不確定完全情報ゲーム（2016年）

難易度

五⽬並べ(Allis, 1994)

チェッカー (Schaeffer et al., 2007)
オセロ
チェス
将棋
囲碁

ここまで解ける • 後退解析
• 証明数探索(Buro, 2002)• Alpha-beta 探索(Campbell et al., 2002)• 精緻な評価関数(Hoki, Kaneko, JAIR, 2014)

ここまで⼈間に勝てる(Silver et al., Nature, 2016)• モンテカルロ法• 深層学習16

2022/10/18

ゲーム⼈⼯知能の最近の状況
⼈間よりも強い⼈⼯知能を開発した著名な研究• 囲碁・チェス・将棋 (Silver et al., 2018)
種類︓⼆⼈ゼロ和完全情報ゲーム
⼿段︓豊富な計算資源、深層学習、強化学習、ヒューリスティック探索• 6⼈プレイ・ノーリミットのテキサスホールデム (Brown et al., 2019)
種類︓六⼈ゼロ和不完全情報ゲーム
⼿段︓ゲーム抽象化、⼆⼈ゼロ和ゲームのような混合戦略
ヒューリスティック探索• StarCraft II (Vinyals et al., 2019)
種類︓ビデオゲーム（⾮常に複雑なリアルタイムストラテジーゲーム）
⼿段︓豊富な計算資源、豊富な⼈間の知識（プロのリプレイ）の利⽤
深層学習、強化学習、マルチエージェント学習

忙しい時、使う気になれない︕
もう少々お待ちください

マイクロソフト社

アップル社

17