[過去ﾛｸﾞ] 【オセロ,将棋】ボードゲーム【囲碁,War】 (1002ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
474: 2016/08/12(金)00:22 ID:+2V5AEwc(1) AAS
ほほう
460さんも期待出来そうですな
475: 460 2016/08/12(金)02:42 ID:mvQ0iJdF(1/4) AAS
>>472
自分はディープランニングなどの人工知能系はさっぱりなので・・・
310さんはよく勉強されていると思います。
自作オセロですが、今まで32bitで開発していましたが
今ではもう32bitOSを使用する方が稀だと考えて思い切って64bitに移行しました。
探索ノード数がいきなり10〜20%程度上がってビックリしています・・・
476: 460 2016/08/12(金)04:26 ID:mvQ0iJdF(2/4) AAS
あ、探索ノード数ではなく探索速度ですｗ
終盤探索だと10000Knps〜15000Knps程度出せるようになりました。
自分の環境だとWZebraが20000Knpsなので、大幅に負けています・・・
そろそろチューニングも視野に入れつつやっていこうと思います。
まずは探索ノード数を終盤MPCで削減しなくては・・・
477(1): 460 2016/08/12(金)07:59 ID:mvQ0iJdF(3/4) AAS
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 2016/08/12(金)08:01 ID:mvQ0iJdF(4/4) AAS
>>477
FFO#56はH2:+0ではなくH5:+2に訂正です。。
479(1): 310 2016/08/12(金)15:16 ID:USoZXJIB(1/2) AAS
がーん。今まで、こちらはノートPCだしと、密かに思っていましたが、32bitでしたか・・・。
完全に脱帽です。
だったら、僕もこのスレで教わったAVX2とかBMIとかの組込関数使って、あとPPLとか
OpenMPとかで並列化して４コアなら３倍強程度なので、トータル４倍以上に速度アップ
すると思いますよ。つまり、その辺やるだけでEdax並まで行くかなと（汗
ちなみに、DeepLearningはあきらめ方向にだいぶシフトしてきました。
480: 2016/08/12(金)16:41 ID:8u/4Xx1J(1) AAS
仲間が出来ていいのう
481(1): 460 2016/08/12(金)17:56 ID:wDmYSTDl(1) AAS
シングルスレッドだとトッププログラムですら合計2000秒台と限界があるので、マルチスレッド対応は必須ですよね
ただybwc等の並列化アルゴリズムの理解に時間がかかりそう…
482(1): 310 2016/08/12(金)20:50 ID:USoZXJIB(2/2) AAS
>>481
YBWCはnegascoutのnull window searchを並列化して一括処理する
ようなものだと解釈して実装しました。
この辺はゲーム計算メカニズムなる本で勉強したかな。
並列処理のフレームワーク何使うかが問題ですね。
自分はVC++なのでmsdnで情報が得やすいPPLを使いました。
インテルTBBとかOpenMPなんてのもあります。
PPLは結構使いやすかったですが、速度は不明。
まあ、ルートの方でしか使わないので、あまり影響ないと思っています。
手組でマルチスレッドなプログラム書ける人には不要かも知れません。
483: 310 2016/08/13(土)14:18 ID:D+1dBs0T(1/2) AAS
あ、考え方がnegascoutみたいだという事で。
484: 2016/08/13(土)20:35 ID:p7EbJiId(1) AAS
avx2って256bitだよな
オセロだと128bitしか使えないような？
485: 310 2016/08/13(土)20:47 ID:D+1dBs0T(2/2) AAS
方向が８つあって、それぞれの処理を８回計算するとき、
右シフト方向が４つ、左シフト方向が４つ。
256bitは64bit×４。右シフトと左シフトで２回。
というわけで、mobilityとかflipとかで便利に使えます。
486: 460 2016/08/14(日)16:41 ID:ALD5heTO(1/2) AAS
現在、終盤用MPCパラメータ作成中です。
23手完全読みのカットペアに入っています。24手読みの計算が終わったらいったん実装に入るつもりです。
>>310
YBWCに関して調べましたが、そうみたいですね。
MPCパラメータを作成している間に、なんとなくで適当に実装してみましたが
なぜかエラーで落ちまくりでしたｗ
排他がかかっていない致命的な箇所があるのか・・・置換表は排他をかけたのですが・・・
PVライン生成あたりも怪しい、とりあえずもう少し調べてみないとダメそう。
487: 460 2016/08/14(日)16:42 ID:ALD5heTO(2/2) AAS
>>310は>>482の間違いです。。
488(5): 2016/08/17(水)21:19 ID:Z2gXWq7v(1) AAS
俺もボードゲーム系ＡＩでディープラーニング書いてみたいと思ってるけど難しいんだろな。
論理もそうだけど膨大なデータが必要そうだし。
>>479
どのへんで諦めました？
489(1): 310 2016/08/18(木)15:43 ID:7GnJQiSP(1) AAS
>>488
まだ細々やってます（汗
Eigenの導入と、少しづつ進んでいくC++技術のおかげで、前よりは試行の
スピードはアップしていますが、なかなか成果は出ません。まだ、色々な
パターンを試しながらディープラーニングって何ぞやを体感しているところ
なんだと思います。
少なくとも「簡単に凄い事ができそう」という幻想は捨てる事ができました（汗
ボードゲームがターン制なら、基本はmin-Maxになると思います。
まずは、盤面の状態に（恣意的で構いません）点をつける評価関数作るところ
から始めたらどうでしょう？
次のステップで評価関数に統計（線形回帰）を持ち込むと、ディープラーニング
じゃなくても、プレイ譜がたくさん必要になります。
オセロの場合は、Buroさんという先人が、実用レベルの評価関数が線形回帰
で作れる事を示してくれています。
僕がディープラーニングを適用しようと思っているのは、ただの思いつきでして。
場合によっては、より軽くて正確評価関数が作れるかと思いましたが、実際に
始めてみると、なかなか評価関数として機能してくれないし、仮にできたとしても
重いものになっちゃいそうという感じです。
490(1): 488 2016/08/19(金)23:15 ID:i9HkvHw2(1/2) AAS
>>489
手動評価関数はかなり昔五目並べで書いたことあります。
min-maxで思考時間が１手５分くらいかかったけど、
自分でプレーして負かされることもあるくらいの強さにはなりました。
そのBuroさんの線形回帰とやらはWebで論文とか見れたりしますか？
読んでも多分理解できないだろうけどちょっと興味あります。
491: 488 2016/08/19(金)23:23 ID:i9HkvHw2(2/2) AAS
ぐぐったらこんなのがあったけど多すぎ。
外部ﾘﾝｸ[html]:skatgame.net
492(1): 310 2016/08/20(土)16:51 ID:m44rb9b4(1/2) AAS
>>490
Buroさんが作った伝説のオセロプログラムがLogistelloです。
Thellというオセロプログラムの作者の方が日本語で解説してくれています。
外部ﾘﾝｸ[pdf]:sealsoft.jp
5.2の計算の高速化のところの説明（P.8の冒頭）のところ。
自分なりに解釈したら、自分が解釈違いしたのか、説明がおかしいのか、
この通りではなかった記憶があります。
とはいえ、これはオセロの考え方であって、将棋なんかだとbonanzaなどを
参考にすべきだし、全く別のゲームであったら、別な事を考えなければなり
ませんね。当たり前ですが。
493(1): 488 2016/08/20(土)20:33 ID:+7ONDgCM(1) AAS
>>492
パターンの重みの線形和が評価関数になる的なことが書いてあるっぽいですけど、
パターンというのは人間が与えてやるわけですよね？
そのパターンすら学習で求めるというのがディープラーニングなのかと思ってますけど。
まあディープラーニングにはロマンがありますね。
494(1): 310 2016/08/20(土)21:29 ID:m44rb9b4(2/2) AAS
>>493
ですです。
あと、Deepじゃなくても、２層以上のパーセプトロンだと、線形分離不可能問題の
分類ができるようになります。XORの学習が典型ですね。
ところが、パターンの部分まで学習で求めてくれるってのは、やっぱり幻想でして。
ある程度パターンを想定しながら、ネットワークを作らないといかんのではないか
という事に思い至っています。
例えば畳み込みニューラルネットワーク（CNN）で、何故畳み込みをするのかという
と、縦線横線などの隣接ドット同士もつながりを識別してもらうためですし。そもそも
畳み込みのフォワード計算自体が、画像に対して例えば輪郭線強調といったフィル
ターかけるのと、プログラム的に同じものだったりします。学習対象は、フィルターに
なります。
オセロは、囲碁とかと違って、石の色がコロコロ変わるので、隣同士の石のつながで
判断するCNN的なネットワークをそのまま適用できないよなぁというのが、最近の諦め
ポイントであります。
じゃあ、何に頼るかというと、自分はオセロ弱いので・・・No ideaだったりします。
あんな簡単な（DeepLearningと比較して）線形和でBuroさんの評価関数ができています
ので、パターンを活かして、まずはそこに点数を割り振るところをMLPなんかでできない
かなぁと思っています。
495: 488 2016/08/21(日)00:04 ID:EnsCDbgT(1/2) AAS
>>494
>ところが、パターンの部分まで学習で求めてくれるってのは、やっぱり幻想でして。
>ある程度パターンを想定しながら、ネットワークを作らないといかんのではないか
>という事に思い至っています。
ふーむそうなのか。残念。
聞きかじった知識だと夢のような技術なのかと思っちゃったけど、
実戦してみるとなかなか難しいのかぁ。
496(2): 2016/08/21(日)21:39 ID:EnsCDbgT(2/2) AAS
いくらオセロの盤面が小さいからってシングルスレッドで
10000Knps〜15000Knpsというのはとてつもなく速く感じるんだが。
どうやったらそんな速度がでるんだ？
オセロ業界じゃ普通なのか？
497: 310 2016/08/22(月)02:41 ID:2ubnBUwd(1/2) AAS
Kが余計で３桁間違えているんじゃないかと（汗
498: 310 2016/08/22(月)02:46 ID:2ubnBUwd(2/2) AAS
あ、違った。自分が３桁間違えていた。
全然おかしくないです。自分の２コアで１３０００Kくらい出てます。
シングルで同等の速度ですから、かなり速いとは思いますが、
敢えて言うなら２倍程度なら縮められないとは思えない差です。
499: 460 2016/08/22(月)08:13 ID:yZES3OuI(1) AAS
終盤MPCを実装完了してFFOを測定してみました。。
残すのはFFO#57のみですが、この時点で9364秒と1万秒を割ってるので
10%程度の高速化は期待できそうです。（評価テーブルは64ビット移行＋120万局から変更なし）
500: 460 2016/08/22(月)09:20 ID:qlwiS2PE(1) AAS
>>496
簡単な実装だと終盤探索は2000万ノード/秒いけますね。
合法手生成が将棋などより速いので。
とはいえ、中盤探索だと色々やるので5000knps程度に落ちてしまってます。
501(1): 496 2016/08/22(月)21:10 ID:WzxI/O2e(1) AAS
2000万ノード/sとかってsseやavx使って始めて可能になるレベル？
オセロの合法手の実装になにかすごい効率的なビット演算やってるとか？
502(2): 460 2016/08/23(火)11:44 ID:sSUGbl7L(1/2) AAS
>>501
終盤探索だと合法手生成は葉ノードの近くでは使わないので、ループや条件分岐を使ったコードでなければアセンブラでなくても速度はそれなりに出ますよ。
こことかが参考になります。
外部ﾘﾝｸ:d.hatena.ne.jp
自分はこんな感じのコードをアセンブラに落として少し改変したものを使ってますー
503: 460 2016/08/23(火)11:47 ID:sSUGbl7L(2/2) AAS
置換表に超大バグがあることに気づき修正したらFFO45が32秒になりました…w
180万局の学習を朝に終えたので今晩再度FFOを測定しようと思います。
上下前次1-新書関写板覧索設栞歴
あと 499 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ
ぬこの手 ぬこTOP 0.023s