[過去ﾛｸﾞ] 【オセロ,将棋】ボードゲーム【囲碁,War】 (1002ﾚｽ)

【オセロ,将棋】ボードゲーム【囲碁,War】 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/

上下前次1-新
通常表示 512ﾊﾞｲﾄ分割 ﾚｽ栞
抽出解除 ﾚｽ栞

---

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

---

310: 名前は開発中のものです。 [sage] 2015/08/18(火) 16:59:55.72 ID:QcCJSSMl どなたか教えていただけますか？ 最近、オセロAIのプログラミングをCで行っています。 今は、探索ロジックの勉強のため、終盤の完全読みを作っています。 置換表付negaMax、置換表付PVSは通常の探索ではきちんと動作しています。 現在MTD(ｆ）にとりかかりました。MTD(f)では、ドライバは擬似コードそのまま。 テスト関数は置換表付negaMaxを流用していますが、そのままだとFail-LowとminMax値 の区別がつかずに、Fail-Lowの指し手を返してしまうので、初段のみαを-1する事で、 内部的に区別できるようにしています。 動作確認にいくつかテストケースでテストしましたが、FFO#40の時におかしな事がおきます。 （FFO：http://www.radagast.se/othello/ffotest.html） 問題）本来の評価値は+38（A2B1C1…）なのに、+30が返る。 以下、判明している状況です。 １）置換表を使用せずにMTD(ｆ）を動作させる。　−＞正解 ２）単体でNull Window Searchを行う。　　　　　　−＞正解 ３）置換表を使用してMTD(f)を動作させる。　　　−＞少なくともFFO#40では誤答する ４）FFO#40で失敗する条件は、ｆにminMAX値より幾分小さい値（黒+30未満）を設定したとき。 ５）negaMax初段でαを-1するロジックを入れなくても、同じ事になります。 デバッグで確認したところ、Fail-Highになるべき条件（黒+30や黒+36の時）で、下限値を 返しています。同一条件で、下限をさらに-1してテストしたところ、α<g<βである事が確認 できましたので、minMax値として間違った値が返っていることになります。 どうも原因は置換表にあり、Null Window Searchの中で、何回も再利用していることに あるように思います。とはいえ、MTD(f)といえば置換法を再利用する事が前提です。 どこかに誤りがあるのではないかと思います。 同じような問題に遭遇した人はいますか？ http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/310

311: 310 [sage] 2015/08/18(火) 17:06:51.32 ID:QcCJSSMl ちなみに、置換表のキーは、盤面と手番です。 ハッシュ値を使用し、衝突した場合は、チェーンで下につなげています。 今のところ、メモリーの上限等は設定しておらず、領域も足りています。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/311

313: 310 [sage] 2015/08/18(火) 23:21:46.36 ID:5wjtKO2B 何がですか？ http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/313

315: 310 [sage] 2015/08/19(水) 09:33:45.34 ID:DdofkXsp いなければ仕方ないですね。 テスト関数を置換表付negascoutにしたら、ちゃんと答えが返ってくるようになりました。 けど、なんか気持ち悪い。置換表の扱い方は一緒なので、たまたま上手く行ってるだけ ではないかと思います。むむむ。 MTD(f)にこだわり続けてもあんまり意味が無いので、評価関数づくりに入ります。 ３層パーセプトロン型にするか、普通の線形回帰にするか。 パーセプトロンタイプは、パターン学習のタイプを作ってみましたが、学習データ３４０万 棋譜に対して、１回回すのに３日がかりという状態で、検証サイクルが回しづらい状況な ので、簡略化をするか、線形回帰を試すか思案中です。最終的には、両方作って対戦 させてみるかと思っています。いつになる事やら。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/315

316: 310 [sage] 2015/08/24(月) 09:51:00.08 ID:Y8Lk5h3w BITBOARDで確定石をそこそこ正確に求める方法を考えました。 思いっきり脱線中ｗ ただ、斜め方向に「列すべてに石が置かれている」状態を検出する方法と、 その時に、斜め方向の列すべてに確定ビット（仮）を建てる良い方法が見つ からずに、斜め方向のAND用の定数配列を用意してループを１５回回してる。 縦横は、分割統治でそこそこなロジックになったんだけど。 ４５度回転を使っても、そんなに高速化できそうにないなぁ。 もちろん、完璧な確定石ではありません。 拾った石は確実に確定石ですが、確定石なのに拾えない石が若干あります。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/316

317: 310 [sage] 2015/09/02(水) 11:43:34.50 ID:s0BtWfox ぬぬぬ。パターンによる線形回帰の石差予想。 最急降下法は収束してるんだけど平均２乗誤差が４８０とかになる。 １σでいうと１局面あたり２２石（黒石の数では１１石）もの誤差。 これでは使い物にならない。 ステージ分割しているんだけど、ステージが進んでも誤差はほぼ一緒。 ウェイトがオールゼロでも似たような数字になるレベル。 テストデータで局面評価させると、それなりに石差は計算しているっぽいが、 最善手で終局まで打ったデータ入れるとステージによって評価値が全く違う。 初期値をゼロからスタートすると、この辺なんだけど、１とかからスタートすると もっと誤差が大きいところで収束してしまう。初期値を乱数にしたら、更に大きな 誤差で収束してしまう。 ローカルミニマムに捕まってるのかなぁ。 いくつかミスは見つけたけど、本質的な場所じゃないので、結果も変わらず。 むむむむ。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/317

319: 310 [sage] 2015/09/02(水) 21:57:59.44 ID:5gNGVEfH 正規化というと、thellさんのlearning.pdfで言うところの、αの設定ですか？ 当初はmin（β/100,β/Nj）の正規化型で作ってましたが、上手くいかないので 収束を早めるのは後回にして、今は単純にステージ毎の局面データ件数α=β/Nの 形にしてます。 が、発散を避けようとすると、βをあまりに小さくしなければならないのが、なんか変な 気がしています。今は10の-7〜-8乗くらいの値です。やっぱり変ですよね。 最急降下法のコードどこか間違えてるんだろうなぁ。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/319

322: 310 [sage] 2015/09/03(木) 10:19:29.05 ID:Fd8XT4rV 色々と失礼しました。 もう一度、よーく上記pdfを読み返していたところ、原因らしきものが見つかりました。 記載にあいまいというか、ちょっとおかしいところがあって、式の変形をしっかり追って 確認すれば良かったのですが、思い込みで解釈をして変な計算をしていました。 そこをとりあえずざっと修正したところ、遅々としつつも収束に向かっている模様ですが、 まだまだ完全ではないようです。ある程度二乗誤差が減ったところで、また増え始めたり しています。正規化も試したけど、やはり同じ。 もう少し、検討してみます。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/322

323: 310 [sage] 2015/09/03(木) 10:38:17.33 ID:Fd8XT4rV >>320 もともとひっくり返しあった後の終局を予測するのが目的なので、教師データは最終局面 の石差です。盤面の特徴（パターン）から、最終石差を予想するための重回帰計算なので、 その時点の石数は、説明変数に入れてません。なので、パターンの選択が適切なら、 最善手の応酬において１手毎にどれだけ石数が入れ替わろうと、影響を受けずに、 二乗誤差が終局に近づくほど減っていくと予想されます。 というか、そうなるように説明変数であるところのパターンを模索していくと理解しています。 手元にあるwzebraなんかは、評価値と称して最終石差予想が表示されているのですが、 やはり、ある程度の誤差を含みつつも、大きくぶれているようには見えません。 評価関数の使い道を考えると、実は絶対値はそれほど重要ではありません。 中盤探索のｎ手読みの時の盤面評価と、ムーブオーダリングに使うので、ある局面から 派生したｎ手先の局面における相対的な関係が保たれていればOKです。 また、MTD(f)法などを使う時の、ｆの初期値設定にも使います。この時は絶対値で正確な 方が良いはずですが、外れはすぐにカットされて次に行くので、トータルの時間に対する 影響は小さいように感じます。 とはいえ、相対的な関係が保たれているのかをチェックするのは難しいですから、 結局のところ出来上がった評価関数の評価は、教師データとの二乗誤差の小ささに するしかないかなと。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/323

324: 310 [sage] 2015/09/07(月) 01:11:39.28 ID:OHPpdG+6 収束しかかった二乗誤差がまた増え始める原因はまだわかりません。 増え始めるまでは収束方向には向かっているのは確かなのでβの初期設定を いって誤魔化す方向で。最急降下法ってこんなものなのかなぁ。 一通り納得したので、パターンをLogistelloと同一のものにまで拡充してスムージングも 入れてみましたが、新たなバグを仕込んでしまった模様で、一部計算がぐちゃぐちゃorz バグ探しの旅に出ます。 裏で、Solverの速度アップを検討。 CountBitとPOPCountを組み込み関数にしてみました。FFO#40で30%ほど改善。 続いてFlip関数を６４個のポインタ関数にしてみましたが、時間はほぼ変わらず。 ポインタ関数内の処理が非効率なのか。 Flipのデバッグ中に確定石計算でバグっぽいものを見つけましたが、回帰が落ち着く まで見なかった事にします。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/324

327: 310 [sage] 2015/09/14(月) 09:33:29.38 ID:Rx5y2/Cc 線形回帰で相変わらず時間食ってます。 一応、バグらしきものはそれなりに解消されましたが、やはりいかんせん収束が遅い。 一晩かけて５０〜１００試行して、途中で止めてやり直しなんてのやってる間に１週間は あっという間に経ってしまうものです。まだ誤差が大きい。１０００回程度回して、どこまで 収束するか見てみようかなと。またぞろ３層パーセプトロンが気になる今日この頃。 確定石計算もバグ取りはできたと思いますが、その分計算が１．５倍ほどに膨れてしまい ました。しばらく思考実験していたら、確定石なのに確定していると評価できない確実な パターンも思いついてしまって、どうせその程度のものなら重い確定石計算しないで普通 に準確定石程度にしとくのが良いかと悩み中。 Solverの速度アップですが、前からやろうと思っていた事を少しづつやっていますが、 統計とってきちんとやっていないので１０％くらいの差だと良くわからない状況です。 コードのメンテナンス性が下がるのがネック。negaMAXが思いの他高速化してしまい ましたが、MTD(ｆ）が低速化しているかも（謎）。 それなりに評価関数が動きだしたので、置換表２枚にして反復深化も試してますが、 信じられないくらい劇遅状態です。これ本当にコストに見合うのかなぁ。評価関数の 計算が、というか、その中の確定石計算が重いんだと思うけど・・・。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/327

328: 310 [sage] 2015/09/14(月) 17:35:45.53 ID:Rx5y2/Cc 反復深化が劇遅なのは、使い方を誤っていました。 リーフのところまで使うとコストアップなのは考えれば当然でした。 まあ、おバカなバグもありましたが。 negaMaxに対して反復深化を試すと、１割程度の高速化となりましたが、 negaScoutに対してやると多少低速化して、negaMaxの反復深化と変わらない速度に。 scout missが３倍近く増えているので、評価関数の精度があまり良くないためかなと。 move orderには、通常はmobilityとコーナー着手を使用しているのですが、これ、 何故か（少なくともFFO#40に対しては）scout missが恐ろしく少ないのです・・・。 MTD(f)が遅いのも、最初に設定するfを評価関数の値にして、それが結構外れで、 探索範囲が広がったのが原因です。scout missと同様に、結局のところ、途中で評価関数 を求めるタイプの高速化は、評価関数の精度次第という当たり前の結果に。 評価関数入れるとノード探索時間が1/10になるので、やはり評価関数用の確定石計算は 準確定石にレベルダウンしようかと思います。中盤AIでの話ですが。 今FFO#40が９秒台なので、あと３〜５倍高速化したい。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/328

330: 310 [sage] 2015/09/15(火) 20:18:36.71 ID:egtjjW0V 準確定石の計算って実は思ったよりコストフルかもと気づいてしまい、 急きょコーディングして比較してみる事にしました。 releaseモードだと、自分の計算方法では跡形も残らないため、時間計測不可能。 debugモードでも、数十倍速いと言う結果になりましたので、今の確定石計算ロジック は、悪いモノではないと自分に言い聞かせる事にしました。 それより、回帰の学習で、少しずつ少しずつ２５０回くらいまで学習進めていたのですが、 バグを見つけてしまい、またやり直しです。むむむ。しかも、なおした事で計算時間が ２〜３倍になってしまうという。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/330

332: 310 [sage] 2015/09/22(火) 22:15:30.40 ID:70n8Fwqa 回帰は地道に学習中。もう少しやってみるって感じだけど、収束状態の誤差が大きいのは ステージ分割でオリジナルな変な事をしているからじゃないかと気になりだした。 あと数百回学習を回したら、通常のステージ分割版も作ってみるかなと。 色々いじってるうちに、FFO#40が６．２秒まで来た。何が良かったのか良くわからない。 反復深化をターゲットに改良しているんだけど、negaScoutも同じ時間。 FFO#41を試したら、反復深化で４５秒弱、negaScoutで３０秒弱という結果に。 探索ノード数がすごい事になってるので、反復深化のmoveorderのどこかがおかしい 気がしている。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/332

333: 310 [sage] 2015/09/25(金) 16:54:56.15 ID:9OkLc3+M 回帰のステージ分割というかスムージングを、ネット上でノウハウ公開されてるみなさん と同じようにしたら、１σで６を切ってきた。やっぱ、スムージングやり過ぎて、精度が 落ちていたのね。同一ステージ内でも値がばらついているので本当に必要なのか、 気になるので、落ち着いたら両方試そうかと。先に方向性見ちゃったから本来とは 逆順になっちゃうけど。 色々頑張ったら、FFO#40が５．１秒、#41が２０秒、#42が１８秒となりました。 ソースとにらめっこしてれば、ネタはそれなりに出てくるものだなぁと。 しかし、１０年前のCPU使ってるThellにようやく勝てた程度。 Zebraの速さは何なんだと。こちらはcore i7だというのに。 目下の悩みは、_mm_popcnt_u64とBitScanFoward64が使えずに、それぞれ32ビット版を 使っている事。外部依存のところで関数の存在は確認しているんだけど、「そんな名前ない」 と出てくる。Cは趣味のAVRで小さいプログラムしか作った事がなかったけど、VC++くらい 巨大になると、どーもよーわからん。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/333

334: 310 [sage] 2015/10/04(日) 01:12:59.97 ID:+bDErzEp 色々やって、FFO#40でnegaScoutで３．４秒まで来ました。 反復深化は異なる方法で２種類作ってみたけど、FFO#40程度の深さだとnegaScoutとの 差が出てこない。２２手とか２４手とかまで行くと、差が出てくるように感じるけど、後回し。 どうしても気になって、Zebraのソース解説（日本語）を見つけて、そこに出てるソースを 見ました。自分なりにロジック面で工夫した事はほぼ同じ事をやっている。流石。 あとマクロを多用してる。僕はインライン指定でコンパイラ任せ。 マクロにするとデバッグが極端に大変になるので、マクロ化するのは最後。 そしてaspiration windowと称しているWindowの取り方が独特で、ここに高速化の 秘密があるとみた。早速真似してみると、また>>310のような問題が・・・ 今回は前より理解が進んでいたため、２点修正して解消。 副次的に>>310の問題も、直ったと思う。 が、もう一つ答えを間違うケースを見つけてしまった。 今まではルートノードに問題があったけど、こちらはもっと下位ノードで戻り値がコンタミ してる感じ。デバッグが難しく、重症っぽい。むむむ。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/334

335: 310 [sage] 2015/10/07(水) 17:10:37.74 ID:i7/9rua6 デバッグで試しに変えた箇所を戻し忘れたりして、二次災害三次災害を出して、 相当混乱したけど、やっぱり境界問題だった。これmoveorderの順によって出ない 可能性もあるので厄介。自分は開き直って、探索の幅に-1つけてるけど、皆さんは どう回避しているのかなぁ。 zebraのwindowの取り方は、基本的にMTD(f)みたいに置換表利用を前提とした、 固定分割サーチだけど、negaScout（MTD(f)やzebra方式の中で使用している）と 速度的には同等な感じ。最初の探索で勝敗がわかるという点がメリットなのか。 MTD(f)は評価関数が正しくないと、検索時間が伸びる可能性があって、以前から negaScout単体でも十分な気がしてる。 FFO#40は後述の静的評価関数を判明しているパラメータで最適化すると、 negaMaxで５秒台。negaScoutで３．４秒前後。MTD(f)で２．６秒前後。 ThellさんのHP記載よりは高速化したけど、zebraにはまだ勝てないというか、テストした FFO#41〜#43ではzebraの高速度合（ノード数の少なさ）が突出している。 ノード削減はmvorder用の静的評価関数に掛かっている。静的評価関数のパラメーター をいじってるけど、FFO#40最速のパラメータとFFO#43最速のパラメータが違い、#43用は #43ではノード数を半減できるのに、#40では増えて遅くなってしまう。negaMaxで初段の 評価順見てると、まだまだなので、何か別の発想で並び替えが必要な感じ。 評価関数は１０００回くらい回してようやく良い感じになってきたけど、まだ収束しては いない感じ。学習係数はもっと大胆に大きくしても良かったかな。ここまでやると、 スムージング無しを試すのが億劫になってくる。 反復深化は、ソースのメンテが追い付いていないので、一回破棄。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/335

336: 310 [sage] 2015/10/12(月) 23:43:49.17 ID:ZTwsIi7y 色々やってるけど、FFO#40では速度向上はほとんどなし。 置換表のサイズが見えて来たので、１件ごとにmallocしていたのを、配列にして一括で 領域確保するように変更（当初の形）したら、速度のバラツキがだいぶ減ったように思う。 NPSが変動すると、何か悪いことしかたと悩んでしまい、修正して二次災害を起こすので 地味に大事かな。 FFO#43は多少高速化してて、パラメータ最適化するとMTD(f)で１２秒台くらい。置換表 適用範囲の指定を下（葉）からしていたのを、上（ルート）からに変えた。あと、MTD(ｆ） などでは何回も置換表を読むので、２回目からはmoveorderに置換表の評価を使うよう にした。 BITBOARDだと開放度の計算が簡単だという事に気づいて、静的評価関数に使ってみた けど、現在使用中の次手mobility＋αの順序より劣る感じ。＋αが角とか×とかなので、 序盤から中盤用なのかなぁ。 negaScoutに加えた修正をnegaMaxに適用していたら、negaMaxがおかしくなった。 直して計測したらFFO#40が４０秒程度に。冷静に考えると、これが常識的な速度だと思う。 前回の５秒台がどこから出て来たのか、今となってはわからない。前段の＋α箇所も 結構変えていて、negaMaxはmoveorderで露骨にノードが増減するので、奇跡的な順序 が実現できていたのか。それともバグやオペミス勘違いかも。 そろそろ本格的にネタ切れ。この辺が限界かなぁ。 後回しにしていた修正箇所を直して綺麗になったら、中盤に行くかな。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/336

337: 310 [sage] 2015/10/14(水) 23:51:46.51 ID:V3YF/mde negaMaxはmoveorderの修正漏れでバグってて、直したらやはりFFO#40で５．４秒でした。 MTD(ｆ）は２．４秒でzebra並になったけど、#41以後は３〜４倍時間がかかる。 その差は探索ノード数に比例してる。前向き枝刈使うわけにはいかないし、#41以降の 差を詰めるにはmoveorderしかないと思う。 とはいえ主だった事は一通り試してしまった。むむむ。 偶数理論で思いついた方法が純粋に面白そうなので組んでみる。 想定では、速度が結構遅くなるはずなんだけど、まあ面白そうという事で。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/337

338: 310 [sage] 2015/10/16(金) 10:24:07.38 ID:Q2afyb0d 偶数理論の関数は思いのほか軽くできて、オーバーヘッドの心配が少ないです。 BITBOARDの空マスを、囲まれて独立している塊ごとに分離してBITBOARD配列にして 返す関数を作りました。これをPOPCountで数えて着手した場所が偶数空エリアなのか 奇数空エリアなのかを判定します。 最初にテストしたFFO#43のMTD(ｆ）でいきなり３０％近く高速化して「やった！」と思った のもつかの間。実はミスで判定を逆にしてまして、偶数マスに打って奇数を相手に渡すと 加点になってました。で、いろいろテストした結果、最初にやったケースではたまたま 良かっただけみたい。例えばnegaScoutやnegaMaxでテストすると、係数変えたり判定 方法に工夫を加えたりいろいろしてみても、何をやっても探索ノードが増えてしまう。 自分はオセロ弱いので、必勝法みたいに言われているものが、アバウト的に最善手に 近い手を選んでくれるんなら、並び順の優先順位計算に、あるウェイトで入れてみようか 的に考えるだけでした。意味とか深く考えるよりやってみるという感じでした。が、最後に 残った２つの空所が偶数と奇数とかの例ならわかりやすいけど、空所が４〜５か所ある ような状況で偶数理論を当てはめようというのが間違いなのかなぁと。 あと、薄々思っているんだけど、テストケースとしてFFOは良くないんじゃないかと（汗 FFOに最適化してると、もっと出現頻度が高い例題でより高速化できる可能性を放棄 しちゃっている事にならないかと。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/338

339: 310 [sage] 2015/10/17(土) 09:29:41.90 ID:uZH1KzRS 最終２手高速化したあたりから、ノード数が過小になっていたので、それを直しました。 自分のと比較すればよいかと思って放置していましたが、そろそろちゃんと比較しようかなと。 結果、探索ノードが思っていた以上に多かった事、そしてNPSは９〜１１K出てるので、 NPSを落としてノード削減する余地があるという結果に。 あまりテストしていなかったFFO#41と42ではzebra方式と呼んでいた（後述）方法が、自分の 中では最速で、MTD(ｆ）の結果があまり思わしくない事も。MTD(ｆ）の#40は初期条件が良か ったからの模様。 ここらへんでもう一度、zebraサイトのFFOテストページにあるcomplete logなるものを見て みると、全然違う。バージョン違いなのか、やってる事が全く違う。 浅い探索をしてｆを決めてNull window search（正確には幅３なので正解が判別できる） を繰り返しているように見える。けど、ログ上に％が出てきて、９８％、９９％、％無しみたい になっているので、何らかの方法で前向き枝刈しながら、評価値を求めていき、最後まで 幅３の探索しかしていないのかな。こういうのをPVSって言うのかな。 浅い読みとか、前向き枝刈とか絡んでくるんなら、中盤探索をやってから戻ってきた方が よいのかな。。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/339

342: 310 [sage] 2015/10/30(金) 17:31:41.23 ID:uxyAnbEX 棋譜ベースで序盤２０手の定石DB作った。 定石DBは置換表をベースに作ったので、検索は速いけど、容量が大きい・・・。 簡単にαβで２０手探索してみた。 ネットで調べた定石集に載っていない手筋が出てきてしまった。むむむ。 ５手目までエビ系で、しかも石差＋２で黒勝ち。棋譜が偏っているのかな。 棋譜は例の５０万棋譜計画の奴で１０手目、２０手目以降を訂正したというデータ。 明らかに壊れたデータが入っていたりと、何かと使いにくい箇所があるデータだけど、 定石DB作るにはこの量でも足りないのかも。 定石探索用の簡易版minMaxを作りながらつらつら考えていたら、終盤探索の moveorderをもっと良くする方法を思いついた。評価関数の精度次第だけど。 新評価関数は、途中でうっかり仕込んだバグで遅延。ようやく原因が見つかって、３００回 試行まで来た。もうちょい収束させたいけど、テストに使える程度にはなってると思う。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/342

343: 310 [sage] 2015/11/08(日) 00:32:40.41 ID:LMw8+3qF moveorderを早くする方法というのは、事前に軽く探索した手順を保存し、その手順から 優先して探索するというもの。理論的にはscout missがゼロになる。 探索した手順を取り出す仕組みが必要になるので、その辺を改造しようと思ったところで、 悪い癖が出てしまいました。Cベースのソースを一旦棚上げして、C++ベースのクラスを 利用した形で一から作り直してしまいました。 moveorderの配列をvectorに変えたり、unordered_mapを見つけたので置換表に使って みたり。置換表は、システム任せにして動的にメモリ確保に行かすと、探索ノードの減少 以上に速度低下して使えない。最初からある程度メモリ確保させようとしているんだけど、 いまいち設定がわからない。動的にメモリ確保するので、速度のバラツキも大きい。 そもそもC++は初めてなので、目的がオセロからC++というかunordered_mapの習得に なりかかっていたので、一旦棚上げして、配列ベースの自作ハッシュの置換表に戻る 方向にしました。 とはいえ置換表を外してもnode/secが5kくらいしか出ていないので、実装が悪いところもありそう。 というわけで完全に寄り道しちゃってます。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/343

344: 310 [sage] 2015/11/12(木) 16:56:19.10 ID:4hPfHY6k ようやく、C++ベースの終盤探索（negaScout）が、Cベースより若干速くなりました。 ・unordered_mapの速度のバラツキはデバッガー上限定。 実行ファイルでも多少ばらつくけど、メモリ効率＆メンテナンス性からunordered_mapを採用。 ・探索した確定手順を返す方法の検討で苦戦。 negaScout＋置換表では原理的に無理と認識するのに時間を要しただけでしたorz 置換表無しnegaScoutかnegaMax＋置換表では、後者の方が高速。 ・確定手順を元にmoveorderする改造の効果は限定的。 moveorderで先頭にする処理が重い模様。適用範囲を狭めて行くと１〜３手で同等の速度。 ・ハッシュキー生成簡素化で若干速度アップ。 ・その他、細かいスピードアップ。 確定手順の導入で５０％以上速度アップを目論んでいたのですが、無駄な努力でありました。 一応、与える確定手順の数はマクロ定義で可変できるようにしてあります。 評価関数も修正を加えたいので、データ変換部からまた作り直しです。 目標も無しに同じ事２回やるのは面倒だなぁ。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/344

345: 310 [sage] 2015/11/19(木) 14:23:44.03 ID:W/V+CKXD 定石部分もクラス化が終わりました。クラスなんての扱うの初めてなので、もうちょっと 綺麗にできたかなと思う面もありますが、C++習得が目的ではないので。 終盤確定読みは０．０５秒刻みで速度アップ。FFO#40で２．３秒になりました。 今まで、速いプログラムでは３０手目くらいから勝敗判定を始めると言う記述を読んで、 なんて速いんだと思いつつ、何に使うんだろうと思っていましたが、ようやく腑に落ちました。 オセロというゲームは勝敗だけが問題で、勝つんなら２石差で十分。「少なくとも負けない 手」というなら、(-1,0)のNull windowで探索してβカットされた手を選べば良い。評価値は 不定（これより良いという値）でも負けない手であるという点では「確定」手順です。moveorder が正確なら、極端に石差を減らす手も選ばない。これなら現状でも２５手ちょいくらいは行けそう。 ただ、これは勝勢の時の話で、敗勢の時の評価値は「これより悪い」という数字だし、 逆転は相手のミスに期待するしかなく、相手も同等のロジックのAI相手だと必敗となる。 結局定石段階で勝負がつく事になります。 今、定石DBは３０手を前提に組んでいますが、３１手目から勝敗判定ができるんなら、定石 を外れない限り中盤探索が不要になり、定石から外れた時にのみ中盤探索が必要になる。 つまり中盤探索は対PC戦では重要度が低く、定石が切れたら、即、終盤探索が始まる。 そもそも評価関数が良ければ、中盤もあまり深く探索する必要がないわけで。 深く読む意味って、なるべく評価が正確なステージを使いたいからなんだなぁと。 というわけで、次はそろそろ中盤探索です。Multi Prob Cutの英語論文を読まねばならぬ・・・。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/345

346: 310 [sage] 2015/11/21(土) 00:05:47.02 ID:WWzrsUCT 定石DBを使って３０手目まで着手した盤面の予想石差が２で勝ち判定だったので、 試しに３１手目から勝敗判定をしてみました。 (-1,0)のNull windowで７分３０秒ほどで解けました。 （参考）勝ちと引き分けを区別するために(-1,1)で計算すると９分３０秒ほど。 探索ノード数がintではオーバーフローしてしまった・・・。 これから、３３〜４手目（残り２６〜７手）くらいで、１０秒程度で解けると予想されます。 勝勢ならこれで良いのですが、敗勢の時は、初段がβカットされないので１０倍程度 時間がかかる。そうすると、残り２５〜６手目くらいが勝敗読みの限度かなと。 もっと高速化が必要なのか。それとも、何か発想の転換ができるのか。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/346

347: 310 [sage] 2015/11/23(月) 21:01:42.47 ID:24rahmZ0 ProbCutとMultiProbCutのBUROさんの論文あらかた読み終えました。 最初、MPCの方から読んでちんぷんかんぷんだったので、ProbCutを読んで、 戻って来て、ようやく実装のイメージが湧くところまで来ました。 というか、この発想に至る道具立てや考え方は、既に揃ってた感じ。例えば>>323とか。 これ>>345-346の勝敗判定の高速化に使える気がする。相手側の手番では 前向きカットしないようにすれば、相手の反駁手を見逃さないからいけるんかなと。 あまり深い読みで使用するとパラメータ作りでしばらくPCを占有しそうだけど。 カットペアは結構アドホックに決めているのかな。各組合せを総当たりで調べても、 σにそんな差があるとは思えないし、特異的に良い組み合わせがあるとも思えないし、 むしろ読む深さの差が増えるにつれてダラダラとσが大きくなって行くだけじゃないか と思う。毎深さごとにMPCしてもオーバーヘッド負けになるだろうし、再帰的に使う事を 考えたら、２＾ｎ＋αで４，８，１２，１６，２０，２４ってな感じで良いのかな。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/347

348: 310 [sage] 2015/11/25(水) 22:32:57.73 ID:APRE5Y1F 条件を決めて簡単にMPCパラメータの計算プログラムを作って検証してみました。 ３０手目の時点（深さ３０）の時の浅い探索０〜１０手でMPCパラメータを計算してみました。 例の３００万件棋譜の３０手目以後完全読み（らしい）１９０万件ほどのデータからランダム に２００件ほど抽出して使用。 結論）δが１０石、R-2が０．７未満という状態で、とても使えたものではないという事に。 ただ、３５、４０、４５手目時点からのカットを試す価値はあるかも知れない。 一方、３０手目の時点で、深さ１０の探索に対して、浅い探索６までで計算すると、 浅い探索４手でδが２石、R-2が０．９３１、浅い探索６手でσが１．５石、R-2が０．９６２ 程度と、まずまずの結果に。これが、論文通りの使い方。 当たり前だけど、こちらは十分使えそう。ただ、結局深い探索に対して浅い探索の深さを 決めるのに、全パターン試すしか無いという。まあ、BUROさんのマネしちゃえば良いけど。 あと、中盤読みのプログラム、やっつけで、終盤探索の手順作成用の浅い読みプログラム 転用したんだけど、これnegaMaxなのよね。negaScout＋MTD(f)にするなり、もう少し、 素の高速化をしないとパラメータ計算が大変。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/348

350: 310 [sage] 2015/12/02(水) 23:21:25.70 ID:Xp/MZwxE とりあえずMPCの仕組と終盤探索用のパラメータだけ作り、終盤探索と勝敗判定に 適用してみました。 勝敗判定は３１手目から。浅い探索は残り手数の1/3。T=1.5で時間短縮が微妙な感じ。 終盤探索はFFO#40でテストしたところ、T=1.5だと途中で正解着手がカットされている 模様で、T=2.0で正解。T=2.0だと時間変わらずみたいな微妙な結果に。 もう一度、MPCの論文を良く読んでみましたが、どちらかというと評価関数の精度の差 の方が大きい様子で、もともと標準偏差が倍近いので、そこを何とかしなきゃならんと。 論文を良く読むと・・・評価関数に確定石はおろか、mobilityも使っていない。使っている のは、パリティー（手番）だけで、ここは自分の方が精度が良い方法のはず。という事で、 急きょ評価関数の説明変数をパターンだけにして再計算に着手しました。 とはいえ、書いてある学習係数があまりに違いすぎるので、自分がバグってる可能性も。 また、ネットでBUROさんのパワポ資料（２００２年）みたいなのを見つけて読んでみると、 「selective endgame search」と称して、MPCの終盤探索への応用がサラっと書かれて いて、「いまどきの強いオセロプログラムはみんなやってる」との事。iterative deepingを 前提にしているのでmoveorder作成で使ってるのかなぁ。正解着手だけ与えても速度アップ は限界があり、正解以外着手のnull window searchの時間がバカにならないので。 あと、中盤探索は（１７，５）というカットペアの記載あり。zebraのFFOのログでは中盤探索が 2.5ｋNPSなのに対して、僕のは250MPSと、速度が1/10なので・・・深さ１７はしんどいかなと。 ちょっと期待しているのは、前述のとおり確定石計算を評価関数で使用しなくなったので その分は速度アップしていないかなぁと。 評価関数の再計算を始めてしまったので、しばらくは中盤探索が動かせません。 というか、本当にLRの計算があっているのか、バグは無いのか、不安になる… http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/350

352: 310 [sage] 2015/12/04(金) 23:35:12.62 ID:DNSRUk3b 結局、確定石が評価関数の誤差の大きさと、収束性の悪さの原因だったみたいです。 前半から中盤はmobilityのウェイトが大きそうなので、とりあえず復活させてみました。 あと、スムージングは、あるステージで出現しなかったパターンが隣接ステージにある 可能性も考慮し、ウェイトがゼロのパターンを減らす目的もあるようです。 実際、２００試行ちょっとでかなり誤差が減ったのですが、FFO#40で試すと途中の評価値 のバラツキというか、極端に０に近い局面が現れて、２σ以上の差異が簡単に出てしまい ます。そこで、ちょっとだけスムージングを入れて、かつデバッグ段階ではウェイトゼロの 出現をアラームできるように改造しようかと思っています。 評価関数の重要性を痛感しています。しばらくは、ここで悩む事になるのかなぁ。 最低でも３００試行するとなると３日かかる。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/352

353: 310 [sage] 2015/12/05(土) 23:27:03.86 ID:VLRyPTJJ モビリティーも収束悪化の原因でした。 確定石の数にしても、モビリティにしても、ある程度大きな数字が出るものがダメっぽいです。 評価パターンとウェイトを確認できるようにして、FFO#40〜41の完全読みに登場する盤面を チェックしましたが、ウェイトゼロのパターンは出現していないようです。 評価値が大きくぶれるところがありますので、スムージングを入れてみて計算開始です。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/353

354: 310 [sage] 2015/12/07(月) 10:00:41.29 ID:JSVZKjkd スムージングも外してみたら、Buroさんの論文なみ（か、それ以下）のσが出そうな 感じになってきました。収束が良いのでβも大きくできたし、その後の計算でも工夫を 入れたので、Buroさん論文みたいに３００回試行で十分なレベルになりそうです。 ウェイトゼロのパターンはありました。FFO#40の５０手目のCORN２ｘ５に１つ現れます。 現在selective endgame searchがどんなものなのか、想像を膨らませています。 iterative widening endcutのイメージがなんとなくつかめてきました。 ソースを探して見ちゃえば早いんだろうけど、面倒だし、想像だけで頑張る。 MPCが動いたら、solver改造して、本当に速くなるのか確認する。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/354

355: 310 [sage] 2015/12/10(木) 23:16:49.62 ID:lQAJMVKx 結局、評価関数は１０００回試行までやってます。 β・1/Nでやってるけど、それだと収束が遅いので、１００回試行ごとにβを倍々に。 １０００試行目で発散するステージが出たので、βを下げて最後の１００試行を実行中。 その間、反復深化などで使えるように、置換表を改造。前回評価範囲をmoveorderで 再利用します。いちいち消しているとメモリ解放で時間がかかるし、全データを入れたまま 用途をキーで区別すると、使用時に選択する事になりオーバーヘッドが気になるので、 一番新しい評価値をひたすら上書きし、置換表として使用する時のみ、今回探索か 区別するようにしました。moveorderで若干割り切った作りです。 同時に中盤探索（MPCなし、反復深化）をちゃんと作ってみました。MPC計算で、結構深い 深さまで探索する予定なので、反復深化が上手く機能するようなMPC計算ロジックを考え ようと思っています。 それができたらiterative wideningのテストをしてみようと思います。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/355

356: 310 [sage] 2015/12/11(金) 22:32:36.55 ID:c1YdnEjo あちゃ。ウィンドウ幅１でiterative wideningやると、正解着手もβカットされた手も 置換表の値が全部同じになって、次の探索でmoveorderが意味なしになって、 速度が大幅低下する事が発覚。 仕組み考えないと・・・。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/356

357: 310 [sage] 2015/12/13(日) 23:14:55.34 ID:RUGsIY6w 一応回避したけど、MPCの速度向上は限定的。 中盤探索というか評価関数が驚くほど遅いのだろうという結論に。 放置していた中盤探索の素の高速化に入ります。 １か所ネタはあるんだけど。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/357

359: 310 [sage] 2015/12/20(日) 17:21:06.88 ID:UpZkem/K 中盤探索で改良をしたらかえって遅くなるを繰り返してます。 で、やけくそ気味にmoveorderの「置換表がない時」の計算値を、簡素化してみたら 中盤探索の速度そのままに、終盤探索部分の探索ノードが減少して高速化。 終盤探索部分も同様に簡素化したら、FFO#40で1.75秒以下になりました。 それでも相変わらず#41/42はzebraがずーっと早い。 で、MPC使うと遅くなる理由を考えていたら、いま使っているMPCのセットは終盤探索用に、 残り手数と浅い読みのセットを独自パターンにして計算した奴だと言う事を思い出した。 深い探索のスコア＝終局のスコアとなり、深い探索が不要になるので。 中盤の高速化するネタももう出てきそうにないし、先に進むか・・・ http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/359

361: 310 [sage] 2015/12/23(水) 16:26:13.00 ID:MLtsaD3t どもです。 Ｂｕｒｏさんのパワポっぽい資料に名前しか書いてないので中身がわかりません。 わかっているのはＭＰＣと併用するらしいことくらいです。 iterative wideningで検索すると確かに碁の関連の英語論文がヒットしますね。 関係なさそうだと思って放置していましたが、ちょっと見てみようかなぁ。 置換表云々は、僕の想像です。 αβを前提にしたアルゴリズムで高速化するネタの一つに、moveorderを工夫して βカットが起きやすくするってのがあると思います。 反復試行する際、置換表には前回の評価の範囲が入っています。 それを今回探索のmoveorderの並べ替えに利用しようというものです。 反復深化なんかと同じ考え方です。 逆に言うと、反復を前提としたアルゴリズムで高速化するネタが、それくらいしか 思い浮かばないのです。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/361

363: 310 [sage] 2015/12/23(水) 22:38:37.71 ID:MLtsaD3t >>362 ご助言ありがとうございます。 MPCはまだ途中ですが、そんな感じです。 終盤ｎ手高速化の類もしています。中盤探索だと葉に近いところで置換表外すと、 著しく速度が低下するので、最後まで置換表を使っています。 で、中盤の速度がいまいちで１２手読みくらいが実用範囲って感じです。 MPCでｄ計算に１００棋譜くらい試して一晩で計算できる範囲は１３〜１４手くらいが 限界な感じです。そろそろMPC計算しちゃおうかと思いつつ、まだ悶々と中盤探索で どこか高速化できないかトライ中です。 SIMD命令はコンパイルオプションでそれらしい場所があったので、設定してみましたが、 速度変わらずで放置しています。どうやって使うものなのでしょうか？ そもそも、組込関数のpopcountとかbitscanで64ビット版が使えずに放置してる状況です。 並列化はMPCが終わって、一通りオセロの形にしてから、次ステップで勉強しようかと 思っています。 アスピレーションサーチは、１σは±７〜８手なので試しに±８の幅にしてテストしてみた ところ、確かに若干高速化できている様子です。mtd(f)は下から寄っていく時はβカットが 効くのですが上から寄っていく時は遅いので、一発目で探索できる確率を上げつつ、 ある程度幅を絞るには、このくらいがちょうど良い感じですね。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/363

364: 310 [sage] 2015/12/24(木) 20:33:24.09 ID:zDiJT168 ちと調べてみました。SIMD命令はx64でコンパイルしている時は、設定しなくても自動的に 使うようになっているみたいな説明を見つけました。 並列化とかベクター化とかもコンパイラが自動でやってくれるみたいですが、レポート出し たら確かに一つも対象になっていませんでした。評価値算出とmobilityの２関数は、なんか 効きそうな気がしますので、少し悶々とトライしてみます。 また、_mm_popcnt_u64と_BitscanFoward64は、今やってみたら、何故か使えました。 色々とコンパイラのオプションをいじったのが原因かなぁ。謎。 多少速度アップした模様です。 アスピレーションウィンドウはｄの計算しなきゃと思っていましたが、よくよく考えたら、 評価関数の計算時の誤差ログが残っていますので、そいつでパラメータ作成してみます。 と、久々にFFO#43まで時間計測したところ、#43で答えが違ってる。 数か月前に最終２手高速化をいじった時にバグを仕込んだ模様です。 調べようとdebugモードにしたら64ビット組込関数が使えない。 やっぱりコンパイルオプションのどこかみたいですが、わからない。 だんだん問題が発散してきて、頭の切り替えが追い付かなくなってますorz http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/364

366: 310 [sage] 2015/12/24(木) 22:56:29.36 ID:zDiJT168 _mm_popcnt_u32()はすでに使っていました。u64が使えなかっただけです。 u32→u64で３〜５％くらいの高速化になっています。 困った事に、debugビルドの側では、まだ64bit版が使えていません。 debugを使いたい時は32bitに直さないといけない。 コンパイルオプションをいろいろ見比べていますが、どこなのかいまだにわかりません。 #43は最終２手なのか１手なのか、どちらにバグがあるのか切り分けようとして ソースいじっているうちに直ってしまいました（汗）。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/366

368: 310 [sage] 2015/12/26(土) 11:23:54.66 ID:2a5cp76f どもです。バグったところはMPC使って無い箇所でした。 コンパイラの自動ループ展開は上記２か所で試してますが、なかなかうまく行きません。 なんとか依存関係を解消してループ展開強制すると劇的に速度低下する状態です。 その代り、いろいろググっていたら、BMI命令を見つけて、BLSIとPEXTを使ってみました。 速度バランスが変わったのでパラメータで置換表適用範囲を狭めるなどもしましたが、 FFO#40で1.55秒前後まで高速化できました。中盤探索も高速化はしているはずですが、 数％程度の改善というところでしょうか。まだ５０％は高速化したい状態です。 色々アドバイスいただいたお蔭で、ようやくSIMDまわりの使い方がわかってきました。 ここまで来ると、BITBOARD操作の関数の見直しをしたくなりますね。 中盤探索の一番重い部分なので。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/368

369: 310 [sage] 2015/12/28(月) 10:45:49.88 ID:i0yT273K デバッグモードでu64系の関数が使えない件、解消しました。 MTD(ｆ）に代えてアスピレーションウィンドウを採用しました。 中盤探索は、隣の評価値をたどっていくと、かえって遅くなるのでnegaScoutだけで 探索していましたが、これでMPC計算が多少高速化できそうです。 MPC計算はまだしていません。反復深化でどのくらいの深さの探索で、どのくらいの 件数なら実用的に計算できるか試行しています。１４手読みまでは行けそうですが、 １５手だと厳しいかなぁという状態。２０手付近では盤面によっては、探索ノードが爆発的 に増えて、時間のバラツキも大きいです。 また、FFO#40-44の完全読みを計測しました。zebra比で#40は圧勝、#41-42は引き分け ですが、#43-44は完敗。理由は#43-44は正解となる初手が２つあるためで、#43は１０秒 以上かかってます。むむむ。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/369

371: 310 [sage] 2015/12/29(火) 02:31:09.04 ID:F/Ba7yoX ちょっと一括変換操作を誤って大変な事になっていました。一通り直していたところ、 FFO#40で1.45秒程度が出るようになってしまいました。多分、修復がてら置換表登録・ 検索関数の変数の並びを、整列したのが効いたのだと思っていますが、びっくりポンです。 前回課題の正解着手が複数あるケースですが、MTD(ｆ）のような評価値決め打ち系の 探索では、ぴったりの答えが見つかった時点で、ほかの手を探索する必要が無い事に 気づき、直してみたところ、FFO#44は速度アップしました。が、#43はまだ駄目です。 とはいえ、#43は浅い探索の評価値が外れすぎて時間がかかっているような感じなので、 浅い探索の深さを残り手数で調整すると直りそうな気がしています。 あと、FFOテストの全データをテストできるように登録しましたが、#59を見て、はたと、 途中全滅時のスコア計算が違う事に気づきました。自分のは一番単純なアメリカルール です。ここを直すと、確実に時間が遅くなるような気がしますが、明日直してみます。 てな事をやって、一晩に０．１秒（比率にして７％前後）も短縮していると、まだなんか やる事があるんじゃないかと・・・。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/371

373: 310 [sage] 2015/12/29(火) 10:25:40.74 ID:F/Ba7yoX って、βカットしない事を確認しなきゃきゃいけないから、ぴったりの答えがあっても 全手を探索しないとダメじゃん。すんません。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/373

374: 310 [sage] 2015/12/29(火) 10:52:28.77 ID:F/Ba7yoX >>372 やったりやらなかったりで、いろいろ比較して試してます。 MTD(ｆ）では、ワーストケースではウィンドウ中心が評価値の最少単位で動く関係で、 １石以下の少数計算をする中盤探索では、よけいに時間がかかる事が多いです。 そのため、アスピレーションウィンドウ導入前はただのnegaScoutにしてました。 終盤探索は、最少単位が１石になりますので、許容範囲です。 MTD(ｆ）もアスピレーションウィンドウも、所詮本チャンのnegaScoutを呼び出すための ドライバーにすぎないので、どちらも用意して、何かの折に速度比較しています。 今回は、ボツりましたが、ぴったりの値が見つかったら後の探索を省略する際には、 MTD(ｆ）の方がマッチングが良かったので、そうしました。 ボツになりましたので、またアスピレーションウィンドウに戻りましたが。 #40ではzebraよりはるかに高速化できましたが、#43など遅いケースでは、数倍の時間が かかります。こういうタイプの時間差は、単純な高速化じゃなくて、何らかのアルゴリズム の違いがあるのかなと想像しています。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/374

375: 310 [sage] 2015/12/30(水) 00:01:33.75 ID:lfikhn/D 結局、本日は探索速度アップばかりやってました。 中盤探索というか評価関数の計算でBMI2命令を徹底的に使ってみました。 また、ボードの回転操作系も見直しました。 １０％程度は高速化できたと思います。でも、期待したほどではなかった。 あと、速度アップするなら、ボードの対角線転置かなぁ。あと効果は微妙だけど、１８０度 回転がビットオーダーの逆転なので、これも何か組み込み関数があったらうれしいなと。 終盤探索では、FFO#59問題に対処。 スコア計算の修正と、全滅など６４石の差がついた時に、βカットと同様に後続の探索を パスして時短。minMaxで言うところのα値の更新があり得なくなるからです。 浅い探索が１１手だと３秒程度で解けるのに、１５手だと６０秒かかったりと、いまいち動き に納得がいかないので、まだ何か問題があるかも知れません。 中盤探索をあと５０％は高速化したいなぁ。というか、zebra見てるとできるはず。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/375

376: 310 [sage] 2015/12/31(木) 21:04:10.05 ID:i5TR43+g 2015年の年の瀬は、MPC計算のメモリーリークの原因探しで更けていく・・・ 置換表クラスあたりっぽいんだけど、デバッグの仕方が良くわからないという・・・ http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/376

377: 310 [sage] 2015/12/31(木) 23:46:42.84 ID:i5TR43+g ギリギリ１２時前に直った。 メモリリークではなく、不正なアクセスでした。 多分直ったと思う・・・ 来年の抱負は、MPCの計算をする事と、GUIを作る事です。 元々VBのGUIからDLLで呼び出すつもりでしたが、なんとなくC++でやってみようか という気になってきています。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/377

378: 310 [sage] 2016/01/03(日) 11:08:48.54 ID:3YPfF+nL バグは解消してました。なんとも不可思議な事になっていました。 スタック領域を破壊していて、破壊された箇所がたまたまdepth（残り探索深さ）だったため、 探索深さがマチマチになってました。計算時間やメモリ使用量が異常になる以外は、そこそこ それっぽい探索結果が出ていたため、メモリリークだと思ってしまったという。 中盤探索の置換表適用範囲も、ちゃんと効くようになって深さ１１〜１２まで置換表を使用 するのが効果的と出て、探索値のバラツキもそこそこ揃って、探索時間も予想できる範囲に。 メモリ使用量も安定しました。 ある棋譜に対し、２０手目から終局まで順に、深さ１〜１７の探索を、反復深化を活用しながら 探索値を求めるプログラムを用意して、１４棋譜を対象に実行したところ凡そ７時間で完了。 速度的にはこんなものかなぁという感じ。もっとも、深さ１７だと結構、探索時間・ノード数の バラツキが大きいので、１０件前後だと終了時刻もバラツクはず。 とりあえず、棋譜からランダムに１０件程度を抽出し、この探索結果を貯めていくところまで 作りました。トータル１００件程度集めれば、MPCパラメータ計算には十分だと思う。 探索結果を貯めてあるので、毎晩１０件くらいづつ追加し、直説法で都度パラメータ再計算 して精度を上げていく事ができる。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/378

379: 310 [sage] 2016/01/04(月) 22:22:10.63 ID:1p46+Vgy MPCのための探索データ蓄積の間に、並列処理について調べてみました。 VC++だとopenMPとPPLってのが使えるみたいです。 ?concurrent_unordered_mapが便利そうなので、PPLにしよううかなと。 で、脳内コーディングであれこれ考えていたら、AIの中でBoardクラスを参照渡しして、 差分型で盤面を進めたり戻したりしているのが、とても並列処理と相性が悪い事に 思い至りまして・・・。コピー型に戻して、何をクラス化するのかとか見直してみようかと 言う事に。 多分数日がかりになるかなと。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/379

383: 310 [sage] 2016/01/09(土) 02:12:28.10 ID:GhyCVx1P どもです。 とりあえず、コピー方式に変えてましたが、変にバグを仕込んだりして、時間がかかって ました。ようやくデバッグもあらかた終わったのですが、まだ原因不明・解釈不能な速度 差があって、終盤探索のみ速度が１０％以上低下した状態です。 というか、コピー版を書きながら気づいた箇所を、ボードクラス版にも反映すると、ボード クラス版が高速化して、差が広がるという。 で、クラス版がFFO#40で１．４０〜１．４２秒になりました。 >>380さん おっしゃる通りですorz プログラム直しながら、ネットでVC++の解説をつまみ読みしながらのコーディングに 限界を感じたので、オライリーさんの出番という事で、アマゾンに本を数冊注文しました。 到着待ちの間にやるなら、適当に作っていったクラスの整理統合かなぁ。 あと、openMPのお勉強。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/383

385: 310 [sage] 2016/01/10(日) 01:14:26.88 ID:F6Uvkb4b うわ。色々やり方あるのね。 VC++だとPPL、openMP、std::threadか。 PPLについては、逐次処理のまま置換表で使っているunordered_mapをconcurrent版に 変えてみたところ、置換表付探索の速度がおおよそ半分になってしまったので、結構 微妙な印象を持っています。 とりあえずopenMPでどこまでできるか試してみて、気に入らなかったらstd::threadで 細かく制御できないか考えてみます。 先ほど、コピー版で置換表登録に影響するバグ発見。直したところ、FFO#40が1.26秒 とかになってしまいました（汗）。不可思議な速度差の原因はこれで間違いないと思います。 edaxまであと１０倍の速度アップかぁ。並列化で３倍くらいまで詰められないかと期待。 一応、Boardクラスのポインタ渡し版（差分方式）も試してみましたが、今のところ、若干 速度低下しています。もともとの差分方式は、Boardクラスを継承したAIクラスのメンバ 関数として実装してます。 これらの一見無駄な作業も、バグ探し＆逐次探索の速度アップに有効だったという事でorz http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/385

386: 310 [sage] 2016/01/11(月) 20:31:40.39 ID:IrhGHm3u とりあえずopenMPで並列化トライしてみましたが、コンパイル中に内部エラーになる。 ネットで見ると最適化オプションがらみらしいけど、なんかよくわからなかったのでパス。 PPLを使って、とりあえず並列化のテスト。オセロでは標準的と思われるｎ段YWBCに してみました。forループみたいな特定の形ではPPLは結構簡単という印象。 バグは一通りとれた状態だと思いますが、FFO#40で１．２５秒が０．８５秒程度になり ３０％強の高速化。あと少しだけソース修正するつもり。 使ってるパソコンは２コアでした。昨夜まで４コアのつもりでいましたが（汗）、２コアなら こんなものなのかな。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/386

388: 310 [sage] 2016/01/13(水) 13:02:44.01 ID:Yd1pcfW8 どもです。 コア数２だと、理屈の上では２倍近くまでは速度アップできるのかなぁと思います。 一般的にはどのくらいの倍率をターゲットにしているのでしょうか。 YBWCの適用のパターンをいくつか試しましたが、タスクマネージャーで見たCPU使用率 は、ほぼ１００％になってるので、単純にはスピードアップは難しい感じがしてます。 PPL自身のオーバーヘッドなのか。 PPLは楽ちんだけど、チューニング箇所がなさすぎな感じ。 あと、YBWCやってる以上、YBの着手をmove orderingする意味が無い感じなので、 sortが一つ省けるかなぁというところ。ルートに近いので、あまり効果は無いと思うけど。 ここまで来ると、８コアのパソコン持ってきたら・・・ SIMD拡張命令だBMI命令だを使っておきながら、コア数２で頑張るのもどうかみたいな。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/388

389: 310 [sage] 2016/01/16(土) 09:10:45.76 ID:mjTPCiWE PPLはMicrosoftのDeveloper Networkくらいしか情報が無いので、ひたすらリンクを たどって情報収集してますが、ほとんど機械翻訳で、結局カーソルあてて英文読ま ないと意味が分からないという・・・ で、排他制御とかいい加減にしていたノード数カウントなどをきちんとして、ソースの見易さ と効率を上げようと色々と細かく修正。combinableとかcritical_sectionとかInterlockedとか。 と・・・思ったら・・・中盤探索で確率１０％程度で違う答えが返ってくる・・・ 並列探査のバグはわかりにくくて時間を食ったのですが、どうもcombinableの動作が変。 期待した動作をしていない。でも、情報が無さすぎで、どこを直せば良いのかわからず、 結局同等の機能を動的配列にしてしまった。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/389

390: 310 [sage] 2016/01/16(土) 11:37:48.70 ID:mjTPCiWE 中盤探索を１万回程度回して、違った答えが返ってこない事を確認できました。 ノード数カウントはInterlockedIncrementを使っているんだけど、やはり排他待ちロスが 大きいようで、ノードカウントありだと０．８秒前後、無しだと０．７秒前後になる。 使えなかったcombinableみたいな形にして、一つの再帰関数内はローカル変数で加算 して、最後にまとめて１か所で排他加算するようにしてみようかな。 並列タスクの起動順で、探索ノード数が違ってくる関係で、実行時間のバラつきが±０．５ 秒くらいになっている。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/390

391: 310 [sage] 2016/01/18(月) 09:54:27.64 ID:ED4vwFCp 結局、ノード数・リーフ数カウントは、戻り値を構造体にして返す方向にて検討。 普段の探索には不要だけど、solverだと表示したいので。 これで完全にローカル変数になり、排他ロスを気にする必要がなくなる。 デバッグ用の置換表回りの統計は、所詮デバッグ用なので、一旦全削除。 必要になったら、こちらは#ifdefで囲って、排他加算する。 で、構造体の形であれこれ悩んでいたら、戻り値をクラスにできる事に気が付いて・・・ あらためてC++すげーと感心中。 けど、かなり全面的な修正になるので、時間食ってます。 まずは中盤探索を修正して、ノード数がおかしくない事を確認。 終盤探索の修正はこれから。探索を使う系の統計処理も変更しなきゃならないけど、 MPC以外は、次いつ使うかわからないｗ http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/391

392: 310 [sage] 2016/01/19(火) 00:13:53.27 ID:Dh1WPUXC 終盤探索の修正完了。 ０．８秒±０．０５秒と、結局、Interlockedでグローバル変数のノード数を加算するのと、 大して時間が変わらないか、もしかしたら微妙に遅くなったかも。元に戻すのが面倒 なので、他で改良点を探すしかないかなと。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/392

393: 310 [sage] 2016/01/21(木) 10:04:20.88 ID:c00KCFqr YBWCでは、最適着手手順（PV）のラインで置換表でmoveorderする意味が無いという事 を突き詰めていくと、いちいち前回探索の置換表を引くループを回して、都度最善の着手 を求めるのではなく、前回探索で得たPVを渡せば、時間が短縮できそうな気がしてきま した。ツリーの浅い部分なので、全体にどれくらい効くのかはわかりませんが。 また、浅い探索などで最適着手手順を取得する時、negaScout＋置換表だと正しいscoutmiss が発生した時に、nullサーチ時の置換表が適用されて、それ以後のPVが得られないという 事で、悩むところではあります。 まずは戻り値の構造体でPVを返すように改造して、効果を見たうえで、YBWCを適用する 深さでnegaScoutをやめてnegaMaxにするか、それともnullサーチは置換表適用外とするか どれが良いか試してみようかなと思っています。 できるだけ高い位置で並列化した方が良いという指摘と、置換表もなるべく高い位置で 効かせた方が良いという指摘の、どちらを優先するのかですね。置換表はばっさり探索 をカットできるけど、並列化はカットせずに時短するので、置換表優先かなという気もして いますが、高い位置でどれくらい置換表が効いているのかもわからないですし・・・。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/393

394: 310 [sage] 2016/01/23(土) 01:31:00.95 ID:0OQfWIYl パソコン再起動すると、何かのタスクがCPUを３０％くらい占有してしまいます。 昨日まで快調に動いていたのが突然遅くなって、悩んでいましたが、これが原因のようです。 というわけで、本日は色々改変したソースの速度が計測できずに悶々としてました。 色々すったもんだ挙句、PVラインを渡す形にしましたが、効果があったかどうかは微妙。 色々付け足した事で生じた速度低下はペイしたかなぁという感じで、#40で0.78秒前後。 本格的にネタが尽きて来たので、ここから先は、MPCをきちんと実装してiterative widening にかけるしかないかなぁという感じです。あと、定数で渡している置換表適用高さなどの パラメータを、空マスや使用条件で作ると、実用的になるかな。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/394

395: 310 [sage] 2016/01/27(水) 01:18:29.98 ID:IVwAw5rN オライリーの並列化本が来たので拾い読みしながら並列プログラミングの勉強。 PPLの各アルゴリズムが何を目的とするものなのかが、少しずつ分かってきました。 抽象化度が高いので、最初のとっかかりとしては良いかも。何故かcombinableが 上手く動かないとか、parallel_reduceの中身がよく分からないとかありますが。 で、並列化できるところを探して速度が上がるか試したり、同じ処理をより綺麗に書き 換えしたりして、微妙に速度アップし、0.70〜0.75秒くらい、ノード数が15M、NPSが21M nps程度になりました。たまに0.68秒台が出ます。 Edax4.3のFFOベンチの結果を確認したところ、ノード数で１．５倍、NPSで４倍、計６倍の 差があります。NPSをコア・クロック換算しても１．５〜２倍の差があり、ノード数は別として、 まだ速度アップの余地があるのではないかという事で、単品速度アップに走ってます。 ノード数はMPC導入後のiterative wideningである程度追い付けるかなと淡い期待。 いくつか速度アップネタがありますが、サッカー日本代表見ながらでははかどらず。 続きは明日。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/395

396: 310 [sage] 2016/01/29(金) 11:31:08.14 ID:trvaxUQ+ 先日の速度アップネタはすべて不発でしたが、その際にノード数のカウント漏れを見つけ て、修正したところ、ノード数は１７〜８Mという感じでした。その際に、最終２手高速化の 箇所でもカウント漏れがあり、まずは正確なノード数を簡便に把握しようと外してみたところ、 意に反して速度低下しないところか、どうも微妙に高速化したように見えまして（汗。 最終３手高速化を試してみたり、最終１手高速化も外してみたり、moveorder適用とか、 そもそもmobilityを求めずに空マスを順に着手してみるとか、その辺の適用深さを変えて みたりいろいろとやって現時点の最適パラメータにしてみたところ、0.63〜0.68秒、最速で 0.60秒が出るようになりました。 αβカットの効きが悪くなっているため、ノード数は２４〜２５Mとなりました。 その分NPSは３７〜３８Mと速くなっていますが、こんな方向で高速化してて良いのか？ というわけで、ノード数が違う段階でNPSを比較しても意味が無いという事に気が付きました。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/396

397: 310 [sage] 2016/01/30(土) 20:51:37.62 ID:yCKBToEa 囲碁がすごい事になってますね。オセロで一通り勉強したら小さい盤の囲碁をやって みようと思っていたので、モチベーション低下中。とはいえ、ああいうのをオセロに応用 しようとしたら、あそこまでマシンパワーいらないんじゃないかとか・・・。 ここのところ、もっぱらSTLやPPLの機能を綺麗に使う方向での改良ばかりしてました。 pararell_reduceの使い方もわかりました。negaScoutの繰り返しループが綺麗に並列化 できたんじゃないかと。ただ、MAPする件数がしれているので、parallel_reduceではなく 逐次版のaccumlateの方が速いという結果に。あと、時間計測が結構飛び飛びの値に なるので時間計測関数を精度１msのものに変更。 色々やった結果、若干高速化したうえで、時間のバラつきが消えてくれました。 １００回試行で計測すると610ms±15ms（１σ）となり、逐次処理のほぼ２倍の速度に。 ノード数は同程度で、NPSは40M超えて来ました。このNPSのままノードを半減できれば 良いのに。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/397

398: 310 [sage] 2016/02/07(日) 21:48:19.14 ID:xNqeS9Ve ここら辺で、EDAXとかとの速度差の原因を考えたところ、次の２点が考えられました。 １．評価関数の精度が悪い可能性 ２．個々の関数で速度アップの余地がある可能性 という事で、１は熟考が必要なので後回しで、速度アップの対象として、flipとmobilityの 高速化を検討。とはいえ、良い知恵があるわけでもないので、ネット徘徊。 現在、ポインタ関数で分岐して処理しているflip関数を１発で処理するopenCLのソースを 発見。Master Othelloの作者のものでEDAX4.3のflip関数を参考にしているらしい。 中身を解読するとベクターを使っている。とりあえず処理を真似て逐次処理で組んでみたら 結構速度アップしました。 解読の過程で、ようやくベクタ化の意味がわかったので、mm256系の命令を使って、 ベクタ化してみましたが、若干速度低下。原因は恐らくlzcntで一回ベクタを抜けてしまう 所だと思うので、ハッカーのたしなみを読んでベクタ演算で組み直してみる予定。 合わせてmobility関数もベクタ化。若干速度アップしたかなという程度。 組み込み関数は使い方が面倒臭いので、演算子のオーバーロードしまくってみました。 flip関数は非ベクタの分岐無しバージョン、mobilityはベクタという状態で、500msを切る 数字が出るところまで来ました。flipのベクタ化ができて、パラメータ調整するともうちょい 良い数字が出るかなと期待。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/398

399: 310 [sage] 2016/02/09(火) 01:09:41.58 ID:MeGl+gwc flip関数続き ・lzcntを自前で組んでみましたが、やはり処理が重く速度低下。ボツ。 ・右方向と左方向で処理が違うので、片側＋１８０度回転で、同じ処理にしてlzcnt不使用 にしてみたが、１８０度回転×４が重くて速度低下。ボツ。 ・できるところまでベクタ化して、lzcnt以後はスカラ計算で、速度若干改善。 ・上記からlzcnt後、再度ベクタ化してみたら、速度若干低下したのでボツ。 ・64bit×４の値を代入する関数を変更したら、意に反して結構速度改善。 ・闇雲に__declspec(align(32)) してみたら若干速度改善してバラツキ減少。 これらにより、450msくらいになりました。 ベクタ化はまだ何かありそう。 ちゃんと書いてなかったですが、途中からノート数カウントを外してます。入れると100ms 程度の速度低下になります。一応、デバッグ用に#ifで切り替えられるようになってます。 が、そんな状態なので、nps計算に意味が見いだせないという・・・。 続いて評価関数をベクタ化できないか考えましたが、BMI命令使っているので厳しい。 計算楽にするため、でかい配列を何回も引いているので、ここを何とかしたい気がする。 黒・白・空の３を基数とする３進数でナンバリングしているんだけど、高速で計算する方法 が見つからず。 平衡３進法を手早く計算する方法があると、黒を1、白を-1、空を0にして、定数足すとか できるんだけど、どんなに調べても、基数変換に王道なしという言葉しか見つからない。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/399

401: 310 [sage] 2016/02/20(土) 13:43:08.30 ID:ZGi2V8ih GUIできた。昔作った序盤定石部分と合体。 中盤探索を反復深化にして、３秒を超えて新しい深さに入らないあたりで調整。 MPCで２５手くらいまで読めるように調整。 終盤完全読みは３８手から。３６手からMPC付で完全読み（つまり完全ではない）。 こんな感じでできたので、早速プレイ。自分だと軽く全滅負けしてしまうので、zebra先生 にお越しいただきました。が、滅茶苦茶弱い。 良く見ると、定石が効いている段階で＋１６だったのが、中盤読みになった瞬間に一気に −１４くらいまで落ちて、そのまま挽回できない感じ。zebra先生は、その前に定石から外れ て、既にzebraから見て＋１４程度の評価値を算出している。つまり、定石部分がおかしい。 それ以外は、評価値もzebraとは大きく違わないし、終盤探索もちゃんと機能している感じ。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/401

402: 310 [sage] 2016/02/20(土) 23:06:47.33 ID:ZGi2V8ih zebra先生にならって定石の評価を表示するオプションをつけてみました。 ロジック的には間違いなさそうですが、定石DBがおかしいというか、定石に登録がない 手順に正しい変化があって、それを無視しているため、間違った判断をしているみたい。 一応、完全読みという触れ込みの棋譜を元にしているはずなので、使い方をどこかで 勘違いしているんだと思います。しばらく悩むしかなさそうです。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/402

403: 310 [sage] 2016/02/21(日) 01:04:17.33 ID:nPWuqcvw 試しに定石部分を外して、中盤探索で開始してみたら、zebraの２０手読みに対して ２戦して１勝１分となりました。読みの深さは、こちらが上なので、こんな感じでしょうか。 序盤２０手分は評価値が無いので、２０手近い探索を反復無しで探索するため、MPCを 使っても最初の数手は１手あたり５分以上掛かってしまいます。 定石については、以前にウェブで見つけてテキストに起こした定石データがあるので、 それを評価０で登録してみようかなぁと思っています。 定石の自己学習とか、評価付けとか、どうやるんだろ。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/403

404: 310 [sage] 2016/02/25(木) 21:06:56.39 ID:fXRsnvrs 定石データを、上記の手打ちデータで作り直しました。 当初は並び取りとかの極端な進行以外は評価０．０にしたため、mobility関数のビット列 の下から定石に従って着手する形となり、zebra先生のBookに誘導されるように、少しずつ 不利な定石に乗り換えていき、負けるという展開に（汗 悔しかったので別のソフトを拾い、戦ってみると、そちらには圧勝。決して弱くはないと思う。 また、zebraとの対戦時にBookで評価値がついているものは、それを参考に修正したところ、 時々勝てるような感じになりました。 EDAX先生＋UnifiedBookなるものを拾って、そちらと戦ってみたところ、軽く惨敗。 ｆｊｔ定石とかだと終盤近くまでBookがあるみたいで、Bookが続く限り紛れが無い。 こちらが中盤探索などでミスるたびに−２づつ落としていき、お話にならないレベル差を感じました。 しばし熟考の上、定石の拡張、評価付けを考えてみようかと思います。 あと、評価値が近い時には、何らかの確率で手を選択するようにもしてみたいと思います。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/404

405: 310 [sage] 2016/02/28(日) 01:10:48.52 ID:hQzoi2Tz 縦取り系は白番黒番試して、定石の評価値を修正してみました。 あと、AIの進行ごとのパラメータを試行錯誤して、なるべく負けないようにしてみました。 これにより、AIの読み時間が結構伸びて、１ゲームワーストケースで１手２分、トータル ５分くらい思考してしまいます。これは、反復深化などで、タイムアップをせずに、次の ステップに入る制限時間だけ決めているためです。 EDAX＋Unified Book先生はレベル２１で、黒番白番ともに引き分けになります。 こちらは２０手前に定石が切れていますが、その後も最善手が打てているという事になり ます。こちらは何局打っても手を変えないので、EDAX先生のBookの進行に合わせた だけですが。一方zebra先生は比較的手をいろいろ変えてくるので、勝ち負けが発生します （もちろん、各アプリの設定次第ですが）。 序盤定石の評価値をそれなりにしたら、後は引き分け進行をひたすら登録していって、 相手が最善しか着手しないと信用すると負けないプログラムができちゃうのではないか と、ふと思いましたが・・・。トップ同士の対局が引き分けばかりになるのは、こういう事 なんでしょうね。というか、完全解析ってこれが完成した状態なのか。 EDAX先生のUnified Bookは、いくつかの引き分け進行棋譜の集合体のようですが、 元データが幸い既知のWthor形式なので、それをもらってしまうと、トップレベルになる のかなぁ。トップな人がBook構築に主眼を移したり、開発が止まったりする訳だと。 そろそろ、混とんとしているプログラムを綺麗に直して、パクリBook作って開発終了しちゃ おうかと思い始めています。速度的には、まだまだ改善の余地はありそうですが。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/405

411: 310 [sage] 2016/03/04(金) 10:15:09.55 ID:Q4DtXsqP >>410 一晩考えてみた。 通信回りに興味を持って遊んだのは１５年くらい前だし、Javaとかイメージしかないし。 あまり助言できる事はありませんが、一つ言えるのは、UIに凝ったりサービス内容を 考えたりするのは最後で良いと思います。 Rubyが好きなら、まずはCGIベースで、テキスト表示で対戦を実現する仕掛けを作る事 だと思います。次に複数のユーザーが接続するのであれば、身元確認のためのID/パス ワード管理が必要になりますし、個々の対戦を区別するにはセッション管理が必要になり ます。この辺は、スタンドアロンのアプリには無い、独特の世界なので、結構新しい技術、 テクニックの習得が必要になるかと思います。いまどきあるのかわかりませんが、チャット のスクリプトとかあれば、参考になるかも。 その辺から入り込んで、いろいろ調べていくと、だんだんと必要な技術、知識が増えてくる んじゃないかと思います。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/411

415: 310 [sage] 2016/03/10(木) 02:00:10.79 ID:hvbQwbFh うむむ。 これにて、オセロができたら次は囲碁という目標が雲散霧消してしまいました。 どうしよう。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/415

416: 310 [sage] 2016/03/10(木) 18:05:03.79 ID:b1SmaPOg AlphaGO強すぎ・・・orz 今夜は、囲碁関係者だけじゃなく、AI周りの人も、Google以外全員お通夜ですね。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/416

422: 310 [sage] 2016/03/13(日) 20:47:23.70 ID:50OeMIN8 うむ。なんか期待を裏切られっぱなしｗ この負けっぷりを見ると、囲碁もトライしたくなってくる希ガス。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/422

424: 310 [sage] 2016/03/16(水) 23:06:52.43 ID:YEZK1fac アルファ碁ロスまっただ中ですｗ オセロ作ったおかげで、一連の勝負をいままでとは違う視点で見れたかなぁ。 とりあえず、囲碁のモンテカルロ解説した本と、ディープラーニングの入門書を 買ってきた。さらっと読んだけど、ディープラーニングは理解に時間がかかりそうorz オセロで３層パーセプトロンを試したときは、結局うまく動かなかった。 実装が悪いのもあるけど、学習にもすごく時間がかかった。 あれをディープにしたら、どうなっちゃうんだろうかは不安ではある。 こちとら、SurfacePro3しかないし（汗 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/424

435: 310 [sage] 2016/04/05(火) 10:45:13.03 ID:82XTVDoH 久々登場。アルファ碁ロスがでかすぎて、やる気がでないです。 とりあえず、BOOK上で乱数入れて手をばらけさせるようにしました。あとの課題は、 １．持ち時間制度 ２．ステータスバーの更新 標準のStatusBarだとOnMouseMoveなどで更新されるとの事。 リアルタイムに更新させるためには、マウスくるくるさせてなければならん。 ３．中盤探索の高速化 反復深化＋置換表で高速化が効いていない懸念があるけど未確認。その他の高速化検討 ４．同じ手順で負けないためのBOOKの自動学習 ５．オフラインでの引分手順の自動生成 となります。けど・・・本当にモチベーション上がらない。 時々、気が向いた時に、Zebra先生やEDAX＋UB師匠相手にポチポチ手打ちで対戦して、 相手のBOOKに登録されている引き分け手順を見つけて、手入力でBOOK更新してます。 Zebraは研究モードがあるので、ほぼ拾い終わりましたが、逆に引き分けだらけになりました。 EDAX+UB相手だと、こちらが定石から外れるケースでも、EDAX側は学習データで先が 見えていて打ってくるので、ほぼ負けになります。 たまに、EDAX＋UBも中盤探索が走ってくれて、極まれに勝勢になる事がありますが・・・ 何が腹が立つと言って、そういう時に限って完全読み時にEDAXがバグって、既に石がある 所に着手して逆転した事にされます。もちろん反則なので勝利は勝利ですが、すっきりと 勝たせてもらえないのが腹立たしい。をのれ。 というわけで。やはりオセロは、引き分け手順のリストアップが、強さの肝である事も再確認 してしまいまして。そこまでの根性は無いなぁというのも、モチベーション低下の原因。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/435

448: 310 [sage] 2016/05/16(月) 21:32:31.63 ID:KQ1qSDyb モチベーションダダ下がりだったけど、なんとなくソースの整理していたら、 直したいところがいろいろ出て来て、見直し中。 後ろ向き枝刈で探索時間は変わらないけど、探索ノード数が2/3になった。 この枝刈手法の速度アップできたら面白いかもと思いつつ、元々自分が 結構高速に書いていた処理（未使用）を流用しているから、これ以上速度アップ できるかわからん。 でも、EDAXには勝てないんだろうなぁ・・・ EDAXの孫情報からインスピレーション得てるネタだし。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/448

449: 310 [sage] 2016/05/26(木) 16:01:37.05 ID:ZBCA70ec 遅々として進んでいます。 ソースを一から組みなおして、いろいろと綺麗にしてます。 並列探索を入れない段階で、FFO#40が結構速くなった。 いまさらながらに、FFOテストを40〜59まで実行して比較しようとしたところ、 前から薄々気づいていたけど、FFO#41以後が遅い。酷いケースになると 探索ノード数が１０倍＝時間も１０倍になる（#51）。自分のは指数関数的に 比較的にきれいにノード数が増加している。同じようなノード数のものもあるので、 ZebraやEdaxはどこかで上手にばっさり刈り込んでいる感じ。#52以後は時間が かかりすぎて、未検証ですが。 ZebraやEdaxもノード/秒が一定しているので、置換表みたいな重い方法では なく、簡単な方法で刈り込んでいるっぽい。とすると、moveorderかなぁ。 一応、MPCの99%で評価値の並び順は置換表に残してあるので、そんなに 間違った順番でソートしていないと思うんだけど。 あと、mtd(f)だと最初から最後までNullサーチしかしない事に思い至り、そこで 処理の効率化できる箇所が無いかと考えてます。Nullしかやらないんなら、 アルファ越えの再探索でウィンドウを広げる必要もないわけで。逐次探索部分 では効果不明だけど並列探索だとYBWCでPVを検索し終わるまで待つ必要が そもそもない（仮アルファを求める必要がない）ので、多少速度アップできない かなぁと。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/449

450: 310 [sage] 2016/05/27(金) 00:36:10.52 ID:gIFpjm1c 早々に状況が判明しました。ここに書くと進むんだよなぁ。 mtd(f)＋negaScoutで繰り返し探索しながら、置換表に置換データを置いて、更に それを並び替えに利用していたのですが、最初にPVを探索してしまうと、その後は 別の着手も評価値がαになってしまい、並び替えの意味が無くなっている感じです。 ちなみにPVだけは別ルートで必ず先頭に探索するようにしてあります。 というわけで、テスト的に初段のみ敢えて並び順を逆転させてmtd(f)を未使用にして ただのnegaScoutで、mpc99%→全探索をしてみたところ、探索ノード数がかなり減り ました。置換表使用の深さ全部で並び順を逆転させてみたら、mpcの99%ですら全く 終了する気配がなくなりました。 さて、どうやって実現しようかなと。 今のところ、mpcはかなり高速なので、これをnegaMaxにして。 いわゆる並び替え専用の浅い探査にしようかなと。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/450

464: 310 [sage] 2016/08/03(水) 14:35:23.97 ID:WXOcEHjz ここしばらく、評価関数に新機軸をと、ディープラーニングにトライ中ですが、 囲碁のように、畳み込みの画像認識の応用では、なかなか上手くいかないと 言うか、自分のパソコンで手におえるくらいの規模のネットワークだと全く歯が 立たない感じです。 というわけで、色々と手はいっぱい動かしているのですが、何にも成果があら われていない状況です。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/464

466: 310 [sage] 2016/08/04(木) 01:59:01.51 ID:XH3ZGPYC >>465 最初はGitHUBのDeepLearningの参考プログラムを元に自家製でAutoEncoderにDropoutをつけ たりしてました。 次にCNNで、GitHUBでtiny-cnnというライブラリを落として使用。技術的に凝りすぎライブラリで、 解読するのにC++の勉強が主になってしまいそうなので、改造はあきらめました。 そして、今は、行列ライブラリ（Eigen）落としてきて、自家製に戻りつつあります。Sparse正則化の ために、ミニバッチ処理をしようかと思って（最初のは逐次処理のみ）、ついでにAVX２命令や 並列化対応を、この行列ライブラリに頼ろうかと思ってます。 Eigen使ったMLPでxor解くテストプログラムは、さきほどできましたが、本当にこれで良いのか、 結構不安です。多少間違っていても、収束しちゃうときがあるので。 明日はAdagradに対応させる予定。何とか２〜３層程度で収まらないかな。 パソコン環境が貧弱なので、あまり重い処理ができないのが最大の難点です。 もっとも、できあがった評価関数が重いと、探索深さが浅くなってしまうので、ある程度は妥協 しなきゃならんかなと思っています。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/466

---

ﾒﾓ帳

(0/65535文字)

---

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

---

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

---

Google検索

Wikipedia

---

ぬこの手 ぬこTOP 0.034s