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

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

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

---

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

---

ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡

---

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

---

ﾒﾓ帳

(0/65535文字)

---

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

---

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

---

Google検索

Wikipedia

---

ぬこの手 ぬこTOP 0.049s