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

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

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

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

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

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

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

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

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

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

３層パーセプトロン型にするか、普通の線形回帰にするか。
パーセプトロンタイプは、パターン学習のタイプを作ってみましたが、学習データ３４０万
棋譜に対して、１回回すのに３日がかりという状態で、検証サイクルが回しづらい状況な
ので、簡略化をするか、線形回帰を試すか思案中です。最終的には、両方作って対戦
させてみるかと思っています。いつになる事やら。

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

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

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

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

もちろん、完璧な確定石ではありません。
拾った石は確実に確定石ですが、確定石なのに拾えない石が若干あります。

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

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

初期値をゼロからスタートすると、この辺なんだけど、１とかからスタートすると
もっと誤差が大きいところで収束してしまう。初期値を乱数にしたら、更に大きな
省4

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

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

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

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

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

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

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

もう少し、検討してみます。

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

手元にあるwzebraなんかは、評価値と称して最終石差予想が表示されているのですが、
やはり、ある程度の誤差を含みつつも、大きくぶれているようには見えません。

評価関数の使い道を考えると、実は絶対値はそれほど重要ではありません。
省8

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

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

裏で、Solverの速度アップを検討。
CountBitとPOPCountを組み込み関数にしてみました。FFO#40で30%ほど改善。
続いてFlip関数を６４個のポインタ関数にしてみましたが、時間はほぼ変わらず。
ポインタ関数内の処理が非効率なのか。
省2

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

確定石計算もバグ取りはできたと思いますが、その分計算が１．５倍ほどに膨れてしまい
ました。しばらく思考実験していたら、確定石なのに確定していると評価できない確実な
パターンも思いついてしまって、どうせその程度のものなら重い確定石計算しないで普通
に準確定石程度にしとくのが良いかと悩み中。

Solverの速度アップですが、前からやろうと思っていた事を少しづつやっていますが、
省6

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

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

MTD(f)が遅いのも、最初に設定するfを評価関数の値にして、それが結構外れで、
探索範囲が広がったのが原因です。scout missと同様に、結局のところ、途中で評価関数
省4

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

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

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

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

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

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

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

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

しかし、１０年前のCPU使ってるThellにようやく勝てた程度。
Zebraの速さは何なんだと。こちらはcore i7だというのに。

目下の悩みは、_mm_popcnt_u64とBitScanFoward64が使えずに、それぞれ32ビット版を
省3

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

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

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

そしてaspiration windowと称しているWindowの取り方が独特で、ここに高速化の
秘密があるとみた。早速真似してみると、また>>310のような問題が・・・
今回は前より理解が進んでいたため、２点修正して解消。
省4

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

zebraのwindowの取り方は、基本的にMTD(f)みたいに置換表利用を前提とした、
固定分割サーチだけど、negaScout（MTD(f)やzebra方式の中で使用している）と
速度的には同等な感じ。最初の探索で勝敗がわかるという点がメリットなのか。
MTD(f)は評価関数が正しくないと、検索時間が伸びる可能性があって、以前から
negaScout単体でも十分な気がしてる。

FFO#40は後述の静的評価関数を判明しているパラメータで最適化すると、
省11

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

FFO#43は多少高速化してて、パラメータ最適化するとMTD(f)で１２秒台くらい。置換表
適用範囲の指定を下（葉）からしていたのを、上（ルート）からに変えた。あと、MTD(ｆ）
などでは何回も置換表を読むので、２回目からはmoveorderに置換表の評価を使うよう
にした。

BITBOARDだと開放度の計算が簡単だという事に気づいて、静的評価関数に使ってみた
省9

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

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

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

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

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

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

最初にテストしたFFO#43のMTD(ｆ）でいきなり３０％近く高速化して「やった！」と思った
のもつかの間。実はミスで判定を逆にしてまして、偶数マスに打って奇数を相手に渡すと
加点になってました。で、いろいろテストした結果、最初にやったケースではたまたま
良かっただけみたい。例えばnegaScoutやnegaMaxでテストすると、係数変えたり判定
方法に工夫を加えたりいろいろしてみても、何をやっても探索ノードが増えてしまう。

自分はオセロ弱いので、必勝法みたいに言われているものが、アバウト的に最善手に
省7

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

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

ぬこの手ぬこTOP 0.048s