ゲームの解決
東京大学情報基盤センター 田中哲朗
2022年4月8日 αxSCシンポジウム「ゲームとスーパーコンピュータ」
https://www.cc.kyushu-u.ac.jp/scp/users/news/2021/523.html

自己紹介
●
●

田中哲朗
所属 東京大学情報基盤センター情報メディア教育研究部門○●

スーパーコンピュータを管理する部門ではなく，学内のインフラ (メール，LMS, 演習用端末等)を扱う

過去の研究
○
○
○

プログラミング言語処理系■
AP-1000(当時はスーパーコンピュータとは呼ばなかったと記憶している )でのUtiLisp/C, 関数型言語の並列，分散実行
部品合成による漢字フォントの作成 (和田研フォント)
ゲームプログラミング (扱う対象はボードゲームや，パズルゲームなどが中心 )■ゲームの最善なプレイを計算する = ゲームを解決(Solve)する(数あてゲーム MOO, どうぶつしょうぎ，シンペイ，R-Rivals, 十六むさし, 量子アンパンマンゲーム)■
強いプレイヤを作る (Calculation, GPS将棋)■
ゲームの計算複雑度の証明 (IQ)

2

ゲームの解決

3

研究対象としてのゲーム● 「産業」としてのゲームはコンピュータゲームの比重が大きい○ 2021年度の国内家庭用ゲームソフト（パッケージ版のみ）とハードの売上は 3613.9億円(ファミ通発表)○ 囲碁，将棋，麻雀はいずれも産業として年間 100億円のオーダ○ 任天堂は花札作りで創業● 研究対象としてのコンピュータゲームの難しさ○○○○「ルール」が公開されていない．
ゲームの寿命が短い．
最近はAtari gamesが強化学習のベンチマークとして使われることが多い．
著作権的にgrayな例も．

コンピュータを使わないゲームを対象にした研究が多め
4

コンピュータを使わないゲーム●●●

囲碁，チェスなどは2000年以上の歴史○ ルールは進化している．
物理的な制約などからルールが決まる○ 情報の隠し方 (カード)，サイコロ(6面)○ minesweeperはコンピュータなしには成立しない
審判が不要 or 審判の判断基準が明確○ 「同時着手」の難しさ，「手番」の導入○ 同時着手が難しい例 : 「じゃんけん」■ 超高性能の画像処理とロボットアームを組み合わせ

後漢時代の石棋盤

た，勝率100%のジャンケンロボット (石川正俊研究
室)■ 「後出し」を判定する審判，基準が必要 ?

マインスイーパー(Kmines)5

ゲームの分類●●●●●

一人，二人，多人数○ 1人ゲームは一般に「パズル」と呼ばれる．
完全情報 vs 不完全情報○ カードゲームや麻雀のように他のプレイヤに隠された情報があるかどうか．
確定 vs 不確定
○ サイコロのような不確定要素があるかどうか .
零和 vs 非零和
○ 参加するプレイヤの利得の合計が 0かどうか? (e.g. 囚人のジレンマゲーム )有限 vs 無限○ ゲームが有限時間で終了するかどうか ?

ゲームの性質により「解決 (solve)」の難しさが異なる．

6

パズルの解決●

パズルの状態数○●

N-queens

パズルの最長手数○

ルービックキューブ

7

N-queensの解の数(1)●8-queens○ 8 x 8 のチェス盤に8個のQueenを「互いに攻撃しない○●ように」配置する．
チェスのQueen は将棋の飛車と角を合わせた動き(上下左右斜めの 8方向に障害物がない限りどこまでも移動可能 )対称性を考慮せずに 92個の解(右図はその一例 )○N x N の盤にN個のQueenを配置する場合の配置の数は?
○ 簡単な式で表す方法は見つかっていない．
○ 並列計算には向いている．

♕

♕

♕
♕
♕

♕
♕
♕

8

解の数

N

N-queensの解の数(2)●●●24-queens (吉瀬 2004)○ 34ノード(68プロセッサ )からなるPCクラスタ○ 約22日の計算
25-queens (INRIA 2005)○ 260台のデスクトップマシンの空き時間を利用○ 6ヶ月で計算が終了
26-queens (B. Preußer 2009)○ ドレスデン工科大学のプロジェクト， FPGAで専用ハードウェアを作成○ 9ヶ月で計算が終了○ 2ヶ月違いで， Russian MC# super computing project が結果をconfirm○ NQueens@Home という個人の計算機の余剰時間を用いて計算するプロジェクトも動いていたが，結果を出せなかった．

●●

27-queens (B. Preußer 2016)○ FPGAで作成した専用ハードウェアを並列に動かす○ VHDLファイルを github で公開 https://github.com/JacobCWard/q27/
28-queens○ 取り組んでいる人がいるなら後 1-2 年で結果が出る ?

1

1

2

0

3

0

4

2

5

10

6

4

7

40

8

92

9

352

10

724

11

2,680

12

14,20013

73,712

14

365,59615

2,279,184

16

14,772,512

17

95,815,104

18

666,090,624

19

4,968,057,848

20

39,029,188,884

21

314,666,222,712

22

2,691,008,701,644

23

24,233,937,684,440

24

227,514,171,973,736

25

2,207,893,435,808,350

26

22,317,699,616,364,000

27

234,907,967,154,122,000

9ルービックキューブの最長手数
●
●

●

●
●

