Best Move

4 1 4

2 2

探索順序の重要性

1 4 3 4

Max で小さい値 Min で大きな値 を先に探索

αβ探索で枝刈が起こらない！ 63

効率的な探索

 Null-window search (NWS)

 V より大きいかを調べるなら(v, v+1) で探索

 探索窓の幅がNull, 枝刈がすぐ起こるので高 速

 Principal Variation Search (PVS)

 一番左端は(-∞, ∞)で探索: 評価値v

 残りに、PV の結果を上回る手がないか調べ る

 ⇛ v’ = Null-window search (v, v+1)

上回る(v’ > v) なら(v’, ∞)で再探索 (v’’)

3 4

5 3 6 2 9 5

1

1 2

Root

4 1 4

PVS

左端の探索結果は5.

5より大きくなるか調べたい (5,6) でNWS

(5,6 ) (5,6

) (5,6

)

3

_(5,6

)

2 3

(5,6 ) (5,6 (5,6)

)

1

_(5,6

)

2 2

3 2

5

5

65

探索の効率化に重要な情報

 探索順序

 枝刈が起こらないことも

 探索窓の広さ

 狭いほど枝刈は起こりやすい

 ハッシュ表

 探索結果の保持 : 同一局面の探索を行わない

 手の並び替え: 浅い探索結果を元に

探索の工夫

 枝刈・探索延長

 探索順序

 探索窓

 ハードウェア

 専用ハードウェア (例: Deep Blue)

 CPUのオーバークロック

 マルチコア

 クラスタ/疎結合

67

並列化の難しさ

 処理は並列に行える?

 処理に順序依存性があると難しい

 オーバヘッド

 探索 : (逐次なら)枝刈されるノードの探索

 同期 : 他のプロセッサの結果を待つ

 通信 : 仕事の分割, 仕事を通信, 通信遅延

5 3 6 2 9 5 1 2 Root

3 2

3 ≧ 5

≦ 2 3

≦ 2 1

3

5

≦ 2

αβ探索の結果

枝刈されたノード 枝刈されたノード

69

色のついた分を探索するのが、

探索オーバヘッド

メモリ共有環境

 例: 最近のパソコン Nコア

 プロセッサ間の通信は十分速い

 通信オーバヘッドはあまりない

 PV Split

 PVS の並列化

 左端を1人で展開

 残りのノードを並列にnull window search

 ハッシュ表を共有

 ロックレスハッシュ

PVSplit

71

Min Max

P2 P P1

2 P

P1 P1 P2 P ^P2 1 1

2並列

Processor1,2 (P1,P2)

1 2 2 3 3 4 4 5 5

GPS 将棋の疎結合並列探索

 2010年の第20回大会からクラスタ参加

 順位: 3位 -> 6位 -> 1位!

 コア数: 666, 800, 3200

 情報教育棟のiMac, Amazon EC2 (2011)

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

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

 情報のやり取りがあまり出来ない 協調的に動かすのが難しい

単純なアイデア

 木を展開していき、台数分ノードができ たら全ノードに1台ずつ割り振る

⇛ 無駄な探索がかなり多い

 台数効果が出ない

 将棋の平均合法手数は80

 1手深く探索するには80台

 2手深く探索するには6,400台必要！

73

メモリ非共有環境

 情報のやり取りが通信となり、遅い

 探索結果やハッシュ表

 ハッシュ表については、local, global, ハッ シュ値に応じて割り振る, hybrid などが考え られる

 探索結果を使うには、他の人の仕事が終わる のを待つ必要がある

従来手法

 YBWC, APHID, TDSAB

 YBWC はPVSplit に近い手法

 合議

 将棋では実際に成功した例があまりない

 チェスでもRybka がクラスタ探索をして いるが、詳細は不明

 他ではクラスタ探索を聞かない

75

http://cluster.rybkachess.com/

合議

 お手軽な（疎結合）並列探索

 複数台で1台のマシンよりも強くなる

 4, 8台で55%前後

 逓減は速い

準備:

 異なるプログラムの用意 : 台数分

 評価関数に乱数を入れるなど

手順:

 それぞれ同じ局面を探索

 多数決で指手を選択

8台合議例

77

P1

Root

P2 P3 P4 P5 P6 P7 P8

指手 票

a P1, P2, P4, P8 b P3, P5

c P6, P7

手a が選ばれる

左から手a,b,c と並ぶ

GPS 将棋

 探索窓を共有しない

 同期オーバヘッドと効率のトレードオフ

 ハッシュ表は各自で持つ

 割当て時に前回担当分に割当てられる

 ここでは、通信オーバヘッドはない

 並び替えは探索など

 探索オーバヘッドはあるが、並び替えがうま くいけば、少なく抑えられる

GPS 将棋のアプローチ（概要）

 ルートで手生成

 上位N 手にマシンを割当

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

 残りの手は1台で通常探索

 それぞれ, 手を進めた局面で手生成

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

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

 以下、繰り返し

 「残りの手」が最善となったら探索時間延長

