【オセロ,将棋】ボードゲーム【囲碁,War】

[過去ﾛｸﾞ] 【オセロ,将棋】ボードゲーム【囲碁,War】 (1002ﾚｽ)
上下前次 1-新
抽出解除ﾚｽ栞

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索歴削→次ｽﾚ栞削→次ｽﾚ過去ﾛｸﾞﾒﾆｭｰ

310(283): 2015/08/18(火)16:59 ID:QcCJSSMl(1/2) AAS
AA省

311: 310 2015/08/18(火)17:06 ID:QcCJSSMl(2/2) AAS
ちなみに、置換表のキーは、盤面と手番です。

ハッシュ値を使用し、衝突した場合は、チェーンで下につなげています。
今のところ、メモリーの上限等は設定しておらず、領域も足りています。

313: 310 2015/08/18(火)23:21 ID:5wjtKO2B(1) AAS
何がですか？

315: 310 2015/08/19(水)09:33 ID:DdofkXsp(1) AAS
いなければ仕方ないですね。

テスト関数を置換表付negascoutにしたら、ちゃんと答えが返ってくるようになりました。
けど、なんか気持ち悪い。置換表の扱い方は一緒なので、たまたま上手く行ってるだけ
ではないかと思います。むむむ。

MTD(f)にこだわり続けてもあんまり意味が無いので、評価関数づくりに入ります。

３層パーセプトロン型にするか、普通の線形回帰にするか。
パーセプトロンタイプは、パターン学習のタイプを作ってみましたが、学習データ３４０万
省3

316: 310 2015/08/24(月)09:51 ID:Y8Lk5h3w(1) AAS
BITBOARDで確定石をそこそこ正確に求める方法を考えました。
思いっきり脱線中ｗ

ただ、斜め方向に「列すべてに石が置かれている」状態を検出する方法と、
その時に、斜め方向の列すべてに確定ビット（仮）を建てる良い方法が見つ
からずに、斜め方向のAND用の定数配列を用意してループを１５回回してる。

縦横は、分割統治でそこそこなロジックになったんだけど。

４５度回転を使っても、そんなに高速化できそうにないなぁ。
省2

317: 310 2015/09/02(水)11:43 ID:s0BtWfox(1) AAS
ぬぬぬ。パターンによる線形回帰の石差予想。
最急降下法は収束してるんだけど平均２乗誤差が４８０とかになる。
１σでいうと１局面あたり２２石（黒石の数では１１石）もの誤差。
これでは使い物にならない。

ステージ分割しているんだけど、ステージが進んでも誤差はほぼ一緒。
ウェイトがオールゼロでも似たような数字になるレベル。
テストデータで局面評価させると、それなりに石差は計算しているっぽいが、
省7

319: 310 2015/09/02(水)21:57 ID:5gNGVEfH(1) AAS
正規化というと、thellさんのlearning.pdfで言うところの、αの設定ですか？

当初はmin（β/100,β/Nj）の正規化型で作ってましたが、上手くいかないので
収束を早めるのは後回にして、今は単純にステージ毎の局面データ件数α=β/Nの
形にしてます。

が、発散を避けようとすると、βをあまりに小さくしなければならないのが、なんか変な
気がしています。今は10の-7〜-8乗くらいの値です。やっぱり変ですよね。

最急降下法のコードどこか間違えてるんだろうなぁ。

322: 310 2015/09/03(木)10:19 ID:Fd8XT4rV(1/2) AAS
色々と失礼しました。

もう一度、よーく上記pdfを読み返していたところ、原因らしきものが見つかりました。
記載にあいまいというか、ちょっとおかしいところがあって、式の変形をしっかり追って
確認すれば良かったのですが、思い込みで解釈をして変な計算をしていました。

そこをとりあえずざっと修正したところ、遅々としつつも収束に向かっている模様ですが、
まだまだ完全ではないようです。ある程度二乗誤差が減ったところで、また増え始めたり
しています。正規化も試したけど、やはり同じ。
省1

323(1): 310 2015/09/03(木)10:38 ID:Fd8XT4rV(2/2) AAS
>>320
もともとひっくり返しあった後の終局を予測するのが目的なので、教師データは最終局面
の石差です。盤面の特徴（パターン）から、最終石差を予想するための重回帰計算なので、
その時点の石数は、説明変数に入れてません。なので、パターンの選択が適切なら、
最善手の応酬において１手毎にどれだけ石数が入れ替わろうと、影響を受けずに、
二乗誤差が終局に近づくほど減っていくと予想されます。
というか、そうなるように説明変数であるところのパターンを模索していくと理解しています。
省11

324: 310 2015/09/07(月)01:11 ID:OHPpdG+6(1) AAS
収束しかかった二乗誤差がまた増え始める原因はまだわかりません。
増え始めるまでは収束方向には向かっているのは確かなのでβの初期設定を
いって誤魔化す方向で。最急降下法ってこんなものなのかなぁ。

一通り納得したので、パターンをLogistelloと同一のものにまで拡充してスムージングも
入れてみましたが、新たなバグを仕込んでしまった模様で、一部計算がぐちゃぐちゃorz
バグ探しの旅に出ます。

裏で、Solverの速度アップを検討。
省5

327: 310 2015/09/14(月)09:33 ID:Rx5y2/Cc(1/2) AAS
線形回帰で相変わらず時間食ってます。
一応、バグらしきものはそれなりに解消されましたが、やはりいかんせん収束が遅い。
一晩かけて５０〜１００試行して、途中で止めてやり直しなんてのやってる間に１週間は
あっという間に経ってしまうものです。まだ誤差が大きい。１０００回程度回して、どこまで
収束するか見てみようかなと。またぞろ３層パーセプトロンが気になる今日この頃。

確定石計算もバグ取りはできたと思いますが、その分計算が１．５倍ほどに膨れてしまい
ました。しばらく思考実験していたら、確定石なのに確定していると評価できない確実な
省9

328: 310 2015/09/14(月)17:35 ID:Rx5y2/Cc(2/2) AAS
反復深化が劇遅なのは、使い方を誤っていました。
リーフのところまで使うとコストアップなのは考えれば当然でした。
まあ、おバカなバグもありましたが。