3x3x3のルービックキューブの状態数(面の側面だけを動かした場合)は 43,252,003,274,489,856,000
一手を「6つの面の一つを選んで，90度，180度，270度いずれか回転させる」と定義した時に20手必要な配置があることは1995年に証明(右図のsuperflipがその一つ)
上限は計算機によって29手，26手，25手，22手と改善してきたが，2010年にTomas Rokickiらが，20
手が最長手数であることを求める．
Google社のクラスタを利用して，概算で34.75 CPU
年程度のCPU時間で解決．
発表論文 Rokicki, Tomas, et al. "The diameter ofthe Rubik's cube group is twenty." siam REVIEW
56.4 (2014): 645-670. の付録にinner loopでgccが出したx86_64のアセンブリ言語が掲載されている．

10

二人零和有限確定完全情報ゲーム● 多くのゲームが含まれる．
○ チェス，オセロ，チェッカー，囲碁 (3コウ等を除いて )● 理論的には任意の状態(盤面，手番など)から最善にプレイした時に，手番のプレイ
ヤの得られる利得が計算可能○ 勝ち/負け/引き分けが決定可能 = ゲームの解決●

繰り返しのないゲーム(オセロ，五目並べ(連珠))は比較的解決が容易．

11

繰り返しがあるゲーム
人為的なルールを付け加えることにより，繰り返しを制限●●

囲碁○ コウ : (右図)の形では直後に取り返せない
将棋○ 千日手 : 同じ局面に4回目で引き分け (王手からみの例
外あり)

ルールの限界●●囲碁○ 3コウ : (右図)の形は「双方が合意したら」引き分け
将棋○ 王手千日手ルールと，打ち歩詰めルールの競合 (「最後の審判」という詰将棋問題)○ 千日手 : 1983年以前は「同じ手順の 3回の繰り返し」だったが，有限性に問題
121983年以前の千日手ルールの問題点●●

5つの千日手手順○ 8八金 - 6七銀打 - 8七銀 - 7九金 - 7八銀 - 同金 - 同金 - 同銀
○ 8八金 - 6七銀打 - 8七銀 - 7九金 - 7八金 - 同金 - 同銀 - 同銀
○ 8七銀 - 6七銀打 - 8八金 - 7九金 - 7八銀 - 同金 - 同金 - 同銀
○ 8七銀 - 6七銀打 - 8八金 - 7九金 - 7八金 - 同金 - 同銀 - 同銀
○ 8七銀 - 6七銀打 - 7八銀 - 同銀
手順0と手順1を組み合わせた，3回繰り返しのない無限列の生成○ トゥエ列(Thue–Morse sequence )「同じ局面の4回の繰り返し」は発生しているので，現在のルールでは千日手
13ゲームの解決のレベル●

解けないゲーム○●

超弱解決(ultra weakly solved)○●

初期局面の勝敗は解明されているが，どのような指し手を選択すれば良いのかは分からない．

弱解決(weakly solved)○●

ゲームの状態が有限でない，可能手が有限でないなどの理由で解けないことがわかっているゲーム．

初期局面の勝敗が解明されていて，それを証明するのに必要な各局面の最善手も分かっている．

強解決(strongly solved)○

ゲームのどの状態の勝敗も解明されていて，プレイヤの最善手も分かる．

14

解決したゲームと未解決のゲーム
ゲーム名

局面数(オーダー)

解決

三目並べ

103

強解決(全局面の最善手 )どうぶつしょうぎ

108

強解決

アワリ

1011

弱解決(初期局面からの最善手 )

チェッカー

1020

弱解決

オセロ

1028

未解決

9 x 9 囲碁

1038

未解決

チェス

1047

未解決

将棋

1062 -1069

未解決

19 x 19 囲碁

10169

未解決

●
●
●
●

解決

未解決

宇宙の素粒子の数は 1080程度宇宙の素粒子の数は 1080程度
全世界のハードディスクの出荷容量は 年間7 x 1020バイト程度(2021年推計)
1秒に4 x 1017回の演算をおこなえるスーパーコンピュータを 1年動かした時の総演算数は 1.3 x 1025●15

理論的に解けないゲーム(Conwayのライフゲーム)●●●

正方形のマスが隣接した格子状の世界
各マスはステップごとに生きているか死んでいるの2状態を持つ
縦横斜めに隣接したマスの生きているマスの数でそのマスの次のステップの生死が決定○ 0, 1 – 死○ 2 – そのまま
○ 3–生
○ 4,5,6,7,8 – 死

ゴスパーのグライダーガン[図は wikiepdiaより]
16理論的に解けないゲーム(Conwayのライフゲーム)● 無限の盤面で，初期に有限のマスが埋まったライフゲームで繰り返しパターンに収束するかどうかの判定● 任意のチューリングマシン(無限の記憶容量を持つコンピュータを抽象化したもの)を
ライフゲームの配置に変換可能．
● 停止性を判定できると仮定すると矛盾17

超弱解決の例(ヘックス)●●●

2人のプレイヤが交互に自分の色(図では赤，青)の石を置く
片方のプレイヤが上下を，他方のプレイヤが左右を連結
N x N ヘックスは初期配置からは先手必勝○ すべてのマスが埋まったらどちらかが連結なので引き分けはない．
○ 後手に必勝手順があったと仮定すると，それをなぞること
で先手必勝が言える．
○ 矛盾になるので，背理法により後手の必勝手順がないと証
明できる．

●

