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

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

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

393: 310 2016/01/21(木)10:04 ID:c00KCFqr(1) AAS
YBWCでは、最適着手手順（PV）のラインで置換表でmoveorderする意味が無いという事
を突き詰めていくと、いちいち前回探索の置換表を引くループを回して、都度最善の着手
を求めるのではなく、前回探索で得たPVを渡せば、時間が短縮できそうな気がしてきま
した。ツリーの浅い部分なので、全体にどれくらい効くのかはわかりませんが。

また、浅い探索などで最適着手手順を取得する時、negaScout＋置換表だと正しいscoutmiss
が発生した時に、nullサーチ時の置換表が適用されて、それ以後のPVが得られないという
事で、悩むところではあります。

まずは戻り値の構造体でPVを返すように改造して、効果を見たうえで、YBWCを適用する
深さでnegaScoutをやめてnegaMaxにするか、それともnullサーチは置換表適用外とするか
どれが良いか試してみようかなと思っています。

できるだけ高い位置で並列化した方が良いという指摘と、置換表もなるべく高い位置で
効かせた方が良いという指摘の、どちらを優先するのかですね。置換表はばっさり探索
をカットできるけど、並列化はカットせずに時短するので、置換表優先かなという気もして
いますが、高い位置でどれくらい置換表が効いているのかもわからないですし・・・。

394: 310 2016/01/23(土)01:31 ID:0OQfWIYl(1) AAS
パソコン再起動すると、何かのタスクがCPUを３０％くらい占有してしまいます。
昨日まで快調に動いていたのが突然遅くなって、悩んでいましたが、これが原因のようです。
というわけで、本日は色々改変したソースの速度が計測できずに悶々としてました。

色々すったもんだ挙句、PVラインを渡す形にしましたが、効果があったかどうかは微妙。
色々付け足した事で生じた速度低下はペイしたかなぁという感じで、#40で0.78秒前後。

本格的にネタが尽きて来たので、ここから先は、MPCをきちんと実装してiterative widening
にかけるしかないかなぁという感じです。あと、定数で渡している置換表適用高さなどの
パラメータを、空マスや使用条件で作ると、実用的になるかな。

395: 310 2016/01/27(水)01:18 ID:IVwAw5rN(1) AAS
オライリーの並列化本が来たので拾い読みしながら並列プログラミングの勉強。
PPLの各アルゴリズムが何を目的とするものなのかが、少しずつ分かってきました。
抽象化度が高いので、最初のとっかかりとしては良いかも。何故かcombinableが
上手く動かないとか、parallel_reduceの中身がよく分からないとかありますが。

で、並列化できるところを探して速度が上がるか試したり、同じ処理をより綺麗に書き
換えしたりして、微妙に速度アップし、0.70〜0.75秒くらい、ノード数が15M、NPSが21M
nps程度になりました。たまに0.68秒台が出ます。

Edax4.3のFFOベンチの結果を確認したところ、ノード数で１．５倍、NPSで４倍、計６倍の
差があります。NPSをコア・クロック換算しても１．５〜２倍の差があり、ノード数は別として、
まだ速度アップの余地があるのではないかという事で、単品速度アップに走ってます。
ノード数はMPC導入後のiterative wideningである程度追い付けるかなと淡い期待。

いくつか速度アップネタがありますが、サッカー日本代表見ながらでははかどらず。
続きは明日。

396: 310 2016/01/29(金)11:31 ID:trvaxUQ+(1) AAS
先日の速度アップネタはすべて不発でしたが、その際にノード数のカウント漏れを見つけ
て、修正したところ、ノード数は１７〜８Mという感じでした。その際に、最終２手高速化の
箇所でもカウント漏れがあり、まずは正確なノード数を簡便に把握しようと外してみたところ、
意に反して速度低下しないところか、どうも微妙に高速化したように見えまして（汗。

最終３手高速化を試してみたり、最終１手高速化も外してみたり、moveorder適用とか、
そもそもmobilityを求めずに空マスを順に着手してみるとか、その辺の適用深さを変えて
みたりいろいろとやって現時点の最適パラメータにしてみたところ、0.63〜0.68秒、最速で
0.60秒が出るようになりました。

αβカットの効きが悪くなっているため、ノード数は２４〜２５Mとなりました。
その分NPSは３７〜３８Mと速くなっていますが、こんな方向で高速化してて良いのか？
というわけで、ノード数が違う段階でNPSを比較しても意味が無いという事に気が付きました。