negaMaxに対して反復深化を試すと、１割程度の高速化となりましたが、
negaScoutに対してやると多少低速化して、negaMaxの反復深化と変わらない速度に。
scout missが３倍近く増えているので、評価関数の精度があまり良くないためかなと。
move orderには、通常はmobilityとコーナー着手を使用しているのですが、これ、
省7

330: 310 2015/09/15(火)20:18 ID:egtjjW0V(1) AAS
準確定石の計算って実は思ったよりコストフルかもと気づいてしまい、
急きょコーディングして比較してみる事にしました。

releaseモードだと、自分の計算方法では跡形も残らないため、時間計測不可能。
debugモードでも、数十倍速いと言う結果になりましたので、今の確定石計算ロジック
は、悪いモノではないと自分に言い聞かせる事にしました。

それより、回帰の学習で、少しずつ少しずつ２５０回くらいまで学習進めていたのですが、
バグを見つけてしまい、またやり直しです。むむむ。しかも、なおした事で計算時間が
省1

332: 310 2015/09/22(火)22:15 ID:70n8Fwqa(1) AAS
回帰は地道に学習中。もう少しやってみるって感じだけど、収束状態の誤差が大きいのは
ステージ分割でオリジナルな変な事をしているからじゃないかと気になりだした。
あと数百回学習を回したら、通常のステージ分割版も作ってみるかなと。

色々いじってるうちに、FFO#40が６．２秒まで来た。何が良かったのか良くわからない。
反復深化をターゲットに改良しているんだけど、negaScoutも同じ時間。

FFO#41を試したら、反復深化で４５秒弱、negaScoutで３０秒弱という結果に。
探索ノード数がすごい事になってるので、反復深化のmoveorderのどこかがおかしい
省1

333: 310 2015/09/25(金)16:54 ID:9OkLc3+M(1) AAS
回帰のステージ分割というかスムージングを、ネット上でノウハウ公開されてるみなさん
と同じようにしたら、１σで６を切ってきた。やっぱ、スムージングやり過ぎて、精度が
落ちていたのね。同一ステージ内でも値がばらついているので本当に必要なのか、
気になるので、落ち着いたら両方試そうかと。先に方向性見ちゃったから本来とは
逆順になっちゃうけど。

色々頑張ったら、FFO#40が５．１秒、#41が２０秒、#42が１８秒となりました。
ソースとにらめっこしてれば、ネタはそれなりに出てくるものだなぁと。
省6

334: 310 2015/10/04(日)01:12 ID:+bDErzEp(1) AAS
色々やって、FFO#40でnegaScoutで３．４秒まで来ました。

反復深化は異なる方法で２種類作ってみたけど、FFO#40程度の深さだとnegaScoutとの
差が出てこない。２２手とか２４手とかまで行くと、差が出てくるように感じるけど、後回し。

どうしても気になって、Zebraのソース解説（日本語）を見つけて、そこに出てるソースを
見ました。自分なりにロジック面で工夫した事はほぼ同じ事をやっている。流石。
あとマクロを多用してる。僕はインライン指定でコンパイラ任せ。
マクロにするとデバッグが極端に大変になるので、マクロ化するのは最後。
省7

335: 310 2015/10/07(水)17:10 ID:i7/9rua6(1) AAS
デバッグで試しに変えた箇所を戻し忘れたりして、二次災害三次災害を出して、
相当混乱したけど、やっぱり境界問題だった。これmoveorderの順によって出ない
可能性もあるので厄介。自分は開き直って、探索の幅に-1つけてるけど、皆さんは
どう回避しているのかなぁ。

zebraのwindowの取り方は、基本的にMTD(f)みたいに置換表利用を前提とした、
固定分割サーチだけど、negaScout（MTD(f)やzebra方式の中で使用している）と
速度的には同等な感じ。最初の探索で勝敗がわかるという点がメリットなのか。
省14

336: 310 2015/10/12(月)23:43 ID:ZTwsIi7y(1) AAS
色々やってるけど、FFO#40では速度向上はほとんどなし。
置換表のサイズが見えて来たので、１件ごとにmallocしていたのを、配列にして一括で
領域確保するように変更（当初の形）したら、速度のバラツキがだいぶ減ったように思う。
NPSが変動すると、何か悪いことしかたと悩んでしまい、修正して二次災害を起こすので
地味に大事かな。