先手必勝と分かっているが，具体的にどの手で勝てるか不明○ 弱解決しているのは， 9 x 9 まで(計算機を使った探索 )10 x 10のヘックス画面

18

縦横5目並べ ( 弱解決の例)●●●●

斜めは許さずに5目の連を作る
どのサイズの盤面でも引き分け
畳敷き戦略．畳の片側を相手が埋めたら残りを自分が埋める．
畳全体を含まない1x5, 5x1はない

19

計算機による弱解決●●

Nimなど計算機を使わずに弱解決できるゲームも多い
が，多くのゲームでは計算機によって弱解決用いられる手法○ 初期局面から「勝つプレイヤ」の証明木 (グラフ)を作成する．
○ 「負けプレイヤ」のすべての合法手を探索する○ 「強いプレイヤを作る」の延長．強いプレイヤは「小さい証明木」を得られたり，「証明木に使われない無駄な探索」の比率が小さくで
きる．

●

●

5目並べ(斜めを許す)○ 十分大きな盤面ならば先手勝ち○ 連珠と違い，長連，禁じ手 (黒の三々等)などはない．
チェッカー○ 8 x 8で制約無しの初手で引き分け [アルバータ大 J Schaefferら]○ Chinookという強いプログラムをベースに， 20年近く計算機を回した
結果．岸本さんによる証明数探索の貢献もあり．

[写真はwikipediaより ]20

弱解決にスーパーコンピュータは使えるか?
●

弱解決には，多くの局面(position)の勝敗を探索により求める．
○
○
○

●

総計算時間が重要．
メモリ量があると， transposition table が増やせて探索の効率がよくなるが，影響は小さい．
並列度はあげやすいが，通信はあまり重要ではない．

スーパーコンピュータは使えるが，コストパーフォーマンスは悪い?
○

ノード間通信の速さ， GPUによる並列計算などは活用できない．

21

強解決の例: Tic-Tac-Toe
●
●
●
●
●

「三目並べ」，「まるばつ」など多くの名称あり
3x3のマスを使用
2人のプレイヤが○と×を交互に埋める
縦横斜めに3つ○か×を先に並べたら勝ち
二人零和有限確定完全情報ゲームに属する○ 二人: 二人でプレイ○ 零和: 勝ちを+1, 負けを-1,引き分けを0とすると両プレイ
ヤの利得の和は 0○ 有限: 初手から可能な手は 9，8，7，と減っていき，必ず 9
手で終わる．
○ 確定: さいころを振らない○ 完全情報: 全プレイヤが同じ情報を保持する．

22

Tic-Tac-Toe引き分けの証明

かなり省略しているが，DAGで表現できている23

計算機による強解決●●●

後退解析(retrograde analysis) が用いられる．
○ プログラミングはシンプル（「良い手」を求める必要がない）○ 千日手が引き分けの場合は自然に扱える．
Awari○ 日本ではマンカラという名前で知られる石を動かすゲームの変種の一つ
Connect Four
○ 重力のある場での 4目並べ
○ 標準的には 幅7 x 6 のサイズのボード○ 1988年に弱解決されていたが， 1995年に強解決

24

強解決の方法 : 後退解析(retrograde analysis)● 手番のある「二人零和有限確定完全情報ゲーム」のグラフが与えられた時に，各状態の勝敗を決定する方法．
● 状態集合を以下の3つに分ける○ W0 – 手番の勝ちが決定した状態○ L0 –手番の負けが決定した状態(ゲームによっては存在しない場合も)○ U0 – それ以外

● iを0から増やしながら，以下を繰り返す○ Wi+1=Wi, Li+1=Li○ S ∈Ui について，一手後の状態集合をn(S)とする■ ∃T∈n(S). T∈Li なら，SをWi+1に加える■ ∀T∈n(S). T∈Wiなら，SをLi+1に加える○ それ以外のSはUi+1に加える● (Wi, L_i, U_i)=(Wi+1, Li+1, Ui+1) となったら終了，それぞれ勝ち状態，負け状態，引き分け状態(繰り返しパターンが引き分けの場合)となる．

グラフのノードに勝敗に応じた色を塗っていくことと同じ．
25

解決に関する誤解● 将棋の状態数が1064以上なら，解決するのに世界中のコンピュータを使っても宇宙の歴史よりも長い時間がかかる．
● 「すべての状態を後退解析で求めれば初期局面の勝敗が決定できる」が，「初期局
面の勝敗が決定するのにすべての状態を後退解析で求める必要はない」○ Bridge Itは状態数に関わらず証明可能○ チェッカーを解くのに探索したノード数は 1014程度

26

「どうぶつしょうぎ」の解決●●●●

2008年に女流棋士の北尾まどか初段(当時)がルールを考案したボードゲーム
将棋に類似した簡潔なルール
女流棋士の藤田麻衣子一級(当時)のデザイン
でLPSAから商品化
2009年6月に解決(田中)○ 初手の勝敗○ ルールの妥当性

27

ボード
●
●
●

3x4のボード
4, 1行目は先手，後手の陣地
先手は4の側に，後手は1の側に座る

28

駒
●
●
●
●

「ライオン」 8方向に1マス動ける「きりん」 縦横4方向に1マス動ける「ぞう」 斜め4方向に1マス動ける「ひよこ」 前に1マス動ける．敵陣に入ると「にわとり」になる．「にわとり」は斜め後ろ以外の6方
向に1マス動ける

29

進行
●
●