397: 310 2016/01/30(土)20:51 ID:yCKBToEa(1) AAS
囲碁がすごい事になってますね。オセロで一通り勉強したら小さい盤の囲碁をやって
みようと思っていたので、モチベーション低下中。とはいえ、ああいうのをオセロに応用
しようとしたら、あそこまでマシンパワーいらないんじゃないかとか・・・。

ここのところ、もっぱらSTLやPPLの機能を綺麗に使う方向での改良ばかりしてました。
pararell_reduceの使い方もわかりました。negaScoutの繰り返しループが綺麗に並列化
できたんじゃないかと。ただ、MAPする件数がしれているので、parallel_reduceではなく
逐次版のaccumlateの方が速いという結果に。あと、時間計測が結構飛び飛びの値に
なるので時間計測関数を精度１msのものに変更。

色々やった結果、若干高速化したうえで、時間のバラつきが消えてくれました。
１００回試行で計測すると610ms±15ms（１σ）となり、逐次処理のほぼ２倍の速度に。
ノード数は同程度で、NPSは40M超えて来ました。このNPSのままノードを半減できれば
良いのに。

398: 310 2016/02/07(日)21:48 ID:xNqeS9Ve(1) AAS
ここら辺で、EDAXとかとの速度差の原因を考えたところ、次の２点が考えられました。
１．評価関数の精度が悪い可能性
２．個々の関数で速度アップの余地がある可能性
という事で、１は熟考が必要なので後回しで、速度アップの対象として、flipとmobilityの
高速化を検討。とはいえ、良い知恵があるわけでもないので、ネット徘徊。

現在、ポインタ関数で分岐して処理しているflip関数を１発で処理するopenCLのソースを
発見。Master Othelloの作者のものでEDAX4.3のflip関数を参考にしているらしい。
中身を解読するとベクターを使っている。とりあえず処理を真似て逐次処理で組んでみたら
結構速度アップしました。

解読の過程で、ようやくベクタ化の意味がわかったので、mm256系の命令を使って、
ベクタ化してみましたが、若干速度低下。原因は恐らくlzcntで一回ベクタを抜けてしまう
所だと思うので、ハッカーのたしなみを読んでベクタ演算で組み直してみる予定。
合わせてmobility関数もベクタ化。若干速度アップしたかなという程度。
組み込み関数は使い方が面倒臭いので、演算子のオーバーロードしまくってみました。

flip関数は非ベクタの分岐無しバージョン、mobilityはベクタという状態で、500msを切る
数字が出るところまで来ました。flipのベクタ化ができて、パラメータ調整するともうちょい
良い数字が出るかなと期待。

399: 310 2016/02/09(火)01:09 ID:MeGl+gwc(1) AAS
flip関数続き
・lzcntを自前で組んでみましたが、やはり処理が重く速度低下。ボツ。
・右方向と左方向で処理が違うので、片側＋１８０度回転で、同じ処理にしてlzcnt不使用
にしてみたが、１８０度回転×４が重くて速度低下。ボツ。
・できるところまでベクタ化して、lzcnt以後はスカラ計算で、速度若干改善。
・上記からlzcnt後、再度ベクタ化してみたら、速度若干低下したのでボツ。
・64bit×４の値を代入する関数を変更したら、意に反して結構速度改善。
・闇雲に__declspec(align(32)) してみたら若干速度改善してバラツキ減少。

これらにより、450msくらいになりました。
ベクタ化はまだ何かありそう。

ちゃんと書いてなかったですが、途中からノート数カウントを外してます。入れると100ms
程度の速度低下になります。一応、デバッグ用に#ifで切り替えられるようになってます。
が、そんな状態なので、nps計算に意味が見いだせないという・・・。

続いて評価関数をベクタ化できないか考えましたが、BMI命令使っているので厳しい。
計算楽にするため、でかい配列を何回も引いているので、ここを何とかしたい気がする。
黒・白・空の３を基数とする３進数でナンバリングしているんだけど、高速で計算する方法
が見つからず。
平衡３進法を手早く計算する方法があると、黒を1、白を-1、空を0にして、定数足すとか
できるんだけど、どんなに調べても、基数変換に王道なしという言葉しか見つからない。

400: 2016/02/15(月)00:14 ID:2rfyeFpJ(1) AAS
高速化については一旦棚上げ。何やっても速度が上がらない。
ひたすらノード数カウントの速度低下を抑えて、カウントのバグ取りして。
色々発見はあったけど、結局ソースを綺麗にしただけだった。
後は、いずれゆっくり時間をかけて、評価関数を作り直すかな。

MPCを組みました。一応動作している模様。

これからしばらく、GUI作りに入ります。
MFCよくわからん。