FFO#43は多少高速化してて、パラメータ最適化するとMTD(f)で１２秒台くらい。置換表
適用範囲の指定を下（葉）からしていたのを、上（ルート）からに変えた。あと、MTD(ｆ）
省12

337: 310 2015/10/14(水)23:51 ID:V3YF/mde(1) AAS
negaMaxはmoveorderの修正漏れでバグってて、直したらやはりFFO#40で５．４秒でした。

MTD(ｆ）は２．４秒でzebra並になったけど、#41以後は３〜４倍時間がかかる。
その差は探索ノード数に比例してる。前向き枝刈使うわけにはいかないし、#41以降の
差を詰めるにはmoveorderしかないと思う。

とはいえ主だった事は一通り試してしまった。むむむ。

偶数理論で思いついた方法が純粋に面白そうなので組んでみる。
想定では、速度が結構遅くなるはずなんだけど、まあ面白そうという事で。

338: 310 2015/10/16(金)10:24 ID:Q2afyb0d(1) AAS
偶数理論の関数は思いのほか軽くできて、オーバーヘッドの心配が少ないです。

BITBOARDの空マスを、囲まれて独立している塊ごとに分離してBITBOARD配列にして
返す関数を作りました。これをPOPCountで数えて着手した場所が偶数空エリアなのか
奇数空エリアなのかを判定します。

最初にテストしたFFO#43のMTD(ｆ）でいきなり３０％近く高速化して「やった！」と思った
のもつかの間。実はミスで判定を逆にしてまして、偶数マスに打って奇数を相手に渡すと
加点になってました。で、いろいろテストした結果、最初にやったケースではたまたま
省10

339: 310 2015/10/17(土)09:29 ID:uZH1KzRS(1) AAS
最終２手高速化したあたりから、ノード数が過小になっていたので、それを直しました。
自分のと比較すればよいかと思って放置していましたが、そろそろちゃんと比較しようかなと。
結果、探索ノードが思っていた以上に多かった事、そしてNPSは９〜１１K出てるので、
NPSを落としてノード削減する余地があるという結果に。

あまりテストしていなかったFFO#41と42ではzebra方式と呼んでいた（後述）方法が、自分の
中では最速で、MTD(ｆ）の結果があまり思わしくない事も。MTD(ｆ）の#40は初期条件が良か
ったからの模様。
省8

342: 310 2015/10/30(金)17:31 ID:uxyAnbEX(1) AAS
棋譜ベースで序盤２０手の定石DB作った。
定石DBは置換表をベースに作ったので、検索は速いけど、容量が大きい・・・。

簡単にαβで２０手探索してみた。
ネットで調べた定石集に載っていない手筋が出てきてしまった。むむむ。
５手目までエビ系で、しかも石差＋２で黒勝ち。棋譜が偏っているのかな。

棋譜は例の５０万棋譜計画の奴で１０手目、２０手目以降を訂正したというデータ。
明らかに壊れたデータが入っていたりと、何かと使いにくい箇所があるデータだけど、
省5

343: 310 2015/11/08(日)00:32 ID:LMw8+3qF(1) AAS
moveorderを早くする方法というのは、事前に軽く探索した手順を保存し、その手順から
優先して探索するというもの。理論的にはscout missがゼロになる。
探索した手順を取り出す仕組みが必要になるので、その辺を改造しようと思ったところで、
悪い癖が出てしまいました。Cベースのソースを一旦棚上げして、C++ベースのクラスを
利用した形で一から作り直してしまいました。

moveorderの配列をvectorに変えたり、unordered_mapを見つけたので置換表に使って
みたり。置換表は、システム任せにして動的にメモリ確保に行かすと、探索ノードの減少
省7

344: 310 2015/11/12(木)16:56 ID:4hPfHY6k(1) AAS
ようやく、C++ベースの終盤探索（negaScout）が、Cベースより若干速くなりました。

・unordered_mapの速度のバラツキはデバッガー上限定。
実行ファイルでも多少ばらつくけど、メモリ効率＆メンテナンス性からunordered_mapを採用。
・探索した確定手順を返す方法の検討で苦戦。
negaScout＋置換表では原理的に無理と認識するのに時間を要しただけでしたorz
置換表無しnegaScoutかnegaMax＋置換表では、後者の方が高速。
・確定手順を元にmoveorderする改造の効果は限定的。
省7

345(1): 310 2015/11/19(木)14:23 ID:W/V+CKXD(1) AAS
定石部分もクラス化が終わりました。クラスなんての扱うの初めてなので、もうちょっと
綺麗にできたかなと思う面もありますが、C++習得が目的ではないので。

終盤確定読みは０．０５秒刻みで速度アップ。FFO#40で２．３秒になりました。

今まで、速いプログラムでは３０手目くらいから勝敗判定を始めると言う記述を読んで、
なんて速いんだと思いつつ、何に使うんだろうと思っていましたが、ようやく腑に落ちました。
オセロというゲームは勝敗だけが問題で、勝つんなら２石差で十分。「少なくとも負けない
手」というなら、(-1,0)のNull windowで探索してβカットされた手を選べば良い。評価値は
省11

346(1): 310 2015/11/21(土)00:05 ID:WWzrsUCT(1) AAS
定石DBを使って３０手目まで着手した盤面の予想石差が２で勝ち判定だったので、
試しに３１手目から勝敗判定をしてみました。

(-1,0)のNull windowで７分３０秒ほどで解けました。
（参考）勝ちと引き分けを区別するために(-1,1)で計算すると９分３０秒ほど。
探索ノード数がintではオーバーフローしてしまった・・・。

これから、３３〜４手目（残り２６〜７手）くらいで、１０秒程度で解けると予想されます。
勝勢ならこれで良いのですが、敗勢の時は、初段がβカットされないので１０倍程度
省2

347: 310 2015/11/23(月)21:01 ID:24rahmZ0(1) AAS
ProbCutとMultiProbCutのBUROさんの論文あらかた読み終えました。
最初、MPCの方から読んでちんぷんかんぷんだったので、ProbCutを読んで、
戻って来て、ようやく実装のイメージが湧くところまで来ました。
というか、この発想に至る道具立てや考え方は、既に揃ってた感じ。例えば>>323とか。

これ>>345-346の勝敗判定の高速化に使える気がする。相手側の手番では
前向きカットしないようにすれば、相手の反駁手を見逃さないからいけるんかなと。
あまり深い読みで使用するとパラメータ作りでしばらくPCを占有しそうだけど。
省5

348: 310 2015/11/25(水)22:32 ID:APRE5Y1F(1) AAS
条件を決めて簡単にMPCパラメータの計算プログラムを作って検証してみました。

３０手目の時点（深さ３０）の時の浅い探索０〜１０手でMPCパラメータを計算してみました。
例の３００万件棋譜の３０手目以後完全読み（らしい）１９０万件ほどのデータからランダム
に２００件ほど抽出して使用。

結論）δが１０石、R-2が０．７未満という状態で、とても使えたものではないという事に。
ただ、３５、４０、４５手目時点からのカットを試す価値はあるかも知れない。

一方、３０手目の時点で、深さ１０の探索に対して、浅い探索６までで計算すると、
省7

350: 310 2015/12/02(水)23:21 ID:Xp/MZwxE(1/2) AAS
とりあえずMPCの仕組と終盤探索用のパラメータだけ作り、終盤探索と勝敗判定に
適用してみました。

勝敗判定は３１手目から。浅い探索は残り手数の1/3。T=1.5で時間短縮が微妙な感じ。
終盤探索はFFO#40でテストしたところ、T=1.5だと途中で正解着手がカットされている
模様で、T=2.0で正解。T=2.0だと時間変わらずみたいな微妙な結果に。

もう一度、MPCの論文を良く読んでみましたが、どちらかというと評価関数の精度の差
の方が大きい様子で、もともと標準偏差が倍近いので、そこを何とかしなきゃならんと。
省15

352: 310 2015/12/04(金)23:35 ID:DNSRUk3b(1) AAS
結局、確定石が評価関数の誤差の大きさと、収束性の悪さの原因だったみたいです。
前半から中盤はmobilityのウェイトが大きそうなので、とりあえず復活させてみました。
あと、スムージングは、あるステージで出現しなかったパターンが隣接ステージにある
可能性も考慮し、ウェイトがゼロのパターンを減らす目的もあるようです。

実際、２００試行ちょっとでかなり誤差が減ったのですが、FFO#40で試すと途中の評価値
のバラツキというか、極端に０に近い局面が現れて、２σ以上の差異が簡単に出てしまい
ます。そこで、ちょっとだけスムージングを入れて、かつデバッグ段階ではウェイトゼロの
省3

353: 310 2015/12/05(土)23:27 ID:VLRyPTJJ(1) AAS
モビリティーも収束悪化の原因でした。
確定石の数にしても、モビリティにしても、ある程度大きな数字が出るものがダメっぽいです。

評価パターンとウェイトを確認できるようにして、FFO#40〜41の完全読みに登場する盤面を
チェックしましたが、ウェイトゼロのパターンは出現していないようです。

評価値が大きくぶれるところがありますので、スムージングを入れてみて計算開始です。

354: 310 2015/12/07(月)10:00 ID:JSVZKjkd(1) AAS
スムージングも外してみたら、Buroさんの論文なみ（か、それ以下）のσが出そうな
感じになってきました。収束が良いのでβも大きくできたし、その後の計算でも工夫を
入れたので、Buroさん論文みたいに３００回試行で十分なレベルになりそうです。

ウェイトゼロのパターンはありました。FFO#40の５０手目のCORN２ｘ５に１つ現れます。

現在selective endgame searchがどんなものなのか、想像を膨らませています。
iterative widening endcutのイメージがなんとなくつかめてきました。
ソースを探して見ちゃえば早いんだろうけど、面倒だし、想像だけで頑張る。
省1

355: 310 2015/12/10(木)23:16 ID:lQAJMVKx(1) AAS
結局、評価関数は１０００回試行までやってます。
β・1/Nでやってるけど、それだと収束が遅いので、１００回試行ごとにβを倍々に。
１０００試行目で発散するステージが出たので、βを下げて最後の１００試行を実行中。

その間、反復深化などで使えるように、置換表を改造。前回評価範囲をmoveorderで
再利用します。いちいち消しているとメモリ解放で時間がかかるし、全データを入れたまま
用途をキーで区別すると、使用時に選択する事になりオーバーヘッドが気になるので、
一番新しい評価値をひたすら上書きし、置換表として使用する時のみ、今回探索か
省5

356: 310 2015/12/11(金)22:32 ID:c1YdnEjo(1) AAS
あちゃ。ウィンドウ幅１でiterative wideningやると、正解着手もβカットされた手も
置換表の値が全部同じになって、次の探索でmoveorderが意味なしになって、
速度が大幅低下する事が発覚。

仕組み考えないと・・・。

357: 310 2015/12/13(日)23:14 ID:RUGsIY6w(1) AAS
一応回避したけど、MPCの速度向上は限定的。
中盤探索というか評価関数が驚くほど遅いのだろうという結論に。

放置していた中盤探索の素の高速化に入ります。
１か所ネタはあるんだけど。

359: 310 2015/12/20(日)17:21 ID:UpZkem/K(1) AAS
中盤探索で改良をしたらかえって遅くなるを繰り返してます。

で、やけくそ気味にmoveorderの「置換表がない時」の計算値を、簡素化してみたら
中盤探索の速度そのままに、終盤探索部分の探索ノードが減少して高速化。
終盤探索部分も同様に簡素化したら、FFO#40で1.75秒以下になりました。

それでも相変わらず#41/42はzebraがずーっと早い。

で、MPC使うと遅くなる理由を考えていたら、いま使っているMPCのセットは終盤探索用に、
残り手数と浅い読みのセットを独自パターンにして計算した奴だと言う事を思い出した。
省2

361: 310 2015/12/23(水)16:26 ID:MLtsaD3t(1/2) AAS
どもです。
Ｂｕｒｏさんのパワポっぽい資料に名前しか書いてないので中身がわかりません。
わかっているのはＭＰＣと併用するらしいことくらいです。

iterative wideningで検索すると確かに碁の関連の英語論文がヒットしますね。
関係なさそうだと思って放置していましたが、ちょっと見てみようかなぁ。

置換表云々は、僕の想像です。
αβを前提にしたアルゴリズムで高速化するネタの一つに、moveorderを工夫して
省6

363: 310 2015/12/23(水)22:38 ID:MLtsaD3t(2/2) AAS
>>362
ご助言ありがとうございます。

MPCはまだ途中ですが、そんな感じです。
終盤ｎ手高速化の類もしています。中盤探索だと葉に近いところで置換表外すと、
著しく速度が低下するので、最後まで置換表を使っています。

で、中盤の速度がいまいちで１２手読みくらいが実用範囲って感じです。
MPCでｄ計算に１００棋譜くらい試して一晩で計算できる範囲は１３〜１４手くらいが
省11

364(1): 310 2015/12/24(木)20:33 ID:zDiJT168(1/2) AAS
ちと調べてみました。SIMD命令はx64でコンパイルしている時は、設定しなくても自動的に
使うようになっているみたいな説明を見つけました。

並列化とかベクター化とかもコンパイラが自動でやってくれるみたいですが、レポート出し
たら確かに一つも対象になっていませんでした。評価値算出とmobilityの２関数は、なんか
効きそうな気がしますので、少し悶々とトライしてみます。

また、_mm_popcnt_u64と_BitscanFoward64は、今やってみたら、何故か使えました。
色々とコンパイラのオプションをいじったのが原因かなぁ。謎。
省8

366: 310 2015/12/24(木)22:56 ID:zDiJT168(2/2) AAS
_mm_popcnt_u32()はすでに使っていました。u64が使えなかっただけです。
u32→u64で３〜５％くらいの高速化になっています。

困った事に、debugビルドの側では、まだ64bit版が使えていません。
debugを使いたい時は32bitに直さないといけない。
コンパイルオプションをいろいろ見比べていますが、どこなのかいまだにわかりません。

#43は最終２手なのか１手なのか、どちらにバグがあるのか切り分けようとして
ソースいじっているうちに直ってしまいました（汗）。

368: 310 2015/12/26(土)11:23 ID:2a5cp76f(1) AAS
どもです。バグったところはMPC使って無い箇所でした。

コンパイラの自動ループ展開は上記２か所で試してますが、なかなかうまく行きません。
なんとか依存関係を解消してループ展開強制すると劇的に速度低下する状態です。

その代り、いろいろググっていたら、BMI命令を見つけて、BLSIとPEXTを使ってみました。
速度バランスが変わったのでパラメータで置換表適用範囲を狭めるなどもしましたが、
FFO#40で1.55秒前後まで高速化できました。中盤探索も高速化はしているはずですが、
数％程度の改善というところでしょうか。まだ５０％は高速化したい状態です。
省3

369: 310 2015/12/28(月)10:45 ID:i0yT273K(1) AAS
デバッグモードでu64系の関数が使えない件、解消しました。

MTD(ｆ）に代えてアスピレーションウィンドウを採用しました。
中盤探索は、隣の評価値をたどっていくと、かえって遅くなるのでnegaScoutだけで
探索していましたが、これでMPC計算が多少高速化できそうです。

MPC計算はまだしていません。反復深化でどのくらいの深さの探索で、どのくらいの
件数なら実用的に計算できるか試行しています。１４手読みまでは行けそうですが、
１５手だと厳しいかなぁという状態。２０手付近では盤面によっては、探索ノードが爆発的
省4

371: 310 2015/12/29(火)02:31 ID:F/Ba7yoX(1/3) AAS
ちょっと一括変換操作を誤って大変な事になっていました。一通り直していたところ、
FFO#40で1.45秒程度が出るようになってしまいました。多分、修復がてら置換表登録・
検索関数の変数の並びを、整列したのが効いたのだと思っていますが、びっくりポンです。

前回課題の正解着手が複数あるケースですが、MTD(ｆ）のような評価値決め打ち系の
探索では、ぴったりの答えが見つかった時点で、ほかの手を探索する必要が無い事に
気づき、直してみたところ、FFO#44は速度アップしました。が、#43はまだ駄目です。
とはいえ、#43は浅い探索の評価値が外れすぎて時間がかかっているような感じなので、
省6

373: 310 2015/12/29(火)10:25 ID:F/Ba7yoX(2/3) AAS
って、βカットしない事を確認しなきゃきゃいけないから、ぴったりの答えがあっても
全手を探索しないとダメじゃん。すんません。

374: 310 2015/12/29(火)10:52 ID:F/Ba7yoX(3/3) AAS
>>372
やったりやらなかったりで、いろいろ比較して試してます。

MTD(ｆ）では、ワーストケースではウィンドウ中心が評価値の最少単位で動く関係で、
１石以下の少数計算をする中盤探索では、よけいに時間がかかる事が多いです。
そのため、アスピレーションウィンドウ導入前はただのnegaScoutにしてました。
終盤探索は、最少単位が１石になりますので、許容範囲です。

MTD(ｆ）もアスピレーションウィンドウも、所詮本チャンのnegaScoutを呼び出すための
省7

375: 310 2015/12/30(水)00:01 ID:lfikhn/D(1) AAS
結局、本日は探索速度アップばかりやってました。

中盤探索というか評価関数の計算でBMI2命令を徹底的に使ってみました。
また、ボードの回転操作系も見直しました。
１０％程度は高速化できたと思います。でも、期待したほどではなかった。
あと、速度アップするなら、ボードの対角線転置かなぁ。あと効果は微妙だけど、１８０度
回転がビットオーダーの逆転なので、これも何か組み込み関数があったらうれしいなと。

終盤探索では、FFO#59問題に対処。
省5

376: 310 2015/12/31(木)21:04 ID:i5TR43+g(1/2) AAS
2015年の年の瀬は、MPC計算のメモリーリークの原因探しで更けていく・・・
置換表クラスあたりっぽいんだけど、デバッグの仕方が良くわからないという・・・

377: 310 2015/12/31(木)23:46 ID:i5TR43+g(2/2) AAS
ギリギリ１２時前に直った。
メモリリークではなく、不正なアクセスでした。
多分直ったと思う・・・

来年の抱負は、MPCの計算をする事と、GUIを作る事です。
元々VBのGUIからDLLで呼び出すつもりでしたが、なんとなくC++でやってみようか
という気になってきています。

378: 310 2016/01/03(日)11:08 ID:3YPfF+nL(1) AAS
バグは解消してました。なんとも不可思議な事になっていました。
スタック領域を破壊していて、破壊された箇所がたまたまdepth（残り探索深さ）だったため、
探索深さがマチマチになってました。計算時間やメモリ使用量が異常になる以外は、そこそこ
それっぽい探索結果が出ていたため、メモリリークだと思ってしまったという。

中盤探索の置換表適用範囲も、ちゃんと効くようになって深さ１１〜１２まで置換表を使用
するのが効果的と出て、探索値のバラツキもそこそこ揃って、探索時間も予想できる範囲に。
メモリ使用量も安定しました。
省8

379: 310 2016/01/04(月)22:22 ID:1p46+Vgy(1) AAS
MPCのための探索データ蓄積の間に、並列処理について調べてみました。
VC++だとopenMPとPPLってのが使えるみたいです。
?concurrent_unordered_mapが便利そうなので、PPLにしよううかなと。

で、脳内コーディングであれこれ考えていたら、AIの中でBoardクラスを参照渡しして、
差分型で盤面を進めたり戻したりしているのが、とても並列処理と相性が悪い事に
思い至りまして・・・。コピー型に戻して、何をクラス化するのかとか見直してみようかと
言う事に。
省1

383: 310 2016/01/09(土)02:12 ID:GhyCVx1P(1) AAS
どもです。

とりあえず、コピー方式に変えてましたが、変にバグを仕込んだりして、時間がかかって
ました。ようやくデバッグもあらかた終わったのですが、まだ原因不明・解釈不能な速度
差があって、終盤探索のみ速度が１０％以上低下した状態です。
というか、コピー版を書きながら気づいた箇所を、ボードクラス版にも反映すると、ボード
クラス版が高速化して、差が広がるという。
で、クラス版がFFO#40で１．４０〜１．４２秒になりました。
省6

385: 310 2016/01/10(日)01:14 ID:F6Uvkb4b(1) AAS
うわ。色々やり方あるのね。
VC++だとPPL、openMP、std::threadか。

PPLについては、逐次処理のまま置換表で使っているunordered_mapをconcurrent版に
変えてみたところ、置換表付探索の速度がおおよそ半分になってしまったので、結構
微妙な印象を持っています。
とりあえずopenMPでどこまでできるか試してみて、気に入らなかったらstd::threadで
細かく制御できないか考えてみます。
省7

386: 310 2016/01/11(月)20:31 ID:IrhGHm3u(1) AAS
とりあえずopenMPで並列化トライしてみましたが、コンパイル中に内部エラーになる。
ネットで見ると最適化オプションがらみらしいけど、なんかよくわからなかったのでパス。

PPLを使って、とりあえず並列化のテスト。オセロでは標準的と思われるｎ段YWBCに
してみました。forループみたいな特定の形ではPPLは結構簡単という印象。

バグは一通りとれた状態だと思いますが、FFO#40で１．２５秒が０．８５秒程度になり
３０％強の高速化。あと少しだけソース修正するつもり。

使ってるパソコンは２コアでした。昨夜まで４コアのつもりでいましたが（汗）、２コアなら
省1

388: 310 2016/01/13(水)13:02 ID:Yd1pcfW8(1) AAS
どもです。

コア数２だと、理屈の上では２倍近くまでは速度アップできるのかなぁと思います。
一般的にはどのくらいの倍率をターゲットにしているのでしょうか。

YBWCの適用のパターンをいくつか試しましたが、タスクマネージャーで見たCPU使用率
は、ほぼ１００％になってるので、単純にはスピードアップは難しい感じがしてます。
PPL自身のオーバーヘッドなのか。
PPLは楽ちんだけど、チューニング箇所がなさすぎな感じ。
省4

389: 310 2016/01/16(土)09:10 ID:mjTPCiWE(1/2) AAS
PPLはMicrosoftのDeveloper Networkくらいしか情報が無いので、ひたすらリンクを
たどって情報収集してますが、ほとんど機械翻訳で、結局カーソルあてて英文読ま
ないと意味が分からないという・・・

で、排他制御とかいい加減にしていたノード数カウントなどをきちんとして、ソースの見易さ
と効率を上げようと色々と細かく修正。combinableとかcritical_sectionとかInterlockedとか。

と・・・思ったら・・・中盤探索で確率１０％程度で違う答えが返ってくる・・・
並列探査のバグはわかりにくくて時間を食ったのですが、どうもcombinableの動作が変。
省2

390: 310 2016/01/16(土)11:37 ID:mjTPCiWE(2/2) AAS
中盤探索を１万回程度回して、違った答えが返ってこない事を確認できました。

ノード数カウントはInterlockedIncrementを使っているんだけど、やはり排他待ちロスが
大きいようで、ノードカウントありだと０．８秒前後、無しだと０．７秒前後になる。
使えなかったcombinableみたいな形にして、一つの再帰関数内はローカル変数で加算
して、最後にまとめて１か所で排他加算するようにしてみようかな。

並列タスクの起動順で、探索ノード数が違ってくる関係で、実行時間のバラつきが±０．５
秒くらいになっている。

391: 310 2016/01/18(月)09:54 ID:ED4vwFCp(1) AAS
結局、ノード数・リーフ数カウントは、戻り値を構造体にして返す方向にて検討。
普段の探索には不要だけど、solverだと表示したいので。
これで完全にローカル変数になり、排他ロスを気にする必要がなくなる。

デバッグ用の置換表回りの統計は、所詮デバッグ用なので、一旦全削除。
必要になったら、こちらは#ifdefで囲って、排他加算する。

で、構造体の形であれこれ悩んでいたら、戻り値をクラスにできる事に気が付いて・・・
あらためてC++すげーと感心中。
省4

392: 310 2016/01/19(火)00:13 ID:Dh1WPUXC(1) AAS
終盤探索の修正完了。

０．８秒±０．０５秒と、結局、Interlockedでグローバル変数のノード数を加算するのと、
大して時間が変わらないか、もしかしたら微妙に遅くなったかも。元に戻すのが面倒
なので、他で改良点を探すしかないかなと。

393: 310 2016/01/21(木)10:04 ID:c00KCFqr(1) AAS
YBWCでは、最適着手手順（PV）のラインで置換表でmoveorderする意味が無いという事
を突き詰めていくと、いちいち前回探索の置換表を引くループを回して、都度最善の着手
を求めるのではなく、前回探索で得たPVを渡せば、時間が短縮できそうな気がしてきま
した。ツリーの浅い部分なので、全体にどれくらい効くのかはわかりませんが。

また、浅い探索などで最適着手手順を取得する時、negaScout＋置換表だと正しいscoutmiss
が発生した時に、nullサーチ時の置換表が適用されて、それ以後のPVが得られないという
事で、悩むところではあります。
省7

394: 310 2016/01/23(土)01:31 ID:0OQfWIYl(1) AAS
パソコン再起動すると、何かのタスクがCPUを３０％くらい占有してしまいます。
昨日まで快調に動いていたのが突然遅くなって、悩んでいましたが、これが原因のようです。
というわけで、本日は色々改変したソースの速度が計測できずに悶々としてました。

色々すったもんだ挙句、PVラインを渡す形にしましたが、効果があったかどうかは微妙。
色々付け足した事で生じた速度低下はペイしたかなぁという感じで、#40で0.78秒前後。

本格的にネタが尽きて来たので、ここから先は、MPCをきちんと実装してiterative widening
にかけるしかないかなぁという感じです。あと、定数で渡している置換表適用高さなどの
省1

395: 310 2016/01/27(水)01:18 ID:IVwAw5rN(1) AAS
オライリーの並列化本が来たので拾い読みしながら並列プログラミングの勉強。
PPLの各アルゴリズムが何を目的とするものなのかが、少しずつ分かってきました。
抽象化度が高いので、最初のとっかかりとしては良いかも。何故かcombinableが
上手く動かないとか、parallel_reduceの中身がよく分からないとかありますが。

で、並列化できるところを探して速度が上がるか試したり、同じ処理をより綺麗に書き
換えしたりして、微妙に速度アップし、0.70〜0.75秒くらい、ノード数が15M、NPSが21M
nps程度になりました。たまに0.68秒台が出ます。
省6

396: 310 2016/01/29(金)11:31 ID:trvaxUQ+(1) AAS
先日の速度アップネタはすべて不発でしたが、その際にノード数のカウント漏れを見つけ
て、修正したところ、ノード数は１７〜８Mという感じでした。その際に、最終２手高速化の
箇所でもカウント漏れがあり、まずは正確なノード数を簡便に把握しようと外してみたところ、
意に反して速度低下しないところか、どうも微妙に高速化したように見えまして（汗。

最終３手高速化を試してみたり、最終１手高速化も外してみたり、moveorder適用とか、
そもそもmobilityを求めずに空マスを順に着手してみるとか、その辺の適用深さを変えて
みたりいろいろとやって現時点の最適パラメータにしてみたところ、0.63〜0.68秒、最速で
省4

397: 310 2016/01/30(土)20:51 ID:yCKBToEa(1) AAS
囲碁がすごい事になってますね。オセロで一通り勉強したら小さい盤の囲碁をやって
みようと思っていたので、モチベーション低下中。とはいえ、ああいうのをオセロに応用
しようとしたら、あそこまでマシンパワーいらないんじゃないかとか・・・。

ここのところ、もっぱらSTLやPPLの機能を綺麗に使う方向での改良ばかりしてました。
pararell_reduceの使い方もわかりました。negaScoutの繰り返しループが綺麗に並列化
できたんじゃないかと。ただ、MAPする件数がしれているので、parallel_reduceではなく
逐次版のaccumlateの方が速いという結果に。あと、時間計測が結構飛び飛びの値に
省5

398: 310 2016/02/07(日)21:48 ID:xNqeS9Ve(1) AAS
ここら辺で、EDAXとかとの速度差の原因を考えたところ、次の２点が考えられました。
１．評価関数の精度が悪い可能性
２．個々の関数で速度アップの余地がある可能性
という事で、１は熟考が必要なので後回しで、速度アップの対象として、flipとmobilityの
高速化を検討。とはいえ、良い知恵があるわけでもないので、ネット徘徊。

現在、ポインタ関数で分岐して処理しているflip関数を１発で処理するopenCLのソースを
発見。Master Othelloの作者のものでEDAX4.3のflip関数を参考にしているらしい。
省10

399: 310 2016/02/09(火)01:09 ID:MeGl+gwc(1) AAS
flip関数続き
・lzcntを自前で組んでみましたが、やはり処理が重く速度低下。ボツ。
・右方向と左方向で処理が違うので、片側＋１８０度回転で、同じ処理にしてlzcnt不使用
にしてみたが、１８０度回転×４が重くて速度低下。ボツ。
・できるところまでベクタ化して、lzcnt以後はスカラ計算で、速度若干改善。
・上記からlzcnt後、再度ベクタ化してみたら、速度若干低下したのでボツ。
・64bit×４の値を代入する関数を変更したら、意に反して結構速度改善。
省12

401: 310 2016/02/20(土)13:43 ID:ZGi2V8ih(1/2) AAS
GUIできた。昔作った序盤定石部分と合体。
中盤探索を反復深化にして、３秒を超えて新しい深さに入らないあたりで調整。
MPCで２５手くらいまで読めるように調整。
終盤完全読みは３８手から。３６手からMPC付で完全読み（つまり完全ではない）。

こんな感じでできたので、早速プレイ。自分だと軽く全滅負けしてしまうので、zebra先生
にお越しいただきました。が、滅茶苦茶弱い。

良く見ると、定石が効いている段階で＋１６だったのが、中盤読みになった瞬間に一気に
省3

402: 310 2016/02/20(土)23:06 ID:ZGi2V8ih(2/2) AAS
zebra先生にならって定石の評価を表示するオプションをつけてみました。
ロジック的には間違いなさそうですが、定石DBがおかしいというか、定石に登録がない
手順に正しい変化があって、それを無視しているため、間違った判断をしているみたい。

一応、完全読みという触れ込みの棋譜を元にしているはずなので、使い方をどこかで
勘違いしているんだと思います。しばらく悩むしかなさそうです。

403: 310 2016/02/21(日)01:04 ID:nPWuqcvw(1) AAS
試しに定石部分を外して、中盤探索で開始してみたら、zebraの２０手読みに対して
２戦して１勝１分となりました。読みの深さは、こちらが上なので、こんな感じでしょうか。
序盤２０手分は評価値が無いので、２０手近い探索を反復無しで探索するため、MPCを
使っても最初の数手は１手あたり５分以上掛かってしまいます。

定石については、以前にウェブで見つけてテキストに起こした定石データがあるので、
それを評価０で登録してみようかなぁと思っています。

定石の自己学習とか、評価付けとか、どうやるんだろ。

404: 310 2016/02/25(木)21:06 ID:fXRsnvrs(1) AAS
定石データを、上記の手打ちデータで作り直しました。
当初は並び取りとかの極端な進行以外は評価０．０にしたため、mobility関数のビット列
の下から定石に従って着手する形となり、zebra先生のBookに誘導されるように、少しずつ
不利な定石に乗り換えていき、負けるという展開に（汗

悔しかったので別のソフトを拾い、戦ってみると、そちらには圧勝。決して弱くはないと思う。
また、zebraとの対戦時にBookで評価値がついているものは、それを参考に修正したところ、
時々勝てるような感じになりました。
省5

405: 310 2016/02/28(日)01:10 ID:hQzoi2Tz(1) AAS
縦取り系は白番黒番試して、定石の評価値を修正してみました。
あと、AIの進行ごとのパラメータを試行錯誤して、なるべく負けないようにしてみました。
これにより、AIの読み時間が結構伸びて、１ゲームワーストケースで１手２分、トータル
５分くらい思考してしまいます。これは、反復深化などで、タイムアップをせずに、次の
ステップに入る制限時間だけ決めているためです。

EDAX＋Unified Book先生はレベル２１で、黒番白番ともに引き分けになります。
こちらは２０手前に定石が切れていますが、その後も最善手が打てているという事になり
省12

411(1): 310 2016/03/04(金)10:15 ID:Q4DtXsqP(1) AAS
>>410
一晩考えてみた。

通信回りに興味を持って遊んだのは１５年くらい前だし、Javaとかイメージしかないし。
あまり助言できる事はありませんが、一つ言えるのは、UIに凝ったりサービス内容を
考えたりするのは最後で良いと思います。

Rubyが好きなら、まずはCGIベースで、テキスト表示で対戦を実現する仕掛けを作る事
だと思います。次に複数のユーザーが接続するのであれば、身元確認のためのID/パス
省6

415: 310 2016/03/10(木)02:00 ID:hvbQwbFh(1) AAS
うむむ。
これにて、オセロができたら次は囲碁という目標が雲散霧消してしまいました。

どうしよう。

416: 310 2016/03/10(木)18:05 ID:b1SmaPOg(1) AAS
AlphaGO強すぎ・・・orz

今夜は、囲碁関係者だけじゃなく、AI周りの人も、Google以外全員お通夜ですね。

422: 310 2016/03/13(日)20:47 ID:50OeMIN8(1) AAS
うむ。なんか期待を裏切られっぱなしｗ

この負けっぷりを見ると、囲碁もトライしたくなってくる希ガス。

424: 310 2016/03/16(水)23:06 ID:YEZK1fac(1) AAS
アルファ碁ロスまっただ中ですｗ

オセロ作ったおかげで、一連の勝負をいままでとは違う視点で見れたかなぁ。
とりあえず、囲碁のモンテカルロ解説した本と、ディープラーニングの入門書を
買ってきた。さらっと読んだけど、ディープラーニングは理解に時間がかかりそうorz

オセロで３層パーセプトロンを試したときは、結局うまく動かなかった。
実装が悪いのもあるけど、学習にもすごく時間がかかった。
あれをディープにしたら、どうなっちゃうんだろうかは不安ではある。
省1

435: 310 2016/04/05(火)10:45 ID:82XTVDoH(1) AAS
久々登場。アルファ碁ロスがでかすぎて、やる気がでないです。

とりあえず、BOOK上で乱数入れて手をばらけさせるようにしました。あとの課題は、
１．持ち時間制度
２．ステータスバーの更新
標準のStatusBarだとOnMouseMoveなどで更新されるとの事。
リアルタイムに更新させるためには、マウスくるくるさせてなければならん。
３．中盤探索の高速化
省15

448: 310 2016/05/16(月)21:32 ID:KQ1qSDyb(1) AAS
モチベーションダダ下がりだったけど、なんとなくソースの整理していたら、
直したいところがいろいろ出て来て、見直し中。

後ろ向き枝刈で探索時間は変わらないけど、探索ノード数が2/3になった。
この枝刈手法の速度アップできたら面白いかもと思いつつ、元々自分が
結構高速に書いていた処理（未使用）を流用しているから、これ以上速度アップ
できるかわからん。

でも、EDAXには勝てないんだろうなぁ・・・
省1

449: 310 2016/05/26(木)16:01 ID:ZBCA70ec(1) AAS
遅々として進んでいます。
ソースを一から組みなおして、いろいろと綺麗にしてます。
並列探索を入れない段階で、FFO#40が結構速くなった。

いまさらながらに、FFOテストを40〜59まで実行して比較しようとしたところ、
前から薄々気づいていたけど、FFO#41以後が遅い。酷いケースになると
探索ノード数が１０倍＝時間も１０倍になる（#51）。自分のは指数関数的に
比較的にきれいにノード数が増加している。同じようなノード数のものもあるので、
省12

450: 310 2016/05/27(金)00:36 ID:gIFpjm1c(1) AAS
早々に状況が判明しました。ここに書くと進むんだよなぁ。

mtd(f)＋negaScoutで繰り返し探索しながら、置換表に置換データを置いて、更に
それを並び替えに利用していたのですが、最初にPVを探索してしまうと、その後は
別の着手も評価値がαになってしまい、並び替えの意味が無くなっている感じです。
ちなみにPVだけは別ルートで必ず先頭に探索するようにしてあります。

というわけで、テスト的に初段のみ敢えて並び順を逆転させてmtd(f)を未使用にして
ただのnegaScoutで、mpc99%→全探索をしてみたところ、探索ノード数がかなり減り
省5

464(1): 310 2016/08/03(水)14:35 ID:WXOcEHjz(1) AAS
ここしばらく、評価関数に新機軸をと、ディープラーニングにトライ中ですが、
囲碁のように、畳み込みの画像認識の応用では、なかなか上手くいかないと
言うか、自分のパソコンで手におえるくらいの規模のネットワークだと全く歯が
立たない感じです。

というわけで、色々と手はいっぱい動かしているのですが、何にも成果があら
われていない状況です。

466: 310 2016/08/04(木)01:59 ID:XH3ZGPYC(1) AAS
>>465
最初はGitHUBのDeepLearningの参考プログラムを元に自家製でAutoEncoderにDropoutをつけ
たりしてました。

次にCNNで、GitHUBでtiny-cnnというライブラリを落として使用。技術的に凝りすぎライブラリで、
解読するのにC++の勉強が主になってしまいそうなので、改造はあきらめました。

そして、今は、行列ライブラリ（Eigen）落としてきて、自家製に戻りつつあります。Sparse正則化の
ために、ミニバッチ処理をしようかと思って（最初のは逐次処理のみ）、ついでにAVX２命令や
省7

上下前次 1-新書関写板覧索設栞歴

ｽﾚ情報赤ﾚｽ抽出画像ﾚｽ抽出歴の未読ｽﾚ AAｻﾑﾈｲﾙ

ぬこの手ぬこTOP 0.064s