先手から交互に1手ずつ駒を動かす．パスは許されない
自分の手番では以下のいずれかのプレイ○ ボード上の自分の駒を動かす．動かす先はボード上の空きマスか，敵の駒のあるマス．敵の駒のあるマスに移動すると敵の駒を捕まえて持ち駒にする．
○ 持ち駒を空きマスに置く (打つ)．「にわとり」を捕まえても持ち駒として打つときは「ひよこ」として打つ

初期配置
30

ルール
● ゲームの目標○ 相手のライオンを捕まえる○ 相手の陣地に自分のライオンが入り，直後に捕まえられない (トライ勝ち)．

● 同じ局面に3回目に到達すると引き分け○ 「同じ手順を3回」というのはミスらしい● 二歩，打ち歩詰め，一段目の歩打ち，王手千日手に相当する反則はなし

31

全局面列挙の結果● メモリ16GB, Opteron 2.6GHzマシンを使用● 約19分で終了, メモリは最大13GB程度使用● 局面数は 246,803,167● 1局面8byteで記録しても， 2GBのメモリで記録可能，ファイルに保存して再利用● 末端局面以外は 99,485,568● 実はこちらを保存するだけでも良かった．

32

後退解析の結果●●●

メモリ16GBのOpteron 2.6GHzのマシンを使用
5.5時間
繰り返しは173回で終了(勝ちに要する最大手
数は173)

勝ちに要する手数が173の局面．勝つ手はB4ライオン

勝ち局面

引き分け局面

負け局面

計56,474,473

2,682,700

40,328,395

99,485,568

33

初期局面の勝敗●●●

後手勝ちで78手を要する最小手数での証明グラフのサイズは2,431,444(局面を暗記すれば常に勝てる)
最短の応手○ 「B2ひよこ」->「同ぞう(76手)」○ 「C3きりん」->「A2きりん(78手)」○ 「C3ライオン」，「A3ライオン」->「A2きりん」,「B3ひよこ(78手)」34ツークツワンク局面●

次の手番だけパスできたら勝ちになる負け局
面●

21,839個見つかる(手番を入れ替えると到達不能のものは除く)●

手番を入れ替えた局面が元と対称な局面も71
個○

このうちの一つが初期配置

対称なツークツワンク局面
35

敵陣へのひよこ打ち●

一般には悪手だが将棋と違って禁止はされていない●チェックするプログラムを作成○●

ひよこ打ちのみが有効な局面は 68

敵陣へのひよこ打ちを禁止するルールにすと，4301局面で勝敗が変わる．ただし，初期局面の後手78手勝ちは変化せず

敵陣へのひよこ打ちが有効な局面
36

詰みのある局面●「詰み」の定義○ 相手がパスすると次の手で勝つ (敵ライオンを捕まえる
or 自ライオンがトライする )手(王手)の連続で勝てる●すべての「詰み」局面の列挙○ 「王手」のみで勝つ局面を後退解析で求める○ 勝ち局面の約 30%に詰みあり

手数

局面数

1

11,520,862

3

3,579,697

5

1,314,521

7495,3849

194,087

11

71,563

13

27,699

15

7,487

17

2,173

19

386

21

134

23

4

計

17,213,997

37

23手詰み局面

詰み以外の短い勝ちがある

38

強解決にスーパーコンピュータは使えるか?
●

状態数の大きいゲームの強解決には，ディスク容量が必要○●

結果を最終的に公開するのが前提

後退解析中はメインメモリ容量も必要○

すべての状態をメモリ上に置かなくても解析可能なゲームは多い (e.g. オセロの後退解析をおこなう場合，n手目での勝敗を高速に求めるには n+1手目での勝敗がメインメモリ上にあれば良い )．

●●スレッド並列化は容易
分散メモリでもそれぞれのノードに十分なメモリがあれば，並列化は可能．

●●●

使えるが，コストパーフォーマンスは悪い?
ノード間通信の速さ，GPUによる並列計算などは活用できない．
解くことにニュース的な意味があり，手頃な状態数(1014-1015)のゲームがあれば．
39

強いプレイヤを作る : GPS将棋を振り返る40

強いプレイヤを作る●「ゲームをプレイする能力 = 人間の知能の象徴」であり，コンピュータでゲームをプレイできることを示すことがコンピュータの能力を示すこと．
○●

強い人間プレイヤがいるゲームで人間のトップを超える．
○○●

10年前ですら「コンピュータは永遠に将棋の名人には勝てない」という人はいた．
「プロ」がいるボードゲームはそれほど多くない．
人間のトップが明確でないゲームも (例として UNO をあげようと思ったが， UNOは2021年に初めて優勝賞金5万ドルの世界大会が開かれていた )強い人間プレイヤがいるゲームでも人間が戦ってくれないことも．
○○

人間プレイヤはメリットが大きくない．
強い人間プレイヤ本人は OKでも，周囲(所属団体等)が受けてくれないことも．

41

未解決ゲームで人間をどう超えるか?
(コンピュータチェスの歴史)●

コンピュータ開発の最初期から研究の対象○ 1949年, C. Shannon, Programming a Computer for Playing
Chessで基本的なアイデアが出現．
■ ミニマックス法 : 人間のプレイ時の思考と類似

42

ミニマックス法●●

評価関数 (人間の場合は形勢判断)○ ゲームの局面を「無理やり」数値化○ 2つの局面のどちらが有利か比較可能に
探索 (人間の場合は先読み)○ 双方が最善の手を何手か続けた後の局面の評価値 (局局面

面に評価関数を適用して得られる値 )を比較