401: 310 2016/02/20(土)13:43 ID:ZGi2V8ih(1/2) AAS
GUIできた。昔作った序盤定石部分と合体。
中盤探索を反復深化にして、３秒を超えて新しい深さに入らないあたりで調整。
MPCで２５手くらいまで読めるように調整。
終盤完全読みは３８手から。３６手からMPC付で完全読み（つまり完全ではない）。

こんな感じでできたので、早速プレイ。自分だと軽く全滅負けしてしまうので、zebra先生
にお越しいただきました。が、滅茶苦茶弱い。

良く見ると、定石が効いている段階で＋１６だったのが、中盤読みになった瞬間に一気に
−１４くらいまで落ちて、そのまま挽回できない感じ。zebra先生は、その前に定石から外れ
て、既にzebraから見て＋１４程度の評価値を算出している。つまり、定石部分がおかしい。

それ以外は、評価値もzebraとは大きく違わないし、終盤探索もちゃんと機能している感じ。

402: 310 2016/02/20(土)23:06 ID:ZGi2V8ih(2/2) AAS
zebra先生にならって定石の評価を表示するオプションをつけてみました。
ロジック的には間違いなさそうですが、定石DBがおかしいというか、定石に登録がない
手順に正しい変化があって、それを無視しているため、間違った判断をしているみたい。

一応、完全読みという触れ込みの棋譜を元にしているはずなので、使い方をどこかで
勘違いしているんだと思います。しばらく悩むしかなさそうです。

403: 310 2016/02/21(日)01:04 ID:nPWuqcvw(1) AAS
試しに定石部分を外して、中盤探索で開始してみたら、zebraの２０手読みに対して
２戦して１勝１分となりました。読みの深さは、こちらが上なので、こんな感じでしょうか。
序盤２０手分は評価値が無いので、２０手近い探索を反復無しで探索するため、MPCを
使っても最初の数手は１手あたり５分以上掛かってしまいます。

定石については、以前にウェブで見つけてテキストに起こした定石データがあるので、
それを評価０で登録してみようかなぁと思っています。

定石の自己学習とか、評価付けとか、どうやるんだろ。

404: 310 2016/02/25(木)21:06 ID:fXRsnvrs(1) AAS
定石データを、上記の手打ちデータで作り直しました。
当初は並び取りとかの極端な進行以外は評価０．０にしたため、mobility関数のビット列
の下から定石に従って着手する形となり、zebra先生のBookに誘導されるように、少しずつ
不利な定石に乗り換えていき、負けるという展開に（汗

悔しかったので別のソフトを拾い、戦ってみると、そちらには圧勝。決して弱くはないと思う。
また、zebraとの対戦時にBookで評価値がついているものは、それを参考に修正したところ、
時々勝てるような感じになりました。

EDAX先生＋UnifiedBookなるものを拾って、そちらと戦ってみたところ、軽く惨敗。
ｆｊｔ定石とかだと終盤近くまでBookがあるみたいで、Bookが続く限り紛れが無い。
こちらが中盤探索などでミスるたびに−２づつ落としていき、お話にならないレベル差を感じました。

しばし熟考の上、定石の拡張、評価付けを考えてみようかと思います。
あと、評価値が近い時には、何らかの確率で手を選択するようにもしてみたいと思います。

405: 310 2016/02/28(日)01:10 ID:hQzoi2Tz(1) AAS
縦取り系は白番黒番試して、定石の評価値を修正してみました。
あと、AIの進行ごとのパラメータを試行錯誤して、なるべく負けないようにしてみました。
これにより、AIの読み時間が結構伸びて、１ゲームワーストケースで１手２分、トータル
５分くらい思考してしまいます。これは、反復深化などで、タイムアップをせずに、次の
ステップに入る制限時間だけ決めているためです。

EDAX＋Unified Book先生はレベル２１で、黒番白番ともに引き分けになります。
こちらは２０手前に定石が切れていますが、その後も最善手が打てているという事になり
ます。こちらは何局打っても手を変えないので、EDAX先生のBookの進行に合わせた
だけですが。一方zebra先生は比較的手をいろいろ変えてくるので、勝ち負けが発生します
（もちろん、各アプリの設定次第ですが）。

序盤定石の評価値をそれなりにしたら、後は引き分け進行をひたすら登録していって、
相手が最善しか着手しないと信用すると負けないプログラムができちゃうのではないか
と、ふと思いましたが・・・。トップ同士の対局が引き分けばかりになるのは、こういう事
なんでしょうね。というか、完全解析ってこれが完成した状態なのか。

