CSA例会 YSSの16台クラスタ探索について 2014/05/10 山下 宏 クラスタ探索 GPS MinMax木を再構成 読み筋通り局面が進んだ場合、該当マシンの探索を停止させない Bonanza MinMax木を再構成 合議も利用(探索時間のコントロール用) YSS MinMax木を再構成 Puellaα 一番左の手以外の深さ1,2,3の子を同時に探索 α値が変わらない、と仮定したギャンブル ponanza 楽観合議 基礎データ(すべて1000局の自己対戦) 探索ノード数を4分の1、2分の1での勝率 勝率 0.072 4分の1 75k vs 300k 75000局面/手と300000局面/手の対戦 0.221 2分の1 150k vs 300k 0.341 200k vs 300k 0.420 250k vs 300k 0.574 350k vs 300k 0.641 400k vs 300k 0.713 500k vs 300k 0.789 600k vs 300k 参考(旧YSS) 0.667 2秒 vs 1秒 fish系の探索はノード数の差がかなり大きく勝率に出る ハッシュを毎回クリアした場合 0.287 300k vs 300k ハッシュを消すとかなり勝率が下がる。思考時間が半分相当。 --> 前回探索を担当したマシンに同じ局面以下を割り当てるのが大事？ ハッシュを消さないローカルマシン1台での結果(75k x16台 対 300k 1台) 0.481 4k 75k n=16 ( 8, 2,2,2,2,2,2,2, 2) 0.334 4k 75k n=16 ( 8, 2,2,2,2,2,2,2, 2) ハッシュを消す 0.311 4k 75k n=16 ( 8, 2,2,2,2,2,2,2, 2) ハッシュを消す 前回の深いPVを使わない 参考 0.614 2台の楽観合議 3スレッド x2 - 3スレッド 1.3倍程度の高速化にしかなってないか。 MinMax木再構成 短い時間で上位N手を調べて、それを分配。 GPS将棋は1秒や、実現確率の値(探索なし)。 Bonanzaは0.1秒 YSSは選手権では0.3秒(16000局面探索を15回) 上位N手以外の手は「その他」でまとめて1台で探索。 αβ値は共有しない。 マシンごとに探索深さはバラバラ。 マシンが2台の場合は、浅い探索での最善手とそれ以外、の2つ？ 勝率 浅い探索のノード数 0.602 1k 最善とその他 300k 0.613 4k 最善とその他 300k 0.638 30k 最善とその他 300k 0.746 300k 最善とその他 300k 4kぐらいを適切と考えると、2台の楽観合議とほぼ同じ勝率 マシンが3台の場合は 「最善」「2番目」「その他」か 「最善−最善」「最善−その他」「その他」。 0.711 4k 300k 「最善−最善」「最善−その他」「その他」 0.775 4k 300k 「最善」「2番目」「その他」 明らかにRootを3つに分割するほうが0.775でよい。 3台でほぼ2倍速の効果。 浅い探索のノード数の比較 3台 0.725 1k 最善、次善、その他 300k 0.710 4k 最善、次善、その他 300k 0.739 30k 最善、次善、その他 300k 0.877 300k 最善、次善、その他 300k 3台 0.688 1k 最善最善、最善その他、その他 300k 0.691 4k 最善最善、最善その他、その他 300k 0.740 30k 最善最善、最善その他、その他 300k 0.837 300k 最善最善、最善その他、その他 300k 5台 0.739 1k 最善、2番目、3番目、4番目、その他 300k 0.747 4k 最善、2番目、3番目、4番目、その他 300k 0.793 30k 最善、2番目、3番目、4番目、その他 300k 0.896 300k 最善、2番目、3番目、4番目、その他 300k 6台 0.729 1k 最善、2番目、3番目、4番目、5番目、その他 300k 0.777 4k 最善、2番目、3番目、4番目、5番目、その他 300k 0.821 30k 最善、2番目、3番目、4番目、5番目、その他 300k 0.890 300k 最善、2番目、3番目、4番目、5番目、その他 300k 1kと4kでは大差ないように見える。 1kだとほとんど深さ1の静止探索で終わってしまう程度 難しいのは何手に分割していくか 浅い探索の評価値の差が大きければ、それ以降は分割しないと？ 1手目の探索値が+500、2手目が+400と100点差がついたら2手目以降は 「その他」にして1手目の最善を分割していく 8台分割。基本はRootを4手に分割。 2番目の差がついた手を「その他」に含める 0.252 4k 75k nMachines= 8, (4, 3,2,2) STOP_SPLIT_DIFF = 100 0.304 4k 75k nMachines= 8, (4, 3,2,2) STOP_SPLIT_DIFF = 200 0.308 4k 75k nMachines= 8, (4, 3,2,2) STOP_SPLIT_DIFF = 400 0.310 4k 75k nMachines= 8, (4, 3,2,2) STOP_SPLIT_DIFF = 800 2番目の差がついた手は分割するが3番目以降は「その他」で 0.291 4k 75k nMachines= 8, (4, 3,2,2) STOP_SPLIT_DIFF = 100 0.308 4k 75k nMachines= 8, (4, 3,2,2) STOP_SPLIT_DIFF = 200 0.305 4k 75k nMachines= 8, (4, 3,2,2) STOP_SPLIT_DIFF = 400 0.305 4k 75k nMachines= 8, (4, 3,2,2) STOP_SPLIT_DIFF = 800 100点差で分割をやめる場合には悪化。 --> 浅い探索の評価値はほとんど信用できないかも YSSが選手権で使った分配。16台。 Rootで8つ、2手目は2つ。3手目も2つ。Rootの最善-最善、の変化のみ3手の深さで探索。 0.393 4k 75k N=16 ( 8, 2,2,2,2,2,2,2, 2) ... 採用してたもの 0.351 4k 75k N=16 ( 8, 4,3,3,2) 0.306 4k 75k N=16 ( 4, 4,3,3, 2,2,2,2,2) 3.2倍程度の高速化にはなっていた？ (4倍で0.50、2倍で0.22程度、なので) どの手が採用されたか？ 2次予選、決勝11局の合計。(4局はログの保存忘れ) Rootで8個に分割した場合のみ(定跡や王手で1手だけなどを除く) 最善 339 57% 浅い読みでの最善。予測が当たった場合は2手前のPVの手 2番目 82 13% 予測は 56% 当たった(304/537) 3番目 37 6% 4番目 24 4% 5番目 26 4% 6番目 18 3% 7番目 7 1% その他 60 10% --------------------- 合計 593 100% 割合に応じたマシンを分配すればいいのでは？(小谷先生) その他を2つ以上に分割したほうがいいかも。 角打ち、飛車打ち、など似た手は1台にまとめるとハッシュ効果がでるかも(柿木さん) YSSがやってた工夫 前回の深いPVがあれば、その手を優先的に分割 ▲26歩△34歩▲25歩△33角▲76歩...、がPVでこれを探索していたマシンが13番なら 次の3手目の探索で ▲25歩△33角▲76歩 の探索はマシン13番に割り振る(予測が当たったときのみ) GPS将棋の大玉送り方式の方がより洗練されてます。 現役プロ棋士に勝ち越したコンピュータ将棋 三浦弘行八段とGPS将棋との対局を振り返って https://ipsj.ixsq.nii.ac.jp/ej/?action=pages_view_main&active_action=repository_view_main_item_detail&item_id=94776&item_no=1&page_id=13&block_id=8 世界コンピュータ将棋選手権参加報告及び, GPS将棋のアルゴリズム http://www-erato.ist.hokudai.ac.jp/docs/seminar/erato20120524.takeuchi.pdf GPW2010 最善手の予測に基づくゲーム木探索の分散並列実行 http://www.graco.c.u-tokyo.ac.jp/~kaneko/papers/gpw2010-slide.pdf 浅い探索で2番目が500点差以上あるときはeasyとして探索を早く打ち切る。 心配 ある手を無視した探索をしてるので、その局面のハッシュ情報は正しくない。 無視しない探索で来た場合に嘘の情報を返す可能性あり。 --> 実験中は特別悪影響みたいなのは出てこなかった。 費用 Amazon EC2から c3.8xlarge 16core HT (32 threads) E5-2680 2.80GHz 60GB、を16台借りた。全256コア。 2日間で665$(約7万円)、395時間。テストはなしでぶっつけ本番。 1台あたり$1.68/1時間。3月までは$2.4で30%値下がりした。 アメリカ(Oregon)のサーバを。0.2秒ぐらいの遅延がある。 日本(東京)のサーバだともう少し早いが料金も高くなる。 スポットインスタンスを使えば1割程度で借りれるらしい。 グローバルIPを16個使ったが、1個でローカルIP15個、もできるらしい。 実装 あから2010の時の金子さんの実装が役にたってます。 USIで通信。 無視する手を ignore_moves で指定。 position startpos moves 5i5h 5a5b ignore_moves 7g7f 2g2f 5h6h 5h4h go stop go が来た回数と bestmove を送った回数を覚えておき、stopが来たときに if ( usi_go_count <= usi_bestmove_count ) この stop は無視 とする。bestmoveを送った直後にstopが来るのを防ぐため sshでpipeで通信。Ayaのroot並列の実装とほぼ同じです。 http://www.yss-aya.com/book2011/cluster20120306.zip 探索サーバはアメリカにおき、日本-アメリカ間の通信は最小に なるようにしていた。 探索ログ(決勝のponanza-YSS戦) http://www.yss-aya.com/20140505pona.txt 思考ログの読み方 http://524.teacup.com/yss/bbs/2390 参考データ(ハッシュ共有の1台実験)、微妙に条件が違うので参考程度で 75kを16台と300kを1台。0.500になれば4倍速でていることになる。浅い探索は4kを15回。 0.388 4k 75k n=16 4, 3,3,3, 2,2,2,2,2,2 深さ1(root)は4つ(3手+その他)に分割。深さ2では3つ、深さ3では2つに分割 0.363 4k 75k n=16 4, 4,4,4, 2,2,2 0.419 4k 75k n=16 5, 4,4,3, 3,2 2 0.399 4k 75k n=16 6, 4,4,3, 2,2 0.417 4k 75k n=16 7, 4,4,3,2 0.434 4k 75k n=16 8, 4,3,3,2 0.409 4k 75k n=16 9, 4,3,2,2 0.443 4k 75k n=16 10, 4,3,2 0.439 4k 75k n=16 11, 3,3,2 0.396 4k 75k n=16 12, 3,2,2 0.409 4k 75k n=16 13, 3,2 0.396 4k 75k n=16 14, 2,2 0.407 4k 75k n=16 15, 2 0.324 4k 75k n=16 16, 0.473 4k 75k n=16 ( 6, 2,2,2,2,2, 2,2,2,2,2) 0.467 4k 75k n=16 ( 7, 2,2,2,2,2,2, 2,2,2) 0.481 4k 75k n=16 ( 8, 2,2,2,2,2,2,2, 2) ---> 選手権で採用した構成 0.426 4k 75k n=16 (10, 3,3,2,2) 0.455 4k 75k n=16 (10, 3,3,2,2) 0.448 4k 75k n=16 (10, 3,2,2,2,2) 0.434 4k 75k n=16 (10, 2,2,2,2,2,2) 0.450 4k 75k n=16 ( 8, 2,2,2,2,2,2,2, 2) 0.396 4k 75k nMachines=16 ( 4, 4,4,4, 2,2,2) 0.409 4k 75k nMachines=16 ( 5, 4,4,3,3, 2) 0.421 4k 75k nMachines=16 ( 6, 4,4,3,2,2) 0.448 4k 75k nMachines=16 ( 6, 2,2,2,2,2, 2,2,2,2,2) 0.442 4k 75k nMachines=16 ( 5, 2,2,2,2, 2,2,2,2, 2,2,2) 0.412 4k 75k nMachines=16 ( 4, 2,2,2, 2,2,2, 2,2,2, 2,2,2) 0.380 4k 75k nMachines=16 ( 3, 2,2, 2,2, 2,2, 2,2, 2,2, 2,2 2,2 2,2) 0.245 4k 75k nMachines=16 ( 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2) 0.582 4k 150k nMachines= 8, N>=6,3 N>=3,2 (4, 3,2,2) 0.580 4k 150k nMachines= 8, N>=4,2 0.681 4k 150k nMachines=16, N>=6,3 N>=3,2 N>=16,4 (5, 4(2),4,3,3) 0.649 4k 150k nMachines=16, N>=6,3 N>=3,2 N>=16,5 (6, 4,4,3,2,2) 最初の1手だけの浅い探索を25倍かけた場合。合計すると4k*15=60kに。大差なし。 0.319 1k 75k nMachines= 8, (4, 3,2,2) if ( i==0 && node_n <= 0 ) fish_limit_nodes *= 25; 0.278 1k 75k nMachines= 8, (4, 3,2,2) if ( i==0 && node_n <= 1 ) fish_limit_nodes *= 13; 0.371 4k 150k nMachines= 2 0.382 4k 150k nMachines= 2, find_split_pv_hash() 深い探索のPVを利用(予測が当たったときのみ有効) 0.493 4k 150k nMachines= 4 (3, 2) 0.510 4k 150k nMachines= 4 (3, 2), find_split_pv_hash() 0.353 4k 75k nMachines= 8 (4, 3,2,2) 0.314 4k 75k nMachines= 8 (4, 3,2,2), find_split_pv_hash() 0.402 4k 75k nMachines=16 (8, 4,3,2,2) 0.415 4k 75k nMachines=16 (8, 4,3,2,2), find_split_pv_hash() 0.420 4k 75k nMachines=16 (10, 4,3,2) 0.423 4k 75k nMachines=16 (10, 4,3,2), find_split_pv_hash() 0.410 4k 75k nMachines=16 ( 7, 4,4,3,2), find_split_pv_hash() 0.404 4k 75k nMachines=16 ( 8, 4,3,3,2), find_split_pv_hash() 0.400 4k 75k nMachines=16 ( 9, 4,3,2,2), find_split_pv_hash() 0.415 4k 75k nMachines=16 (10, 4,3,2 ), find_split_pv_hash() 0.455 4k 75k nMachines=16 (11, 3,3,2 ), find_split_pv_hash() 0.426 4k 75k nMachines=16 (12, 3,2,2 ), find_split_pv_hash() 0.455 4k 75k nMachines=16 (10, 3,3,2,2), find_split_pv_hash() 0.448 4k 75k nMachines=16 (10, 3,2,2,2,2), find_split_pv_hash() 0.434 4k 75k nMachines=16 (10, 2,2,2,2,2,2), find_split_pv_hash() 0.450 4k 75k nMachines=16 ( 8, 2,2,2,2,2,2,2, 2), find_split_pv_hash() 0.449 self1 4k 75k nMachines=16 (11, 3,3,2 ), find_split_pv_hash() 0.443 self2 4k 75k nMachines=16 (12, 3,2,2 ), find_split_pv_hash() 0.417 self3 4k 75k nMachines=16 (13, 3,2 ), find_split_pv_hash() 0.388 self4 4k 75k nMachines=16 (14, 2,2 ), find_split_pv_hash() 0.397 self5 4k 75k nMachines=16 (15, 2 ), find_split_pv_hash() 0.426 self7 4k 75k nMachines=16 (10, 3,3,2,2), find_split_pv_hash() 0.481 self8 4k 75k nMachines=16 ( 8, 2,2,2,2,2,2,2, 2), find_split_pv_hash() 0.467 self9 4k 75k nMachines=16 ( 7, 2,2,2,2,2,2, 2,2,2), find_split_pv_hash() 0.473 selfa 4k 75k nMachines=16 ( 6, 2,2,2,2,2, 2,2,2,2,2), find_split_pv_hash() w3680yss.txt 0.299 4k 75k nMachines=8 4, 3,2,2 0.304 4k 75k nMachines=8 5, 3,2 0.330 4k 75k nMachines=8 6, 2,2 0.334 4k 75k nMachines=8 7, 2 0.363 4k 75k nMachines=16 4, 4,4,4, 2,2,2 0.419 4k 75k nMachines=16 5, 4,4,3, 3,2 2 0.399 4k 75k nMachines=16 6, 4,4,3, 2,2 0.417 4k 75k nMachines=16 7, 4,4,3,2 0.434 4k 75k nMachines=16 8, 4,3,3,2 0.409 4k 75k nMachines=16 9, 4,3,2,2 0.443 4k 75k nMachines=16 10, 4,3,2 0.412 4k 75k nMachines=16 10, 4,3,2 追試 0.411 4k 75k nMachines=16 10, 4,3,2 投了でVALUE_MATED_IN_MAX_PLY 0.423 4k 75k nMachines=16 11, 3,3,2 投了でVALUE_MATED_IN_MAX_PLY 0.388 4k 75k nMachines=16 4, 3,3,3, 2,2,2,2,2,2 0.439 4k 75k nMachines=16 11, 3,3,2 0.396 4k 75k nMachines=16 12, 3,2,2 0.409 4k 75k nMachines=16 13, 3,2 0.396 4k 75k nMachines=16 14, 2,2 0.407 4k 75k nMachines=16 15, 2 0.324 4k 75k nMachines=16 16, 0.398 1k 75k nMachines=16 10, 4,3,2 if ( i==0 && node_n <= 0 ) fish_limit_nodes *= 49; 0.388 1k 75k nMachines=16 10, 4,3,2 if ( i==0 && node_n <= 1 ) fish_limit_nodes *= 25;