オセロを速く解く話/solveothello

京大マイコンクラブの春合宿で、オセロを速く「解く」ことについて特化して話したスライドです。

Transcript

1. オセロを速く解く話 KMC6 回生 prime @2019 年 KMC 春合宿
2. 2 自己紹介 KMC-ID prime そすうぽよ Twitter: @_primenumber Mastodon: @prime@mstdn.poyo.me poyo 鯖新規登録受付中！ GitHub: @primenumber
3. 5 概要 オセロを速く「解く」ことに注力します 強いオセロプログラムを作ることが目標ではない 結果的に強いオセロプログラムは作れる CPU だけでなく様々なハードウェアを駆使して高速化
4. 6 目次 オセロを解くとは CPU で解く GPU で解く PEZY-SC/SC2 で解く FPGA で解く 並列化アルゴリズム
5. 7 オセロを解くとは あるオセロの盤面が与えられたときに、両プレイヤーが 最善を尽くしたときの試合結果を求めること → 最善を尽くすとは？
6. 8 最善を尽くすとは 再帰的に定義される ゲームが終了している盤面→なにもしない（自明） それ以外→手番のプレイヤーが 1 手プレイしたあとの盤面 それぞれについて、両者が最善を尽くした場合の結果を 求め、そのうち手番のプレイヤーにとって最も良い結果と なる盤面に遷移するプレイをする
7. 9 最善を尽くす例 丸が各盤面、矢印がプレイ（ゲーム木という） 各数字は石差 +6 -8 +20 +4 +16 先手 後手 終局
8. 10 最善を尽くす例 後手は後手にとって最も有利な局面に遷移する -8 +4 +6 -8 +20 +4 +16 先手 後手 終局
9. 11 最善を尽くす例 先手は先手にとって最も有利な局面に遷移する +4 -8 +4 +6 -8 +20 +4 +16 先手 後手 終局
10. 12 最善を尽くす例 両者が最善を尽くすと先手の 4 石勝ち +4 -8 +4 +6 -8 +20 +4 +16 先手 後手 終局
11. 13 MiniMax 法 オセロなどの二人零和有限確定完全情報ゲームを解く アルゴリズムの１つ 定義に従い再帰的に最善手を求めるアルゴリズム ゲーム木の大きさにおおよそ比例した時間がかかる → ゲーム木は残り石数が増えると爆発的に大きくなるので 残り石数が増えるごとに計算時間も爆発的に大きくなる
12. 14 NegaMax 法 MiniMax 法では自分の手番では最大値、相手の手番 では最小値を計算する必要がある 手番によって実装を変える必要がある 手番が変わるごとに試合結果を -1 倍して計算する 常に最大値を計算すれば良くなる 実装が簡単になる 計算量はほとんど同じ
13. 15 NegaMax 法 +6 -8 +20 +4 +16 先手 後手 終局
14. 16 NegaMax 法 -1 倍して最大値を取る +8 -4 +6 -8 +20 +4 +16 先手 後手 終局 -6 +8 -20 -4 -16
15. 17 NegaMax 法 -1 倍して最大値を取る +4 +8 -4 +6 -8 +20 +4 +16 先手 後手 終局 -8 +4
16. 18 NegaMax 法の実装
17. 19 FFO ベンチマーク コンピューターオセロ界で最も有名なベンチマークテスト FFO#1 から #79 まであり、おおよそ番号順に難しく なっていく FFO#1 でも 14 石空きであり、人間が読み切るのは かなり難しい
18. 20 FFO#1, #2 NegaMax 探索だと最も簡単な部類でも時間がかかる #1 #2 探索時間（秒） 498.901 265.216
19. 21 AlphaBeta 法 順番に読んでいると、読まなくても良い分岐があることが 赤の盤面を評価している時、その子ノードについて 12 より良い盤面は相手は選ばない 20 より悪い盤面は自分は選ばない つまりこの盤面は 選ばれない +20 +20 +12 +32 +12 +20
20. 22 AlphaBeta 法 選ばれない盤面なら読まなくても試合結果には影響しない この盤面の探索をここで打ち切ることが出来る 局面を読む順番に依存するが、大幅な高速化が見込める 実際の実装では、 alpha 値と beta 値という２つの 値を持つ 「 alpha 値と beta 値の間にだけ興味がある」という意味
21. 23 NegaAlpha 法 NegaMax 法と同様に手番が変わるたびに -1 倍する 子ノードの α 値は -beta 、 β 値は -alpha になる 子ノードの結果が beta 以上なら枝刈りできる 実装が簡単になる 計算量はほとんど同じ
22. 24 NegaAlpha 法の実装
23. 25 NegaAlpha 法の効果 #1 #2 mini-max （秒） 498.901 265.216 alpha-beta （秒） 0.776 0.63
24. 26 NegaAlpha 法の効果 #1 #2 mini-max （秒） 498.901 265.216 alpha-beta （秒） 0.776 0.63 数百倍高速化
25. 27 CPU での高速化テクニック 速さ優先探索 ビットボード 葉の近くに対する最適化 SIMD/ ビット演算命令 NegaScout 法 置換表 評価関数の利用
26. 28 速さ優先探索 真ん中の赤の局面を読む時、探索を途中で打ち切る ためには +20 以下の局面を見つければ良い 最善手である必要はない 最も読む局面数が少ない局面から 読みたい +20 +20 +32 +20
27. 29 速さ優先探索 着手可能手が少ない局面から順番に読む 着手可能手の数は読む局面数と正の相関があると 考えられるので、読む局面数が少ないと考えられる 速さ優先探索という Fastest-First Heuristic +20 +20 +32 可能手 5 可能手 3 可能手 9 +20
28. 30 速さ優先探索 着手可能手が少ない局面から順番に読む 着手可能手の数は読む局面数と正の相関があると 考えられるので、読む局面数が少ないと考えられる 速さ優先探索という Fastest-First Heuristic +20 +20 +32 可能手 5 可能手 3 可能手 9 +20
29. 31 ベンチマーク mini-max alpha-beta fastest-first 0.01 0.1 1 10 100 1000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
30. 32 ベンチマーク mini-max alpha-beta fastest-first 0.01 0.1 1 10 100 1000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 〜 35 倍程度の高速化
31. 33 ビットボード オセロの盤面は 8*8=64 マス 各マスは空き、黒、白のいずれか これを 64bit 整数 2 つで持つ 自分の石のある位置、相手の石のある位置 64bit*2=128bit=16Byte で盤面を表現できる メモリ使用量の削減になる 手番の交代は 2 つの整数の入れ替えで表現できる
32. 34 ビットボード ある場所に石を置いた際にひっくり返る石の計算 今の盤面で石を置ける場所の計算 両方とも分岐なしで算術演算とビット演算で出来る
33. 35 ビットボードでひっくり返る石の計算 簡単のため横 1 列、左向きの計算を説明 × 印の場所に白石を置いた時
34. 36 ビットボードでひっくり返る石の計算 ビットボードでの表現 1 0 1 1 1 0 1 0 0 1 0 0 0 0 0 1 黒石 白石
35. 37 ビットボードでひっくり返る石の計算 左端の黒石は今後の計算に邪魔なのでなくす 0 0 1 1 1 0 1 0 0 1 0 0 0 0 0 1 黒石 白石
36. 38 ビットボードでひっくり返る石の計算 置く場所より左が 1 のマスクを作る 0 0 1 1 1 0 1 0 0 1 0 0 0 0 0 1 黒石 白石 1 1 1 1 1 0 0 0 マスク
37. 39 ビットボードでひっくり返る石の計算 マスクの反転と黒石の OR を取る 必要な範囲の黒石の位置だけ取り出す 0 0 1 1 1 0 1 0 0 1 0 0 0 0 0 1 黒石 白石 1 1 1 1 1 0 0 0 マスク 0 0 1 1 1 1 1 1 演算結果
38. 40 ビットボードでひっくり返る石の計算 さっきの結果に +1 する 置く位置から黒石がどこまで連続するかわかる 0 0 1 1 1 0 1 0 0 1 0 0 0 0 0 1 黒石 白石 0 1 0 0 0 0 0 0 結果 0 0 1 1 1 1 1 1 結果 +1
39. 41 ビットボードでひっくり返る石の計算 白石、マスクと AND を取る 挟む反対側の石の位置がわかる（挟めなければ 0 になる） 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 白石 1 1 1 1 1 0 0 0 マスク 0 1 0 0 0 0 0 0 結果 +1 反対側の石
40. 42 ビットボードでひっくり返る石の計算 反対側の石 -1 とマスクの AND を取る ひっくり返る石の位置がわかる 0 1 0 0 0 0 0 0 1 1 1 1 1 0 0 0 マスク 反対側の石 0 0 1 1 1 1 1 1 0 0 1 1 1 0 0 0 反対側 -1 反転する石
41. 43 ビットボードでひっくり返る石の計算 右方向も似たような方法で求められる 8*8 盤面でもマスクを使うと同様にして求められる 横方向だけでなく縦や斜め方向も求められる
42. 44 ビットボードで着手可能位置の計算 これができると速さ優先探索が高速になる これも各方向に分けて高速に計算することができる
43. 45 ベンチマーク mini-max alpha-beta fastest-first bit-board 0.01 0.1 1 10 100 1000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
44. 46 ベンチマーク mini-max alpha-beta fastest-first bit-board 0.01 0.1 1 10 100 1000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 5 倍程度の高速化
45. 47 葉の近くに対する最適化 ゲーム木の葉の近く（終局間際）では 速さ優先探索はコストが大きい 着手可能位置の計算や、ソートのコストが大きい そこで、残り石数によって速さ優先探索するかどうか分岐 残り 6 石以下ではナイーブな探索に切り替え
46. 48 ベンチマーク mini-max alpha-beta fastest-first bit-board leaf-opti 0.01 0.1 1 10 100 1000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
47. 49 ベンチマーク mini-max alpha-beta fastest-first bit-board leaf-opti 0.01 0.1 1 10 100 1000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 2 倍程度の高速化
48. 50 SIMD/ ビット演算命令 SIMD(Single Instruction Multiple Data) 1 命令で複数データを処理すること SSE, AVX, NEON など ビット演算命令 特定のビット演算を高速化する命令 ひっくり返る石の計算、着手可能位置の計算に利用
49. 51 ベンチマーク mini-max alpha-betafastest-first bit-board leaf-opti avx2-popcnt 0.01 0.1 1 10 100 1000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
50. 52 ベンチマーク mini-max alpha-betafastest-first bit-board leaf-opti avx2-popcnt 0.01 0.1 1 10 100 1000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 2 倍程度の高速化
51. 53 NegaScout 法 αβ 探索では Alpha 値以下のノードには興味がない 何も更新されないので 先頭以外の各子ノードについて、 alpha 値を超えるかどうかだけ探索 solve(next, -alpha-1, -alpha) で実現できる 超えるなら改めて完全探索 solve(next, -beta, -alpha) する
52. 54 ベンチマーク 0.01 0.1 1 10 100 1000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
53. 55 ベンチマーク 0.01 0.1 1 10 100 1000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 1 〜 3 倍程度の高速化
54. 56 置換表 異なる打ち方から同じ盤面に到達することがある 同じ盤面を何度も探索する代わりに表に読んだ結果を保存 2 回目からは表を参照するだけで計算が終わる 実際には αβ 探索なので真の結果の範囲しかわからない 範囲を保存して今後の探索に活かす
55. 57 ベンチマーク 0.01 0.1 1 10 100 1000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
56. 58 ベンチマーク 0.01 0.1 1 10 100 1000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 1 〜 1.7 倍程度の高速化
57. 59 評価関数の利用 αβ 探索は、局面を読む順番に依存するが高速
58. 60 評価関数の利用 αβ 探索は、局面を読む順番に依存するが高速
59. 61 評価関数の利用 αβ 探索は、局面を読む順番に依存するが高速 自分に有利な局面から読んだほうが良いことが多い alpha 値が大きくなってよりたくさん枝刈りできるため
60. 62 評価関数の利用 速く読むためには、子ノードの結果が欲しい 子ノードの結果を知るためには、実際に読む必要がある 循環している…
61. 63 評価関数の利用 子ノードの結果の近似値を使うことで解決する 近似値によって並べ替える 近似値の計算 f( 盤面 )= そのノードを最後まで読んだ結果の近似値 となるような f が欲しい f を評価関数という 評価関数の作り方はいくつもあるが、精度の高いものを紹介
62. 64 評価関数の作り方 要は盤面の「良さ」を評価したい 良い盤面ならプラス、悪い盤面ならマイナスになる プレイヤーにとって有利・不利な点を見つける
63. 65 例：辺の評価 辺の石の配置によって有利・不利があると言われている 山：有利 ウィング：不利 爆弾：一概には言えない
64. 66 評価関数の作成 辺のありうるパターンは 3^8=6561 通り そのそれぞれに点数を付ける 山は +100 、ウィングは -100 など 4 辺の点数の和を盤面の評価値とする
65. 67 より良い評価関数 辺だけでなく隅の周辺や、縦横斜めの列にも点数をつける 評価値は各パターンに対する点数の和 x x x x x x x x x x x x x x x x x x x x x x x x x x x x
66. 68 より良い評価関数 点数の付け方も人力でやるのは大変 盤面と実際に完全読みを行った結果の組をたくさん用意 100 万組ぐらいは欲しい 評価関数の評価値と完全読みの結果が近くなるように学習 実際にはスパースな線型方程式を解くだけで出来る
67. 69 評価関数の適用 パターンによる評価関数の計算はそれなりに重い 残り数石なら最後まで読んでしまったほうが速いし正確 速さ優先探索との兼ね合いもある 12 石以上空いているときに採用する
68. 70 評価関数の適用 20 石空きの局面に対する評価関数の評価より 15 石空きの局面に対する評価関数の評価のほうが正確 かと言って毎回 5 手分読んでいては時間がかかりすぎる 最初に何手か評価関数の値を用いて浅い αβ 探索をする 探索時の結果をテーブルに保存しておき、完全読みに使う
69. 71 ベンチマーク 0.01 0.1 1 10 100 1000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
70. 72 ベンチマーク 0.01 0.1 1 10 100 1000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 1 〜 10 倍程度の高速化 (#39 は除く )
71. 73 葉に対する最適化その 2 1 石空きかどうかで場合分けをして最適化する 少しだけ効果がある
72. 74 ベンチマーク 0.01 0.1 1 10 100 1000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
73. 75 ベンチマーク 0.01 0.1 1 10 100 1000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 5% 程度の高速化
74. 76 実装 https://github.com/primenumber/rust-reversi Rust で実装
75. 77 オセロを解く 20 石空きぐらいは簡単に読めるようになった 時間をかければ更に空きマスが多くても解ける 初手（ 60 石空き）から解けるか…？
76. 78 計算量の見積もり 大体 1 〜 5*10^7nodes/sec 出ている ゲーム木の大きさは 10^54 、局面数は 10^28 程度 あくまで推定だか、大きくは外れていないと思われる αβ 探索は、理想的な場合はノード数が平方根ぐらい 置換表を使えば 10^14 ぐらい読めば良い…？ 単純計算で 3*10^6sec=35 日程度
77. 79 オセロを解く 実際に 35 日計算機を回す 残念ながら解けない 10^14 のメモリはない αβ 法にとって理想的な条件ではない
78. 80 オセロを解く 読む必要のあるノード数を見積もるのは難しい 10^15 程度なら 1 年程度走らせればよいが… 10^16, 10^17,… ぐらいあったら…？ 最悪死んでしまう また、 10 年 100 年プログラムを動かし続けるのは難しい
79. 81 オセロを解く どうしようもないのか…？
80. 82 オセロを解く どうしようもないのか…？ 待って！ 我々はまだ CPU の一部しか使っていない
81. 83 マルチスレッド化 サーバー用 CPU を使えば数十スレッド並列実行可能 単純計算で数十倍速くなる 1 〜 2*10^9nodes/sec 程度
82. 84 並列に解く とりあえず、一つの局面を並列化して読むのではなく、 多数の局面を並列に読むことを考える 単に 1 局面あたり 1 並列で解く アルゴリズムが単純になる 一つの局面を並列化するのはあとで考える
83. 85 GPU の利用 並列計算なら CPU より並列計算に適したデバイスがある GPU (Graphic Processing Unit) 画像処理を行うプロセッサ PC で画面に映像を出すのに使われる 並列計算に向いている GPGPU General Purpose computing on GPU GPU を汎用計算に使うこと
84. 86 GPU の利用 実装してみた https://github.com/primenumber/GPUOthello2 αβ 法 + 葉から遠いところで速さ優先探索 + 静的並べ替え 再帰をループで実装する必要があり、かなり移植に苦労
85. 87 GPU での分岐 GPU は何スレッドかを 1 つに束ねて実行している 16, 32, 64 スレッドなど 束ねられたスレッドは同一の命令を実行する 分岐があった場合 分岐の方向が全部同じ場合 分岐の方向の命令だけ実行する 分岐の方向が違う場合 両方のパスをマスク付きで実行する
86. 88 GPU での分岐 分岐の方向が同じ場合 if (X) { A; B; } else { C; D; } X==true X==true X==true X==true A A A A B B B B
87. 89 GPU での分岐 分岐の方向が違う場合 if (X) { A; B; } else { C; D; } X==true X==false X==false X==true A A A A B B B B C C C C D D D D
88. 90 GPU で再帰 + 分岐 GPU で再帰 + 各スレッドでバラバラに分岐すると、 1 スレッド以外はほぼ常にマスクされている状態になる void f() { if (X) { f(); } else { A; } } X !X !X X !X X X X
89. 91 GPU で再帰 + 分岐 GPU で再帰 + 各スレッドでバラバラに分岐すると、 1 スレッド以外はほぼ常にマスクされている状態になる void f() { if (X) { f(); } else { A; } } X !X !X X !X X X X f() f() f() f() f()
90. 92 GPU で再帰 + 分岐 GPU で再帰 + 各スレッドでバラバラに分岐すると、 1 スレッド以外はほぼ常にマスクされている状態になる void f() { if (X) { f(); } else { A; } } X !X !X X !X X X X f() f() f() f() f() !X X !X X X
91. 93 GPU で再帰 + 分岐 GPU で再帰 + 各スレッドでバラバラに分岐すると、 1 スレッド以外はほぼ常にマスクされている状態になる void f() { if (X) { f(); } else { A; } } X !X !X X !X X X X f() f() f() f() f() !X X !X X X f() f() f()
92. 94 GPU で再帰 + 分岐 GPU で再帰 + 各スレッドでバラバラに分岐すると、 1 スレッド以外はほぼ常にマスクされている状態になる void f() { if (X) { f(); } else { A; } } X !X !X X !X X X X f() f() f() f() f() !X X !X X X f() f() f() X !X !X
93. 95 GPU で再帰 + 分岐 GPU で再帰 + 各スレッドでバラバラに分岐すると、 1 スレッド以外はほぼ常にマスクされている状態になる void f() { if (X) { f(); } else { A; } } X !X !X X !X X X X f() f() f() f() f() !X X !X X X f() f() f() X !X !X f()
94. 96 GPU で再帰 + 分岐 GPU で再帰 + 各スレッドでバラバラに分岐すると、 1 スレッド以外はほぼ常にマスクされている状態になる void f() { if (X) { f(); } else { A; } } X !X !X X !X X X X f() f() f() f() f() !X X !X X X f() f() f() X !X !X f() !X
95. 97 GPU で再帰 + 分岐 GPU で再帰 + 各スレッドでバラバラに分岐すると、 1 スレッド以外はほぼ常にマスクされている状態になる void f() { if (X) { f(); } else { A; } } X !X !X X !X X X X f() f() f() f() f() !X X !X X X f() f() f() X !X !X f() !X A
96. 98 GPU で再帰 + 分岐 GPU で再帰 + 各スレッドでバラバラに分岐すると、 1 スレッド以外はほぼ常にマスクされている状態になる マスクされている間は計算していないのと同じ 演算能力の 1/16 や 1/32 しか使えない
97. 99 GPU での実装 αβ 法を素直に実装すると、再帰 + 分岐になる 各スレッドがバラバラに分岐して CPU より遅くなる そこで、スタックをメモリ上に用意し、再帰をループに 再帰はスタックを用いてループで書けることが知られている ループを用いると一重の分岐コストだけで済む 約 5*10^9nodes/sec NegaScout 等が実装されていないので、 nodes/sec の比ほどは速くはならない
98. 100 GPU の問題点 とはいえ、分岐のせいでそれなりに演算器は遊んでしまう GPU の構造上の問題なので、どうしようもない… GPU 以外の並列計算機を探さなければ…
99. 101 PEZY-SC/SC2 PEZY Computing 社の開発している MIMD プロセッサ 各スレッドが完全に独立して動作する 分岐によるペナルティがない！ PEZY-SC/SC2 の搭載されている菖蒲 (/SystemB) スパコ ンを使わせてもらえることになった 2017 年 12 月（ちょうど社長が逮捕された頃）
100. 102 PEZY-SC/SC2 版ソルバー 実装してみた https://github.com/primenumber/PEZY-Othello 8*10^9 nodes/sec (on PEZY-SC2 1 モジュール ) スタック領域が 1 スレッドあたり 2KB/2.5KB しかないため、かなり移植に苦労した
101. 103 PEZY-SC/SC2 版ソルバー αβ 法 + 葉から遠いところで速さ優先探索 + 静的並べ替え + 置換表 +NegaScout 評価関数の利用はまだうまく行っていない MIMD 動作のため、速さ優先探索の分岐ペナルティが なくなり、かなり葉の近くまで速さ優先探索出来るので nodes/sec の違い以上に速い
102. 104 PEZY-SC/SC2 版の実装 スタック領域が狭い 再帰で実装すると 10 石ぐらいしか読めない 結局 GPU と同様にメモリ上にスタックを構築、ループ化
103. 105 PEZY-SC/SC2 の問題点 スループットを出すにはかなりの並列度が必要 1 モジュールあたり数十万局面必要 1CPU に 4 〜 8 モジュール繋がっているので全体では 数百万局面必要 1 局面を解くのにかかる時間（レイテンシ）は長い 700MHz, 4 スレッド交代のため
104. 106 さらなる高速化を目指して どういうアーキテクチャなら良い？ 浮動小数点演算は不要 整数乗算も（いまのところ）いらない ビット演算、シフト、加算減算ばかり 理想的にはオセロ専用回路があると良い
105. 107 そんなものはない 浮動小数点演算はともかく、整数乗算もカットしたような アーキテクチャは殆ど無い オセロ専用回路を載せたアーキテクチャなど当然ない
106. 108 無いなら作る！ FPGA Field-Programmable Gate Array の略 自分で自由に回路を組むことが出来る オセロ専用回路のあるプロセッサを作れる！
107. 109 オセロソルバー on FPGA Othello ソルバーと FPGA は相性が良い FPGA にとって苦手な演算がいらない 乗算器の数も余裕がある ビット演算などが得意 オセロ専用回路を作れる
108. 110 オセロソルバー on FPGA 2018 年 5 月〜 https://github.com/primenumber/FPGAOthello 現在の仕様 パイプラインプロセッサ、 9 ステージ 9cycle / node を 9 並列 @1 コア 100MHz 程度 数千 LUT&FF / 1 コア 愚直な αβ 法
109. 111 FPGA 版の実装 FPGA では再帰をそのまま回路に落とし込むのは難しい スタックを Block RAM 上に作ってループで解く またか… パイプライン化するためには工夫が必要 すべての実行パスでサイクル数を揃える ステートマシンが単純なループになるようにする Block RAM へのアクセス回数を減らす 2 ポートしかないため
110. 112 オセロソルバー on FPGA のアーキテクチャ 9 段パイプライン Fetch Decode1 Decode2 Exec1 Exec2 Exec3 Exec4 Check Write Stack [154bit width * (16*9) depth] Dual Port BRAM
111. 113 Fetch ステージ 前回のループの処理で 石を置いたとき・新たな探索がスタートしたとき 前回のループからデータが送られてくるので、 それをスタックに書き込む それ以外 スタックのトップから探索情報を読みこむ
112. 114 Decode ステージ 探索情報を元に何をすべきか決める この局面を探索し終えた場合 パスの場合：パスの操作をする 終局の場合：石差計算をして親ノードに結果を伝える それ以外：親ノードに結果を伝える αβ 法の枝刈りが出来る場合 親ノードに結果を伝える それ以外 通常の探索をする
113. 115 Exec ステージ まだ探索していない子ノードを探索したい 空きマスの中から一つ選ぶ 4 サイクル掛けてひっくり返る石の計算をする 通常の探索でない場合は何もしない
114. 116 Check ステージ ひっくり返る石があるか確かめて、やることを決める ある場合 石を置いて子ノードの探索に移る ない場合 次の空きマスを調べる
115. 117 Write ステージ 結果をスタックに書き込んだり、次のループに渡したり 石を置ける場合 石を置いたことをスタックに記録、次のループに子ノードを 渡す 置けない場合：その場所を調べたことをスタックに記録 終局の場合：スコアを次のループで親ノードに渡す などなど…
116. 118 オセロソルバー on FPGA の性能 AWS F1 インスタンスに載っている、 Xilinx UltraScale+ VU9P で考える 2,364K FF & 1,182K LUT だいたい 300 コアぐらいは載りそう？ 3*10^10 nodes/sec 程度
117. 119 オセロソルバー on FPGA の今後の展望 Fetch ステージでスタックへの書き込みをやめる 次の Write ステージで書き込めば原理上行ける Simple Dual Port RAM にできる アーキテクチャによっては BRAM の数を減らせる Fetch/Decode と Exec/Check/Write を分ける Fetch/Decode を高速に動かす Exec は半分くらい演算器が遊んでいるので有効活用したい 速さ優先探索等を行う・クロック周波数の向上
118. 120 オセロソルバー on FPGA の問題点 速さ優先探索等をしていないのでそんなに速くない 将来的には実装したい たくさんのコアをつないだときのタスクの与え方 ラウンドロビンでタスクを与えるなどの工夫が必要 CPU との接続 バスと FIFO を介して接続する…？
119. 121 全体アーキテクチャ予想図 CPU 速さ優先探索コア 速さ優先探索コア Core Core Core Core Core Core Core Core Core Core Core Core スイッチ
120. 122 目標性能 10^12nodes/sec@AWS f1.16xlarge 8 モジュールの FPGA 搭載 300 コア / モジュール 2nodes/cycle >200MHz
121. 123 並列化について とりあえず並列で速く解けるようになった やりたいことは１つの盤面について深く速く読むこと
122. 124 αβ 探索の並列化 αβ 探索の並列化は難しい 枝刈りできるかどうかが過去の探索結果に依存するため 完全読みでなければ Lazy SMP というよい手法がある 今回は完全読みなので YBWC や APHID という手法を使う
123. 125 YBWC あるノードを探索するとき、ノードが「良い」順番なら、 α 値の更新は先頭ノードでしか起こらない 仮定の元では、先頭ノード以外はどんな順番で探索しても 良い 先頭だけ直列で探索し、残りの探索を並列化する
124. 126 ベンチマーク @4 コア 8 スレッド 0.01 0.1 1 10 100 1000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
125. 127 ベンチマーク @4 コア 8 スレッド 0.01 0.1 1 10 100 1000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 1 〜 3 倍程度の高速化 (#47 等は除く )
126. 128 APHID マスタースレッドとたくさんのワーカスレッドに分ける マスタースレッドは根に近い数段を探索する 根から一定段数進んだら、ワーカーにその局面の探索を 投げる マスタースレッド自身はワーカーの探索が終わるまでは 評価関数を用いた推定値を使って探索を続ける マスタースレッドは繰り返し探索し、推定値を使わなく なったら終了
127. 129 YBWC vs APHID コア数が少ない時： YBWC の方がよい コア数が多い時： APHID の方がよいはず… 現状では CPU 版 : YBWC GPU/PEZY-SC2 版 : APHID の亜種 非同期にタスクを投げるのが難しいので亜種 FPGA 版 : APHID の予定
128. 130 現状の進捗 6x6 オセロ 初手からの 32 手完全読み CPU 版（評価関数なし） : 1 時間 34 分 GPU 版 : 43 分 PEZY-SC2 版 : 未実装（ GPU 版と同程度？） FPGA 版 : 未実装（ GPU 版よりかなり速いはず…） 目標性能が出れば 1 秒未満で解けるが…
129. 131 今後の展望 まずは有名な定石や 6x8 オセロを解く 評価関数の精度向上 より「賢く」評価関数を使う 並列化の効率向上 FPGA の利用
130. 132 今後の展望 8x8 オセロを解く より精度の高い評価関数の作成（ Deep Learning? ） 分散コンピューティング より賢い分散・並列化アリゴリズム
131. 133 まとめ 様々なテクニックにより探索を高速化出来た いろいろなハードウェアを検討し、ソルバーを実装した CPU, GPU, PEZY-SC/SC2, FPGA 探索の並列化アルゴリズムを実装した アーキテクチャやアルゴリズムは改善の余地あり 今後のそすうぽよ先生の進捗にご期待ください！