EDAX先生のUnified Bookは、いくつかの引き分け進行棋譜の集合体のようですが、
元データが幸い既知のWthor形式なので、それをもらってしまうと、トップレベルになる
のかなぁ。トップな人がBook構築に主眼を移したり、開発が止まったりする訳だと。

そろそろ、混とんとしているプログラムを綺麗に直して、パクリBook作って開発終了しちゃ
おうかと思い始めています。速度的には、まだまだ改善の余地はありそうですが。

406(27): じょげなら ◆kXDiHQuNQ2 2016/02/29(月)19:18 ID:etqtABZA(1/3) AAS
ライフゲーム囲碁というゲームのネット対局場を作りたいです。
囲碁でいうKGSみたいなのが理想です。
プログラムはある程度わかりますが、ネット関連の知識が乏しいです。
何から始めればいいですか？

407: 2016/02/29(月)19:21 ID:etqtABZA(2/3) AAS
ＵＲＬがＮＧワードに引っかかる…

408: 2016/02/29(月)19:34 ID:etqtABZA(3/3) AAS
好きな言語
C++
C#
Ruby

嫌いな言語
Java
Python
Perl

409: ４０６ 2016/03/01(火)20:52 ID:6wFQeZGp(1) AAS
とりあえずHTML5の本買ってきた

410(1): 406 2016/03/03(木)19:44 ID:Hi4nZgiL(1) AAS
外部ﾘﾝｸ:fast-uploader.com
碁石をぽちぽち置けるところまで作った

411(1): 310 2016/03/04(金)10:15 ID:Q4DtXsqP(1) AAS
>>410
一晩考えてみた。

通信回りに興味を持って遊んだのは１５年くらい前だし、Javaとかイメージしかないし。
あまり助言できる事はありませんが、一つ言えるのは、UIに凝ったりサービス内容を
考えたりするのは最後で良いと思います。

Rubyが好きなら、まずはCGIベースで、テキスト表示で対戦を実現する仕掛けを作る事
だと思います。次に複数のユーザーが接続するのであれば、身元確認のためのID/パス
ワード管理が必要になりますし、個々の対戦を区別するにはセッション管理が必要になり
ます。この辺は、スタンドアロンのアプリには無い、独特の世界なので、結構新しい技術、
テクニックの習得が必要になるかと思います。いまどきあるのかわかりませんが、チャット
のスクリプトとかあれば、参考になるかも。

その辺から入り込んで、いろいろ調べていくと、だんだんと必要な技術、知識が増えてくる
んじゃないかと思います。

412: 406 2016/03/04(金)18:58 ID:w3YPuhPg(1) AAS
>>411
レスありがとうございます。
確かにセッション管理とか知らないです。
チャット調べてみます。

413: 406 2016/03/07(月)21:05 ID:NI+TTWmM(1) AAS
RoRの本買ってきた。
チャットはまだ調べてない。

414: 2016/03/09(水)19:45 ID:Cf1/SDqU(1) AAS
うおおおおセドルがああああぁぁぁ

415: 310 2016/03/10(木)02:00 ID:hvbQwbFh(1) AAS
うむむ。
これにて、オセロができたら次は囲碁という目標が雲散霧消してしまいました。

どうしよう。

416: 310 2016/03/10(木)18:05 ID:b1SmaPOg(1) AAS
AlphaGO強すぎ・・・orz

今夜は、囲碁関係者だけじゃなく、AI周りの人も、Google以外全員お通夜ですね。

417: 2016/03/10(木)19:38 ID:SphVvbk5(1) AAS
３１０氏もalpha碁注目してたか。
セドル一発入れてほしいなぁ

418: 2016/03/11(金)09:04 ID:HTdTU0Fi(1) AAS
浮上

419: 2016/03/12(土)12:19 ID:k2nAbsiz(1) AAS
おお、このスレ生きてたんだ

なんで RoR なんか見てるのよスレ間違えたかと思った

420: 2016/03/13(日)18:01 ID:X9umXTnK(1) AAS
せどるううううッよくやったあああああぁっ
人類の勝利やあああぁぁっ

421: 2016/03/13(日)19:02 ID:Gv0++KTh(1) AAS
お、第四局はセドル勝ったか

422: 310 2016/03/13(日)20:47 ID:50OeMIN8(1) AAS
うむ。なんか期待を裏切られっぱなしｗ

この負けっぷりを見ると、囲碁もトライしたくなってくる希ガス。

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

あと 580 ﾚｽあります
ｽﾚ情報赤ﾚｽ抽出画像ﾚｽ抽出歴の未読ｽﾚ

ぬこの手ぬこTOP 0.021s