評価関数
評価値

391

43

チェスの評価関数●

比較的少数の評価項目
○

駒の価値
■

●

例：ポーン100点、ビショップとナイト 300点、ルーク500点、クイーン900点、キング無限大点

○

玉の安全度

○

駒が自由に動けるか

パラメータ調整○

手調整○

自動調整(機械学習の試みも )44

1手読み + 評価値•

1手進め、評価値の高い手を選ぶ○ 評価値が完璧なら解析

実際のゲーム:○ 評価値は不正確○ 「双方が最善の手を何手か続けた後の局面」を求めて
評価

MA
X

+100

0

-90

⇒ 深い探索(ミニマックス探索)が必要

45

ミニマックス探索
Maxプレイヤは最大値
Min プレイヤは最小値を選択

最善手順

Root

3

3
3
3
5

3

5
2

6

5
2

9

1

2

Minプレイヤ

2

4

1

1
5

Maxプレイヤ

4

1

2
2

4

1
3

4

1

4

数字は”評価値”
点数が高いほどMaxプレイヤが有利
46

様々な改善(1949年-1997年)●●

評価関数の向上○

有効な評価項目の導入○

終盤(チェスでは駒数は減っていく )は後退解析で強解決 (駒数6個以下は解析済み )探索の効率化○

無駄な探索の省略 (枝刈り)■○探索の並列化■○アルファベータ探索，局面表，キラームーブ
マルチプロセッサ，マルチコア，クラスタ化

探索の高速化■プログラミング技術，専用ハードウェアの作成

47

1997/5/12 世界チャンピオンに勝利●●

IBM Deep Blue○

並列マシン+チェス専用ハードウェア○

1秒間に1億局面探索

世界チャンピオンのカスパロフに勝利(米国時
間5/11)○

6戦して2勝1敗3分

48

その後のコンピュータチェス●

Deep Blueは直後にプロジェクト解散●

普通のPCでも強くなる．

●○

PCの速度向上+ソフトウェアの改良○

何度か行われた人間のトップとの対戦はコンピュータチェス側の勝利 (報道は控えめ )，最近は余り行われない(結果が見えている )．

○駒落ちのハンディ戦でも人間のトップに勝利

人間のチェス大会は残る○

カンニング対策が必要

49

将棋の特徴●チェスと類似点多い○ インドのチャトランガが起源？
○ ヨーロッパ : チェス○ アジア: 各国の将棋■ 中国・韓国・タイ・モンゴルなど

他の将棋類との大きな違い● 取った駒を再利用○ 終盤でも駒数が同じ : 合法手の数も減らない ⬄終盤
データベースが作れるチェス●

駒の動きが弱い○ 先まで進まないと得が見えない手もおおい．

2013年に見つかった日本最古の将棋駒(産経ニュースより )50

コンピュータ将棋の歴史(1)●

1975年に初めて動くプログラムが作成される○スタートはコンピュータチェスの 25年遅れ●

1980年頃からコンピュータ将棋同士の対戦●

1980年代中頃からPC/ゲーム機用ソフトの開発○

森田将棋等が有名
ファミリーコンピュータ森田将棋

51コンピュータ将棋の歴史(2)●●●1990年コンピュータ将棋協会(CSA)設立○ コンピュータ将棋選手権を毎年開催○ 会誌の発行
1994年からほぼ毎年ゲームプログラミング
ワークショップ(GPW)を開催○ ゲーム情報学関係の「研究」発表の場の提供○ 夜にはコンピュータ将棋の大会も1999年に情報処理学会ゲーム情報学研究会が活動開始○ 定期的に研究会を開催， GPWも研究会主催にhttp://www.computer-shogi.org/

http://www.ipsj.or.jp/sig/gi/gpw/

http://www.ipsj.or.jp/sig/gi/

52

コンピュータ将棋の進歩(コンピュータチェスとの比較)●

将棋は駒の動きが弱い，盤面が広い○

長手数後を見越した構想■○

浅い読みでも間に合うように，評価関数の質の向上■●

長手数を探索するために，読む手を絞る (枝刈りする)技術の開発( 例: 実現確率探索 (激指) )評価関数の調整項目が増えて，人手での調整の限界

持ち駒が打てる．終盤に合法手が減らない○

詰将棋関係の技術が進歩 ( 例: 証明数探索)53

アマトップに迫るコンピュータ将棋● 1996年 森田将棋，柿木将棋 vs 飯田5段 6枚落ち2勝1敗(以下もコンピュータ将棋視点)● 2001年 IS将棋 vs 高橋女流二段 負け● 2003年 IS将棋 vs 勝又五段 二枚落ち 勝ち● 2004年 YS将棋 vs 勝又五段 飛車落ち 勝ち● 2005年 激指 vs 勝又五段 角落ち 勝ち● 2005年 激指 アマ竜王戦 ベスト16● 2005年 TACOS vs 橋本五段 負け

これがきっかけで，プロ棋士の対局禁止令(将棋連盟の許可なしのコンピュータ
54
将棋と対局の禁止)が出される．

Bonanza登場 (2005年)●●●●

海外で化学のPDをしていた保木邦仁さん(現電通大)が開発
第16回コンピュータ将棋選手権初出場初優勝
その後の成績は、他のトップ３とほぼ同じ強さ
1万以上のパラメータを全自動で調整(その後2億)○ 情報科学用語でいう「機械学習」の手法○ 一般用語の「学習」というイメージではなく，単なる数値計算●

