[過去ﾛｸﾞ]
【オセロ,将棋】ボードゲーム【囲碁,War】 (1002ﾚｽ)
【オセロ,将棋】ボードゲーム【囲碁,War】 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/
上
下
前
次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索
歴削→次ｽﾚ
栞削→次ｽﾚ
過去ﾛｸﾞﾒﾆｭｰ
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
329: 名前は開発中のものです。 [sage] 2015/09/14(月) 21:42:06.86 ID:1S1dymvg その情熱がうらやましい http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/329
330: 310 [sage] 2015/09/15(火) 20:18:36.71 ID:egtjjW0V 準確定石の計算って実は思ったよりコストフルかもと気づいてしまい、 急きょコーディングして比較してみる事にしました。 releaseモードだと、自分の計算方法では跡形も残らないため、時間計測不可能。 debugモードでも、数十倍速いと言う結果になりましたので、今の確定石計算ロジック は、悪いモノではないと自分に言い聞かせる事にしました。 それより、回帰の学習で、少しずつ少しずつ２５０回くらいまで学習進めていたのですが、 バグを見つけてしまい、またやり直しです。むむむ。しかも、なおした事で計算時間が ２〜３倍になってしまうという。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/330
331: 名前は開発中のものです。 [sage] 2015/09/19(土) 00:46:12.58 ID:OgvQcqwn 回帰がやっとまともっぽいところまで収束するようになりました。 今、２５０回学習で、最終ステージが１σ＝７．５程度です。 このペースだと、もっと学習させても、たいして変わらない気もしますが、 もう少し学習を進めてみようかと思います。 この評価関数を元に、反復深化＋MTDF+negaScoutなsolverを動かして FFO#40で８秒程度になります。インライン関数化とか、最終２手展開とか やるべき事はある程度やっちゃったので、自分の力だとこの辺が限度かも。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/331
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
340: 名前は開発中のものです。 [sage] 2015/10/19(月) 09:50:52.09 ID:BMJ9Bhec とりあえず、ざっくり中盤探索のnegaScoutを組んでみた。 素の状態で１０手読みくらいなら１手１０秒以内に終わりそうな感じ。 だけど、いろいろと気になる点が。 とり同一局面から着手可能な手の評価値の順番は、あまりくるっては いないように見える。ただ、評価値事態は結構ずれている。 そして、黒番白番で精度が全く違うように見える。 言われてみれば、同一局面でも手番が逆転すると評価は全く変わるからなぁ。 今は、手番も一つのパラメータにしちゃってるから、その差異は埋められない。 パラメーターとか評価関数の区分とか再考の余地があるんじゃないかと。 前向き枝刈するにしても、評価関数がフィックスしないとダメじゃないかと。 というわけで、しばらく評価関数方面で時間つぶしかなぁ。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/340
341: 名前は開発中のものです。 [sage] 2015/10/26(月) 09:44:35.41 ID:uWG/Yjb0 中盤探索に入るにあたって、評価関数の計算の試作をいろいろしているんだけど、 いまいちぱっとしない。１００回学習で１晩かかるし、３００回試行くらいしないと傾向が 見えてこないので、時間がかかる。 で、仕方ないので、裏で序盤定石を作り始めてしまった。 こちらも棋譜ベースで作ろうと考えている。 そこまで来た時に、データベースのどういうデータが使いたいのかが、逆にはっきりして 来て、今使ってる３６０万件棋譜の中のデータを選別しようかという方向に傾きつつあります。 が、やっつけで作って中身が思い出せないフォーマット変換のプログラムから直さなきゃならん。 開き直って、もう１度、データ変換から作り直そうかなと・・・ http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/341
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
349: 名前は開発中のものです。 [sage] 2015/11/29(日) 22:05:16.61 ID:gx8DmdDE googleとかfbが囲碁のAI作ってるが、どんなもんなの http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/349
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
351: 名前は開発中のものです。 [sage] 2015/12/02(水) 23:37:59.26 ID:Xp/MZwxE >>349 囲碁オセロ板の該当スレで聞いた方が良いかなと。 コンピューター囲碁ソフトについて語るスレ30 [転載禁止]©2ch.net http://kanae.2ch.net/test/read.cgi/gamestones/1447640768/ http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/351
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
ﾒﾓ帳
(0/65535文字)
上
下
前
次
1-
新
書
関
写
板
覧
索
設
栞
歴
あと 645 ﾚｽあります
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.012s