13/07/07 NY:AN:NY.AN tapz/Poj.net
作りたい奴はすでに作り始めてたりする
ハンターハンターに出てきた架空のゲーム「軍儀」
ｽﾚﾘﾝｸ(cgame板)l50
306:名前は開発中のものです。
13/07/08 NY:AN:NY.AN VxgBNd3t.net
なるほど、高さ＝三次元的なゲームだったのか。
二段や三段のコマは一段のコマには抜けれず壁の役割になれる。
壁構築で地形みたいな要素にもなる感じかな？
307:名前は開発中のものです。
13/07/09 NY:AN:NY.AN PWW1vFJn.net
高さを考慮したSLGといえば、タクティクスオウガ系のゲーム画面（盤面）になりそう・・・
308:名前は開発中のものです。
13/08/03 NY:AN:NY.AN gVJOFEFN.net
age
309:名前は開発中のものです。
14/09/08 16:59:53.68 67y2qr+m.net
教京サーバアビエ無戸籍交際薬剤消毒介護職利権ローション羽田帝国上層部24時間パトロール義務上野飲み会マックさむらいニューヨーク森林火災チェック問題ヤーフォー確定申告不足ラーメンスーパーポイントdビデオデッキ破壊タイピングGTX860MIGOZ
教京サーバアビエ無戸籍交際薬剤消毒介護職利権ローション羽田帝国上層部24時間パトロール義務上野飲み会マックさむらいニューヨーク森林火災グリーにんにく牡丹黒家宝ラーメン
教京サーバアビエ無戸籍交際薬剤消毒介護職利権ローション羽田帝国上昇部24時間パトロール義務セコム強盗マックさむらいニューヨーク森林火災グリーにんにく牡丹黒家宝ラーメン
築地TPP偏食中国人勧誘マナー憤怒北京オリンピックパブ立橋フロアWHO経済制裁代協議会飲み食い代官僚日テレ漏洩ボーリングITC問題調査福岡駐車近代道廃人画税幕張銀行ググール無断決裁広告料寒孫ゼリー失調栄養士指的フィルム不毛ハンバーグースラーメン
糞箱弐個弐個沖縄ランド近年ペット原発難民船頭100万円コミックコラムシフト廃品鉄工業プラチナ小スモ再販問題WHO光金アナ雪エネルギーソーシャル決裁ニッカン奮闘鬼記者サービスカ米ラマン露店捜査キセルストアアイダホ会長農家不動産工場感激息子
310:名前は開発中のものです。
15/08/18 16:59:55.72 QcCJSSMl.net
どなたか教えていただけますか？
最近、オセロAIのプログラミングをCで行っています。
今は、探索ロジックの勉強のため、終盤の完全読みを作っています。
置換表付negaMax、置換表付PVSは通常の探索ではきちんと動作しています。
現在MTD(ｆ）にとりかかりました。MTD(f)では、ドライバは擬似コードそのまま。
テスト関数は置換表付negaMaxを流用していますが、そのままだとFail-LowとminMax値
の区別がつかずに、Fail-Lowの指し手を返してしまうので、初段のみαを-1する事で、
内部的に区別できるようにしています。
動作確認にいくつかテストケースでテストしましたが、FFO#40の時におかしな事がおきます。
（FFO：URLﾘﾝｸ(www.radagast.se)）
問題）本来の評価値は+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)といえば置換法を再利用する事が前提です。
どこかに誤りがあるのではないかと思います。
同じような問題に遭遇した人はいますか？
311:310
15/08/18 17:06:51.32 QcCJSSMl.net
ちなみに、置換表のキーは、盤面と手番です。
ハッシュ値を使用し、衝突した場合は、チェーンで下につなげています。
今のところ、メモリーの上限等は設定しておらず、領域も足りています。
312:名前は開発中のものです。
15/08/18 21:27:38.25 ZHAQ4NnD.net
正気か？
313:310
15/08/18 23:21:46.36 5wjtKO2B.net
何がですか？
314:名前は開発中のものです。
15/08/18 23:27:30.51 ZHAQ4NnD.net
その質問に答えられる人間が２ｃｈにいると？
315:310
15/08/19 09:33:45.34 DdofkXsp.net
いなければ仕方ないですね。
テスト関数を置換表付negascoutにしたら、ちゃんと答えが返ってくるようになりました。
けど、なんか気持ち悪い。置換表の扱い方は一緒なので、たまたま上手く行ってるだけ
ではないかと思います。むむむ。
MTD(f)にこだわり続けてもあんまり意味が無いので、評価関数づくりに入ります。
３層パーセプトロン型にするか、普通の線形回帰にするか。
パーセプトロンタイプは、パターン学習のタイプを作ってみましたが、学習データ３４０万
棋譜に対して、１回回すのに３日がかりという状態で、検証サイクルが回しづらい状況な
ので、簡略化をするか、線形回帰を試すか思案中です。最終的には、両方作って対戦
させてみるかと思っています。いつになる事やら。
316:310
15/08/24 09:51:00.08 Y8Lk5h3w.net
BITBOARDで確定石をそこそこ正確に求める方法を考えました。
思いっきり脱線中ｗ
ただ、斜め方向に「列すべてに石が置かれている」状態を検出する方法と、
その時に、斜め方向の列すべてに確定ビット（仮）を建てる良い方法が見つ
からずに、斜め方向のAND用の定数配列を用意してループを１５回回してる。
縦横は、分割統治でそこそこなロジックになったんだけど。
４５度回転を使っても、そんなに高速化できそうにないなぁ。
もちろん、完璧な確定石ではありません。
拾った石は確実に確定石ですが、確定石なのに拾えない石が若干あります。
317:310
15/09/02 11:43:34.50 s0BtWfox.net
ぬぬぬ。パターンによる線形回帰の石差予想。
最急降下法は収束してるんだけど平均２乗誤差が４８０とかになる。
１σでいうと１局面あたり２２石（黒石の数では１１石）もの誤差。
これでは使い物にならない。
ステージ分割しているんだけど、ステージが進んでも誤差はほぼ一緒。
ウェイトがオールゼロでも似たような数字になるレベル。
テストデータで局面評価させると、それなりに石差は計算しているっぽいが、
最善手で終局まで打ったデータ入れるとステージによって評価値が全く違う。
初期値をゼロからスタートすると、この辺なんだけど、１とかからスタートすると
もっと誤差が大きいところで収束してしまう。初期値を乱数にしたら、更に大きな
誤差で収束してしまう。
ローカルミニマムに捕まってるのかなぁ。
いくつかミスは見つけたけど、本質的な場所じゃないので、結果も変わらず。
むむむむ。
318:名前は開発中のものです。
15/09/02 16:33:21.80 6FNrQBf/.net
正規化をミスってる
319:310
15/09/02 21:57:59.44 5gNGVEfH.net
正規化というと、thellさんのlearning.pdfで言うところの、αの設定ですか？
当初はmin（β/100,β/Nj）の正規化型で作ってましたが、上手くいかないので
収束を早めるのは後回にして、今は単純にステージ毎の局面データ件数α=β/Nの
形にしてます。
が、発散を避けようとすると、βをあまりに小さくしなければならないのが、なんか変な
気がしています。今は10の-7～-8乗くらいの値です。やっぱり変ですよね。
最急降下法のコードどこか間違えてるんだろうなぁ。
320:名前は開発中のものです。
15/09/03 04:25:48.28 CNXgxM7O.net
でもオセロだったら最終数手で１１石くらいひっくり返ってぶれるのは普通じゃない？
321:名前は開発中のものです。
15/09/03 04:36:35.33 CNXgxM7O.net
あ、オセロのＡＩにはぜんぜん詳しくないんだけど
対局を見てたらクルクル石差が入れ替わるので
読み切らずに局面から石差を判断すると
どうなるんかなと思って
322:310
15/09/03 10:19:29.05 Fd8XT4rV.net
色々と失礼しました。
もう一度、よーく上記pdfを読み返していたところ、原因らしきものが見つかりました。
記載にあいまいというか、ちょっとおかしいところがあって、式の変形をしっかり追って
確認すれば良かったのですが、思い込みで解釈をして変な計算をしていました。
そこをとりあえずざっと修正したところ、遅々としつつも収束に向かっている模様ですが、
まだまだ完全ではないようです。ある程度二乗誤差が減ったところで、また増え始めたり
しています。正規化も試したけど、やはり同じ。
もう少し、検討してみます。
323:310
15/09/03 10:38:17.33 Fd8XT4rV.net
>>320
もともとひっくり返しあった後の終局を予測するのが目的なので、教師データは最終局面
の石差です。盤面の特徴（パターン）から、最終石差を予想するための重回帰計算なので、
その時点の石数は、説明変数に入れてません。なので、パターンの選択が適切なら、
最善手の応酬において１手毎にどれだけ石数が入れ替わろうと、影響を受けずに、
二乗誤差が終局に近づくほど減っていくと予想されます。
というか、そうなるように説明変数であるところのパターンを模索していくと理解しています。
手元にあるwzebraなんかは、評価値と称して最終石差予想が表示されているのですが、
やはり、ある程度の誤差を含みつつも、大きくぶれているようには見えません。
評価関数の使い道を考えると、実は絶対値はそれほど重要ではありません。
中盤探索のｎ手読みの時の盤面評価と、ムーブオーダリングに使うので、ある局面から
派生したｎ手先の局面における相対的な関係が保たれていればOKです。
また、MTD(f)法などを使う時の、ｆの初期値設定にも使います。この時は絶対値で正確な
方が良いはずですが、外れはすぐにカットされて次に行くので、トータルの時間に対する
影響は小さいように感じます。
とはいえ、相対的な関係が保たれているのかをチェックするのは難しいですから、
結局のところ出来上がった評価関数の評価は、教師データとの二乗誤差の小ささに
するしかないかなと。
324:310
15/09/07 01:11:39.28 OHPpdG+6.net
収束しかかった二乗誤差がまた増え始める原因はまだわかりません。
増え始めるまでは収束方向には向かっているのは確かなのでβの初期設定を
いって誤魔化す方向で。最急降下法ってこんなものなのかなぁ。
一通り納得したので、パターンをLogistelloと同一のものにまで拡充してスムージングも
入れてみましたが、新たなバグを仕込んでしまった模様で、一部計算がぐちゃぐちゃorz
バグ探しの旅に出ます。
裏で、Solverの速度アップを検討。
CountBitとPOPCountを組み込み関数にしてみました。FFO#40で30%ほど改善。
続いてFlip関数を６４個のポインタ関数にしてみましたが、時間はほぼ変わらず。
ポインタ関数内の処理が非効率なのか。
Flipのデバッグ中に確定石計算でバグっぽいものを見つけましたが、回帰が落ち着く
まで見なかった事にします。
325:名前は開発中のものです。
15/09/10 17:45:51.81 R9JX9LJx.net
将棋の全駒にユニークなIDを振り、局面を将棋盤に見立てたkoma[9,9]にIDを入れることで表現しようと思っています
その場合、駒のIDから座標を取得するいい方法ってないんでしょうか？
IF文、Case文のオンパレードになってしまうのは仕方ないのでしょうか・・・・
言語C#
326:名前は開発中のものです。
15/09/13 16:22:10.24 5eWB08IT.net
駒側にも座標を持っちゃえば？
327:310
15/09/14 09:33:29.38 Rx5y2/Cc.net
線形回帰で相変わらず時間食ってます。
一応、バグらしきものはそれなりに解消されましたが、やはりいかんせん収束が遅い。
一晩かけて５０～１００試行して、途中で止めてやり直しなんてのやってる間に１週間は
あっという間に経ってしまうものです。まだ誤差が大きい。１０００回程度回して、どこまで
収束するか見てみようかなと。またぞろ３層パーセプトロンが気になる今日この頃。
確定石計算もバグ取りはできたと思いますが、その分計算が１．５倍ほどに膨れてしまい
ました。しばらく思考実験していたら、確定石なのに確定していると評価できない確実な
パターンも思いついてしまって、どうせその程度のものなら重い確定石計算しないで普通
に準確定石程度にしとくのが良いかと悩み中。
Solverの速度アップですが、前からやろうと思っていた事を少しづつやっていますが、
統計とってきちんとやっていないので１０％くらいの差だと良くわからない状況です。
コードのメンテナンス性が下がるのがネック。negaMAXが思いの他高速化してしまい
ましたが、MTD(ｆ）が低速化しているかも（謎）。
それなりに評価関数が動きだしたので、置換表２枚にして反復深化も試してますが、
信じられないくらい劇遅状態です。これ本当にコストに見合うのかなぁ。評価関数の
計算が、というか、その中の確定石計算が重いんだと思うけど・・・。
328:310
15/09/14 17:35:45.53 Rx5y2/Cc.net
反復深化が劇遅なのは、使い方を誤っていました。
リーフのところまで使うとコストアップなのは考えれば当然でした。
まあ、おバカなバグもありましたが。
negaMaxに対して反復深化を試すと、１割程度の高速化となりましたが、
negaScoutに対してやると多少低速化して、negaMaxの反復深化と変わらない速度に。
scout missが３倍近く増えているので、評価関数の精度があまり良くないためかなと。
move orderには、通常はmobilityとコーナー着手を使用しているのですが、これ、
何故か（少なくともFFO#40に対しては）scout missが恐ろしく少ないのです・・・。
MTD(f)が遅いのも、最初に設定するfを評価関数の値にして、それが結構外れで、
探索範囲が広がったのが原因です。scout missと同様に、結局のところ、途中で評価関数
を求めるタイプの高速化は、評価関数の精度次第という当たり前の結果に。
評価関数入れるとノード探索時間が1/10になるので、やはり評価関数用の確定石計算は
準確定石にレベルダウンしようかと思います。中盤AIでの話ですが。
今FFO#40が９秒台なので、あと３～５倍高速化したい。
329:名前は開発中のものです。
15/09/14 21:42:06.86 1S1dymvg.net
その情熱がうらやましい
330:310
15/09/15 20:18:36.71 egtjjW0V.net
準確定石の計算って実は思ったよりコストフルかもと気づいてしまい、
急きょコーディングして比較してみる事にしました。
releaseモードだと、自分の計算方法では跡形も残らないため、時間計測不可能。
debugモードでも、数十倍速いと言う結果になりましたので、今の確定石計算ロジック
は、悪いモノではないと自分に言い聞かせる事にしました。
それより、回帰の学習で、少しずつ少しずつ２５０回くらいまで学習進めていたのですが、
バグを見つけてしまい、またやり直しです。むむむ。しかも、なおした事で計算時間が
２～３倍になってしまうという。
331:名前は開発中のものです。
15/09/19 00:46:12.58 OgvQcqwn.net
回帰がやっとまともっぽいところまで収束するようになりました。
今、２５０回学習で、最終ステージが１σ＝７．５程度です。
このペースだと、もっと学習させても、たいして変わらない気もしますが、
もう少し学習を進めてみようかと思います。
この評価関数を元に、反復深化＋MTDF+negaScoutなsolverを動かして
FFO#40で８秒程度になります。インライン関数化とか、最終２手展開とか
やるべき事はある程度やっちゃったので、自分の力だとこの辺が限度かも。
332:310
15/09/22 22:15:30.40 70n8Fwqa.net
回帰は地道に学習中。もう少しやってみるって感じだけど、収束状態の誤差が大きいのは
ステージ分割でオリジナルな変な事をしているからじゃないかと気になりだした。
あと数百回学習を回したら、通常のステージ分割版も作ってみるかなと。
色々いじってるうちに、FFO#40が６．２秒まで来た。何が良かったのか良くわからない。
反復深化をターゲットに改良しているんだけど、negaScoutも同じ時間。
FFO#41を試したら、反復深化で４５秒弱、negaScoutで３０秒弱という結果に。
探索ノード数がすごい事になってるので、反復深化のmoveorderのどこかがおかしい
気がしている。
333:310
15/09/25 16:54:56.15 9OkLc3+M.net
回帰のステージ分割というかスムージングを、ネット上でノウハウ公開されてるみなさん
と同じようにしたら、１σで６を切ってきた。やっぱ、スムージングやり過ぎて、精度が
落ちていたのね。同一ステージ内でも値がばらついているので本当に必要なのか、
気になるので、落ち着いたら両方試そうかと。先に方向性見ちゃったから本来とは
逆順になっちゃうけど。
色々頑張ったら、FFO#40が５．１秒、#41が２０秒、#42が１８秒となりました。
ソースとにらめっこしてれば、ネタはそれなりに出てくるものだなぁと。
しかし、１０年前のCPU使ってるThellにようやく勝てた程度。
Zebraの速さは何なんだと。こちらはcore i7だというのに。
目下の悩みは、_mm_popcnt_u64とBitScanFoward64が使えずに、それぞれ32ビット版を
使っている事。外部依存のところで関数の存在は確認しているんだけど、「そんな名前ない」
と出てくる。Cは趣味のAVRで小さいプログラムしか作った事がなかったけど、VC++くらい
巨大になると、どーもよーわからん。
334:310
15/10/04 01:12:59.97 +bDErzEp.net
色々やって、FFO#40でnegaScoutで３．４秒まで来ました。
反復深化は異なる方法で２種類作ってみたけど、FFO#40程度の深さだとnegaScoutとの
差が出てこない。２２手とか２４手とかまで行くと、差が出てくるように感じるけど、後回し。
どうしても気になって、Zebraのソース解説（日本語）を見つけて、そこに出てるソースを
見ました。自分なりにロジック面で工夫した事はほぼ同じ事をやっている。流石。
あとマクロを多用してる。僕はインライン指定でコンパイラ任せ。
マクロにするとデバッグが極端に大変になるので、マクロ化するのは最後。
そしてaspiration windowと称しているWindowの取り方が独特で、ここに高速化の
秘密があるとみた。早速真似してみると、また>>310のような問題が・・・
今回は前より理解が進んでいたため、２点修正して解消。
副次的に>>310の問題も、直ったと思う。
が、もう一つ答えを間違うケースを見つけてしまった。
今まではルートノードに問題があったけど、こちらはもっと下位ノードで戻り値がコンタミ
してる感じ。デバッグが難しく、重症っぽい。むむむ。
335:310
15/10/07 17:10:37.74 i7/9rua6.net
デバッグで試しに変えた箇所を戻し忘れたりして、二次災害三次災害を出して、
相当混乱したけど、やっぱり境界問題だった。これ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で初段の
評価順見てると、まだまだなので、何か別の発想で並び替えが必要な感じ。
評価関数は１０００回くらい回してようやく良い感じになってきたけど、まだ収束しては
いない感じ。学習係数はもっと大胆に大きくしても良かったかな。ここまでやると、
スムージング無しを試すのが億劫になってくる。
反復深化は、ソースのメンテが追い付いていないので、一回破棄。
336:310
15/10/12 23:43:49.17 ZTwsIi7y.net
色々やってるけど、FFO#40では速度向上はほとんどなし。
置換表のサイズが見えて来たので、１件ごとにmallocしていたのを、配列にして一括で
領域確保するように変更（当初の形）したら、速度のバラツキがだいぶ減ったように思う。
NPSが変動すると、何か悪いことしかたと悩んでしまい、修正して二次災害を起こすので
地味に大事かな。
FFO#43は多少高速化してて、パラメータ最適化するとMTD(f)で１２秒台くらい。置換表
適用範囲の指定を下（葉）からしていたのを、上（ルート）からに変えた。あと、MTD(ｆ）
などでは何回も置換表を読むので、２回目からはmoveorderに置換表の評価を使うよう
にした。
BITBOARDだと開放度の計算が簡単だという事に気づいて、静的評価関数に使ってみた
けど、現在使用中の次手mobility＋αの順序より劣る感じ。＋αが角とか×とかなので、
序盤から中盤用なのかなぁ。
negaScoutに加えた修正をnegaMaxに適用していたら、negaMaxがおかしくなった。
直して計測したらFFO#40が４０秒程度に。冷静に考えると、これが常識的な速度だと思う。
前回の５秒台がどこから出て来たのか、今となってはわからない。前段の＋α箇所も
結構変えていて、negaMaxはmoveorderで露骨にノードが増減するので、奇跡的な順序
が実現できていたのか。それともバグやオペミス勘違いかも。
そろそろ本格的にネタ切れ。この辺が限界かなぁ。
後回しにしていた修正箇所を直して綺麗になったら、中盤に行くかな。
337:310
15/10/14 23:51:46.51 V3YF/mde.net
negaMaxはmoveorderの修正漏れでバグってて、直したらやはりFFO#40で５．４秒でした。
MTD(ｆ）は２．４秒でzebra並になったけど、#41以後は３～４倍時間がかかる。
その差は探索ノード数に比例してる。前向き枝刈使うわけにはいかないし、#41以降の
差を詰めるにはmoveorderしかないと思う。
とはいえ主だった事は一通り試してしまった。むむむ。
偶数理論で思いついた方法が純粋に面白そうなので組んでみる。
想定では、速度が結構遅くなるはずなんだけど、まあ面白そうという事で。
338:310
15/10/16 10:24:07.38 Q2afyb0d.net
偶数理論の関数は思いのほか軽くできて、オーバーヘッドの心配が少ないです。
BITBOARDの空マスを、囲まれて独立している塊ごとに分離してBITBOARD配列にして
返す関数を作りました。これをPOPCountで数えて着手した場所が偶数空エリアなのか
奇数空エリアなのかを判定します。
最初にテストしたFFO#43のMTD(ｆ）でいきなり３０％近く高速化して「やった！」と思った
のもつかの間。実はミスで判定を逆にしてまして、偶数マスに打って奇数を相手に渡すと
加点になってました。で、いろいろテストした結果、最初にやったケースではたまたま
良かっただけみたい。例えばnegaScoutやnegaMaxでテストすると、係数変えたり判定
方法に工夫を加えたりいろいろしてみても、何をやっても探索ノードが増えてしまう。
自分はオセロ弱いので、必勝法みたいに言われているものが、アバウト的に最善手に
近い手を選んでくれるんなら、並び順の優先順位計算に、あるウェイトで入れてみようか
的に考えるだけでした。意味とか深く考えるよりやってみるという感じでした。が、最後に
残った２つの空所が偶数と奇数とかの例ならわかりやすいけど、空所が４～５か所ある
ような状況で偶数理論を当てはめようというのが間違いなのかなぁと。
あと、薄々思っているんだけど、テストケースとしてFFOは良くないんじゃないかと（汗
FFOに最適化してると、もっと出現頻度が高い例題でより高速化できる可能性を放棄
しちゃっている事にならないかと。
339:310
15/10/17 09:29:41.90 uZH1KzRS.net
最終２手高速化したあたりから、ノード数が過小になっていたので、それを直しました。
自分のと比較すればよいかと思って放置していましたが、そろそろちゃんと比較しようかなと。
結果、探索ノードが思っていた以上に多かった事、そしてNPSは９～１１K出てるので、
NPSを落としてノード削減する余地があるという結果に。
あまりテストしていなかったFFO#41と42ではzebra方式と呼んでいた（後述）方法が、自分の
中では最速で、MTD(ｆ）の結果があまり思わしくない事も。MTD(ｆ）の#40は初期条件が良か
ったからの模様。
ここらへんでもう一度、zebraサイトのFFOテストページにあるcomplete logなるものを見て
みると、全然違う。バージョン違いなのか、やってる事が全く違う。
浅い探索をしてｆを決めてNull window search（正確には幅３なので正解が判別できる）
を繰り返しているように見える。けど、ログ上に％が出てきて、９８％、９９％、％無しみたい
になっているので、何らかの方法で前向き枝刈しながら、評価値を求めていき、最後まで
幅３の探索しかしていないのかな。こういうのをPVSって言うのかな。
浅い読みとか、前向き枝刈とか絡んでくるんなら、中盤探索をやってから戻ってきた方が
よいのかな。。
340:名前は開発中のものです。
15/10/19 09:50:52.09 BMJ9Bhec.net
とりあえず、ざっくり中盤探索のnegaScoutを組んでみた。
素の状態で１０手読みくらいなら１手１０秒以内に終わりそうな感じ。
だけど、いろいろと気になる点が。
とり同一局面から着手可能な手の評価値の順番は、あまりくるっては
いないように見える。ただ、評価値事態は結構ずれている。
そして、黒番白番で精度が全く違うように見える。
言われてみれば、同一局面でも手番が逆転すると評価は全く変わるからなぁ。
今は、手番も一つのパラメータにしちゃってるから、その差異は埋められない。
パラメーターとか評価関数の区分とか再考の余地があるんじゃないかと。
前向き枝刈するにしても、評価関数がフィックスしないとダメじゃないかと。
というわけで、しばらく評価関数方面で時間つぶしかなぁ。
341:名前は開発中のものです。
15/10/26 09:44:35.41 uWG/Yjb0.net
中盤探索に入るにあたって、評価関数の計算の試作をいろいろしているんだけど、
いまいちぱっとしない。１００回学習で１晩かかるし、３００回試行くらいしないと傾向が
見えてこないので、時間がかかる。
で、仕方ないので、裏で序盤定石を作り始めてしまった。
こちらも棋譜ベースで作ろうと考えている。
そこまで来た時に、データベースのどういうデータが使いたいのかが、逆にはっきりして
来て、今使ってる３６０万件棋譜の中のデータを選別しようかという方向に傾きつつあります。
が、やっつけで作って中身が思い出せないフォーマット変換のプログラムから直さなきゃならん。
開き直って、もう１度、データ変換から作り直そうかなと・・・
342:310
15/10/30 17:31:41.23 uxyAnbEX.net
棋譜ベースで序盤２０手の定石DB作った。
定石DBは置換表をベースに作ったので、検索は速いけど、容量が大きい・・・。
簡単にαβで２０手探索してみた。
ネットで調べた定石集に載っていない手筋が出てきてしまった。むむむ。
５手目までエビ系で、しかも石差＋２で黒勝ち。棋譜が偏っているのかな。
棋譜は例の５０万棋譜計画の奴で１０手目、２０手目以降を訂正したというデータ。
明らかに壊れたデータが入っていたりと、何かと使いにくい箇所があるデータだけど、
定石DB作るにはこの量でも足りないのかも。
定石探索用の簡易版minMaxを作りながらつらつら考えていたら、終盤探索の
moveorderをもっと良くする方法を思いついた。評価関数の精度次第だけど。
新評価関数は、途中でうっかり仕込んだバグで遅延。ようやく原因が見つかって、３００回
試行まで来た。もうちょい収束させたいけど、テストに使える程度にはなってると思う。
343:310
15/11/08 00:32:40.41 LMw8+3qF.net
moveorderを早くする方法というのは、事前に軽く探索した手順を保存し、その手順から
優先して探索するというもの。理論的にはscout missがゼロになる。
探索した手順を取り出す仕組みが必要になるので、その辺を改造しようと思ったところで、
悪い癖が出てしまいました。Cベースのソースを一旦棚上げして、C++ベースのクラスを
利用した形で一から作り直してしまいました。
moveorderの配列をvectorに変えたり、unordered_mapを見つけたので置換表に使って
みたり。置換表は、システム任せにして動的にメモリ確保に行かすと、探索ノードの減少
以上に速度低下して使えない。最初からある程度メモリ確保させようとしているんだけど、
いまいち設定がわからない。動的にメモリ確保するので、速度のバラツキも大きい。
そもそもC++は初めてなので、目的がオセロからC++というかunordered_mapの習得に
なりかかっていたので、一旦棚上げして、配列ベースの自作ハッシュの置換表に戻る
方向にしました。
とはいえ置換表を外してもnode/secが5kくらいしか出ていないので、実装が悪いところもありそう。
というわけで完全に寄り道しちゃってます。
344:310
15/11/12 16:56:19.10 4hPfHY6k.net
ようやく、C++ベースの終盤探索（negaScout）が、Cベースより若干速くなりました。
・unordered_mapの速度のバラツキはデバッガー上限定。
実行ファイルでも多少ばらつくけど、メモリ効率＆メンテナンス性からunordered_mapを採用。
・探索した確定手順を返す方法の検討で苦戦。
negaScout＋置換表では原理的に無理と認識するのに時間を要しただけでしたorz
置換表無しnegaScoutかnegaMax＋置換表では、後者の方が高速。
・確定手順を元にmoveorderする改造の効果は限定的。
moveorderで先頭にする処理が重い模様。適用範囲を狭めて行くと１～３手で同等の速度。
・ハッシュキー生成簡素化で若干速度アップ。
・その他、細かいスピードアップ。
確定手順の導入で５０％以上速度アップを目論んでいたのですが、無駄な努力でありました。
一応、与える確定手順の数はマクロ定義で可変できるようにしてあります。
評価関数も修正を加えたいので、データ変換部からまた作り直しです。
目標も無しに同じ事２回やるのは面倒だなぁ。
345:310
15/11/19 14:23:44.03 W/V+CKXD.net
定石部分もクラス化が終わりました。クラスなんての扱うの初めてなので、もうちょっと
綺麗にできたかなと思う面もありますが、C++習得が目的ではないので。
終盤確定読みは０．０５秒刻みで速度アップ。FFO#40で２．３秒になりました。
今まで、速いプログラムでは３０手目くらいから勝敗判定を始めると言う記述を読んで、
なんて速いんだと思いつつ、何に使うんだろうと思っていましたが、ようやく腑に落ちました。
オセロというゲームは勝敗だけが問題で、勝つんなら２石差で十分。「少なくとも負けない
手」というなら、(-1,0)のNull windowで探索してβカットされた手を選べば良い。評価値は
不定（これより良いという値）でも負けない手であるという点では「確定」手順です。moveorder
が正確なら、極端に石差を減らす手も選ばない。これなら現状でも２５手ちょいくらいは行けそう。
ただ、これは勝勢の時の話で、敗勢の時の評価値は「これより悪い」という数字だし、
逆転は相手のミスに期待するしかなく、相手も同等のロジックのAI相手だと必敗となる。
結局定石段階で勝負がつく事になります。
今、定石DBは３０手を前提に組んでいますが、３１手目から勝敗判定ができるんなら、定石
を外れない限り中盤探索が不要になり、定石から外れた時にのみ中盤探索が必要になる。
つまり中盤探索は対PC戦では重要度が低く、定石が切れたら、即、終盤探索が始まる。
そもそも評価関数が良ければ、中盤もあまり深く探索する必要がないわけで。
深く読む意味って、なるべく評価が正確なステージを使いたいからなんだなぁと。
というわけで、次はそろそろ中盤探索です。Multi Prob Cutの英語論文を読まねばならぬ・・・。
346:310
15/11/21 00:05:47.02 WWzrsUCT.net
定石DBを使って３０手目まで着手した盤面の予想石差が２で勝ち判定だったので、
試しに３１手目から勝敗判定をしてみました。
(-1,0)のNull windowで７分３０秒ほどで解けました。
（参考）勝ちと引き分けを区別するために(-1,1)で計算すると９分３０秒ほど。
探索ノード数がintではオーバーフローしてしまった・・・。
これから、３３～４手目（残り２６～７手）くらいで、１０秒程度で解けると予想されます。
勝勢ならこれで良いのですが、敗勢の時は、初段がβカットされないので１０倍程度
時間がかかる。そうすると、残り２５～６手目くらいが勝敗読みの限度かなと。
もっと高速化が必要なのか。それとも、何か発想の転換ができるのか。
347:310
15/11/23 21:01:42.47 24rahmZ0.net
ProbCutとMultiProbCutのBUROさんの論文あらかた読み終えました。
最初、MPCの方から読んでちんぷんかんぷんだったので、ProbCutを読んで、
戻って来て、ようやく実装のイメージが湧くところまで来ました。
というか、この発想に至る道具立てや考え方は、既に揃ってた感じ。例えば>>323とか。
これ>>345-346の勝敗判定の高速化に使える気がする。相手側の手番では
前向きカットしないようにすれば、相手の反駁手を見逃さないからいけるんかなと。
あまり深い読みで使用するとパラメータ作りでしばらくPCを占有しそうだけど。
カットペアは結構アドホックに決めているのかな。各組合せを総当たりで調べても、
σにそんな差があるとは思えないし、特異的に良い組み合わせがあるとも思えないし、
むしろ読む深さの差が増えるにつれてダラダラとσが大きくなって行くだけじゃないか
と思う。毎深さごとにMPCしてもオーバーヘッド負けになるだろうし、再帰的に使う事を
考えたら、２＾ｎ＋αで４，８，１２，１６，２０，２４ってな感じで良いのかな。
348:310
15/11/25 22:32:57.73 APRE5Y1F.net
条件を決めて簡単にMPCパラメータの計算プログラムを作って検証してみました。
３０手目の時点（深さ３０）の時の浅い探索０～１０手でMPCパラメータを計算してみました。
例の３００万件棋譜の３０手目以後完全読み（らしい）１９０万件ほどのデータからランダム
に２００件ほど抽出して使用。
結論）δが１０石、R-2が０．７未満という状態で、とても使えたものではないという事に。
ただ、３５、４０、４５手目時点からのカットを試す価値はあるかも知れない。
一方、３０手目の時点で、深さ１０の探索に対して、浅い探索６までで計算すると、
浅い探索４手でδが２石、R-2が０．９３１、浅い探索６手でσが１．５石、R-2が０．９６２
程度と、まずまずの結果に。これが、論文通りの使い方。
当たり前だけど、こちらは十分使えそう。ただ、結局深い探索に対して浅い探索の深さを
決めるのに、全パターン試すしか無いという。まあ、BUROさんのマネしちゃえば良いけど。
あと、中盤読みのプログラム、やっつけで、終盤探索の手順作成用の浅い読みプログラム
転用したんだけど、これnegaMaxなのよね。negaScout＋MTD(f)にするなり、もう少し、
素の高速化をしないとパラメータ計算が大変。
349:名前は開発中のものです。
15/11/29 22:05:16.61 gx8DmdDE.net
googleとかfbが囲碁のAI作ってるが、どんなもんなの
350:310
15/12/02 23:21:25.70 Xp/MZwxE.net
とりあえず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の計算があっているのか、バグは無いのか、不安になる…
351:名前は開発中のものです。
15/12/02 23:37:59.26 Xp/MZwxE.net
>>349
囲碁オセロ板の該当スレで聞いた方が良いかなと。
コンピューター囲碁ソフトについて語るスレ30 [転載禁止]©2ch.net
ｽﾚﾘﾝｸ(gamestones板)
352:310
15/12/04 23:35:12.62 DNSRUk3b.net
結局、確定石が評価関数の誤差の大きさと、収束性の悪さの原因だったみたいです。
前半から中盤はmobilityのウェイトが大きそうなので、とりあえず復活させてみました。
あと、スムージングは、あるステージで出現しなかったパターンが隣接ステージにある
可能性も考慮し、ウェイトがゼロのパターンを減らす目的もあるようです。
実際、２００試行ちょっとでかなり誤差が減ったのですが、FFO#40で試すと途中の評価値
のバラツキというか、極端に０に近い局面が現れて、２σ以上の差異が簡単に出てしまい
ます。そこで、ちょっとだけスムージングを入れて、かつデバッグ段階ではウェイトゼロの
出現をアラームできるように改造しようかと思っています。
評価関数の重要性を痛感しています。しばらくは、ここで悩む事になるのかなぁ。
最低でも３００試行するとなると３日かかる。
353:310
15/12/05 23:27:03.86 VLRyPTJJ.net
モビリティーも収束悪化の原因でした。
確定石の数にしても、モビリティにしても、ある程度大きな数字が出るものがダメっぽいです。
評価パターンとウェイトを確認できるようにして、FFO#40～41の完全読みに登場する盤面を
チェックしましたが、ウェイトゼロのパターンは出現していないようです。
評価値が大きくぶれるところがありますので、スムージングを入れてみて計算開始です。
354:310
15/12/07 10:00:41.29 JSVZKjkd.net
スムージングも外してみたら、Buroさんの論文なみ（か、それ以下）のσが出そうな
感じになってきました。収束が良いのでβも大きくできたし、その後の計算でも工夫を
入れたので、Buroさん論文みたいに３００回試行で十分なレベルになりそうです。
ウェイトゼロのパターンはありました。FFO#40の５０手目のCORN２ｘ５に１つ現れます。
現在selective endgame searchがどんなものなのか、想像を膨らませています。
iterative widening endcutのイメージがなんとなくつかめてきました。
ソースを探して見ちゃえば早いんだろうけど、面倒だし、想像だけで頑張る。
MPCが動いたら、solver改造して、本当に速くなるのか確認する。
355:310
15/12/10 23:16:49.62 lQAJMVKx.net
結局、評価関数は１０００回試行までやってます。
β・1/Nでやってるけど、それだと収束が遅いので、１００回試行ごとにβを倍々に。
１０００試行目で発散するステージが出たので、βを下げて最後の１００試行を実行中。
その間、反復深化などで使えるように、置換表を改造。前回評価範囲をmoveorderで
再利用します。いちいち消しているとメモリ解放で時間がかかるし、全データを入れたまま
用途をキーで区別すると、使用時に選択する事になりオーバーヘッドが気になるので、
一番新しい評価値をひたすら上書きし、置換表として使用する時のみ、今回探索か
区別するようにしました。moveorderで若干割り切った作りです。
同時に中盤探索（MPCなし、反復深化）をちゃんと作ってみました。MPC計算で、結構深い
深さまで探索する予定なので、反復深化が上手く機能するようなMPC計算ロジックを考え
ようと思っています。
それができたらiterative wideningのテストをしてみようと思います。
356:310
15/12/11 22:32:36.55 c1YdnEjo.net
あちゃ。ウィンドウ幅１でiterative wideningやると、正解着手もβカットされた手も
置換表の値が全部同じになって、次の探索でmoveorderが意味なしになって、
速度が大幅低下する事が発覚。
仕組み考えないと・・・。
357:310
15/12/13 23:14:55.34 RUGsIY6w.net
一応回避したけど、MPCの速度向上は限定的。
中盤探索というか評価関数が驚くほど遅いのだろうという結論に。
放置していた中盤探索の素の高速化に入ります。
１か所ネタはあるんだけど。
358:名前は開発中のものです。
15/12/18 00:28:56.19 ht2BaviT.net
中盤探索で２か所改良して、速度は２倍にアップ。まだzebraの６掛け程度の速度です。
終盤探索のiterative wideningを想像しながらテストするも、いまいち速度向上が望めない。
MPCのカット基準を緩めながら（widening）、置換表にmoveorderを貯めていく事でβカット
をどんどん起こさせて、最後の完全読み時点ではほぼ完ぺきな順序に並び変える事で
高速化を実現する方法だと想像しているんだけど、違うのかなぁ。
そんなこんなでやけくそ気味に、浅い探索（１１手読み）＋negaScout(-∞,+∞)を試したら
FFO#40で1.93秒という最速タイムが出てしまった。MPCもMTD(ｆ）も意味なしorz
#41,#42もこの方法でかなり高速化したけど、それでもまだzebraの方が速い。
359:310
15/12/20 17:21:06.88 UpZkem/K.net
中盤探索で改良をしたらかえって遅くなるを繰り返してます。
で、やけくそ気味にmoveorderの「置換表がない時」の計算値を、簡素化してみたら
中盤探索の速度そのままに、終盤探索部分の探索ノードが減少して高速化。
終盤探索部分も同様に簡素化したら、FFO#40で1.75秒以下になりました。
それでも相変わらず#41/42はzebraがずーっと早い。
で、MPC使うと遅くなる理由を考えていたら、いま使っているMPCのセットは終盤探索用に、
残り手数と浅い読みのセットを独自パターンにして計算した奴だと言う事を思い出した。
深い探索のスコア＝終局のスコアとなり、深い探索が不要になるので。
中盤の高速化するネタももう出てきそうにないし、先に進むか・・・
360:名前は開発中のものです。
15/12/23 11:41:36.91 Acs4Om0o.net
iterative wideningって詰め碁用のアルゴリズムっぽいけど違うの？
310の言ってるのってただのAspiration Searchか何かに見えるけど
てか置換表にmoveorderを溜めるとはどういう意味だ
361:310
15/12/23 16:26:13.00 MLtsaD3t.net
どもです。
Ｂｕｒｏさんのパワポっぽい資料に名前しか書いてないので中身がわかりません。
わかっているのはＭＰＣと併用するらしいことくらいです。
iterative wideningで検索すると確かに碁の関連の英語論文がヒットしますね。
関係なさそうだと思って放置していましたが、ちょっと見てみようかなぁ。
置換表云々は、僕の想像です。
αβを前提にしたアルゴリズムで高速化するネタの一つに、moveorderを工夫して
βカットが起きやすくするってのがあると思います。
反復試行する際、置換表には前回の評価の範囲が入っています。
それを今回探索のmoveorderの並べ替えに利用しようというものです。
反復深化なんかと同じ考え方です。
逆に言うと、反復を前提としたアルゴリズムで高速化するネタが、それくらいしか
思い浮かばないのです。
362:名前は開発中のものです。
15/12/23 20:37:25.92 Acs4Om0o.net
ああ、オーダリングに以前の探索の結果を置換表から引いて使うってことか
置換表に順列か何かを放り込んでいくのかな？とか思ってしまった
bitboard + NegaScout + 置換表 + MPC + 評価関数とマージンの学習
をやってるっぽいのはわかったけど、とりあえず定番どころは全部入れてるのかな
NegaScoutで最初のノードを探索するときに、
探索窓を(-inf, inf)で探索せずに、前回の評価値eを使って
(e - d, e + d)で探索して、失敗したときに限り窓を広げて再探索するのがAspiration Searchだけど
もうやってるかな
あとCPUのSIMD命令使ったり、並列化したりとかはめちゃ効果でかいよ
363:310
15/12/23 22:38:37.71 MLtsaD3t.net
>>362
ご助言ありがとうございます。
MPCはまだ途中ですが、そんな感じです。
終盤ｎ手高速化の類もしています。中盤探索だと葉に近いところで置換表外すと、
著しく速度が低下するので、最後まで置換表を使っています。
で、中盤の速度がいまいちで１２手読みくらいが実用範囲って感じです。
MPCでｄ計算に１００棋譜くらい試して一晩で計算できる範囲は１３～１４手くらいが
限界な感じです。そろそろMPC計算しちゃおうかと思いつつ、まだ悶々と中盤探索で
どこか高速化できないかトライ中です。
SIMD命令はコンパイルオプションでそれらしい場所があったので、設定してみましたが、
速度変わらずで放置しています。どうやって使うものなのでしょうか？
そもそも、組込関数のpopcountとかbitscanで64ビット版が使えずに放置してる状況です。
並列化はMPCが終わって、一通りオセロの形にしてから、次ステップで勉強しようかと
思っています。
アスピレーションサーチは、１σは±７～８手なので試しに±８の幅にしてテストしてみた
ところ、確かに若干高速化できている様子です。mtd(f)は下から寄っていく時はβカットが
効くのですが上から寄っていく時は遅いので、一発目で探索できる確率を上げつつ、
ある程度幅を絞るには、このくらいがちょうど良い感じですね。
364:310
15/12/24 20:33:24.09 zDiJT168.net
ちと調べてみました。SIMD命令はx64でコンパイルしている時は、設定しなくても自動的に
使うようになっているみたいな説明を見つけました。
並列化とかベクター化とかもコンパイラが自動でやってくれるみたいですが、レポート出し
たら確かに一つも対象になっていませんでした。評価値算出とmobilityの２関数は、なんか
効きそうな気がしますので、少し悶々とトライしてみます。
また、_mm_popcnt_u64と_BitscanFoward64は、今やってみたら、何故か使えました。
色々とコンパイラのオプションをいじったのが原因かなぁ。謎。
多少速度アップした模様です。
アスピレーションウィンドウはｄの計算しなきゃと思っていましたが、よくよく考えたら、
評価関数の計算時の誤差ログが残っていますので、そいつでパラメータ作成してみます。
と、久々にFFO#43まで時間計測したところ、#43で答えが違ってる。
数か月前に最終２手高速化をいじった時にバグを仕込んだ模様です。
調べようとdebugモードにしたら64ビット組込関数が使えない。
やっぱりコンパイルオプションのどこかみたいですが、わからない。
だんだん問題が発散してきて、頭の切り替えが追い付かなくなってますorz
365:名前は開発中のものです。
15/12/24 20:53:24.01 DG4HDn4P.net
pop_cntはめちゃめちゃ速度上がった経験あるが（三割アップ）
オセロだとそうでもないのかな。
366:310
15/12/24 22:56:29.36 zDiJT168.net
_mm_popcnt_u32()はすでに使っていました。u64が使えなかっただけです。
u32→u64で３～５％くらいの高速化になっています。
困った事に、debugビルドの側では、まだ64bit版が使えていません。
debugを使いたい時は32bitに直さないといけない。
コンパイルオプションをいろいろ見比べていますが、どこなのかいまだにわかりません。
#43は最終２手なのか１手なのか、どちらにバグがあるのか切り分けようとして
ソースいじっているうちに直ってしまいました（汗）。
367:名前は開発中のものです。
15/12/25 15:25:23.28 skIhqDAd.net
>>364
コンパイラの自動ループ展開（あんま賢くない）に限らず、
手動でAVXだのSSE命令だの使えるところは使ったらという話
あとMPCは本質的に前向き枝刈りなので、過激に刈りすぎると答えがずれる可能性はあると思うけど
（バグの原因は当たりがついているようなので関係ない気がするが
368:310
15/12/26 11:23:54.66 2a5cp76f.net
どもです。バグったところはMPC使って無い箇所でした。
コンパイラの自動ループ展開は上記２か所で試してますが、なかなかうまく行きません。
なんとか依存関係を解消してループ展開強制すると劇的に速度低下する状態です。
その代り、いろいろググっていたら、BMI命令を見つけて、BLSIとPEXTを使ってみました。
速度バランスが変わったのでパラメータで置換表適用範囲を狭めるなどもしましたが、
FFO#40で1.55秒前後まで高速化できました。中盤探索も高速化はしているはずですが、
数％程度の改善というところでしょうか。まだ５０％は高速化したい状態です。
色々アドバイスいただいたお蔭で、ようやくSIMDまわりの使い方がわかってきました。
ここまで来ると、BITBOARD操作の関数の見直しをしたくなりますね。
中盤探索の一番重い部分なので。
369:310
15/12/28 10:45:49.88 i0yT273K.net
デバッグモードでu64系の関数が使えない件、解消しました。
MTD(ｆ）に代えてアスピレーションウィンドウを採用しました。
中盤探索は、隣の評価値をたどっていくと、かえって遅くなるのでnegaScoutだけで
探索していましたが、これでMPC計算が多少高速化できそうです。
MPC計算はまだしていません。反復深化でどのくらいの深さの探索で、どのくらいの
件数なら実用的に計算できるか試行しています。１４手読みまでは行けそうですが、
１５手だと厳しいかなぁという状態。２０手付近では盤面によっては、探索ノードが爆発的
に増えて、時間のバラツキも大きいです。
また、FFO#40-44の完全読みを計測しました。zebra比で#40は圧勝、#41-42は引き分け
ですが、#43-44は完敗。理由は#43-44は正解となる初手が２つあるためで、#43は１０秒
以上かかってます。むむむ。
370:名前は開発中のものです。
15/12/28 21:28:38.25 kMgyHY3u.net
オセロ完全解析は何年後くらいになりそうですか？
371:310
15/12/29 02:31:09.04 F/Ba7yoX.net
ちょっと一括変換操作を誤って大変な事になっていました。一通り直していたところ、
FFO#40で1.45秒程度が出るようになってしまいました。多分、修復がてら置換表登録・
検索関数の変数の並びを、整列したのが効いたのだと思っていますが、びっくりポンです。
前回課題の正解着手が複数あるケースですが、MTD(ｆ）のような評価値決め打ち系の
探索では、ぴったりの答えが見つかった時点で、ほかの手を探索する必要が無い事に
気づき、直してみたところ、FFO#44は速度アップしました。が、#43はまだ駄目です。
とはいえ、#43は浅い探索の評価値が外れすぎて時間がかかっているような感じなので、
浅い探索の深さを残り手数で調整すると直りそうな気がしています。
あと、FFOテストの全データをテストできるように登録しましたが、#59を見て、はたと、
途中全滅時のスコア計算が違う事に気づきました。自分のは一番単純なアメリカルール
です。ここを直すと、確実に時間が遅くなるような気がしますが、明日直してみます。
てな事をやって、一晩に０．１秒（比率にして７％前後）も短縮していると、まだなんか
やる事があるんじゃないかと・・・。
372:名前は開発中のものです。
15/12/29 03:05:56.17 rs+91GZQ.net
結局MTD(f)をやってるのかやってないのか意味わからんな
373:310
15/12/29 10:25:40.74 F/Ba7yoX.net
って、βカットしない事を確認しなきゃきゃいけないから、ぴったりの答えがあっても
全手を探索しないとダメじゃん。すんません。
374:310
15/12/29 10:52:28.77 F/Ba7yoX.net
>>372
やったりやらなかったりで、いろいろ比較して試してます。
MTD(ｆ）では、ワーストケースではウィンドウ中心が評価値の最少単位で動く関係で、
１石以下の少数計算をする中盤探索では、よけいに時間がかかる事が多いです。
そのため、アスピレーションウィンドウ導入前はただのnegaScoutにしてました。
終盤探索は、最少単位が１石になりますので、許容範囲です。
MTD(ｆ）もアスピレーションウィンドウも、所詮本チャンのnegaScoutを呼び出すための
ドライバーにすぎないので、どちらも用意して、何かの折に速度比較しています。
今回は、ボツりましたが、ぴったりの値が見つかったら後の探索を省略する際には、
MTD(ｆ）の方がマッチングが良かったので、そうしました。
ボツになりましたので、またアスピレーションウィンドウに戻りましたが。
#40ではzebraよりはるかに高速化できましたが、#43など遅いケースでは、数倍の時間が
かかります。こういうタイプの時間差は、単純な高速化じゃなくて、何らかのアルゴリズム
の違いがあるのかなと想像しています。
375:310
15/12/30 00:01:33.75 lfikhn/D.net
結局、本日は探索速度アップばかりやってました。
中盤探索というか評価関数の計算でBMI2命令を徹底的に使ってみました。
また、ボードの回転操作系も見直しました。
１０％程度は高速化できたと思います。でも、期待したほどではなかった。
あと、速度アップするなら、ボードの対角線転置かなぁ。あと効果は微妙だけど、１８０度
回転がビットオーダーの逆転なので、これも何か組み込み関数があったらうれしいなと。
終盤探索では、FFO#59問題に対処。
スコア計算の修正と、全滅など６４石の差がついた時に、βカットと同様に後続の探索を
パスして時短。minMaxで言うところのα値の更新があり得なくなるからです。
浅い探索が１１手だと３秒程度で解けるのに、１５手だと６０秒かかったりと、いまいち動き
に納得がいかないので、まだ何か問題があるかも知れません。
中盤探索をあと５０％は高速化したいなぁ。というか、zebra見てるとできるはず。
376:310
15/12/31 21:04:10.05 i5TR43+g.net
2015年の年の瀬は、MPC計算のメモリーリークの原因探しで更けていく・・・
置換表クラスあたりっぽいんだけど、デバッグの仕方が良くわからないという・・・
377:310
15/12/31 23:46:42.84 i5TR43+g.net
ギリギリ１２時前に直った。
メモリリークではなく、不正なアクセスでした。
多分直ったと思う・・・
来年の抱負は、MPCの計算をする事と、GUIを作る事です。
元々VBのGUIからDLLで呼び出すつもりでしたが、なんとなくC++でやってみようか
という気になってきています。
378:310
16/01/03 11:08:48.54 3YPfF+nL.net
バグは解消してました。なんとも不可思議な事になっていました。
スタック領域を破壊していて、破壊された箇所がたまたまdepth（残り探索深さ）だったため、
探索深さがマチマチになってました。計算時間やメモリ使用量が異常になる以外は、そこそこ
それっぽい探索結果が出ていたため、メモリリークだと思ってしまったという。
中盤探索の置換表適用範囲も、ちゃんと効くようになって深さ１１～１２まで置換表を使用
するのが効果的と出て、探索値のバラツキもそこそこ揃って、探索時間も予想できる範囲に。
メモリ使用量も安定しました。
ある棋譜に対し、２０手目から終局まで順に、深さ１～１７の探索を、反復深化を活用しながら
探索値を求めるプログラムを用意して、１４棋譜を対象に実行したところ凡そ７時間で完了。
速度的にはこんなものかなぁという感じ。もっとも、深さ１７だと結構、探索時間・ノード数の
バラツキが大きいので、１０件前後だと終了時刻もバラツクはず。
とりあえず、棋譜からランダムに１０件程度を抽出し、この探索結果を貯めていくところまで
作りました。トータル１００件程度集めれば、MPCパラメータ計算には十分だと思う。
探索結果を貯めてあるので、毎晩１０件くらいづつ追加し、直説法で都度パラメータ再計算
して精度を上げていく事ができる。
379:310
16/01/04 22:22:10.63 1p46+Vgy.net
MPCのための探索データ蓄積の間に、並列処理について調べてみました。
VC++だとopenMPとPPLってのが使えるみたいです。
?concurrent_unordered_mapが便利そうなので、PPLにしよううかなと。
で、脳内コーディングであれこれ考えていたら、AIの中でBoardクラスを参照渡しして、
差分型で盤面を進めたり戻したりしているのが、とても並列処理と相性が悪い事に
思い至りまして・・・。コピー型に戻して、何をクラス化するのかとか見直してみようかと
言う事に。
多分数日がかりになるかなと。
380:名前は開発中のものです。
16/01/04 22:36:46.74 iMclxIQO.net
Boardはスレッドごとに持てばいいんでない
スレッドを生成するときだけコピーすれば
381:名前は開発中のものです。
16/01/05 01:07:47.45 UyX0E5Wd.net
自分の場合は将棋作ってて、並列にしたけどstockfishのソースとか参考になるよ
スレッド待機させてノードの終わりの方で判定して、OKなら分割させて
そこで上でも言われてるけど、盤の情報をコピーして走らせるの
自分は盤面作成とか更新巻き戻しなどを最初スレッドとか考えてなく直にアクセスしてて
全てポイントにからに変更するのが、かなりだるかった
382:名前は開発中のものです。
16/01/05 20:35:26.92 zrGyzNpa.net
へーこのスレって意外と人いるんだなぁ
将棋作ってる人がいるとは驚き
383:310
16/01/09 02:12:28.10 GhyCVx1P.net
どもです。
とりあえず、コピー方式に変えてましたが、変にバグを仕込んだりして、時間がかかって
ました。ようやくデバッグもあらかた終わったのですが、まだ原因不明・解釈不能な速度
差があって、終盤探索のみ速度が１０％以上低下した状態です。
というか、コピー版を書きながら気づいた箇所を、ボードクラス版にも反映すると、ボード
クラス版が高速化して、差が広がるという。
で、クラス版がFFO#40で１．４０～１．４２秒になりました。
>>380さん
おっしゃる通りですorz
プログラム直しながら、ネットでVC++の解説をつまみ読みしながらのコーディングに
限界を感じたので、オライリーさんの出番という事で、アマゾンに本を数冊注文しました。
到着待ちの間にやるなら、適当に作っていったクラスの整理統合かなぁ。
あと、openMPのお勉強。
384:名前は開発中のものです。
16/01/09 02:32:30.66 Uphigh+6.net
最近のvc++使ってるのなら普通にstd::threadでやるのもいいかも
385:310
16/01/10 01:14:26.88 F6Uvkb4b.net
うわ。色々やり方あるのね。
VC++だとPPL、openMP、std::threadか。
PPLについては、逐次処理のまま置換表で使っているunordered_mapをconcurrent版に
変えてみたところ、置換表付探索の速度がおおよそ半分になってしまったので、結構
微妙な印象を持っています。
とりあえずopenMPでどこまでできるか試してみて、気に入らなかったらstd::threadで
細かく制御できないか考えてみます。
先ほど、コピー版で置換表登録に影響するバグ発見。直したところ、FFO#40が1.26秒
とかになってしまいました（汗）。不可思議な速度差の原因はこれで間違いないと思います。
edaxまであと１０倍の速度アップかぁ。並列化で３倍くらいまで詰められないかと期待。
一応、Boardクラスのポインタ渡し版（差分方式）も試してみましたが、今のところ、若干
速度低下しています。もともとの差分方式は、Boardクラスを継承したAIクラスのメンバ
関数として実装してます。
これらの一見無駄な作業も、バグ探し＆逐次探索の速度アップに有効だったという事でorz
386:310
16/01/11 20:31:40.39 IrhGHm3u.net
とりあえずopenMPで並列化トライしてみましたが、コンパイル中に内部エラーになる。
ネットで見ると最適化オプションがらみらしいけど、なんかよくわからなかったのでパス。
PPLを使って、とりあえず並列化のテスト。オセロでは標準的と思われるｎ段YWBCに
してみました。forループみたいな特定の形ではPPLは結構簡単という印象。
バグは一通りとれた状態だと思いますが、FFO#40で１．２５秒が０．８５秒程度になり
３０％強の高速化。あと少しだけソース修正するつもり。
使ってるパソコンは２コアでした。昨夜まで４コアのつもりでいましたが（汗）、２コアなら
こんなものなのかな。
387:名前は開発中のものです。
16/01/11 21:53:26.50 oLh2eOse.net
2コアYBWCにしてはまあまあ並列化されてるような感じ
もちろんもっと効率化はできるけど
388:310
16/01/13 13:02:44.01 Yd1pcfW8.net
どもです。
コア数２だと、理屈の上では２倍近くまでは速度アップできるのかなぁと思います。
一般的にはどのくらいの倍率をターゲットにしているのでしょうか。
YBWCの適用のパターンをいくつか試しましたが、タスクマネージャーで見たCPU使用率
は、ほぼ１００％になってるので、単純にはスピードアップは難しい感じがしてます。
PPL自身のオーバーヘッドなのか。
PPLは楽ちんだけど、チューニング箇所がなさすぎな感じ。
あと、YBWCやってる以上、YBの着手をmove orderingする意味が無い感じなので、
sortが一つ省けるかなぁというところ。ルートに近いので、あまり効果は無いと思うけど。
ここまで来ると、８コアのパソコン持ってきたら・・・
SIMD拡張命令だBMI命令だを使っておきながら、コア数２で頑張るのもどうかみたいな。
389:310
16/01/16 09:10:45.76 mjTPCiWE.net
PPLはMicrosoftのDeveloper Networkくらいしか情報が無いので、ひたすらリンクを
たどって情報収集してますが、ほとんど機械翻訳で、結局カーソルあてて英文読ま
ないと意味が分からないという・・・
で、排他制御とかいい加減にしていたノード数カウントなどをきちんとして、ソースの見易さ
と効率を上げようと色々と細かく修正。combinableとかcritical_sectionとかInterlockedとか。
と・・・思ったら・・・中盤探索で確率１０％程度で違う答えが返ってくる・・・
並列探査のバグはわかりにくくて時間を食ったのですが、どうもcombinableの動作が変。
期待した動作をしていない。でも、情報が無さすぎで、どこを直せば良いのかわからず、
結局同等の機能を動的配列にしてしまった。
390:310
16/01/16 11:37:48.70 mjTPCiWE.net
中盤探索を１万回程度回して、違った答えが返ってこない事を確認できました。
ノード数カウントはInterlockedIncrementを使っているんだけど、やはり排他待ちロスが
大きいようで、ノードカウントありだと０．８秒前後、無しだと０．７秒前後になる。
使えなかったcombinableみたいな形にして、一つの再帰関数内はローカル変数で加算
して、最後にまとめて１か所で排他加算するようにしてみようかな。
並列タスクの起動順で、探索ノード数が違ってくる関係で、実行時間のバラつきが±０．５
秒くらいになっている。
391:310
16/01/18 09:54:27.64 ED4vwFCp.net
結局、ノード数・リーフ数カウントは、戻り値を構造体にして返す方向にて検討。
普段の探索には不要だけど、solverだと表示したいので。
これで完全にローカル変数になり、排他ロスを気にする必要がなくなる。
デバッグ用の置換表回りの統計は、所詮デバッグ用なので、一旦全削除。
必要になったら、こちらは#ifdefで囲って、排他加算する。
で、構造体の形であれこれ悩んでいたら、戻り値をクラスにできる事に気が付いて・・・
あらためてC++すげーと感心中。
けど、かなり全面的な修正になるので、時間食ってます。
まずは中盤探索を修正して、ノード数がおかしくない事を確認。
終盤探索の修正はこれから。探索を使う系の統計処理も変更しなきゃならないけど、
MPC以外は、次いつ使うかわからないｗ
392:310
16/01/19 00:13:53.27 Dh1WPUXC.net
終盤探索の修正完了。
０．８秒±０．０５秒と、結局、Interlockedでグローバル変数のノード数を加算するのと、
大して時間が変わらないか、もしかしたら微妙に遅くなったかも。元に戻すのが面倒
なので、他で改良点を探すしかないかなと。
393:310
16/01/21 10:04:20.88 c00KCFqr.net
YBWCでは、最適着手手順（PV）のラインで置換表でmoveorderする意味が無いという事
を突き詰めていくと、いちいち前回探索の置換表を引くループを回して、都度最善の着手
を求めるのではなく、前回探索で得たPVを渡せば、時間が短縮できそうな気がしてきま
した。ツリーの浅い部分なので、全体にどれくらい効くのかはわかりませんが。
また、浅い探索などで最適着手手順を取得する時、negaScout＋置換表だと正しいscoutmiss
が発生した時に、nullサーチ時の置換表が適用されて、それ以後のPVが得られないという
事で、悩むところではあります。
まずは戻り値の構造体でPVを返すように改造して、効果を見たうえで、YBWCを適用する
深さでnegaScoutをやめてnegaMaxにするか、それともnullサーチは置換表適用外とするか
どれが良いか試してみようかなと思っています。
できるだけ高い位置で並列化した方が良いという指摘と、置換表もなるべく高い位置で
効かせた方が良いという指摘の、どちらを優先するのかですね。置換表はばっさり探索
をカットできるけど、並列化はカットせずに時短するので、置換表優先かなという気もして
いますが、高い位置でどれくらい置換表が効いているのかもわからないですし・・・。
394:310
16/01/23 01:31:00.95 0OQfWIYl.net
パソコン再起動すると、何かのタスクがCPUを３０％くらい占有してしまいます。
昨日まで快調に動いていたのが突然遅くなって、悩んでいましたが、これが原因のようです。
というわけで、本日は色々改変したソースの速度が計測できずに悶々としてました。
色々すったもんだ挙句、PVラインを渡す形にしましたが、効果があったかどうかは微妙。
色々付け足した事で生じた速度低下はペイしたかなぁという感じで、#40で0.78秒前後。
本格的にネタが尽きて来たので、ここから先は、MPCをきちんと実装してiterative widening
にかけるしかないかなぁという感じです。あと、定数で渡している置換表適用高さなどの
パラメータを、空マスや使用条件で作ると、実用的になるかな。
395:310
16/01/27 01:18:29.98 IVwAw5rN.net
オライリーの並列化本が来たので拾い読みしながら並列プログラミングの勉強。
PPLの各アルゴリズムが何を目的とするものなのかが、少しずつ分かってきました。
抽象化度が高いので、最初のとっかかりとしては良いかも。何故かcombinableが
上手く動かないとか、parallel_reduceの中身がよく分からないとかありますが。
で、並列化できるところを探して速度が上がるか試したり、同じ処理をより綺麗に書き
換えしたりして、微妙に速度アップし、0.70～0.75秒くらい、ノード数が15M、NPSが21M
nps程度になりました。たまに0.68秒台が出ます。
Edax4.3のFFOベンチの結果を確認したところ、ノード数で１．５倍、NPSで４倍、計６倍の
差があります。NPSをコア・クロック換算しても１．５～２倍の差があり、ノード数は別として、
まだ速度アップの余地があるのではないかという事で、単品速度アップに走ってます。
ノード数はMPC導入後のiterative wideningである程度追い付けるかなと淡い期待。
いくつか速度アップネタがありますが、サッカー日本代表見ながらでははかどらず。
続きは明日。
396:310
16/01/29 11:31:08.14 trvaxUQ+.net
先日の速度アップネタはすべて不発でしたが、その際にノード数のカウント漏れを見つけ
て、修正したところ、ノード数は１７～８Mという感じでした。その際に、最終２手高速化の
箇所でもカウント漏れがあり、まずは正確なノード数を簡便に把握しようと外してみたところ、
意に反して速度低下しないところか、どうも微妙に高速化したように見えまして（汗。
最終３手高速化を試してみたり、最終１手高速化も外してみたり、moveorder適用とか、
そもそもmobilityを求めずに空マスを順に着手してみるとか、その辺の適用深さを変えて
みたりいろいろとやって現時点の最適パラメータにしてみたところ、0.63～0.68秒、最速で
0.60秒が出るようになりました。
αβカットの効きが悪くなっているため、ノード数は２４～２５Mとなりました。
その分NPSは３７～３８Mと速くなっていますが、こんな方向で高速化してて良いのか？
というわけで、ノード数が違う段階でNPSを比較しても意味が無いという事に気が付きました。
397:310
16/01/30 20:51:37.62 yCKBToEa.net
囲碁がすごい事になってますね。オセロで一通り勉強したら小さい盤の囲碁をやって
みようと思っていたので、モチベーション低下中。とはいえ、ああいうのをオセロに応用
しようとしたら、あそこまでマシンパワーいらないんじゃないかとか・・・。
ここのところ、もっぱらSTLやPPLの機能を綺麗に使う方向での改良ばかりしてました。
pararell_reduceの使い方もわかりました。negaScoutの繰り返しループが綺麗に並列化
できたんじゃないかと。ただ、MAPする件数がしれているので、parallel_reduceではなく
逐次版のaccumlateの方が速いという結果に。あと、時間計測が結構飛び飛びの値に
なるので時間計測関数を精度１msのものに変更。
色々やった結果、若干高速化したうえで、時間のバラつきが消えてくれました。
１００回試行で計測すると610ms±15ms（１σ）となり、逐次処理のほぼ２倍の速度に。
ノード数は同程度で、NPSは40M超えて来ました。このNPSのままノードを半減できれば
良いのに。
398:310
16/02/07 21:48:19.14 xNqeS9Ve.net
ここら辺で、EDAXとかとの速度差の原因を考えたところ、次の２点が考えられました。
１．評価関数の精度が悪い可能性
２．個々の関数で速度アップの余地がある可能性
という事で、１は熟考が必要なので後回しで、速度アップの対象として、flipとmobilityの
高速化を検討。とはいえ、良い知恵があるわけでもないので、ネット徘徊。
現在、ポインタ関数で分岐して処理しているflip関数を１発で処理するopenCLのソースを
発見。Master Othelloの作者のものでEDAX4.3のflip関数を参考にしているらしい。
中身を解読するとベクターを使っている。とりあえず処理を真似て逐次処理で組んでみたら
結構速度アップしました。
解読の過程で、ようやくベクタ化の意味がわかったので、mm256系の命令を使って、
ベクタ化してみましたが、若干速度低下。原因は恐らくlzcntで一回ベクタを抜けてしまう
所だと思うので、ハッカーのたしなみを読んでベクタ演算で組み直してみる予定。
合わせてmobility関数もベクタ化。若干速度アップしたかなという程度。
組み込み関数は使い方が面倒臭いので、演算子のオーバーロードしまくってみました。
flip関数は非ベクタの分岐無しバージョン、mobilityはベクタという状態で、500msを切る
数字が出るところまで来ました。flipのベクタ化ができて、パラメータ調整するともうちょい
良い数字が出るかなと期待。
399:310
16/02/09 01:09:41.58 MeGl+gwc.net
flip関数続き
・lzcntを自前で組んでみましたが、やはり処理が重く速度低下。ボツ。
・右方向と左方向で処理が違うので、片側＋１８０度回転で、同じ処理にしてlzcnt不使用
にしてみたが、１８０度回転×４が重くて速度低下。ボツ。
・できるところまでベクタ化して、lzcnt以後はスカラ計算で、速度若干改善。
・上記からlzcnt後、再度ベクタ化してみたら、速度若干低下したのでボツ。
・64bit×４の値を代入する関数を変更したら、意に反して結構速度改善。
・闇雲に__declspec(align(32)) してみたら若干速度改善してバラツキ減少。
これらにより、450msくらいになりました。
ベクタ化はまだ何かありそう。
ちゃんと書いてなかったですが、途中からノート数カウントを外してます。入れると100ms
程度の速度低下になります。一応、デバッグ用に#ifで切り替えられるようになってます。
が、そんな状態なので、nps計算に意味が見いだせないという・・・。
続いて評価関数をベクタ化できないか考えましたが、BMI命令使っているので厳しい。
計算楽にするため、でかい配列を何回も引いているので、ここを何とかしたい気がする。
黒・白・空の３を基数とする３進数でナンバリングしているんだけど、高速で計算する方法
が見つからず。
平衡３進法を手早く計算する方法があると、黒を1、白を-1、空を0にして、定数足すとか
できるんだけど、どんなに調べても、基数変換に王道なしという言葉しか見つからない。
400:名前は開発中のものです。
16/02/15 00:14:34.50 2rfyeFpJ.net
高速化については一旦棚上げ。何やっても速度が上がらない。
ひたすらノード数カウントの速度低下を抑えて、カウントのバグ取りして。
色々発見はあったけど、結局ソースを綺麗にしただけだった。
後は、いずれゆっくり時間をかけて、評価関数を作り直すかな。
MPCを組みました。一応動作している模様。
これからしばらく、GUI作りに入ります。
MFCよくわからん。
401:310
16/02/20 13:43:08.30 ZGi2V8ih.net
GUIできた。昔作った序盤定石部分と合体。
中盤探索を反復深化にして、３秒を超えて新しい深さに入らないあたりで調整。
MPCで２５手くらいまで読めるように調整。
終盤完全読みは３８手から。３６手からMPC付で完全読み（つまり完全ではない）。
こんな感じでできたので、早速プレイ。自分だと軽く全滅負けしてしまうので、zebra先生
にお越しいただきました。が、滅茶苦茶弱い。
良く見ると、定石が効いている段階で＋１６だったのが、中盤読みになった瞬間に一気に
－１４くらいまで落ちて、そのまま挽回できない感じ。zebra先生は、その前に定石から外れ
て、既にzebraから見て＋１４程度の評価値を算出している。つまり、定石部分がおかしい。
それ以外は、評価値もzebraとは大きく違わないし、終盤探索もちゃんと機能している感じ。
402:310
16/02/20 23:06:47.33 ZGi2V8ih.net
zebra先生にならって定石の評価を表示するオプションをつけてみました。
ロジック的には間違いなさそうですが、定石DBがおかしいというか、定石に登録がない
手順に正しい変化があって、それを無視しているため、間違った判断をしているみたい。
一応、完全読みという触れ込みの棋譜を元にしているはずなので、使い方をどこかで
勘違いしているんだと思います。しばらく悩むしかなさそうです。
403:310
16/02/21 01:04:17.33 nPWuqcvw.net
試しに定石部分を外して、中盤探索で開始してみたら、zebraの２０手読みに対して
２戦して１勝１分となりました。読みの深さは、こちらが上なので、こんな感じでしょうか。
序盤２０手分は評価値が無いので、２０手近い探索を反復無しで探索するため、MPCを
使っても最初の数手は１手あたり５分以上掛かってしまいます。
定石については、以前にウェブで見つけてテキストに起こした定石データがあるので、
それを評価０で登録してみようかなぁと思っています。
定石の自己学習とか、評価付けとか、どうやるんだろ。
404:310
16/02/25 21:06:56.39 fXRsnvrs.net
定石データを、上記の手打ちデータで作り直しました。
当初は並び取りとかの極端な進行以外は評価０．０にしたため、mobility関数のビット列
の下から定石に従って着手する形となり、zebra先生のBookに誘導されるように、少しずつ
不利な定石に乗り換えていき、負けるという展開に（汗
悔しかったので別のソフトを拾い、戦ってみると、そちらには圧勝。決して弱くはないと思う。
また、zebraとの対戦時にBookで評価値がついているものは、それを参考に修正したところ、
時々勝てるような感じになりました。
EDAX先生＋UnifiedBookなるものを拾って、そちらと戦ってみたところ、軽く惨敗。
ｆｊｔ定石とかだと終盤近くまでBookがあるみたいで、Bookが続く限り紛れが無い。
こちらが中盤探索などでミスるたびに－２づつ落としていき、お話にならないレベル差を感じました。
しばし熟考の上、定石の拡張、評価付けを考えてみようかと思います。
あと、評価値が近い時には、何らかの確率で手を選択するようにもしてみたいと思います。
405:310
16/02/28 01:10:48.52 hQzoi2Tz.net
縦取り系は白番黒番試して、定石の評価値を修正してみました。
あと、AIの進行ごとのパラメータを試行錯誤して、なるべく負けないようにしてみました。
これにより、AIの読み時間が結構伸びて、１ゲームワーストケースで１手２分、トータル
５分くらい思考してしまいます。これは、反復深化などで、タイムアップをせずに、次の
ステップに入る制限時間だけ決めているためです。
EDAX＋Unified Book先生はレベル２１で、黒番白番ともに引き分けになります。
こちらは２０手前に定石が切れていますが、その後も最善手が打てているという事になり
ます。こちらは何局打っても手を変えないので、EDAX先生のBookの進行に合わせた
だけですが。一方zebra先生は比較的手をいろいろ変えてくるので、勝ち負けが発生します
（もちろん、各アプリの設定次第ですが）。
序盤定石の評価値をそれなりにしたら、後は引き分け進行をひたすら登録していって、
相手が最善しか着手しないと信用すると負けないプログラムができちゃうのではないか
と、ふと思いましたが・・・。トップ同士の対局が引き分けばかりになるのは、こういう事
なんでしょうね。というか、完全解析ってこれが完成した状態なのか。
EDAX先生のUnified Bookは、いくつかの引き分け進行棋譜の集合体のようですが、
元データが幸い既知のWthor形式なので、それをもらってしまうと、トップレベルになる
のかなぁ。トップな人がBook構築に主眼を移したり、開発が止まったりする訳だと。
そろそろ、混とんとしているプログラムを綺麗に直して、パクリBook作って開発終了しちゃ
おうかと思い始めています。速度的には、まだまだ改善の余地はありそうですが。
406:じょげなら ◆kXDiHQuNQ2
16/02/29 19:18:07.19 etqtABZA.net
ライフゲーム囲碁というゲームのネット対局場を作りたいです。
囲碁でいうKGSみたいなのが理想です。
プログラムはある程度わかりますが、ネット関連の知識が乏しいです。
何から始めればいいですか？
407:名前は開発中のものです。
16/02/29 19:21:39.28 etqtABZA.net
ＵＲＬがＮＧワードに引っかかる…
408:名前は開発中のものです。
16/02/29 19:34:26.59 etqtABZA.net
好きな言語
C++
C#
Ruby
嫌いな言語
Java
Python
Perl
409:４０６
16/03/01 20:52:33.32 6wFQeZGp.net
とりあえずHTML5の本買ってきた
410:406
16/03/03 19:44:49.47 Hi4nZgiL.net
URLﾘﾝｸ(fast-uploader.com)
碁石をぽちぽち置けるところまで作った
411:310
16/03/04 10:15:09.55 Q4DtXsqP.net
>>410
一晩考えてみた。
通信回りに興味を持って遊んだのは１５年くらい前だし、Javaとかイメージしかないし。
あまり助言できる事はありませんが、一つ言えるのは、UIに凝ったりサービス内容を
考えたりするのは最後で良いと思います。
Rubyが好きなら、まずはCGIベースで、テキスト表示で対戦を実現する仕掛けを作る事
だと思います。次に複数のユーザーが接続するのであれば、身元確認のためのID/パス
ワード管理が必要になりますし、個々の対戦を区別するにはセッション管理が必要になり
ます。この辺は、スタンドアロンのアプリには無い、独特の世界なので、結構新しい技術、
テクニックの習得が必要になるかと思います。いまどきあるのかわかりませんが、チャット
のスクリプトとかあれば、参考になるかも。
その辺から入り込んで、いろいろ調べていくと、だんだんと必要な技術、知識が増えてくる
んじゃないかと思います。
412:406
16/03/04 18:58:38.77 w3YPuhPg.net
>>411
レスありがとうございます。
確かにセッション管理とか知らないです。
チャット調べてみます。
413:406
16/03/07 21:05:27.22 NI+TTWmM.net
RoRの本買ってきた。
チャットはまだ調べてない。
414:名前は開発中のものです。
16/03/09 19:45:29.94 Cf1/SDqU.net
うおおおおセドルがああああぁぁぁ
415:310
16/03/10 02:00:10.79 hvbQwbFh.net
うむむ。
これにて、オセロができたら次は囲碁という目標が雲散霧消してしまいました。
どうしよう。
416:310
16/03/10 18:05:03.79 b1SmaPOg.net
AlphaGO強すぎ・・・orz
今夜は、囲碁関係者だけじゃなく、AI周りの人も、Google以外全員お通夜ですね。
417:名前は開発中のものです。
16/03/10 19:38:43.78 SphVvbk5.net
３１０氏もalpha碁注目してたか。
セドル一発入れてほしいなぁ
418:名前は開発中のものです。
16/03/11 09:04:36.30 HTdTU0Fi.net
浮上
419:名前は開発中のものです。
16/03/12 12:19:15.41 k2nAbsiz.net
おお、このスレ生きてたんだ
なんで RoR なんか見てるのよスレ間違えたかと思った
420:名前は開発中のものです。
16/03/13 18:01:59.50 X9umXTnK.net
せどるううううッよくやったあああああぁっ
人類の勝利やあああぁぁっ
421:名前は開発中のものです。
16/03/13 19:02:49.19 Gv0++KTh.net
お、第四局はセドル勝ったか
422:310
16/03/13 20:47:23.70 50OeMIN8.net
うむ。なんか期待を裏切られっぱなしｗ
この負けっぷりを見ると、囲碁もトライしたくなってくる希ガス。
423:406
16/03/15 20:44:49.53 NF77F+OG.net
RoRとjavascriptの連携がよくわからん。
でもちょっとづつだけど進んでる。
424:310
16/03/16 23:06:52.43 YEZK1fac.net
アルファ碁ロスまっただ中ですｗ
オセロ作ったおかげで、一連の勝負をいままでとは違う視点で見れたかなぁ。
とりあえず、囲碁のモンテカルロ解説した本と、ディープラーニングの入門書を
買ってきた。さらっと読んだけど、ディープラーニングは理解に時間がかかりそうorz
オセロで３層パーセプトロンを試したときは、結局うまく動かなかった。
実装が悪いのもあるけど、学習にもすごく時間がかかった。
あれをディープにしたら、どうなっちゃうんだろうかは不安ではある。
こちとら、SurfacePro3しかないし（汗
425:406
16/03/19 20:06:25.11 Ik15FlWh.net
railsでdeviseとかいうgemをつかってユーザー認証機能実装したけど、
複数ユーザーがログインして対局させる方法がサッパリわからん。
426:406
16/03/24 20:20:54.97 C08ak5N3.net
ブラウザ閉じたときに自動ログアウトのやり方がわからん
427:名前は開発中のものです。
16/03/25 13:51:48.34 9Ea9sx62.net
ブラウザは通信があった時にしかクライアントの消息が確認できない。
ｎ分アクセスが無かったらサーバー側で勝手にログアウトさせちゃう
タイムアウト方式が普通かなと。その時間経過後にアクセスがあっても
ログインからやり直し。
このログインからタイムアウト（ログアウト）までの間をセッションと呼ぶ。
428:名前は開発中のものです。
16/03/25 14:16:19.46 9Ea9sx62.net
１行目おかしかった。
＞WEBサーバ、ブラウザという仕組みは、ブラウザから通信があった時にしか、
＞サーバーはブラウザの消息を確認できない。
に修正。
１．初画面からログインする
２．サーバが、HTMLにセッションNoを埋め込んで、ブラウザに表示。
サーバでは、セッションIDを配列などで管理して、IDと最終アクセス時間をとっておく。
３．ブラウザ側からのCGIリクエストには、必ずセッションNoを入れて送信。
セッションNoで、相手がだれか（ID)を特定して、処理を行う。
つまり、個々の処理はセッションNoで管理されている。
４．ブラウザからCGIリクエストが来た時に、タイムアウトしていたら、ログアウト処理へ
あと、ゴミ掃除で１日１回くらいタイムアウトしているものを削除。
この辺が基本。対局型の場合。
５．２つのセッションが対局している事になるので、対局管理する配列を用意。
６．相手の着手待ちの時に、どうするのか？その辺が肝。
HTMLに細工して、１秒ごとにリロードさせる。リロードにより、着手が行われたか
それとも秒読み時間切れになったか？判断をサーバーに依頼する。
などなど。やり方は色々あるかと思う。
とにかく、肝は、情報がブツ切れで、あちこちにある事。これにより、サーバーで簡単に判断
ができない事があるので、いくつかの機能をブラウザスクリプトに依頼しなきゃならん。
それでも、相手が放置して逃げた時、ブラウザを閉じて逃げた時（回線切断やPCダウン）、
などなどの例外が起きるので、それらをタイムアウト検出などで拾わにゃならん。
どうするのかなどの、例外処理をリストアップして、一つずつ対応を決めていく事。
プログラムテクニックはどうとでもなるけど、例外事象の拾い上げの方が大変。
429:406
16/03/25 17:43:19.31 /V6G/Eic.net
丁寧にありがとうございます。
javascriptのwindow.oncloseからなんとかならないかといろいろ調べていましたが、無理筋なんでしょうか。
タイムアウト検討してみます。
430:名前は開発中のものです。
16/03/26 21:27:54.24 DUGO8n57.net
>>429
そういう事を考えるんなら、Javaアプレットとか、ActiveXとかの、
ブラウザ上で動いて通信できる方法を試した方が良いかもね。
431:406
16/03/30 21:45:07.64 yYbYes7U.net
すいません、教えてください。
４．ブラウザからCGIリクエストが来た時に、タイムアウトしていたら、ログアウト処理へ
あと、ゴミ掃除で１日１回くらいタイムアウトしているものを削除。
このゴミ掃除というのはサーバー側がクライアント側から何のアクションも受けずに
能動的にタイムアウトしているセッションをみつけ削除するということですか？
どうやって書けばいいのかわからないのですが…
432:名前は開発中のものです。
16/03/30 23:26:15.10 DNbQONAE.net
>>431
そうです。別にしなくても良いし、月１回手作業で削除しても良いけどね。
433:406
16/03/31 20:31:39.10 dkaj1Oq1.net
>>432
手作業ですかうーん。
まあ、頭の片隅に置いておきます。
ありがとうございます。
434:名前は開発中のものです。
16/04/01 19:52:02.46 JLskKsZt.net
隠しコマンド受け付けるようにしておいて
管理者のクライアントから定期的にコマンドを投げればいい
435:310
16/04/05 10:45:13.03 82XTVDoH.net
久々登場。アルファ碁ロスがでかすぎて、やる気がでないです。
とりあえず、BOOK上で乱数入れて手をばらけさせるようにしました。あとの課題は、
１．持ち時間制度
２．ステータスバーの更新
標準のStatusBarだとOnMouseMoveなどで更新されるとの事。
リアルタイムに更新させるためには、マウスくるくるさせてなければならん。
３．中盤探索の高速化
反復深化＋置換表で高速化が効いていない懸念があるけど未確認。その他の高速化検討
４．同じ手順で負けないためのBOOKの自動学習
５．オフラインでの引分手順の自動生成
となります。けど・・・本当にモチベーション上がらない。
時々、気が向いた時に、Zebra先生やEDAX＋UB師匠相手にポチポチ手打ちで対戦して、
相手のBOOKに登録されている引き分け手順を見つけて、手入力でBOOK更新してます。
Zebraは研究モードがあるので、ほぼ拾い終わりましたが、逆に引き分けだらけになりました。
EDAX+UB相手だと、こちらが定石から外れるケースでも、EDAX側は学習データで先が
見えていて打ってくるので、ほぼ負けになります。
たまに、EDAX＋UBも中盤探索が走ってくれて、極まれに勝勢になる事がありますが・・・
何が腹が立つと言って、そういう時に限って完全読み時にEDAXがバグって、既に石がある
所に着手して逆転した事にされます。もちろん反則なので勝利は勝利ですが、すっきりと
勝たせてもらえないのが腹立たしい。をのれ。
というわけで。やはりオセロは、引き分け手順のリストアップが、強さの肝である事も再確認
してしまいまして。そこまでの根性は無いなぁというのも、モチベーション低下の原因。
436:406
16/04/06 22:31:38.47 SXJnF3U3.net
ログインユーザー一覧表示できるようになりました。
RoRのコーディングは一休みして棋譜管理にとりかかろうと思ってます。
SGFをパクろうかとおもってますが、結構難しい orz.
437:406
16/04/08 22:18:30.78 kkoRA2nm.net
棋譜ツリー表示すんの結構メンドクサイような希ガス
いいライブラリはないんか
438:406
16/04/09 23:59:42.58 SBv5rCvL.net
KGSのレーティングシステム難しい。
まだそんなこと考える段階じゃないけど。
439:406
16/04/11 21:25:49.37 A4FL2sT8.net
javascriptでオブジェクトの比較ってjsonで変換してそれを比較しろとか某ページで見たけど
そんな事せにゃならんの？
440:406
16/04/12 23:02:53.74 xYnFmhAQ.net
URLﾘﾝｸ(textuploader.com)
棋譜ツリーだいぶ形になってきた。
441:406
16/04/16 22:59:10.60 MXucFBba.net
Rails側とjavascript側の連携がやっぱわからん。
色々めんどくさすぎ。
442:406
16/04/23 00:16:56.63 Gce7F8Ms.net
エンコード間違えてて動かなかったわ。
railsがログ吐いてくれてなきゃ一生気づかなかっただろうな。
443:406
16/04/27 21:48:14.23 JGExYAi7.net
開発に使ってたノートのキーボードが一部効かなくなったわorz.
windowsにログインできなくて焦った。
アカウントでも乗っ取られたのかと思ったらソフトキーボード使ったらログインできた。
ＵＳＢキーボードとかで代用できればいいんだがどうかな～。
444:406
16/05/02 21:58:59.67 i7WwatVD.net
invalid multibyte character
とかってエラーが出るんだけど、どこに全角があるのかさっぱりわからん。
app/controllers/application_controller.rb:1にあるらしいんだけどいくら調べてもみつからん。
445:406
16/05/02 23:06:51.86 i7WwatVD.net
以下のログが出るんだけど、だれか原因わかる人いない？
Started GET "/" for ::1 at 2016-05-02 22:55:10 +0900
ActiveRecord::SchemaMigration Load (1.2ms) SELECT "schema_migrations".* FROM "schema_migrations"
ArgumentError (invalid multibyte character):
app/controllers/application_controller.rb:3:in `<top (required)>'
app/controllers/home_controller.rb:5:in `<top (required)>'
446:４０６
16/05/03 11:00:58.43 6pwgCgml.net
すいません、解決しました。
447:４０６
16/05/13 22:42:29.22 Zx20RSfa.net
やはりポーリングだけでは限界があるか？
448:310
16/05/16 21:32:31.63 KQ1qSDyb.net
モチベーションダダ下がりだったけど、なんとなくソースの整理していたら、
直したいところがいろいろ出て来て、見直し中。
後ろ向き枝刈で探索時間は変わらないけど、探索ノード数が2/3になった。
この枝刈手法の速度アップできたら面白いかもと思いつつ、元々自分が
結構高速に書いていた処理（未使用）を流用しているから、これ以上速度アップ
できるかわからん。
でも、EDAXには勝てないんだろうなぁ・・・
EDAXの孫情報からインスピレーション得てるネタだし。
449:310
16/05/26 16:01:37.05 ZBCA70ec.net
遅々として進んでいます。
ソースを一から組みなおして、いろいろと綺麗にしてます。
並列探索を入れない段階で、FFO#40が結構速くなった。
いまさらながらに、FFOテストを40～59まで実行して比較しようとしたところ、
前から薄々気づいていたけど、FFO#41以後が遅い。酷いケースになると
探索ノード数が１０倍＝時間も１０倍になる（#51）。自分のは指数関数的に
比較的にきれいにノード数が増加している。同じようなノード数のものもあるので、
ZebraやEdaxはどこかで上手にばっさり刈り込んでいる感じ。#52以後は時間が
かかりすぎて、未検証ですが。
ZebraやEdaxもノード/秒が一定しているので、置換表みたいな重い方法では
なく、簡単な方法で刈り込んでいるっぽい。とすると、moveorderかなぁ。
一応、MPCの99%で評価値の並び順は置換表に残してあるので、そんなに
間違った順番でソートしていないと思うんだけど。
あと、mtd(f)だと最初から最後までNullサーチしかしない事に思い至り、そこで
処理の効率化できる箇所が無いかと考えてます。Nullしかやらないんなら、
アルファ越えの再探索でウィンドウを広げる必要もないわけで。逐次探索部分
では効果不明だけど並列探索だとYBWCでPVを検索し終わるまで待つ必要が
そもそもない（仮アルファを求める必要がない）ので、多少速度アップできない
かなぁと。
450:310
16/05/27 00:36:10.52 gIFpjm1c.net
早々に状況が判明しました。ここに書くと進むんだよなぁ。
mtd(f)＋negaScoutで繰り返し探索しながら、置換表に置換データを置いて、更に
それを並び替えに利用していたのですが、最初にPVを探索してしまうと、その後は
別の着手も評価値がαになってしまい、並び替えの意味が無くなっている感じです。
ちなみにPVだけは別ルートで必ず先頭に探索するようにしてあります。
というわけで、テスト的に初段のみ敢えて並び順を逆転させてmtd(f)を未使用にして
ただのnegaScoutで、mpc99%→全探索をしてみたところ、探索ノード数がかなり減り
ました。置換表使用の深さ全部で並び順を逆転させてみたら、mpcの99%ですら全く
終了する気配がなくなりました。
さて、どうやって実現しようかなと。
今のところ、mpcはかなり高速なので、これをnegaMaxにして。
いわゆる並び替え専用の浅い探査にしようかなと。
451:406
16/06/27 22:12:32.72 rUgIsnK8.net
対局場は結構難しいorzので一旦横に置いておいて
手始めにもうすこし簡単な１人ゲームからPHPで作ろうと思ってます。
具体的にはこれ
URLﾘﾝｸ(www.vector.co.jp)
の一人プレー場とランキングを作りたいです。
元ネタはコンウェイの天使と悪魔という問題みたいですね～。
452:406
16/07/02 23:28:52.20 qo9Pciu3.net
URLﾘﾝｸ(textuploader.com)
とりあえず、HTML & javascriptでシコシコ書いてます。
だいぶ大分形になってきました。
遊んでみてください。
453:406
16/07/02 23:40:37.16 qo9Pciu3.net
なんか文字化けしてんなぁ
なんでだ？
まあいいか
454:名前は開発中のものです。
16/07/14 21:31:20.75 GXGadAU3.net
必殺技が使えるリアルタイムアクションオセロまだですか
455:名前は開発中のものです。
16/07/17 23:40:28.28 M3Q2Msci.net
とりあえず公開しました。
ランキングはまだ未実装です。
URLﾘﾝｸ(nagata442000.xxx.ne.jp)
xxxはさくらに変えてください。
456:455
16/07/18 00:05:57.51 Lx2YZiAH.net
455=406です。
457:406
16/07/21 23:55:32.48 oilR8wYn.net
うーんアクセスがないぜ。
検索エンジンにも引っかからないし。
SEOとかいうのに手を染めるしかないのか？
458:406
16/07/27 00:25:34.27 42/ungMS.net
結果を保存できるようにした。
459:406
16/07/27 22:44:58.98 42/ungMS.net
棋譜を登録＆閲覧＆再生できるようにした。
そろそろ宣伝かな～。
460:名前は開発中のものです。
16/08/01 12:39:59.89 BFi+UVWj.net
このようなスレがあるとは…
自作でオセロソフトを作成している者です
現在は自己対局による学習中です
初手f5
以降ランダム7手～8手、
中盤8手読み
中盤で次善手を85%の確率で一手のみ打つ
終盤20マス空き読み切り
で300万棋譜集めようかと
この設定であれば一局1～3秒程度なので２ヶ月半くらいで達成できる予定です
まだ86万局程度ですが、今のところFFOはこんな感じです
FFO#40 (a2:+38) 1.36sec FFO#41 (h4: +0) 3.75sec
FFO#42 (G2: +6) 4.86sec FFO#43 (C7:-12) 6.33sec
FFO#44 (B8:-14) 9.46sec FFO#45 (b2: +6) 64.88sec
FFO#46 (b3: -8) 13.20sec FFO#47 (G2: +4) 5.66sec
FFO#48 (F6:+28) 67.74sec FFO#49 (e1:+16) 121.90sec
FFO#50 (d8:+10) 376.73sec FFO#51 (E2: +6) 86.08sec
FFO#52 (a3:+0) 132.61sec
461:406
16/08/02 00:17:59.05 R38aaX9h.net
だれかSEOのやりかた教えてくれ。
462:460
16/08/02 09:44:26.07 /HFRnWj4.net
白の得点が微妙にマイナスに傾いているので9手目までランダムに固定しました。
初手はf5なので8手目までだと白の方がランダム手数多くなってしまうことに気づいて・・・
9手目ランダムだと7手目までの評価値はまともな値にならないのですが、そこはBOOKでどうにかしようかと。
まともな値にならないだけで、互角定石以外に進行したりとかはしないので、とりあえず無視します。
463:406
16/08/02 20:37:12.35 R38aaX9h.net
Google検索で引っかかるようになったみたいです。
でもコンウェイの天使と悪魔なんてワード検索する人そんなにいないだろな。
464:310
16/08/03 14:35:23.97 WXOcEHjz.net
ここしばらく、評価関数に新機軸をと、ディープラーニングにトライ中ですが、
囲碁のように、畳み込みの画像認識の応用では、なかなか上手くいかないと
言うか、自分のパソコンで手におえるくらいの規模のネットワークだと全く歯が
立たない感じです。
というわけで、色々と手はいっぱい動かしているのですが、何にも成果があら
われていない状況です。
465:名前は開発中のものです。
16/08/03 22:36:32.67 u2EcbVrc.net
>>464
ディープラーニングってライブラリ使ってんの？
それとも自家製？
466:310
16/08/04 01:59:01.51 XH3ZGPYC.net
>>465
最初はGitHUBのDeepLearningの参考プログラムを元に自家製でAutoEncoderにDropoutをつけ
たりしてました。
次にCNNで、GitHUBでtiny-cnnというライブラリを落として使用。技術的に凝りすぎライブラリで、
解読するのにC++の勉強が主になってしまいそうなので、改造はあきらめました。
そして、今は、行列ライブラリ（Eigen）落としてきて、自家製に戻りつつあります。Sparse正則化の
ために、ミニバッチ処理をしようかと思って（最初のは逐次処理のみ）、ついでにAVX２命令や
並列化対応を、この行列ライブラリに頼ろうかと思ってます。
Eigen使ったMLPでxor解くテストプログラムは、さきほどできましたが、本当にこれで良いのか、
結構不安です。多少間違っていても、収束しちゃうときがあるので。
明日はAdagradに対応させる予定。何とか２～３層程度で収まらないかな。
パソコン環境が貧弱なので、あまり重い処理ができないのが最大の難点です。
もっとも、できあがった評価関数が重いと、探索深さが浅くなってしまうので、ある程度は妥協
しなきゃならんかなと思っています。
467:名前は開発中のものです。
16/08/04 22:03:08.50 5/KmfpOW.net
壮絶やな。
その情熱がうらやましいぜ。
468:310
16/08/05 20:44:21.05 sOgjr/Uz.net
楽しんでやってますので（笑
で、AdagradとSparse正則化ができました。Sparse正則化は思ったより時間がかかり
ませんでした。さすが行列ライブラリって感じです。AdagradとSparse正則化込みで、
結果も、正則化もちゃんと出来てますので、多分間違いはないでしょう。
今夜はオセロ関連ライブラリ持ってきて、学習データ作って、Sparse Auto Encoder
にしてテストです。全結合層クラスを積み重ねていくだけだし、データ作成は３回目
なので、後は簡単ですが、隠れ層のノード数と、目標とする活性ノード数を色々試す
のが面倒です。
まあ、ここまで全敗なので、あんまり期待していないけどさ（汗
やればやるほどBuroさんの評価関数の凄さがわかってきます。
469:460
16/08/08 01:32:00.53 1caSYJwt.net
PV-LINE(最善の着手リスト)の表示を実装してみました。
PVノードの更新は非常にまれな事象ですが、あまり深い所で表示更新すると
やはり探索速度に影響与えてしまうので、6手目以下の浅いノードで表示更新しています。
あと自己対局棋譜が100万局集まったので、中盤MPCパラメータを作成中です。
現在20手読みのカットペアの計算に入ったところで、これが終われば終盤MPCの実装に入ろうと思います。
470:名前は開発中のものです。
16/08/10 01:12:31.39 BL+f+Yy5.net
310と460はホントに別人なのか？
ディープにオセロＡＩに取り組む人が２人も現れるとはにわかには信じがたいｗ
471:310
16/08/10 22:37:11.88 C09Nh62j.net
>>470
他のスレで出会って、誘導させていただきました。
ほんと絶滅危惧種ですよね（汗
Auto EncoderにSparse正則化を加えましたが、やっぱり特徴抽出は
簡単ではないようです。Auto Encoderとしては申し分なく機能している
のですが・・・線形回帰をつけて評価値を算出してみたのですが、ただの
乱数返しているような状態になります。
なんか、微妙に恒等変換を学んでいる臭いんだよなぁ。むむむ。
472:名前は開発中のものです。
16/08/10 22:53:03.62 BL+f+Yy5.net
>>310はかなりハイレベルだと俺は思ってるが
>>310からみて>>460はいい線行ってるの？
473:310
16/08/11 23:18:44.20 M0iE7EXH.net
>>472
僕は全然ハイレベルじゃないですよ。
すぐ脱線して役に立たないことばかりやってるだけです。
別スレでお互いのFFOテストの結果を見せっこしたところ、
前半５つで、速度はほぼ同じくらいでした。
>>460さんと情報交換したところ、末端ノードの高速化の
方向性が全く逆だったのが意外でした。
474:名前は開発中のものです。
16/08/12 00:22:58.37 +2V5AEwc.net
ほほう
460さんも期待出来そうですな
475:460
16/08/12 02:42:42.36 mvQ0iJdF.net
>>472
自分はディープランニングなどの人工知能系はさっぱりなので・・・
310さんはよく勉強されていると思います。
自作オセロですが、今まで32bitで開発していましたが
今ではもう32bitOSを使用する方が稀だと考えて思い切って64bitに移行しました。
探索ノード数がいきなり10～20%程度上がってビックリしています・・・
476:460
16/08/12 04:26:50.73 mvQ0iJdF.net
あ、探索ノード数ではなく探索速度ですｗ
終盤探索だと10000Knps～15000Knps程度出せるようになりました。
自分の環境だとWZebraが20000Knpsなので、大幅に負けています・・・
そろそろチューニングも視野に入れつつやっていこうと思います。
まずは探索ノード数を終盤MPCで削減しなくては・・・
477:460
16/08/12 07:59:35.21 mvQ0iJdF.net
64ビット移行＋120万局の学習でFFOテストの結果をまとめました。
32ビット＋86万局の学習だと合計が17219.7sだったので36%ほど高速化しています。
シングルスレッド動作なので、将来的にはマルチに移行したいところ・・・
OS:Win10 CPU:i5-6500 キャッシュサイズ:128MB
FFO#40 (a2:+38) 1.04s FFO#41 (h4: +0) 3.22s
FFO#42 (G2: +6) 4.01s FFO#43 (G3:-12) 13.10s
FFO#44 (D2:-14) 3.22s FFO#45 (b2: +6) 58.63s
FFO#46 (b3: -8) 10.27s FFO#47 (G2: +4) 4.60s
FFO#48 (F6:+28) 36.09s FFO#49 (e1:+16) 50.33s
FFO#50 (d8:+10) 354.14s FFO#51 (E2: +6) 59.20s
FFO#52 (a3:+0) 142.79s FFO#53 (d8:-2) 656.87s
FFO#54 (c7:-2) 1718.85s FFO#55 (G6:+0) 5588.48s
FFO#56 (H2:+0) 314.27s FFO#57 (a6:-10) 1045.01s
FFO#58 (g1:+4) 973.58s FFO#59 (g8:+64) 0.25s
合計11037.95s（トッププログラムは合計で600秒台orz）
478:460
16/08/12 08:01:32.72 mvQ0iJdF.net
>>477
FFO#56はH2:+0ではなくH5:+2に訂正です。。
479:310
16/08/12 15:16:23.38 USoZXJIB.net
がーん。今まで、こちらはノートPCだしと、密かに思っていましたが、32bitでしたか・・・。
完全に脱帽です。
だったら、僕もこのスレで教わったAVX2とかBMIとかの組込関数使って、あとPPLとか
OpenMPとかで並列化して４コアなら３倍強程度なので、トータル４倍以上に速度アップ
すると思いますよ。つまり、その辺やるだけでEdax並まで行くかなと（汗
ちなみに、DeepLearningはあきらめ方向にだいぶシフトしてきました。
480:名前は開発中のものです。
16/08/12 16:41:11.53 8u/4Xx1J.net
仲間が出来ていいのう
481:460
16/08/12 17:56:57.44 wDmYSTDl.net
シングルスレッドだとトッププログラムですら合計2000秒台と限界があるので、マルチスレッド対応は必須ですよね
ただybwc等の並列化アルゴリズムの理解に時間がかかりそう…
482:310
16/08/12 20:50:39.55 USoZXJIB.net
>>481
YBWCはnegascoutのnull window searchを並列化して一括処理する
ようなものだと解釈して実装しました。
この辺はゲーム計算メカニズムなる本で勉強したかな。
並列処理のフレームワーク何使うかが問題ですね。
自分はVC++なのでmsdnで情報が得やすいPPLを使いました。
インテルTBBとかOpenMPなんてのもあります。
PPLは結構使いやすかったですが、速度は不明。
まあ、ルートの方でしか使わないので、あまり影響ないと思っています。
手組でマルチスレッドなプログラム書ける人には不要かも知れません。
483:310
16/08/13 14:18:44.65 D+1dBs0T.net
あ、考え方がnegascoutみたいだという事で。
484:名前は開発中のものです。
16/08/13 20:35:07.80 p7EbJiId.net
avx2って256bitだよな
オセロだと128bitしか使えないような？
485:310
16/08/13 20:47:52.09 D+1dBs0T.net
方向が８つあって、それぞれの処理を８回計算するとき、
右シフト方向が４つ、左シフト方向が４つ。
256bitは64bit×４。右シフトと左シフトで２回。
というわけで、mobilityとかflipとかで便利に使えます。
486:460
16/08/14 16:41:37.52 ALD5heTO.net
現在、終盤用MPCパラメータ作成中です。
23手完全読みのカットペアに入っています。24手読みの計算が終わったらいったん実装に入るつもりです。
>>310
YBWCに関して調べましたが、そうみたいですね。
MPCパラメータを作成している間に、なんとなくで適当に実装してみましたが
なぜかエラーで落ちまくりでしたｗ
排他がかかっていない致命的な箇所があるのか・・・置換表は排他をかけたのですが・・・
PVライン生成あたりも怪しい、とりあえずもう少し調べてみないとダメそう。
487:460
16/08/14 16:42:16.06 ALD5heTO.net
>>310は>>482の間違いです。。
488:名前は開発中のものです。
16/08/17 21:19:58.40 Z2gXWq7v.net
俺もボードゲーム系ＡＩでディープラーニング書いてみたいと思ってるけど難しいんだろな。
論理もそうだけど膨大なデータが必要そうだし。
>>479
どのへんで諦めました？
489:310
16/08/18 15:43:08.07 7GnJQiSP.net
>>488
まだ細々やってます（汗
Eigenの導入と、少しづつ進んでいくC++技術のおかげで、前よりは試行の
スピードはアップしていますが、なかなか成果は出ません。まだ、色々な
パターンを試しながらディープラーニングって何ぞやを体感しているところ
なんだと思います。
少なくとも「簡単に凄い事ができそう」という幻想は捨てる事ができました（汗
ボードゲームがターン制なら、基本はmin-Maxになると思います。
まずは、盤面の状態に（恣意的で構いません）点をつける評価関数作るところ
から始めたらどうでしょう？
次のステップで評価関数に統計（線形回帰）を持ち込むと、ディープラーニング
じゃなくても、プレイ譜がたくさん必要になります。
オセロの場合は、Buroさんという先人が、実用レベルの評価関数が線形回帰
で作れる事を示してくれています。
僕がディープラーニングを適用しようと思っているのは、ただの思いつきでして。
場合によっては、より軽くて正確評価関数が作れるかと思いましたが、実際に
始めてみると、なかなか評価関数として機能してくれないし、仮にできたとしても
重いものになっちゃいそうという感じです。
490:488
16/08/19 23:15:11.39 i9HkvHw2.net
>>489
手動評価関数はかなり昔五目並べで書いたことあります。
min-maxで思考時間が１手５分くらいかかったけど、
自分でプレーして負かされることもあるくらいの強さにはなりました。
そのBuroさんの線形回帰とやらはWebで論文とか見れたりしますか？
読んでも多分理解できないだろうけどちょっと興味あります。
491:488
16/08/19 23:23:27.55 i9HkvHw2.net
ぐぐったらこんなのがあったけど多すぎ。
URLﾘﾝｸ(skatgame.net)
492:310
16/08/20 16:51:13.03 m44rb9b4.net
>>490
Buroさんが作った伝説のオセロプログラムがLogistelloです。
Thellというオセロプログラムの作者の方が日本語で解説してくれています。
URLﾘﾝｸ(sealsoft.jp)
5.2の計算の高速化のところの説明（P.8の冒頭）のところ。
自分なりに解釈したら、自分が解釈違いしたのか、説明がおかしいのか、
この通りではなかった記憶があります。
とはいえ、これはオセロの考え方であって、将棋なんかだとbonanzaなどを
参考にすべきだし、全く別のゲームであったら、別な事を考えなければなり
ませんね。当たり前ですが。
493:488
16/08/20 20:33:47.55 +7ONDgCM.net
>>492
パターンの重みの線形和が評価関数になる的なことが書いてあるっぽいですけど、
パターンというのは人間が与えてやるわけですよね？
そのパターンすら学習で求めるというのがディープラーニングなのかと思ってますけど。
まあディープラーニングにはロマンがありますね。
494:310
16/08/20 21:29:23.21 m44rb9b4.net
>>493
ですです。
あと、Deepじゃなくても、２層以上のパーセプトロンだと、線形分離不可能問題の
分類ができるようになります。XORの学習が典型ですね。
ところが、パターンの部分まで学習で求めてくれるってのは、やっぱり幻想でして。
ある程度パターンを想定しながら、ネットワークを作らないといかんのではないか
という事に思い至っています。
例えば畳み込みニューラルネットワーク（CNN）で、何故畳み込みをするのかという
と、縦線横線などの隣接ドット同士もつながりを識別してもらうためですし。そもそも
畳み込みのフォワード計算自体が、画像に対して例えば輪郭線強調といったフィル
ターかけるのと、プログラム的に同じものだったりします。学習対象は、フィルターに
なります。
オセロは、囲碁とかと違って、石の色がコロコロ変わるので、隣同士の石のつながで
判断するCNN的なネットワークをそのまま適用できないよなぁというのが、最近の諦め
ポイントであります。
じゃあ、何に頼るかというと、自分はオセロ弱いので・・・No ideaだったりします。
あんな簡単な（DeepLearningと比較して）線形和でBuroさんの評価関数ができています
ので、パターンを活かして、まずはそこに点数を割り振るところをMLPなんかでできない
かなぁと思っています。