79

N=M=1

Min Max

P P8 7 P6

8並列

P 5

A

P

P3 4

P2 P1

Root

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

N=2, M=1

81

Min Max

P 1

A P 1

5

P1 ^{4 P}

11並列 Root

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

P3 P2

P 1 0

P6 P7 P8 ^P9

83

台数分割

 良い手には多く割当、良くない手にはあ まり割当てたくない

 “良い手”がわかれば探索する必要はない

 順位付けが必要

 1秒での探索や実現確率の上位の手を利用 (2010,2011)

上位を選ぶ (2012)

 前回その局面を探索した

⇛ 前回の探索結果の上位N手 (new)

 探索していないが、5秒以上ある ⇛ 1秒で探索した結果の上位N手

 実現確率の上位N手

85

探索時間延長

 「残りの手」が一番良い ⇛ 探索時間延長

 他の手よりも浅い ∵ 1台で複数の手を担当

 ⇛ 信用出来ない

 「残りの手」以外での1位はそのまま探索

 他は「残りの手」の最善の探索に再割当

 「残りの手」を読んでいた1台は、新しい 残りの手を探索（これは問題）

問題点

 「残りの手」を読んでいた1台は、新しい残 りの手を探索

 「新しい、残りの手」は1台で探索

 やはり怪しい

 浅い探索の結果が選ばれる可能性がある

 本番でも起きていた様子

 どうすべきだったか

 「残りの手」で良い手

 「残りの手」以外での1位の手

 だけを探索すれば良い

87

探索時間延長（延長前）

P P 11

5

P1 ^{4 P}

Root

P3 P2

P 1 0

P6 P7 P8 ^P9

手a

手b 手c

手d = best

手a, 手b に比べて3手浅い手d が最善

評価値: d > a > b >

c

探索時間延長（再割当後）

89

P5 P11

P1 ₄ ^P

Root

P3 P2

P 1 0

P6 P7 P8 ^P9

手a

手b 手d 手c

上位N(=2)手の最善(a) : そのまま探索を続行

上位N(=2)手の残り (b) :

プロセッサ(6-10)を集め、

最善手d を探索

残りの手(c,d)の担当は 新しい残りの手(b,c)を探 索

GPS 将棋のアプローチ（再掲）

 ルートで手生成

 上位N 手にマシンを割当

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

 残りの手は1台で通常探索

 それぞれ, 手を進めた局面で手生成

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

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

 以下、繰り返し

「残りの手」が最善となったら探索時間延長

選手権での構成

 マスタ 1台

 情報の統合など

 スレーブ 792台

 探索

 詰将棋専用スレーブ 4台

 詰将棋専用

91

今年のクラスタ差分

 Perl, ruby からC++ へ書き換え

 速度向上

 タスク分割方法

 性能向上

 探索時間延長

 探索結果の信頼性を向上

マシンスペック

iMac Core 2 Duo

iMac

Core i 5

Amazon EC2

その他 コア 数 2010 307 0 0 7 666 2011 208 0 40 15 832 2012 0 _CPU 788 0 #core #cpu memory 9 3224

iMac Core 2 Duo

2.0GHz

Intel Core 2 Duo

2 1 2GB

iMac

Core i 5

2.5GHz

Intel Core i 5

4 1 4GB Amazon

EC2

2.93GHz?

Intel Xeon X5570

4 2 23GB

93

対戦実験

 今年も行なっていない

参考記録:

 金子, 田中「最善手の予測に基づくゲーム木 探索の分散並列実行 」 GPW2010

 逐次よりも強い

 8コアでメモリ共有探索4コアと同等

（勝,負,引分） メモリ共有型

1コア 2コア 4コア

クラスタ8コア 71 – 28 - 57 – 29 - 43 – 50 -

計算機群（再掲）

 情報基盤センター教育用計算機を利用

 東京大学駒場キャンパス情報教育棟

 平日と土曜日は学生が利用

 土曜日は一部演習室は閉鎖されている

 日曜祝日しか利用できない！

 利用申請が必要

 申請者は離れられない

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

95

他の部分の去年との違い

 評価関数

 古いバージョンに勝ち越すものを採用

 探索

 チェスプログラムStockfish を将棋へ移植

 gpsfish

 今回探索のスレーブとして利用

 チェスと将棋の違いに起因する問題が多々

 稲庭対策がない / クラスタはあり

 詰将棋がない / クラスタはあり

(元)駒得少年の冒険

関連 URL

 GPS将棋



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



http://twitter.com/gpsshogi

 Floodgate （コンピュータ将棋対局道 場）



http://wdoor.c.u-tokyo.ac.jp/shogi

 第22回コンピュータ将棋選手権



http://www.computer-shogi.org/wcsc22/

97

ドキュメント内 世界コンピュータ将棋選手権参加報告、及び、GPS 将棋の技術 (ページ 63-98)