手で調整した部分はない (プログラマは弱い)[CSA選手権ページより ]55

考え方: 兄弟局面の比較●●●●

人間の棋譜が大量に入手できるようになる．
○ ネット対局場，ネット中継
人間が指した手を高く評価させる○ 人間の指手を模倣
チェスでも構想はあった
将棋に適切だった○ 兄弟の比較 (GPS将棋 2003)○ 探索の併用 Bonanza (保木 2006)○ 勾配降下の効率化、 l1正則化等 GPS将棋 (2008)

A
他の手

プロ
の手

B

B1

B2

B>B1
B>B2
と理解
56

考え方: 探索の併用
A

A
他の手

プロ
の手

B

B1

B2

B>B1, B>B2
と理解

他の手

プロ
の手

安定した局面

B

B1

B2

B’

B1’

B2’

B’>B1’, B’>B2’と理解

ミニマックス探索の最善応手

57

プロに迫るコンピュータ将棋
●
●
●
●
●
●

2006年 Bonanza vs 加藤アマ 負け
2007年 Bonanza vs 渡辺竜王 負け
2007年 YSS vs 加藤アマ負け
2008年 激指 vs 清水上アマ 勝ち，棚瀬将棋 vs 加藤アマ 勝ち(2008年 リーマン・ショック)
2010年 あから2010 vs 清水女流王将 勝ち○●

激指，GPS将棋, Bonanza, YSSの合議+クラスタ

2012年 ボンクラーズ vs 米長永世棋聖 勝ち○

第1回将棋電王戦 (スポンサーはニコニコ動画のドワンゴ社 )58

田中とコンピュータ将棋の関わり●

日本のゲーム情報学研究で，将棋がメジャーだったがゲーム情報学を研究テーマにして（ゲームプログラミングワークショップが開始された1994年頃）から，将棋とは距離を置いていた．
○○●

高校時代囲碁部だったが，将棋は指さない．
囲碁はやるつもりではいた．

近くの研究室○○

教育用計算機センター（当時）の隣の大型計算機センターの金田康正研究室（当時）大学院生だった棚瀬寧さんが中心となって開発した「 IS将棋」，黒田 久泰さんがスーパーコンピュータ上で動かした「スーパー将棋」
情報工学専攻 (当時)の近山隆先生の研究室の大学院生（鶴岡慶雅さん，横山大作さんなど）が開発した「激指」

59

将棋プログラムを始める．
●

田中哲朗. "部分計算を用いた手生成の高速化." 情報処理学会研究報告ゲーム情報学 (GI) 2000.52 (2000-GI-003) (2000): 25-32.
○
○
○
○
○

●

partial evaluator を用いた将棋の move generationの高速化．
実際には使おうとした partial evauator C-Mix, TEMPOなどが能力不足で実用にはならずに，自作の部分計算プログラムを使う．
C++のtemplateを用いたmeta programming で，同様のことができる（しかもコントロールできる）ことに気づく．
将棋プログラムを作り始める．

“premature optimization is the root of all evil”出発点から間違っていた．

2001年5月の選手権に参加申し込み．
○○

本業（情報基盤センターの仕事，講義等）が忙しくて，一次予選前夜にほぼ徹夜して開発．当日朝の時点で，move generatorに不安あり．
一次予選の第 1戦の数手目で合法でない手を指して，反則負け．第 2戦目から棄権したので，最下
位が決定．

60

GPS将棋プロジェクトの開始●●

2001年に自分の研究室に大学院生が入学したのをきっかけに，近くの研究室の大学院生にも声をかけて， GPS(ゲームプログラミングセミナー )という名前の輪講を始めていた．
将棋に興味を持つ参加者が増え， 2003年の大会に GPS将棋として参加．
○ GPSとは別に定期的に開発者が開発ミーティング○ 当時の強いプログラムが商品販売も見越して非公開だったので，弱い頃から公開する．
■ 田中哲朗, 副田俊介, and 金子知適. "高速将棋ライブラリOpenShogiLib の作成."○●

ゲームプログラミングワークショップ2003 論文集 2003 (2003): 114-117.
機械学習を用いた評価関数の作成■ 金子知適, 田中哲朗, 山口和紀, & 川合慧. (2003). 駒の関係を利用した将棋の評
価関数. ゲームプログラミングワークショップ2003 論文集, 2003, 14-21.
■ Bonanzaの機械学習による

中心人物は金子知適さん○ 田中はコード書き．主に高速化「CPUの気持ちになって」■ 速度へのこだわりすぎは続く．
● 新しいSIMD命令，新しいCPU, 有料コンパイラ(Intel, PGI)●

コンピュータ将棋の対戦場である wdoor を始める．

2009年初優勝時
田中 哲朗, 金子 知適, 森脇
大悟, 副田 俊介, 林 芳樹,
竹内 聖悟

61

GPS将棋●●2003年の選手権は 1次予選 2勝5敗で敗退
将棋に興味を持つ参加者が増え，2003年の大会にGPS将棋として参加．
○
○

○

●
●

GPSとは別に定期的に開発者が開発ミーティング
当時の強いプログラムが商品販売も見越して非公開だったので，弱い頃から公開する．
■ 田中哲朗, 副田俊介, and 金子知適. "高速将棋ライブラリ OpenShogiLib の作成." ゲームプロ
グラミングワークショップ 2003 論文集 2003 (2003): 114-117.
機械学習を用いた評価関数の作成■ 金子知適, 田中哲朗, 山口和紀, & 川合慧. (2003). 駒の関係を利用した将棋の評価関数 .
ゲームプログラミングワークショップ 2003 論文集, 2003, 14-21.
■ Bonanzaの機械学習による評価関数のパラメータ学習と比較すると，学習中に探索を入れない点，またBonanza 4.0 以降採用された玉を含む 3駒間の関係と比較すると2004年の選手権は1次予選通過，2次予選敗退．
2005年の選手権で決勝進出，決勝では8チーム中8位
62

GPS将棋●●●●2006年 Bonanzaが世界コンピュータ将棋選手権に初出場，優勝．
GPS将棋は 2006-2008年の3年間2次予選落ち．
2009年 初優勝
2010年から疎結合並列化に着手○○

本体にほとんど手を加えずにワーカーとして利用，独立したマスタープログラムが， USIプロトコル(将棋エンジンと GUIプログラムの間の通信に用いるためのプロトコル )で通信．
当初はマスタープログラムを Ruby 言語で作成，後で C++ に63想定するクラスタ (疎結合)並列環境●●

ネットワークで接続されたマシン群○

通信速度はそんなに速くない○

情報のやり取りがあまり出来ない○

協調的に動かすのが難しい

普通のPCをたくさんつなげてもOK○

スーパーコンピュータ，クラウドでも実現可能だが，オーバースペック

たまたま，近くに休日限定で使える(大学の許可は必要)PC群がある
64

情報基盤センター教育用計算機●

学部学生の利用のための計算機環境
○
○
○

●

東京大学駒場キャンパス情報教育棟に約800台○●

2012年3月に導入
端末は iMac 21.5インチ : Intel Core i5 2.5GHz クワッドコア, メ
モリ4GB
本郷，駒場，柏キャンパスに 全1321台配置
土曜日/日曜日は自習室(約120台)のみ学生が利用

自習室を除く667台分の利用申請○○○

情報メディア教育専門委員会
情報教育棟委員会
利用条件■ センター教員が現地で監視■ 報酬，謝礼を受け取らない

http://gps.tanaka.ecc.u-tokyo.ac.jp/gpsshogi

65

なぜスーパーコンピュータを使わなかったのか?
●

情報基盤センターのスーパーコンピュータの個人利用アカウントは数年に一度は申請していた．
○ スーパーコンピュータのプロセッサが普通の x86_64になり，OSがLinuxになった頃●

本番の対戦には不向き○ 多くのノードが使えるバッチ実行は対戦時間に合わせて動かせない（東工大の Tsubameがうらやまし
かった）．

●

学習や自己対戦は速いが．
○ 長時間実行させるには，手元の Linuxクラスタで並列に実行させた方が楽 (サーバ室に研究用の Linuxマ
シンを置けるという恵まれた環境 )．

66

GPS将棋のクラスタ並列探索●

始点局面で手生成●

上位N 手にマシンを割当

●

●

○

順位に応じて台数を変化○

残りの手は1台で通常探索それぞれ, 手を進めた局面で手生成○

各手の台数が 1台なら1台で通常探索○

上位M手にマシンを割当 , 残りは1台で探索○

以下、繰り返し「残りの手」が最善となったら探索時間延長67

N=2, M=1
Root

11並列

Max
Min

P11
A

P1

P2

P10

P5

P3

P4

P11 と比較し, Aの子ノードは3手深く探索

P6

P7

P8

P9

68

90台程度の並列探索の可視化

69792台の並列探索の可視化

70クラスタ化

世界コンピュータ将棋選手権での戦歴
優勝

2位

3位

2002年

激指

IS将棋

KCC将棋

2003年

IS将棋

YSS

激指

2004年

YSS

激指

IS将棋

2005年

激指

KCC将棋

IS将棋

2006年

Bonanza

YSS

KCC将棋

2007年

YSS

棚瀬将棋

激指

2008年

激指

棚瀬将棋

Bonanza

2009年

GPS将棋

大槻将棋

文殊

2010年

激指

習甦

GPS将棋

2011年

ボンクラーズ

Bonanza

習甦

2012年

GPS将棋

Puella α

ツツカナ

2013年

BonanzaPonanza

GPS将棋71

第2回電王戦出場権獲得

第2回将棋電王戦(1)2012年1月 第1回将棋電王戦の米長永世棋聖の敗北をうけて，急遽5対5の団体戦の開催を決定●●●●2012年5月 世界コンピュータ将棋選手権の上位5プログラム(GPS将棋，Puellaα, ツツカナ, Ponanza, 習甦)を指名
2012年12月 記者発表会で，プロ側メンバー(三浦八段(現九段)，塚田九段，船江五段，佐藤四段，阿部四段)と組み合わせ，先後を決定
ソフトウェアの事前提供
○
○
○
○
○
○

記者発表会で，ソフトウェアの事前提供の打診を受ける．
GPS将棋: 公開しているものをダウンロードして使える．
Puella α : 提供しない
ツツカナ: 提供する
Ponanza: 提供しない
習甦: 提供する

72

第2回将棋電王戦(2)●

第1戦 習甦 × ○阿部四段(先)●第2戦 Ponanza(先)○ ×佐藤四段○ 現役男性プロ棋士相手に初勝利●

第3戦ツツカナ○ ×船江五段(先)●第4戦Puella α(先) △ △塚田九段○ 入玉将棋が苦手という当時のコンピュータ将棋の弱点を再確認●

第5戦 GPS将棋 vs 三浦八段(現九段)○ 団体戦でもコンピュータ将棋側の勝利

73

当日の体制●対局室での将棋盤操作，指し手の入力は将棋連盟スタッフに依頼●

金子知適准教授が対局開始時，終了時に対応．システムのセットアップ，将棋連盟
でのシステム監視●田中哲朗は駒場キャンパス情報教育棟でクラスタに使う端末の準備，システム監視,
取材対応●

他2名は，午前は駒場キャンパス，午後は将棋連盟に移動●システムや通信に不具合が生じないか，終局まで気が休まらなかった．

74

対局中の読み筋公開●

GPS将棋が着手するごとに，読み筋と評価値を公開○

クラスタ探索のアピール○

人間が介在していないことの証明■

チェスでは人間が介在したというクレームがあった．

75

対戦後の反応●●

報道○

NHKニュース等のテレビ，各新聞等多数○

第2戦(男性プロ棋士相手の初勝利 )にも増して，トップ棋士相手の勝利ということで注目される

プロ棋士の反応○

三浦八段(当時)「こう指せばよかったと悔やんでいる手はまったくない」 ,「GPSも、一手の悪手も指していない」○

渡辺竜王(当時)「決定的に悪くならないのならば新定跡誕生です。」「えらく細い攻めを繋ぐんですね。驚きま
した。」

76

第2回電王戦後のGPS将棋●●

電王戦直後の世界コンピュータ将棋選手権は3位 (並列化の影響で痛いバグが出た)人間との対戦の場である第3回将棋電王戦，将棋電王戦FINALなどに出るための将棋電王トーナメ
ントは指定された1台のPCでの対戦になる．
○○●

その後の世界コンピュータ将棋選手権は2014年は1台のPCで参加11位，2015年以降はAWSなどを利用，2015年の5位を最後に決勝（8チーム）には入れず．
○●

人間側に有利な「固定したプログラムを事前に人間側に貸与」というルールと合わせて，人間との対戦を「良い勝負」に見せるという意味で，興行的には妥当な選択か ?
GPS将棋は賞金が出る，「疎結合並列探索の研究」という研究テーマを生かせないので，出場しない．

教育用計算機システムの端末を利用した並列計算は 2014年以降は研究としての意義を見いだせないため，申請せず．

対面でのミーティングも2015年6月を最後

77

その後のコンピュータ将棋
●

●

●
●
●
●
●

人間との対局は2017年，Ponanzaが佐藤天彦名人(当時)に勝って終了
Bonanza 6.0の3駒間の関係をベースにした(手番を入れてパラメータ数を倍にしたもの)評価関数に加えて，ニューラルネットワーク風の評価関数 NNUE により，表現力が増す．
強化学習ベースの学習が進む (プロの棋譜よりも自分自身の読みを学習した方が良い)．
DeepMindの AlphaZero に影響を受けたCNNを用いた Deep NN と，MCTSでも強くなる．
定跡の自動生成
プロとの公式対戦はないが，成立するとしたらハンディ戦? (角落ち? 飛車落ち? 2枚落ち?)「2013年のGPS将棋にはスマホでも勝てる」=> あり得ない話ではない．
78

今後，解決に大量の計算資源が必要そうな問題

79強いプレイヤを作る意味がありそうなゲーム●「人間のトップを倒す」という目標が残っているボードゲーム等ではラスボスの「囲碁」が倒された以上，もう残っていない○●●

正確にいうと，麻雀は「 Super Phoenix」はトップに並んだが，完全に超えたとは言えないが (2人ゲー
ムと比べて，多人数ゲームの難しさ )．

コンピュータ同士の対戦での強さを求める，人間のトップに対して「より大きいハンディ」で勝つという目的で，より強いプレイヤを作ることは意味がある．
その過程では，強化学習，定跡作成などCPUパワーは必要．
○

スーパーコンピュータを使う名目はあるかどうか ?

80

強解決が可能そうなゲーム●

2048の期待値最大化○ 状態数はラフに上限を求めるとそれなりの大きさに○○なるが，実際にはそれよりは小さいはず．
次に到達するのは，盤上の数字の和が +2 or +4 の局面のみなので，抗体解析の際にディスクを有効に活用可能．
状態数の正確な見積もりができないと，スパコンを使うまでもない問題だったり，使ってもそれなりに時間がかかる問題だったり．

81

弱解決が可能そうなゲーム●

リバーシ(オセロ)○ 状態数1028はチェッカー1020よりもかなり大きい○ 合流が少なく手数の上限が決まっているので， treeとし○て探索した時の無駄が少ない．
■ end game databaseを作成しなくても良い．
■ たとえば，初期配置が引き分けと証明する場合
は，黒の立場から引き分け以上になる証明木を，白の立場から引き分け以上になる証明木を構成する．
■ 最も楽観的な見積もりとしては，状態数 101428で完
全にtreeと見做せるとしたら，証明木は 10（100T）程度のサイズになる．
個人的な見解だが，お金をつぎ込めば現在でも弱解決は可能と思われる．
■ まずは強いオセロプログラムが必要．すでにある
プロジェクトとの連携が有効か ? (チェッカーの弱解決は)82