【オセロ,将棋】ボードゲーム【囲碁,War】 at GAMEDEV
【オセロ,将棋】ボードゲーム【囲碁,War】 - 暇つぶし2ch412:406
16/03/04 18:58:38.77 w3YPuhPg.net
>>411
レスありがとうございます。
確かにセッション管理とか知らないです。
チャット調べてみます。

413:406
16/03/07 21:05:27.22 NI+TTWmM.net
RoRの本買ってきた。
チャットはまだ調べてない。

414:名前は開発中のものです。
16/03/09 19:45:29.94 Cf1/SDqU.net
うおおおおセドルがああああぁぁぁ

415:310
16/03/10 02:00:10.79 hvbQwbFh.net
うむむ。
これにて、オセロができたら次は囲碁という目標が雲散霧消してしまいました。

どうしよう。

416:310
16/03/10 18:05:03.79 b1SmaPOg.net
AlphaGO強すぎ・・・orz

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

417:名前は開発中のものです。
16/03/10 19:38:43.78 SphVvbk5.net
310氏もalpha碁注目してたか。
セドル一発入れてほしいなぁ

418:名前は開発中のものです。
16/03/11 09:04:36.30 HTdTU0Fi.net
浮上

419:名前は開発中のものです。
16/03/12 12:19:15.41 k2nAbsiz.net
おお、このスレ生きてたんだ



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

420:名前は開発中のものです。
16/03/13 18:01:59.50 X9umXTnK.net
せどるううううッよくやったあああああぁっ
人類の勝利やあああぁぁっ

421:名前は開発中のものです。
16/03/13 19:02:49.19 Gv0++KTh.net
お、第四局はセドル勝ったか

422:310
16/03/13 20:47:23.70 50OeMIN8.net
うむ。なんか期待を裏切られっぱなしw

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

423:406
16/03/15 20:44:49.53 NF77F+OG.net
RoRとjavascriptの連携がよくわからん。
でもちょっとづつだけど進んでる。

424:310
16/03/16 23:06:52.43 YEZK1fac.net
アルファ碁ロスまっただ中ですw

オセロ作ったおかげで、一連の勝負をいままでとは違う視点で見れたかなぁ。
とりあえず、囲碁のモンテカルロ解説した本と、ディープラーニングの入門書を
買ってきた。さらっと読んだけど、ディープラーニングは理解に時間がかかりそうorz

オセロで3層パーセプトロンを試したときは、結局うまく動かなかった。
実装が悪いのもあるけど、学習にもすごく時間がかかった。
あれをディープにしたら、どうなっちゃうんだろうかは不安ではある。
こちとら、SurfacePro3しかないし(汗

425:406
16/03/19 20:06:25.11 Ik15FlWh.net
railsでdeviseとかいうgemをつかってユーザー認証機能実装したけど、
複数ユーザーがログインして対局させる方法がサッパリわからん。

426:406
16/03/24 20:20:54.97 C08ak5N3.net
ブラウザ閉じたときに自動ログアウトのやり方がわからん

427:名前は開発中のものです。
16/03/25 13:51:48.34 9Ea9sx62.net
ブラウザは通信があった時にしかクライアントの消息が確認できない。

n分アクセスが無かったらサーバー側で勝手にログアウトさせちゃう
タイムアウト方式が普通かなと。その時間経過後にアクセスがあっても
ログインからやり直し。

このログインからタイムアウト(ログアウト)までの間をセッションと呼ぶ。

428:名前は開発中のものです。
16/03/25 14:16:19.46 9Ea9sx62.net
1行目おかしかった。

>WEBサーバ、ブラウザという仕組みは、ブラウザから通信があった時にしか、
>サーバーはブラウザの消息を確認できない。

に修正。

1.初画面からログインする
2.サーバが、HTMLにセッションNoを埋め込んで、ブラウザに表示。
  サーバでは、セッションIDを配列などで管理して、IDと最終アクセス時間をとっておく。
3.ブラウザ側からのCGIリクエストには、必ずセッションNoを入れて送信。
  セッションNoで、相手がだれか(ID)を特定して、処理を行う。
  つまり、個々の処理はセッションNoで管理されている。
4.ブラウザからCGIリクエストが来た時に、タイムアウトしていたら、ログアウト処理へ
  あと、ゴミ掃除で1日1回くらいタイムアウトしているものを削除。

この辺が基本。対局型の場合。

5.2つのセッションが対局している事になるので、対局管理する配列を用意。
6.相手の着手待ちの時に、どうするのか?その辺が肝。
  HTMLに細工して、1秒ごとにリロードさせる。リロードにより、着手が行われたか
  それとも秒読み時間切れになったか?判断をサーバーに依頼する。
  などなど。やり方は色々あるかと思う。

とにかく、肝は、情報がブツ切れで、あちこちにある事。これにより、サーバーで簡単に判断
ができない事があるので、いくつかの機能をブラウザスクリプトに依頼しなきゃならん。
それでも、相手が放置して逃げた時、ブラウザを閉じて逃げた時(回線切断やPCダウン)、
などなどの例外が起きるので、それらをタイムアウト検出などで拾わにゃならん。

どうするのかなどの、例外処理をリストアップして、一つずつ対応を決めていく事。
プログラムテクニックはどうとでもなるけど、例外事象の拾い上げの方が大変。

429:406
16/03/25 17:43:19.31 /V6G/Eic.net
丁寧にありがとうございます。
javascriptのwindow.oncloseからなんとかならないかといろいろ調べていましたが、無理筋なんでしょうか。
タイムアウト検討してみます。

430:名前は開発中のものです。
16/03/26 21:27:54.24 DUGO8n57.net
>>429
そういう事を考えるんなら、Javaアプレットとか、ActiveXとかの、
ブラウザ上で動いて通信できる方法を試した方が良いかもね。

431:406
16/03/30 21:45:07.64 yYbYes7U.net
すいません、教えてください。

4.ブラウザからCGIリクエストが来た時に、タイムアウトしていたら、ログアウト処理へ
  あと、ゴミ掃除で1日1回くらいタイムアウトしているものを削除。

このゴミ掃除というのはサーバー側がクライアント側から何のアクションも受けずに
能動的にタイムアウトしているセッションをみつけ削除するということですか?
どうやって書けばいいのかわからないのですが…

432:名前は開発中のものです。
16/03/30 23:26:15.10 DNbQONAE.net
>>431
そうです。別にしなくても良いし、月1回手作業で削除しても良いけどね。

433:406
16/03/31 20:31:39.10 dkaj1Oq1.net
>>432
手作業ですかうーん。
まあ、頭の片隅に置いておきます。
ありがとうございます。

434:名前は開発中のものです。
16/04/01 19:52:02.46 JLskKsZt.net
隠しコマンド受け付けるようにしておいて
管理者のクライアントから定期的にコマンドを投げればいい

435:310
16/04/05 10:45:13.03 82XTVDoH.net
久々登場。アルファ碁ロスがでかすぎて、やる気がでないです。

とりあえず、BOOK上で乱数入れて手をばらけさせるようにしました。あとの課題は、
1.持ち時間制度
2.ステータスバーの更新
標準のStatusBarだとOnMouseMoveなどで更新されるとの事。
リアルタイムに更新させるためには、マウスくるくるさせてなければならん。
3.中盤探索の高速化
反復深化+置換表で高速化が効いていない懸念があるけど未確認。その他の高速化検討
4.同じ手順で負けないためのBOOKの自動学習
5.オフラインでの引分手順の自動生成
となります。けど・・・本当にモチベーション上がらない。

時々、気が向いた時に、Zebra先生やEDAX+UB師匠相手にポチポチ手打ちで対戦して、
相手のBOOKに登録されている引き分け手順を見つけて、手入力でBOOK更新してます。
Zebraは研究モードがあるので、ほぼ拾い終わりましたが、逆に引き分けだらけになりました。
EDAX+UB相手だと、こちらが定石から外れるケースでも、EDAX側は学習データで先が
見えていて打ってくるので、ほぼ負けになります。

たまに、EDAX+UBも中盤探索が走ってくれて、極まれに勝勢になる事がありますが・・・
何が腹が立つと言って、そういう時に限って完全読み時にEDAXがバグって、既に石がある
所に着手して逆転した事にされます。もちろん反則なので勝利は勝利ですが、すっきりと
勝たせてもらえないのが腹立たしい。をのれ。

というわけで。やはりオセロは、引き分け手順のリストアップが、強さの肝である事も再確認
してしまいまして。そこまでの根性は無いなぁというのも、モチベーション低下の原因。

436:406
16/04/06 22:31:38.47 SXJnF3U3.net
ログインユーザー一覧表示できるようになりました。
RoRのコーディングは一休みして棋譜管理にとりかかろうと思ってます。
SGFをパクろうかとおもってますが、結構難しい orz.

437:406
16/04/08 22:18:30.78 kkoRA2nm.net
棋譜ツリー表示すんの結構メンドクサイような希ガス
いいライブラリはないんか

438:406
16/04/09 23:59:42.58 SBv5rCvL.net
KGSのレーティングシステム難しい。
まだそんなこと考える段階じゃないけど。

439:406
16/04/11 21:25:49.37 A4FL2sT8.net
javascriptでオブジェクトの比較ってjsonで変換してそれを比較しろとか某ページで見たけど
そんな事せにゃならんの?

440:406
16/04/12 23:02:53.74 xYnFmhAQ.net
URLリンク(textuploader.com)
棋譜ツリーだいぶ形になってきた。

441:406
16/04/16 22:59:10.60 MXucFBba.net
Rails側とjavascript側の連携がやっぱわからん。
色々めんどくさすぎ。

442:406
16/04/23 00:16:56.63 Gce7F8Ms.net
エンコード間違えてて動かなかったわ。
railsがログ吐いてくれてなきゃ一生気づかなかっただろうな。

443:406
16/04/27 21:48:14.23 JGExYAi7.net
開発に使ってたノートのキーボードが一部効かなくなったわorz.
windowsにログインできなくて焦った。
アカウントでも乗っ取られたのかと思ったらソフトキーボード使ったらログインできた。
USBキーボードとかで代用できればいいんだがどうかな~。

444:406
16/05/02 21:58:59.67 i7WwatVD.net
invalid multibyte character
とかってエラーが出るんだけど、どこに全角があるのかさっぱりわからん。
app/controllers/application_controller.rb:1にあるらしいんだけどいくら調べてもみつからん。

445:406
16/05/02 23:06:51.86 i7WwatVD.net
以下のログが出るんだけど、だれか原因わかる人いない?


Started GET "/" for ::1 at 2016-05-02 22:55:10 +0900
ActiveRecord::SchemaMigration Load (1.2ms) SELECT "schema_migrations".* FROM "schema_migrations"

ArgumentError (invalid multibyte character):
app/controllers/application_controller.rb:3:in `<top (required)>'
app/controllers/home_controller.rb:5:in `<top (required)>'

446:406
16/05/03 11:00:58.43 6pwgCgml.net
すいません、解決しました。

447:406
16/05/13 22:42:29.22 Zx20RSfa.net
やはりポーリングだけでは限界があるか?

448:310
16/05/16 21:32:31.63 KQ1qSDyb.net
モチベーションダダ下がりだったけど、なんとなくソースの整理していたら、
直したいところがいろいろ出て来て、見直し中。

後ろ向き枝刈で探索時間は変わらないけど、探索ノード数が2/3になった。
この枝刈手法の速度アップできたら面白いかもと思いつつ、元々自分が
結構高速に書いていた処理(未使用)を流用しているから、これ以上速度アップ
できるかわからん。

でも、EDAXには勝てないんだろうなぁ・・・
EDAXの孫情報からインスピレーション得てるネタだし。

449:310
16/05/26 16:01:37.05 ZBCA70ec.net
遅々として進んでいます。
ソースを一から組みなおして、いろいろと綺麗にしてます。
並列探索を入れない段階で、FFO#40が結構速くなった。

いまさらながらに、FFOテストを40~59まで実行して比較しようとしたところ、
前から薄々気づいていたけど、FFO#41以後が遅い。酷いケースになると
探索ノード数が10倍=時間も10倍になる(#51)。自分のは指数関数的に
比較的にきれいにノード数が増加している。同じようなノード数のものもあるので、
ZebraやEdaxはどこかで上手にばっさり刈り込んでいる感じ。#52以後は時間が
かかりすぎて、未検証ですが。

ZebraやEdaxもノード/秒が一定しているので、置換表みたいな重い方法では
なく、簡単な方法で刈り込んでいるっぽい。とすると、moveorderかなぁ。
一応、MPCの99%で評価値の並び順は置換表に残してあるので、そんなに
間違った順番でソートしていないと思うんだけど。

あと、mtd(f)だと最初から最後までNullサーチしかしない事に思い至り、そこで
処理の効率化できる箇所が無いかと考えてます。Nullしかやらないんなら、
アルファ越えの再探索でウィンドウを広げる必要もないわけで。逐次探索部分
では効果不明だけど並列探索だとYBWCでPVを検索し終わるまで待つ必要が
そもそもない(仮アルファを求める必要がない)ので、多少速度アップできない
かなぁと。

450:310
16/05/27 00:36:10.52 gIFpjm1c.net
早々に状況が判明しました。ここに書くと進むんだよなぁ。

mtd(f)+negaScoutで繰り返し探索しながら、置換表に置換データを置いて、更に
それを並び替えに利用していたのですが、最初にPVを探索してしまうと、その後は
別の着手も評価値がαになってしまい、並び替えの意味が無くなっている感じです。
ちなみにPVだけは別ルートで必ず先頭に探索するようにしてあります。

というわけで、テスト的に初段のみ敢えて並び順を逆転させてmtd(f)を未使用にして
ただのnegaScoutで、mpc99%→全探索をしてみたところ、探索ノード数がかなり減り
ました。置換表使用の深さ全部で並び順を逆転させてみたら、mpcの99%ですら全く
終了する気配がなくなりました。

さて、どうやって実現しようかなと。
今のところ、mpcはかなり高速なので、これをnegaMaxにして。
いわゆる並び替え専用の浅い探査にしようかなと。

451:406
16/06/27 22:12:32.72 rUgIsnK8.net
対局場は結構難しいorzので一旦横に置いておいて
手始めにもうすこし簡単な1人ゲームからPHPで作ろうと思ってます。

具体的にはこれ

URLリンク(www.vector.co.jp)

の一人プレー場とランキングを作りたいです。
元ネタはコンウェイの天使と悪魔という問題みたいですね~。

452:406
16/07/02 23:28:52.20 qo9Pciu3.net
URLリンク(textuploader.com)

とりあえず、HTML & javascriptでシコシコ書いてます。
だいぶ大分形になってきました。
遊んでみてください。

453:406
16/07/02 23:40:37.16 qo9Pciu3.net
なんか文字化けしてんなぁ
なんでだ?
まあいいか

454:名前は開発中のものです。
16/07/14 21:31:20.75 GXGadAU3.net
必殺技が使えるリアルタイムアクションオセロまだですか

455:名前は開発中のものです。
16/07/17 23:40:28.28 M3Q2Msci.net
とりあえず公開しました。
ランキングはまだ未実装です。

URLリンク(nagata442000.xxx.ne.jp)

xxxはさくらに変えてください。

456:455
16/07/18 00:05:57.51 Lx2YZiAH.net
455=406です。

457:406
16/07/21 23:55:32.48 oilR8wYn.net
うーんアクセスがないぜ。
検索エンジンにも引っかからないし。
SEOとかいうのに手を染めるしかないのか?

458:406
16/07/27 00:25:34.27 42/ungMS.net
結果を保存できるようにした。

459:406
16/07/27 22:44:58.98 42/ungMS.net
棋譜を登録&閲覧&再生できるようにした。
そろそろ宣伝かな~。

460:名前は開発中のものです。
16/08/01 12:39:59.89 BFi+UVWj.net
このようなスレがあるとは…
自作でオセロソフトを作成している者です
現在は自己対局による学習中です
初手f5
以降ランダム7手~8手、
中盤8手読み
中盤で次善手を85%の確率で一手のみ打つ
終盤20マス空き読み切り
で300万棋譜集めようかと
この設定であれば一局1~3秒程度なので2ヶ月半くらいで達成できる予定です
まだ86万局程度ですが、今のところFFOはこんな感じです

FFO#40 (a2:+38) 1.36sec FFO#41 (h4: +0) 3.75sec
FFO#42 (G2: +6) 4.86sec FFO#43 (C7:-12) 6.33sec
FFO#44 (B8:-14) 9.46sec FFO#45 (b2: +6) 64.88sec
FFO#46 (b3: -8) 13.20sec FFO#47 (G2: +4) 5.66sec
FFO#48 (F6:+28) 67.74sec FFO#49 (e1:+16) 121.90sec
FFO#50 (d8:+10) 376.73sec FFO#51 (E2: +6) 86.08sec
FFO#52 (a3:+0) 132.61sec

461:406
16/08/02 00:17:59.05 R38aaX9h.net
だれかSEOのやりかた教えてくれ。

462:460
16/08/02 09:44:26.07 /HFRnWj4.net
白の得点が微妙にマイナスに傾いているので9手目までランダムに固定しました。
初手はf5なので8手目までだと白の方がランダム手数多くなってしまうことに気づいて・・・
9手目ランダムだと7手目までの評価値はまともな値にならないのですが、そこはBOOKでどうにかしようかと。
まともな値にならないだけで、互角定石以外に進行したりとかはしないので、とりあえず無視します。

463:406
16/08/02 20:37:12.35 R38aaX9h.net
Google検索で引っかかるようになったみたいです。
でもコンウェイの天使と悪魔なんてワード検索する人そんなにいないだろな。

464:310
16/08/03 14:35:23.97 WXOcEHjz.net
ここしばらく、評価関数に新機軸をと、ディープラーニングにトライ中ですが、
囲碁のように、畳み込みの画像認識の応用では、なかなか上手くいかないと
言うか、自分のパソコンで手におえるくらいの規模のネットワークだと全く歯が
立たない感じです。

というわけで、色々と手はいっぱい動かしているのですが、何にも成果があら
われていない状況です。

465:名前は開発中のものです。
16/08/03 22:36:32.67 u2EcbVrc.net
>>464
ディープラーニングってライブラリ使ってんの?
それとも自家製?

466:310
16/08/04 01:59:01.51 XH3ZGPYC.net
>>465
最初はGitHUBのDeepLearningの参考プログラムを元に自家製でAutoEncoderにDropoutをつけ
たりしてました。

次にCNNで、GitHUBでtiny-cnnというライブラリを落として使用。技術的に凝りすぎライブラリで、
解読するのにC++の勉強が主になってしまいそうなので、改造はあきらめました。

そして、今は、行列ライブラリ(Eigen)落としてきて、自家製に戻りつつあります。Sparse正則化の
ために、ミニバッチ処理をしようかと思って(最初のは逐次処理のみ)、ついでにAVX2命令や
並列化対応を、この行列ライブラリに頼ろうかと思ってます。

Eigen使ったMLPでxor解くテストプログラムは、さきほどできましたが、本当にこれで良いのか、
結構不安です。多少間違っていても、収束しちゃうときがあるので。
明日はAdagradに対応させる予定。何とか2~3層程度で収まらないかな。

パソコン環境が貧弱なので、あまり重い処理ができないのが最大の難点です。
もっとも、できあがった評価関数が重いと、探索深さが浅くなってしまうので、ある程度は妥協
しなきゃならんかなと思っています。

467:名前は開発中のものです。
16/08/04 22:03:08.50 5/KmfpOW.net
壮絶やな。
その情熱がうらやましいぜ。

468:310
16/08/05 20:44:21.05 sOgjr/Uz.net
楽しんでやってますので(笑

で、AdagradとSparse正則化ができました。Sparse正則化は思ったより時間がかかり
ませんでした。さすが行列ライブラリって感じです。AdagradとSparse正則化込みで、
結果も、正則化もちゃんと出来てますので、多分間違いはないでしょう。

今夜はオセロ関連ライブラリ持ってきて、学習データ作って、Sparse Auto Encoder
にしてテストです。全結合層クラスを積み重ねていくだけだし、データ作成は3回目
なので、後は簡単ですが、隠れ層のノード数と、目標とする活性ノード数を色々試す
のが面倒です。

まあ、ここまで全敗なので、あんまり期待していないけどさ(汗
やればやるほどBuroさんの評価関数の凄さがわかってきます。

469:460
16/08/08 01:32:00.53 1caSYJwt.net
PV-LINE(最善の着手リスト)の表示を実装してみました。
PVノードの更新は非常にまれな事象ですが、あまり深い所で表示更新すると
やはり探索速度に影響与えてしまうので、6手目以下の浅いノードで表示更新しています。

あと自己対局棋譜が100万局集まったので、中盤MPCパラメータを作成中です。
現在20手読みのカットペアの計算に入ったところで、これが終われば終盤MPCの実装に入ろうと思います。

470:名前は開発中のものです。
16/08/10 01:12:31.39 BL+f+Yy5.net
310と460はホントに別人なのか?
ディープにオセロAIに取り組む人が2人も現れるとはにわかには信じがたいw

471:310
16/08/10 22:37:11.88 C09Nh62j.net
>>470
他のスレで出会って、誘導させていただきました。
ほんと絶滅危惧種ですよね(汗


Auto EncoderにSparse正則化を加えましたが、やっぱり特徴抽出は
簡単ではないようです。Auto Encoderとしては申し分なく機能している
のですが・・・線形回帰をつけて評価値を算出してみたのですが、ただの
乱数返しているような状態になります。

なんか、微妙に恒等変換を学んでいる臭いんだよなぁ。むむむ。

472:名前は開発中のものです。
16/08/10 22:53:03.62 BL+f+Yy5.net
>>310はかなりハイレベルだと俺は思ってるが
>>310からみて>>460はいい線行ってるの?

473:310
16/08/11 23:18:44.20 M0iE7EXH.net
>>472
僕は全然ハイレベルじゃないですよ。
すぐ脱線して役に立たないことばかりやってるだけです。

別スレでお互いのFFOテストの結果を見せっこしたところ、
前半5つで、速度はほぼ同じくらいでした。

>>460さんと情報交換したところ、末端ノードの高速化の
方向性が全く逆だったのが意外でした。

474:名前は開発中のものです。
16/08/12 00:22:58.37 +2V5AEwc.net
ほほう
460さんも期待出来そうですな

475:460
16/08/12 02:42:42.36 mvQ0iJdF.net
>>472
自分はディープランニングなどの人工知能系はさっぱりなので・・・
310さんはよく勉強されていると思います。


自作オセロですが、今まで32bitで開発していましたが
今ではもう32bitOSを使用する方が稀だと考えて思い切って64bitに移行しました。
探索ノード数がいきなり10~20%程度上がってビックリしています・・・

476:460
16/08/12 04:26:50.73 mvQ0iJdF.net
あ、探索ノード数ではなく探索速度ですw
終盤探索だと10000Knps~15000Knps程度出せるようになりました。
自分の環境だとWZebraが20000Knpsなので、大幅に負けています・・・
そろそろチューニングも視野に入れつつやっていこうと思います。
まずは探索ノード数を終盤MPCで削減しなくては・・・

477:460
16/08/12 07:59:35.21 mvQ0iJdF.net
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
16/08/12 08:01:32.72 mvQ0iJdF.net
>>477
FFO#56はH2:+0ではなくH5:+2に訂正です。。

479:310
16/08/12 15:16:23.38 USoZXJIB.net
がーん。今まで、こちらはノートPCだしと、密かに思っていましたが、32bitでしたか・・・。
完全に脱帽です。

だったら、僕もこのスレで教わったAVX2とかBMIとかの組込関数使って、あとPPLとか
OpenMPとかで並列化して4コアなら3倍強程度なので、トータル4倍以上に速度アップ
すると思いますよ。つまり、その辺やるだけでEdax並まで行くかなと(汗

ちなみに、DeepLearningはあきらめ方向にだいぶシフトしてきました。

480:名前は開発中のものです。
16/08/12 16:41:11.53 8u/4Xx1J.net
仲間が出来ていいのう

481:460
16/08/12 17:56:57.44 wDmYSTDl.net
シングルスレッドだとトッププログラムですら合計2000秒台と限界があるので、マルチスレッド対応は必須ですよね
ただybwc等の並列化アルゴリズムの理解に時間がかかりそう…

482:310
16/08/12 20:50:39.55 USoZXJIB.net
>>481
YBWCはnegascoutのnull window searchを並列化して一括処理する
ようなものだと解釈して実装しました。

この辺はゲーム計算メカニズムなる本で勉強したかな。

並列処理のフレームワーク何使うかが問題ですね。
自分はVC++なのでmsdnで情報が得やすいPPLを使いました。
インテルTBBとかOpenMPなんてのもあります。
PPLは結構使いやすかったですが、速度は不明。
まあ、ルートの方でしか使わないので、あまり影響ないと思っています。

手組でマルチスレッドなプログラム書ける人には不要かも知れません。

483:310
16/08/13 14:18:44.65 D+1dBs0T.net
あ、考え方がnegascoutみたいだという事で。

484:名前は開発中のものです。
16/08/13 20:35:07.80 p7EbJiId.net
avx2って256bitだよな
オセロだと128bitしか使えないような?

485:310
16/08/13 20:47:52.09 D+1dBs0T.net
方向が8つあって、それぞれの処理を8回計算するとき、

右シフト方向が4つ、左シフト方向が4つ。
256bitは64bit×4。右シフトと左シフトで2回。

というわけで、mobilityとかflipとかで便利に使えます。

486:460
16/08/14 16:41:37.52 ALD5heTO.net
現在、終盤用MPCパラメータ作成中です。
23手完全読みのカットペアに入っています。24手読みの計算が終わったらいったん実装に入るつもりです。

>>310
YBWCに関して調べましたが、そうみたいですね。
MPCパラメータを作成している間に、なんとなくで適当に実装してみましたが
なぜかエラーで落ちまくりでしたw 
排他がかかっていない致命的な箇所があるのか・・・置換表は排他をかけたのですが・・・
PVライン生成あたりも怪しい、とりあえずもう少し調べてみないとダメそう。

487:460
16/08/14 16:42:16.06 ALD5heTO.net
>>310>>482の間違いです。。

488:名前は開発中のものです。
16/08/17 21:19:58.40 Z2gXWq7v.net
俺もボードゲーム系AIでディープラーニング書いてみたいと思ってるけど難しいんだろな。
論理もそうだけど膨大なデータが必要そうだし。

>>479
どのへんで諦めました?

489:310
16/08/18 15:43:08.07 7GnJQiSP.net
>>488
まだ細々やってます(汗

Eigenの導入と、少しづつ進んでいくC++技術のおかげで、前よりは試行の
スピードはアップしていますが、なかなか成果は出ません。まだ、色々な
パターンを試しながらディープラーニングって何ぞやを体感しているところ
なんだと思います。

少なくとも「簡単に凄い事ができそう」という幻想は捨てる事ができました(汗


ボードゲームがターン制なら、基本はmin-Maxになると思います。
まずは、盤面の状態に(恣意的で構いません)点をつける評価関数作るところ
から始めたらどうでしょう?

次のステップで評価関数に統計(線形回帰)を持ち込むと、ディープラーニング
じゃなくても、プレイ譜がたくさん必要になります。

オセロの場合は、Buroさんという先人が、実用レベルの評価関数が線形回帰
で作れる事を示してくれています。

僕がディープラーニングを適用しようと思っているのは、ただの思いつきでして。
場合によっては、より軽くて正確評価関数が作れるかと思いましたが、実際に
始めてみると、なかなか評価関数として機能してくれないし、仮にできたとしても
重いものになっちゃいそうという感じです。

490:488
16/08/19 23:15:11.39 i9HkvHw2.net
>>489
手動評価関数はかなり昔五目並べで書いたことあります。
min-maxで思考時間が1手5分くらいかかったけど、
自分でプレーして負かされることもあるくらいの強さにはなりました。

そのBuroさんの線形回帰とやらはWebで論文とか見れたりしますか?
読んでも多分理解できないだろうけどちょっと興味あります。

491:488
16/08/19 23:23:27.55 i9HkvHw2.net
ぐぐったらこんなのがあったけど多すぎ。
URLリンク(skatgame.net)

492:310
16/08/20 16:51:13.03 m44rb9b4.net
>>490
Buroさんが作った伝説のオセロプログラムがLogistelloです。
Thellというオセロプログラムの作者の方が日本語で解説してくれています。
URLリンク(sealsoft.jp)

5.2の計算の高速化のところの説明(P.8の冒頭)のところ。
自分なりに解釈したら、自分が解釈違いしたのか、説明がおかしいのか、
この通りではなかった記憶があります。

とはいえ、これはオセロの考え方であって、将棋なんかだとbonanzaなどを
参考にすべきだし、全く別のゲームであったら、別な事を考えなければなり
ませんね。当たり前ですが。

493:488
16/08/20 20:33:47.55 +7ONDgCM.net
>>492
パターンの重みの線形和が評価関数になる的なことが書いてあるっぽいですけど、
パターンというのは人間が与えてやるわけですよね?

そのパターンすら学習で求めるというのがディープラーニングなのかと思ってますけど。
まあディープラーニングにはロマンがありますね。

494:310
16/08/20 21:29:23.21 m44rb9b4.net
>>493
ですです。

あと、Deepじゃなくても、2層以上のパーセプトロンだと、線形分離不可能問題の
分類ができるようになります。XORの学習が典型ですね。

ところが、パターンの部分まで学習で求めてくれるってのは、やっぱり幻想でして。
ある程度パターンを想定しながら、ネットワークを作らないといかんのではないか
という事に思い至っています。

例えば畳み込みニューラルネットワーク(CNN)で、何故畳み込みをするのかという
と、縦線横線などの隣接ドット同士もつながりを識別してもらうためですし。そもそも
畳み込みのフォワード計算自体が、画像に対して例えば輪郭線強調といったフィル
ターかけるのと、プログラム的に同じものだったりします。学習対象は、フィルターに
なります。

オセロは、囲碁とかと違って、石の色がコロコロ変わるので、隣同士の石のつながで
判断するCNN的なネットワークをそのまま適用できないよなぁというのが、最近の諦め
ポイントであります。

じゃあ、何に頼るかというと、自分はオセロ弱いので・・・No ideaだったりします。
あんな簡単な(DeepLearningと比較して)線形和でBuroさんの評価関数ができています
ので、パターンを活かして、まずはそこに点数を割り振るところをMLPなんかでできない
かなぁと思っています。

495:488
16/08/21 00:04:33.21 EnsCDbgT.net
>>494

>ところが、パターンの部分まで学習で求めてくれるってのは、やっぱり幻想でして。
>ある程度パターンを想定しながら、ネットワークを作らないといかんのではないか
>という事に思い至っています。

ふーむそうなのか。残念。
聞きかじった知識だと夢のような技術なのかと思っちゃったけど、
実戦してみるとなかなか難しいのかぁ。

496:名前は開発中のものです。
16/08/21 21:39:11.08 EnsCDbgT.net
いくらオセロの盤面が小さいからってシングルスレッドで
10000Knps~15000Knpsというのはとてつもなく速く感じるんだが。
どうやったらそんな速度がでるんだ?
オセロ業界じゃ普通なのか?

497:310
16/08/22 02:41:50.59 2ubnBUwd.net
Kが余計で3桁間違えているんじゃないかと(汗

498:310
16/08/22 02:46:41.58 2ubnBUwd.net
あ、違った。自分が3桁間違えていた。

全然おかしくないです。自分の2コアで13000Kくらい出てます。
シングルで同等の速度ですから、かなり速いとは思いますが、
敢えて言うなら2倍程度なら縮められないとは思えない差です。

499:460
16/08/22 08:13:03.66 yZES3OuI.net
終盤MPCを実装完了してFFOを測定してみました。。
残すのはFFO#57のみですが、この時点で9364秒と1万秒を割ってるので
10%程度の高速化は期待できそうです。(評価テーブルは64ビット移行+120万局から変更なし)

500:460
16/08/22 09:20:01.85 qlwiS2PE.net
>>496
簡単な実装だと終盤探索は2000万ノード/秒いけますね。
合法手生成が将棋などより速いので。
とはいえ、中盤探索だと色々やるので5000knps程度に落ちてしまってます。

501:496
16/08/22 21:10:28.52 WzxI/O2e.net
2000万ノード/sとかってsseやavx使って始めて可能になるレベル?
オセロの合法手の実装になにかすごい効率的なビット演算やってるとか?

502:460
16/08/23 11:44:32.28 sSUGbl7L.net
>>501
終盤探索だと合法手生成は葉ノードの近くでは使わないので、ループや条件分岐を使ったコードでなければアセンブラでなくても速度はそれなりに出ますよ。
こことかが参考になります。
URLリンク(d.hatena.ne.jp)

自分はこんな感じのコードをアセンブラに落として少し改変したものを使ってますー

503:460
16/08/23 11:47:50.11 sSUGbl7L.net
置換表に超大バグがあることに気づき修正したらFFO45が32秒になりました…w
180万局の学習を朝に終えたので今晩再度FFOを測定しようと思います。

504:310
16/08/23 13:54:12.88 LVh7XLe+.net
>>502
そのサイトは知りませんでしたが、同じことやっています。
自分の場合は、それをAVX2命令で1,7,8,9ビットシフトを4つ並列で動かす様にして、
右シフト左シフト2回の演算をC++で組んでます。並べて書くと混乱しそうだったので
演算オーバーライドしまくりで、バグ防止しました。
やっぱりアセンブラの方が速いんでしょうね。


ディープラーニングな評価関数の方ですが、突然収束を始めました。
まだ途中ですが、見た感じざっくりで、平均二乗誤差の平方根(σ)が0.6石程度に
収まりそうです。2σで1石、スコアは2づつ変わるので、評価逆転が起きる確率を
数%程度にするには、0.5石以下にしたい。

肝はミニバッチのサイズだった様です(謎)。ハイパーパラメータとしては考慮対象外
でしたが、テスト用に小さくすると収束が悪くなる感触があったので、思い切って大き
くしてみたところ…大きくすればするほど記録を更新していくという状態。ついに212640
件という特大バッチサイズにしてしまいました。メモリー的にはまだいけるかも。

今までの比較検討データは全てパーになったので、検討済のネットワークも、バッチ
サイズ変えて再評価です。今やってるのは、Buroさんパターンがベースのネットワーク
ですが、もしかしたら入力ベタ打ちで「勝手に特徴抽出してくれる。すげー!」に戻るかも(汗

505:名前は開発中のものです。
16/08/23 19:39:22.88 1+aieVpn.net
>>502
ループはおろか条件分岐すらいらんのか(驚愕)

>>504
おお、ディープラーニング期待してます。

506:名前は開発中のものです。
16/08/23 21:26:59.10 KqeLXU8U.net
文系の俺には全然分からん。
もっと簡素な3目並べなら勝てるAIとか作れないかな(´;ω;`)

507:名前は開発中のものです。
16/08/23 21:47:29.66 1+aieVpn.net
ちょっと興味が湧いたんでとあるオセロアプリ落としてやってみた。
弱設定AIが程よく負けてくれて嬉しいw
一方的にボコされたら詰まらんよな一般人は。
オセロAIはもう神の領域だし。

508:460
16/08/24 01:02:17.32 elb1k4A2.net
色々チューニングしてトライしましたが、FFO57を大きく落としてしまい、放心中ですw
FFO57以外は全体的に高速化しているのですが、合計としてはあまり変わらない結果に・・・
終盤MPC探索中にa6とg7でかなりふらつくので、置換表に次善手も入れておかないとダメかもしれません。
とりあえずEdaxとゼブラのオーダリングあたりのソースを見直す予定です。

name    move    time[s]   node[Mn]
FFO#40  a2:+38   1.05     10.61
FFO#41  h4:+0    3.23     37.85
FFO#42  g2:+6    2.43     31.69
FFO#43  G3:-12   7.69     79.04
FFO#44  D2:-14   5.09     48.95
FFO#45  b2:+6    30.21    409.43
FFO#46  b3:-8    7.23     78.8
FFO#47  G2:+4    3.1     38.9
FFO#48  F6:+28   19.58    207.46
FFO#49  e1:+16   45.11    527.45
FFO#50  d8:+10   144.14    1330
FFO#51  E2:+6    39.91    502.74
FFO#52  a3:+0    52.56    687.22
FFO#53  d8:-2    617.63   8360
FFO#54  c7:-2    944.7    13410
FFO#55  G6:+0    測定中
FFO#56  H5:+2    262.85   3410
FFO#57  a6:-10   1523.67  19710
FFO#58  g1:+4     674.09   9760
FFO#59  g8:+64    1.08    5.57

合計4385.35[s](FFO55未測定) 合計ノード数:58645.71[Mn]

509:310
16/08/24 10:40:19.04 GpcelPIW.net
こちらも大バグを見つけて放心中です(汗

ミニバッチサイズごときで収束具合が大きく変わるのがおかしい点。
ミニバッチサイズを大きくすると、収束点がかなり規則的に減少していくように見える点。
この2点から、寝ながらデバッグしてたんですが、テストデータの件数で平均を出すべき
ところで、ミニバッチサイズで割っていた事に思い当りました。

で、修正して、行列の列数で割るようにしたのですが、今度は列数がリセットされていない
事が判明。どうもポインタ渡しで行列を渡した時に行数・列数が正しく引き継がれないよう
な現象のようです。

というわけで、一瞬大喜びしましたが、全くのやり直しとなりました。

510:460
16/08/24 14:56:52.40 Kkx6VEyM.net
>>509
学習プログラムのバグはやっかいですよね。
自分も何回ひどい目に遭ったか…
今でもまだありそうな気がして怖いですw

511:460
16/08/24 22:16:05.70 elb1k4A2.net
FFO57をどうにかしようとチューニングをして、なんとかFFO57が1200秒台に縮まりました。
ある程度縮まったので、期待せずにもう一度全部を測定してみると
全体がかなり高速化されていて、FFO55がまさかの3774秒までに縮まりました!(奇跡)
とりあえずこれをオーダリングの暫定最終結果として、次は並列化に手を出してみようと思います。
まずはYBWCアルゴリズムの実装方法の検討から・・・

FFO#40 (a2:+38) 1.05s FFO#41 (h4: +0) 3.19s
FFO#42 (G2: +6) 2.55s FFO#43 (G3:-12) 7.82s
FFO#44 (D2:-14) 4.18s FFO#45 (b2: +6) 29.77s
FFO#46 (b3: -8) 6.99s FFO#47 (G2: +4) 3.10s
FFO#48 (F6:+28) 19.49s FFO#49 (e1:+16) 36.63s
FFO#50 (d8:+10) 128.15s FFO#51 (E2: +6) 50.46s
FFO#52 (a3:+0) 36.88s FFO#53 (d8:-2) 427.77s
FFO#54 (c7:-2) 730.26s FFO#55 (G6:+0) 3774.07s
FFO#56 (H2:+0) 185.22s FFO#57 (a6:-10) 1281.31s
FFO#58 (g1:+4) 556.86s FFO#59 (g8:+64) 1.08s

合計:7286.83[s]

512:310
16/08/25 00:17:23.06 ZE8G6YuY.net
>>510
Eigen導入前のプログラムみたいにFFOの盤面渡して評価値見るようにしていれ
ば良かったのですが、あまりに収束しないので、収束の兆しが見えてからやろう
なんて放置していたのが失敗でした。あまりに急速に状況が改善していったので、
0.5石切るか知りたくなって、確認が後回しになってました。反省orz

ちなみに、列数がリセットされない問題も、原因がわかりました。
これも自分のミスというか、Eigenの使い方間違ってました。

Eigen便利すぎて、少なくとも行列演算部分に関してはバグフリーで、簡単に先に
進めちゃうので、細かいところがなおざりになっていたような感じです。

513:460
16/08/25 11:20:22.96 PNQVZmVa.net
そういえばFFOに夢中すぎて中盤の強さ評価を忘れていました。
現在は180万局の学習が終わっていますが、ゼブラ(24手読みBookなし中盤誤差なし)と黒と白で戦い、
それぞれ+8と-2という結果になりました。
完全にBook無しだと、白黒両方とも虎定石からのe3酉定石に分岐するため、
金魚や大量取りなどの主要な引き分けオープニングからの勝率を測定しようと思います。
あとHTML5版のMasterReversiレベル3とも対戦してみましたが、白黒両方とも-2という結果に…orz
Book構築方法もそのうち考えようと思います。

514:460
16/08/27 00:02:49.98 ct+QEGYU.net
学習プログラムのバグが怖くなって見直してたら超大バグを見つけました・・・
パターンモデルのうち、triangle(Thellが用いているモデル)だけが
局面出現数のカウントリセットされておらず延々と増え続けていましたw

あと同じ棋譜が結構あり、ダブった棋譜を全て除去すると180万局よりも10%程度減りそうです。
とりあえず除去中の150万局の棋譜でもう一度再学習します・・・orz

515:460
16/08/27 13:15:04.86 ct+QEGYU.net
学習プログラムのバグを直して再学習させたWZebraとの対局結果ですが、芳しくないです。。
棋譜生成で次善手を選ぶ時、打った後の7手読み(対局が8手読みなので)評価値で全ての手をソートしてから
2番目を選んでいるのですが、評価誤差を全く気にせずに選んでいました。
最善手が+10でも次善手が-4とかいう局面も結構あるので、そういった誤差が大きい手を選んでしまうと棋譜の質が低下します。
なので、最善手と次善手との誤差が-2以下の場合のみ次善手を打つようにしました。
その代わり85%で1回打つという処理を単に5%で打つように変えています。
これでなんとか中盤が強くなればいいですが・・・

516:460
16/08/27 13:18:13.50 ct+QEGYU.net
WZebra24手読みBOOK無し評価誤差なしとの対局結果

ゼブラは評価誤差がEdaxやMasterReversiに比べて大きいので、本来負けちゃいけないんですよね。。
実際50万棋譜計画のやつで学習させた場合はほとんど勝っていました。(負けても-8とかはありえない)

牛定石[f5f6d6]

黒持ち:+2
白持ち:+0

酉フック[f5d6c3d3c4f4c5b3c2e3]
黒持ち:+8
白持ち:-8

金魚[f5d6c3d3c4f4c5b3c2e6]

黒持ち:-2
白持ち:+4


FJT[f5d6c3d3c4f4c5b3c2e6]
黒持ち:-4
白持ち:+2

コンポス[f5d6c3d3c4f4f6]
黒持ち:-2
白持ち:-6

517:名前は開発中のものです。
16/09/01 22:33:13.77 PkLGbL4G.net
マイナーゲームで良質の棋譜が大量にない場合、どうやって学習させればいいんだろう?

518:名前は開発中のものです。
16/09/02 09:47:35.76 +DjGOwAN.net
事前学習じゃなくて、強化学習な手法を試したら良いのではないかな。
何をどうすれば良いのか、俺はわからんけど。

519:名前は開発中のものです。
16/09/03 00:54:14.21 lICUKSF2.net
うおお線形回帰とか最小二乗化とかわかんねぇぇ

520:名前は開発中のものです。
16/09/03 20:21:58.46 lICUKSF2.net
とりあえず自己対戦棋譜が1000局集まりそう。
まだ足りないかな?
ここからどう学習させればいいのか…

521:名前は開発中のものです。
16/09/03 21:00:16.00 DJdWXbUx.net
自分も機械学習とか興味あって細々作ってるけど、とても難しい
学習以外の部分も難しくて辛かったけど、学習はなかなか思い通りにするのに苦労する

とりあえずオンライン学習ってので、自分なりに色々やってみたけど
やっとちょっと上手くいき始めたかなってところ
ミスって学習やり直しとか何回もしてしまった

522:名前は開発中のものです。
16/09/03 22:28:55.42 lICUKSF2.net
今ブラッドリーテリーのモデルとやらを調べてる
数式ムズイT△T

523:460
16/09/04 01:59:20.91 f4dqEnZp.net
>>520
オセロは今でこそ強いソフト同士の棋譜が手に入りますが、
初期は人が対局した棋譜(ISOなど)を残り十数手のみ修正して学習させていたようです。

マイナーゲームが何かによりますが、オセロみたく終盤で神のような読み切りが出来る場合は
自己対局の教師あり学習で適当なモデルでもかなり強くすることはできるかと思います。

524:460
16/09/04 02:00:39.37 f4dqEnZp.net
レス番号間違えました。。>>523>>517宛てです。。

525:460
16/09/04 02:14:06.21 f4dqEnZp.net
自己対局中は暇なので、GUIの拡大縮小対応に手を出してみようと思ってドツボにはまりました。。
C#って描画ほんと遅いですね。。フルスクリーンにするとリスケールも含めて150msecぐらいかかります。
1024x768くらいだと50msecなのでギリギリ許容範囲内かなぁ。

あとGUIの実装に合わせて定石の変化度をツールバーから選べるよう実装していたのですが、
変化度を上げると着手時になぜか頻繁に落ちることが判明。
調べると、定石の木構造を作る処理に壮大なバグがあり、
30万近くある定石のうち1万くらいしか読み込めておらず、
リストも頻繁に上書きされてめちゃめちゃ状態でした。バグというか実装になっていないレベル。。
変化度を弄った時の処理をほとんどテストしなかった数年前の自分を殴りたい。。
かなり昔のコードなので、もう修正をあきらめて再設計して一新しているところです。

526:310
16/09/04 17:00:43.77 WEaBeSKk.net
実際、開発中ってアドレナリン出てるから、ほとんどノーテストで行けるところまで
行っちゃって後で何やってるの俺?って事がしばしば(汗

というかここ数日も、非常につまらない確認漏れというか、毎回間違うswitch文でバグ
出しているのに気づかずに、これはメモリーリークか?それとも計算式が間違ったのか?
みたいな状態になっていました・・・。

さて、今いじってるディープラーニングの仕組みは、かなり汎用性持たせて作ってます。
あまりに収束具合が悪いので、試しに、Buroさんモデルにしてみました。1層の活性化
関数無しにして、入力プログラムを流用するだけなので簡単です。でも、なかなか収束
しない。そこで、過去にどこまで収束したのか、残ってるログを探したところ・・・実際、
同じような感じ(1σ=約3.5石)でした・・・つまり、なんかできてると言えばできているし
これで満足かといえば満足ではなしと。また、なまじデバッグでまじまじ評価値を見ちゃっ
たため、これで本当に使えてるのか?状態です。

で、ミイラ取りがミイラになって、ディープラーニングの学習係数の最適化手法とか、
学習効率向上の方法を色々実装してました。勾配ノイズなる手法も入れてみました。
一体自分はどこに向かっているのだろうって状態です。

527:460
16/09/05 19:53:28.81 5Av5ahUz.net
そういえば散々オセロソフトを開発しておきながらネット対戦のオセロを一回もやった事ないなと思い・・・
やってみると案外勝ててしまいました。
この形は有利不利とかイメージだけで打っていましたが、、人間のパターン認識も結構優秀ってことですかねw

528:460
16/09/05 20:11:21.05 5Av5ahUz.net
>>526
ディープランニングはやはりなかなか曲者のようですな。
こちらも終盤の評価値が悪いところはよく見えて良いところは悪く見えるという平均化が起こっていてやばいです・・・
まずは次善手の割合を調整したのでどうなることやら。。
というかもうランダム数手をやめて、引き分けオープニングからの棋譜生成を重点的にやった方がいいのか考え中です。

529:名前は開発中のものです。
16/09/05 20:52:57.56 A3E5Chzv.net
学習始めたら速いPCが欲しくなってしまった
結果が出るまで時間掛かるなあ

530:310
16/09/05 22:33:11.28 KkVISbKe.net
上に書いた通り、線形回帰はディープラーニングに内包される計算手法ですので
(実際に最急降下法とバックプロパゲーション部分以外の計算式はほぼ同じ)、
学習率の設定にディープラーニングの最新の手法が使えるんじゃないかと思います。

学習率を外から与えるのではなく、初期値だけ与えて、後は誤差の具合を管理して
動的に変える。しかも、各重み毎に個別に学習率を変える。という発想です。

参考)
URLリンク(postd.cc)
URLリンク(qiita.com)
※)数式で、ただの変数のように書いてますが、行列だったりベクトルだったり解読が必要です

自分はこの中で一番新しいSMORMS3を使用してみたところ、モーメンタム法の10倍
以上の速さ(学習回数)で収束するようになったと感覚的に感じています。大体30~
50回も回せば収束してしまう感じです。実装&テストだけして確認していませんが、
AdamやRMSpropでもそん色ない程度には速くなると思います。

でも、早いPCで解決できるんなら、それに越した事はありませんねorz

531:名前は開発中のものです。
16/09/05 22:36:42.16 omFelghI.net
remi coulomの書いたMM法のコード見つけたが難しくて読めないorzorzorz
頑張って読むか

532:310
16/09/05 22:41:44.52 KkVISbKe.net
いかなディープラーニングでも評価関数をいきなり作るのは厳しい気がしてきてます。

ここはアルファ碁の学習の仕方にならって、最初は次の1手を学習させてみようかと。
で、今までは頭でわかったつもりになっていた、多クラス分類問題を調べてみると、
Softmax関数の微分(バックプロパゲーションで必要)がわからない事にあらためて
気が付きました。

幸い、Softmax関数の定義があるひな形プログラムがあったので、これから解読です。

人さまのプログラムを見ると、自分がいかにC++を知らないのか、思い知らされますorz

533:460
16/09/07 01:48:41.72 UfwPrMcb.net
自己対局ですが、8手読みの20マス空き完全読み設定だと、2日で大体20万局終わることが分かりました。
ここまで速いと10手読みの22マス空き読みにランクアップしてみたいところ。。
体感だと1/3くらい遅くなっているのですが、22マス空き読みだと偏りもひどくて、
1~2日やってみないとなんとも言えない感じです。
2日で7万局程度終えられるなら、それでのんびりやろうかと思います。

534:460
16/09/07 03:02:28.63 UfwPrMcb.net
今しがた動かし中ですが、400局完了まで16~17分でした。
1時間で1400局程度できそうなので、1か月で100万局くらい行けそうです。
とりあえずこのまま100万局集めようと思いますw

あと、初手ラムダムをやめて最悪手が数%程度で打つよう、評価値によって着手確率を調整しました。
最悪手の絶対値の1.2倍をそれぞれの評価値に加算した後の総和を使って
それぞれ加算した評価値を除算という古典的な方法ですが・・・
この方法だと絶対値が0に近いと悲惨な事が起こるので、絶対値は>=4にしています。

535:名前は開発中のものです。
16/09/07 23:27:08.71 4MEE20eO.net
誰かヘルプ!
このページのmm.tar.bz2の使い方わかる人いない?

URLリンク(www.remi-coulom.fr)

makeしてexe作るところまではできたんだけど
README通りにmm.exe < input.dat > output.dat
ってやってもoutput.datが空ファイルにしかならない。

536:460
16/09/07 23:57:41.97 UfwPrMcb.net
>>535
とりあえずmm.exe < input.datでコンソールに何が出てきてるか見た方が良いかも。
Cygwinでやるとこんなの出てきました。

$ ./mm < input.dat
..
Games = 2
Feature1 -0.89588 2.44949 0.0285792
Feature2 -0.867301 2.38048 0.15838
Feature2 -0.708921 2.0318 0.0737065
Feature2 -0.635214 1.88743 0.0358307
Feature2 -0.599384 1.821 0.0187057
・・・(略)・・・
0 1.49416
1 1.21426
2 0.586193
3 0.668003
4 2.13451

outputは下5行だけが出力されるみたいです。

537:535
16/09/08 00:10:42.63 /oQCQhP8.net
>>536
おお、返信ありがとうございます。
mm.exe < input.datやってみましたが何も出ないです。
もしかしてinput.datはなにか編集しないといけないのでしょうか?

538:535
16/09/08 00:16:47.92 /oQCQhP8.net
すいません。
makefileからコンパイルオプションを取り除いたところ結果が出力されました。
-O3がダメなのかなぁ。

ともかく、ありがとうございました。

539:460
16/09/08 00:21:28.75 LcwQkLYi.net
>>537
input.datは全く編集せずにやりました。
Cygwin64bitだと動くのですが、環境によっては動かないんですかね・・・
gcc-5.4.0でビルドしましたが、コンパイラのバージョンの差異も原因かもです。

540:460
16/09/08 00:23:56.75 LcwQkLYi.net
>>538
動いてよかったです。
最適化が悪さしていましたか。。-O1程度の方がいいかもですね。

541:460
16/09/10 21:06:28.42 FA2ccDEd.net
>>534の読みを深くさせた自己対局棋譜ですが、15万程度集まったので
無理やり学習してWZebraと対局させてみたところ、黒持ちで+12、白持ちで+2でした!
次善手や序盤ランダムの考慮と読みを深くした効果が現れてて安心しました。。100万達成した時の結果が楽しみです。

542:460
16/09/11 09:03:13.98 UepiTkRD.net
ついにBOOKの読み込みとアルファベータによる手の選択を実装できました。
まだ最善しか着手できないので、誤差率によるランダム着手も実装しようと思います。
ゼブラのExtra-Bookをそのまま使っているので、ゆくゆくは自力で構築できるシステムを
考えたいところ。。

543:名前は開発中のものです。
16/09/11 11:41:57.36 dMHrH3w2.net
>>542
やっぱり最終目標は完全解析なんですか?

544:460
16/09/11 15:25:12.97 UepiTkRD.net
>>543
いえ、さすがにそこまでは・・・w
Edaxの作者が完全解析を先行してやってるみたいですし、そこは任せようかなと。
最終的にEdaxやMasterReversiと同等の評価関数やBOOKを作成できるレベルまで持っていきたいです。

545:535
16/09/12 21:36:16.05 vkOlNla9.net
>>535です。
<number of gammas for this feature>というのがよくわからん。
とりあえず1にしとけばOKみたいな?
input.dat色々いじってみたけど確かにそれっぽい値はに出る。

546:310
16/09/12 22:52:49.52 5hD0Gf9W.net
>>460さん、着実に進んでいてうらやましい。

自分はというと、だんだんとオセロの事は忘れて、ディープラーニングのプログラムの
確認修正、機能追加に頭がスイッチしちゃってる感じです。むむむ。

C++スキルも微妙に上がってきていますので、オセロ側に戻る時も、もう1回1から
全部コーディングしなおした方が良いかもw。ほとんどCの状態から始まって、もう3回
くらい書き直しているので、そんなに時間かからないと思うし。

と、どんどん脱線していくのであった。

>>545さん
そのプログラム見てないですが、γというと、たいてい何かの係数パラメータじゃないかと。

547:535
16/09/12 22:58:52.81 vkOlNla9.net
>>546
返信ありがとうございます。
係数ですか。詳しい説明がどこにあるのかわからなくて。。。

プログラムって最初から書き直すほど洗練されていきますよねw

548:535
16/09/14 22:57:07.95 lQtAf6dT.net
本番のデータ使うと結果が表示されないorz
入力ファイルの形式なんか間違ってるんだろうけど
何間違ってるのかわからんorz

549:535
16/09/15 21:47:58.41 NUOEmvbB.net
もしかして万が一だけど同じフィーチャーに属するガンマは同じチームになれないとかあるのか?

550:535
16/09/15 23:35:36.05 NUOEmvbB.net
うお~わかんねぇぇぇ
コード熟読しかないのか?
厳しいぃぃぃ

551:310
16/09/16 00:03:09.94 44uFy3HE.net
featureってコンピュータの世界では、機能を意味するよね。
あと、もう一度読み返すと、γが複数形になってるので、
γの数であってγの値ではなさそう。

「この機能で使用するγの数」となるけど・・・
これだけだと正直なんのこっちゃだねw

この機能が何を表すかどこかに書いてないの?

552:名前は開発中のものです。
16/09/16 07:31:01.43 mrye4Vvn.net
もう一年くらい将棋をちまちま作ってるけど、なかなか強くならないな
最近ようやくアマ高段くらいには行った感じだ
ランダムでただ指すところから始めて、先人の歴史を全部なぞるようにプログラムして来た

みんなはゲームは違うだろうけど、もうその筋ではかなり強いレベルなの?

553:460
16/09/16 13:50:57.59 gJ0b6G2+.net
自己対局での棋譜生成ですが、10手読みだとまだまだ精度が落ちるようで、思いきって中盤16手読みの24手読みにしてみたところ…10分で35局…w
今日は出勤時間がせまっていたのもありこのままで生成していますが、
中盤14手読みか12手読み、22マス空き完全読みにした方が良さそうです。

ああ、PC10台くらい並べて棋譜生成したい…

554:535
16/09/16 21:02:11.49 l6ih+FVI.net
>>551
返信ありがとうございます。

どこかに解説あるんですかね?
ちょっと本気で探してみるか…

555:名前は開発中のものです。
16/09/16 21:22:13.05 l6ih+FVI.net
URLリンク(www.remi-coulom.fr)
の「囲碁の手のパターンのEloレーティングを計算する」をよみゃいいのかな?
もしかして

556:535
16/09/16 22:26:17.01 l6ih+FVI.net
囲碁の手の特徴にパス、トリ、伸び、自己当たり、当たり、
盤端との距離、直前の手との距離、2手前の手との距離、モンテカルロオーナー
などがあると書かれている。

feature=特徴?

557:名前は開発中のものです。
16/09/17 22:31:21.85 mQ7ypIPZ.net
下がりすぎ
上げるぜ

558:460
16/09/18 02:39:21.57 6855FAgd.net
オセロオンラインというアプリに付属されている真・HAYABUSAと対戦してみました。
どうも定石がかなり充実しているようで、普通にやってると
こちら側が記憶していないドロー進行に分岐されて負けます。。
しょうがないので野兎とか序盤から不利な定石に分岐して評価関数の勝負に入らせると、案外勝てましたw
評価チューニングがEdaxなどに比べると結構甘いようです。
とはいえ国産アプリでここまでチューニングされているとは思わなかったので驚いています。

559:名前は開発中のものです。
16/09/18 09:21:43.32 u+E0nELs.net
おめでとうございます

ひょっとして物足りないと感じましたか?
それなら次は
PREMIUM・HAYABUSA に挑戦してみませんか?
いまなら特別キャンペーン中につき(ry

560:535
16/09/21 00:02:39.39 DjDR9tnr.net
すいませんが誰か俺のデータを>>535のmm.exeにかけてみてくれませんか?
まじで何が悪いのかさっぱりわからん。
環境の問題かも?

URLリンク(thuploader.orz.hm)
のmy_input.zipが俺のデータです。

だれか親切な方よろしくお願いします。

561:310
16/09/21 01:01:30.09 CFP8O8Vn.net
>>558
URLリンク(www.slideshare.net)

これですね。色々AIの特徴を説明してますが、まあLogistelloの
日本語解説みたいな感じで、皆さんのAIもほぼ同じ構造かなと
思います。

テレビ番組企画でEdaxと良い勝負するAIを短期間で開発したという
のが開発経緯らしいので、恐らくEdaxをたたき台にして定石DBの
学習をしていると思います。

つまり、Edaxよりちょこっとだけ強ければよいと割り切った目標をたて、
目標がはっきりしている分、手間をかける箇所を、定石DBの対局学習に
集中したって感じだと思います。想像ですが。

で、これ読んだ時に、オセロAIの強さって結局は定石DBじゃんと、
結構真剣に思いまして・・・。まあ、それゆえ、オセロAIの開発者の多くが
ドロー進行のリストアップに走ってしまったのかなぁと。

562:535
16/09/21 20:18:28.81 DjDR9tnr.net
環境が悪いのかと思い押し入れからノートPCを引っ張り出して走らせてみたところ
計算結果がNaNになってるっぽい。
駄目なのか?うーむ。

563:460
16/09/22 13:08:07.84 aLXK2a2e.net
>>561
ほとんど考えずに打ってくるので、もしやと思い定石からわざと外してみたらいきなり10秒超の長考でした・・・w
本当にBOOKの精度がEdaxよりちょっと良いのでしょうね(逆に言うとそれだけ)
開発期間が短期間って制限があったらしいので、しょうがないのでしょうけどもったいない気もします。

564:310
16/09/22 20:43:51.38 esximYO0.net
BOOK学習ってあんまり実装例見ないので、その点は評価しても良いかなと。
Buroさんの論文はあるので、自分もいずれは実装しようと思っています。

が、BOOK学習で、別のオセロプログラムとひたすら対局学習させると、そのプログラム
相手限定ならほぼ負けないBOOKが得られるんです。

EdaxのBookは引き分け進行のリストアップで、そこに記載されていない分岐は、基本は
分岐した方が負けるはずなのですが、分岐後は純粋に評価関数の読みの勝負になるの
で、いかなEdaxでも間違える事があります。で、勝った手順、負けた手順をリストアップし
ていき、負けたら勝つ手順が見つかるまで、ランダムな手番で別の分岐を探していく。

Edax側がBOOK学習をオフにすれば、間違えた箇所は何度対局しても同じ間違いをする
ので、勝った手順になれば勝ちは確定し、負け手順は自分は打たないようになっていく。
要するに、そのプログラムの弱点を学習する事になるので、勝率が上がっていく。

EdaxのBookより精度が良いというのとはちょっと違う気がします。

とはいえ、Edaxとかの引分進行リストをパクっても意味が無いし、限られた時間で、パソコン
ぶん回して引分進行を発見していっても、間に合わないしで、これしかやりようがないんだ
とは思います。

実はこれに気が付いた時、BOOK学習+乱数着手(打たない箇所がない)で、自己対局を
延々と続けていくと、究極のBOOKができるんじゃないかと妄想してしまいましたが、よくよく
考えたら、それって全手順リストアップというか、完全解析大差ない事に気が付きました(汗

565:535
16/09/22 21:29:54.82 kzrJOomn.net
RemiさんのMM法諦めるしかないのかなぁ
他の学習方法探すか…

566:535
16/09/27 23:07:26.38 AU3JIk+S.net
いまいち手ごろな強化学習が見つからなかったので
モンテカルロ木探索をパターンに応用することにした。

567:535
16/09/28 22:21:31.56 DgDU0GF3.net
とりあえずConnect 4のAI書いてるんだけどまあまあ強くなってきた。
Connect 4は完全ソルバが公開されてるので
先手でこれに一発入れるのが当面の目標。

Connect 4 完全ソルバ
URLリンク(connect4.gamesolver.org)

568:535
16/09/29 20:34:59.17 1GHOMTNV.net
評価関数の基になるパターンが悪いせいで
一生学習しても完全ソルバに勝てない気がしてきました。

569:535
16/09/29 21:12:02.15 1GHOMTNV.net
まあ、Connect 4は習作なので一定の成果が確認できたということで一旦休止します。
これから本番のゲームに着手します。

できたConnect 4のexeをアップしてみます。
URLリンク(fast-uploader.com)

Connect 4の経験がない人にはかなり強く感じるはずです。
遊んでみてください。

570:535
16/09/30 22:44:03.81 Ol1OvzoR.net
人為的なパターンを評価関数の基礎においてると
幾ら学習しても完全解析にたどり着かない可能性があるよね?

十分学習すれば完全解析にたどり着くと保証できる
出来るだけ効率の良いパターンセットてのは
なんとか数学的に割り出せないだろうか。

571:460
16/10/01 15:19:39.34 NwASWJgd.net
>>570
オセロしか開発したことがないのですが、connect4のノード数だと4兆程度だと聞きました。
オセロよりも合法手生成が簡単かつ常に7つなので、相当早い段階から完全読み出来そうです。
現在のAI同士を戦わせて数千から1万局程度の棋譜を作成すれば、
簡単なモデル(縦横斜めだけとか)でほぼ完ぺきな評価関数が線形回帰で
出来そうな気がするのですが、どうでしょうか。

572:535
16/10/01 16:21:13.92 UW3pMcrq.net
レスありがとうございます。

線形回帰は試したことないですが縦横斜めのモデルで
勝率で重みを振って評価関数を作ったのが>>569です。

線形回帰で学習させれば>>569はもっと強くなるんですかね。

縦横斜めモデルは意外とイケてないんじゃないかというのが今の私の感触です。

あと初手から10手目位まではBOOK作ったほうが良いのかなぁとも思ったり。

終盤完全読みは今やってないですが、やってみる価値ありそうな気がします。

573:535
16/10/01 22:20:23.15 UW3pMcrq.net
ちょっと思いついたんで、縦横斜めのパターンに加えて、
盤面の空マスの情報をパターンに加えて再学習させてみます。

もしかしてこれなら完全ソルバに一発入るかも?

574:460
16/10/02 00:33:37.72 jNeryq9p.net
>>572
完全読みは深くすればするほど線形回帰で有利になってくるのでオススメです。
オセロでも20手読みの棋譜と22手読みの棋譜では2手違いなのに強さが段違いでしたので・・・

575:535
16/10/02 00:38:22.45 8lzQrfNi.net
レスありがとうございます。

オセロでも20手も読めるのか!
Connect 4ならもっと読めないとダメですね~

線形回帰はちょっと調べてみます。

576:名前は開発中のものです。
16/10/02 01:27:36.48 8lzQrfNi.net
完全読みかなり厳しいorz
なぜオセロは20手も読めるんだろう?
よほど実装がいいのか?

577:460
16/10/02 04:03:56.40 jNeryq9p.net
>>576
オーダリングはしてますか?オーダリング無しだと20手は厳しいと思います。
オセロは最後あたりだと数マスしか無くなるので合法手が1手しかないとかも頻出するのですが
connect4は最後まで7つあるので、20手はちょっと難しいかもですね。。

578:名前は開発中のものです。
16/10/02 18:53:33.45 8lzQrfNi.net
すいません。
オーダリングとはよさそうな枝を先に読むってことでしたっけ?
なぜそれで計算量が削減できるんでしたっけ?
最終的に全部読むなら結局同じのような…
素人考えですが。

579:名前は開発中のものです。
16/10/02 19:09:19.16 8lzQrfNi.net
完全ソルバと対戦させると誤った学習をしてしまってるように見えます。
悪い手を良い手と思ってる。
うーん。
学習量が足りないだけなんだろうか?

580:310
16/10/02 20:32:53.90 n86BxDyi.net
>>578
αβ刈りしているでしょ。

最初に読んだ手でα値が最高値になる。
次の手を1段読んだ時、それを超える手が出ないので、全ての手がβカットの対象となる。

本当に一番良い手を選べるんなら、そもそも読む必要がないけど、何らかのヒューリスティック
な基準でよさそうな手から読むと、それが正解だった時に、βカットが大量発生して、実際に
読む事になるノード数が激減する。

αβ刈りみたいな方法は、後ろ向き枝刈と言って、完全読み切りに必要が無い手を読まずに
済ます手法。

581:名前は開発中のものです。
16/10/02 20:59:00.22 8lzQrfNi.net
レスありがとうございます。

αβですか~。
実はあれ、私、理解してないんですよね。
説明読むとなんとなくわかった気になるんですけど
いまだ実装できたことない。orz
MinMaxなら実装できるんですけどね。

582:名前は開発中のものです。
16/10/02 21:29:32.92 8lzQrfNi.net
αβが最高に上手く働けばMinMaxの倍の深さ読めるんでしたっけ?
それなら20手行けそうですね。

583:535
16/10/03 00:03:31.42 5qtC3pHr.net
完全ソルバでいろいろ試してるんですが、
Connect 4って思ったよりずっと底の浅いゲームのような気がしてきましたw

□□□□□□□
□□□○□□□
□○□●□○□
□●□○□●□
□○□●□○□
□●□○□●□

この配石が必勝法の骨格のようです。
ここさえ押さえればあとは自動的に勝つる。

584:310
16/10/03 01:55:16.80 alBluDZI.net
>>582
深さはなんとも言えないけど、オセロで言えば、αβだけでノード数は1/100くらいに
なるってどこかのサイトに出ていたかな。1/100だとアバウト2~4手くらい深く読めるはず。

置ける箇所が結構絞られるゲームなので置換表入れたら更にいけるかもしれない。
あとはビットマップの実装だね。

ゲームの規模的には(ネットチラ見だけど7兆パターンって書いてあった)完全解析を
ターゲットにしても良い気がする。軽はずみ発言だけど。

585:310
16/10/03 02:02:27.60 alBluDZI.net
ちなみに。当方、Sparse正則化付AutoEncoderの実装に不安が付きまとった挙句、
MNISTという手書き数字認識のテストで動作確認をするという遠回りな事をしてます。
というか、何をしたら認識率改善するのかという事を考えて、色々といじって時間を
食ってました。

結果、オセロの方が盤面は狭いけど、良く現れる状態の数と、その特徴の複雑性が
圧倒的に違うので、やはり畳み込みのような、盤面の特徴の解釈の仕方を外から
与える方向に行く必要がありそうだという事になりました。
いままでも薄々気づいていたんですが。

ただ、画像解析や囲碁のように隣接するノードとの関係性からスタートしても意味がなさ
そうなので、その辺の工夫をしてみようと思っています。

586:535
16/10/03 22:00:29.42 5qtC3pHr.net
完全解析はできるに越したことはないですが、
Connect 4やってるのは勉強の意味あいが強いので
Connect 4以外では通用しないようなヒューリスティックで強くなるのは
出来るだけ避けたいです。
理想的には汎用的な手法で完全解析レベルまでもっていきたいですね。

αβもそろそろ片づけなければいけない宿題ですね。

587:460
16/10/04 00:53:57.08 OTRn7xTU.net
コネクト4、軽く実装してみましたが(ほとんどオセロの流用)
単純アルファベータ、置換無しオーダリング無し、
評価関数が連続している数だけ考慮・・・だと8手涛ヌみは一瞬ですbェ、12手読みはbキでにきついでbキね。。
末セ日評価関数を給lめてみてとりbえず8手読みで535さんのAIと対戦してみる予定ですw

588:535
16/10/04 21:18:36.22 dRd+Ucp+.net
おお!楽しみですね。
ありがとうございます。

工夫無しの8手読みなら勝ちたいですねw

ちなみに私のAIは結構思考時間が長いのでw
統計といえるほどの試合数はこなせないと思いますが期待しちゃいます。
よろしくお願いします。

589:460
16/10/05 00:36:10.60 JvSO0BT6.net
>>588
結果ですが、ぼこぼこにされましたw
ヒューリスティックだとやはり限界ありますね~

590:460
16/10/05 11:21:34.44 WWXbBFqc.net
オセロは大体やることはやったので、そろそろ将棋か囲碁に着手してみようかと思っています。
ルールの実装が楽なのは囲碁なのかな…
自身が囲碁を打ったことがないのでルールから調べないとですがw

591:310
16/10/05 12:08:04.26 Iif/OHnc.net
やっぱ囲碁行きたいですよね。

昔調べた感じでは、日本ルールと中国ルールで勝敗の判定が微妙に違って、日本
ルールだと曖昧なところがあるので、AI開発は中国ルールでしているみたいです。

ルールの実装は着手禁止点が少なくて拍子抜けするくらいですが、その先が・・・
色々と一筋縄ではいかないようです。

オセロの評価関数ですが、AutoEncoderの限界を感じ、DCNNの実装を始めていますが、
バックプロパゲーションがスパゲッティでわけわからん状態になっています。しばらくは
紙と鉛筆で考える必要がありそうです。DCNNがある程度できたら、僕も囲碁に行って
みようかな。

その前にConnect4に脱線してみたい気も(汗

592:535
16/10/05 19:29:25.92 KcSrUkxH.net
>>589 >>590
ん。IDが違いますね。
>>589は偽物ですかね?

593:535
16/10/05 19:48:59.89 KcSrUkxH.net
>>591
囲碁は終局判定させるのも結構難しいみたいですね。
セキの判定とか。

Connect 4は易しすぎず難しすぎずいい塩梅のゲームだと思います。
完全解析も狙えますしw

594:460
16/10/05 21:34:13.58 JvSO0BT6.net
>>592
同一ですよ!
スマホから書き込んだのでID変わってしまいました

595:535
16/10/05 21:53:19.85 KcSrUkxH.net
ん~そっちのID使って同一って言われても。
>>590のIDで書き込みお願いします。

596:名前は開発中のものです。
16/10/05 22:05:36.36 KcSrUkxH.net
まあ、こんな過疎スレでわざわざ嘘をついて騙るひともいない気もしますが…

597:名前は開発中のものです。
16/10/05 22:31:22.88 KcSrUkxH.net
>>590の書き込み時間からすると学校や職場から書き込んだ可能性もありますね。
とすると>>590のIDでは今は書きこめないかもしれませんね。

598:460
16/10/06 20:28:59.44 1mBat3Ee.net
460の名前があるものは偽物ではないので大丈夫です・・・
コテ付けた方がいいかもですけど、まぁこの人数ですし、そこまでする必要もないかなと思いますー

囲碁ですが、ネットから集めた棋譜をざっと見てみましたが、投了がほとんどなんですね・・・
中押し勝ち?はて・・・?となって調べるくらいルールを理解していないという;;
投了だとするとロジスティック回帰でないとあんまり良い精度は出なさそう・・・?
というより一般的な機械学習のアプローチで良いのかも微妙ですね。
やはりディープランニングなのでしょうか。。。腰が引けますw

599:535
16/10/06 21:04:20.88 /7+JrWaw.net
>>598
ん~そうですか。
それは失礼しました。

600:310
16/10/06 22:11:43.15 2nbHwrUk.net
>>598
投了は将棋用語で「参った」です。むしろ中押し勝ちと同じ意味です(汗
将棋の場合、詰まれるまで粘る事はみっともないこととされているので、
入玉とか千日手、反則負けなどの特殊なケースを除けば全て投了です。

囲碁は、逆に終局まで打つ事があって、「数え碁」と呼ぶみたいです。
この間のアルファ碁vsセドルの試合見て覚えました(笑)
オセロのように必ず最後まで打って、得点差がはっきりと出るゲームの
方が珍しいのかも知れません。

オセロみたいなmin-Max+評価関数は既にダメ認定されてます。
アルファ碁までは、MTCS(モンテカルロツリーサーチ)が主流で、
モンテカルロ系には評価関数はありません。着手順決定のための
ヒューリスティックが大事になります。

アルファ碁の登場で、一気にディープラーニングにシフトしていますが、
基本骨格はMTCSです。着手順のヒューリスティックに「次の1手を返す
DCNN」と、評価値たるモンテカルロの勝率に、補助的に「勝率を返す
評価関数としてのDCNN」を組み合わせているようです。

601:310
16/10/08 22:22:06.53 wBSLMo4h.net
あ、MTCSじゃねー。MCTSだ。

>>600書きながら、Q-Learningなるものの存在を思い出して、調べ始めたら、
やっぱりDQN(ブロック崩しで有名になった奴)はQ-Learning+DeepLearning
だった。

興味津々だけど、どんどん発散しちゃうなぁ。

602:535
16/10/10 19:51:24.57 WonRpXhk.net
なんかモチベーションあがらんなぁ
三連休まるまるさぼってしまった。

603:名前は開発中のものです。
16/10/10 22:22:05.27 WonRpXhk.net
将棋電王戦あったみたいですね。

604:名前は開発中のものです。
16/10/10 22:38:31.22 WonRpXhk.net
優勝はポナンザか。
一発勝負のトーナメントなのに強え。

605:名前は開発中のものです。
16/10/10 23:10:57.87 WonRpXhk.net
ん?
一発勝負じゃないのか?

606:310
16/10/13 11:06:43.08 f6Nd8WJL.net
ここ数日、気分転換でConnect4やってました。

ビットマップ方式の置換表付αβのオーダリング無し。リーチ状態のみ後方枝刈。
完全解析ができそうか確認してました。

全42手でルートから30手くらい置換表適用すると、序盤はかなり良いペースで探索
してくれますが、数時間で置換表パンク。置換表を20手くらいまでにとどめると、びっくり
するほど速度低下。手順の前後で簡単に同形が生じるので、置換表が肝なのは確か。
というか、手順前後の同形を排除する仕組みが作れればメモリ節約可能になる。
けど、それを一般化した処理が置換表なので、全てカバーしなくても3手以内くらいで
排除すれば状況はかなり改善するかも知れない。

あと、パンク前も探索が進むにつれて徐々にnpsが低下していきます。原因不明。
書きながら気づいたのですが、置換表のハッシュ値はオセロのものを流用しています。
Connect4はビット数が少ないので、ハッシュ衝突が頻発して、格納効率が低下して
領域拡張が頻繁におきて、探索速度も落ちている可能性があります。

というわけで、現段階では置換表周りを工夫しないと完全解析は厳しそうです。
一方で、空26箇所くらいの終盤探索なら実用的な速度が出そうな感触です。

>>569の完全ソルバは、評価値表示機能があるけど、あの表示の仕方だと、証明数
探索みたいな手法を使っているのかなぁ。ほぼノータイムで最善手のみ着手してくる
ので。完全ソルバの出現で終わっちゃってるゲームなんでしょうね。

で、このゲームってMCTSの練習台にちょうど良いのではないか?とふと思いついて
しまいまして・・・。更に脱線しようかなと思います。Playout関数は作りましたが、ツリー
展開の仕方に疑問があり、まだ調べ中です。

607:名前は開発中のものです。
16/10/13 21:15:41.15 XMNeJMFS.net
310氏もConnect 4 参戦か~

608:535
16/10/13 21:53:14.86 XMNeJMFS.net
名前書き忘れた。

終盤26手読み行けそうというのは流石ですな。
完全解析ってConnect 4だと簡単そうに見えますがこれが意外と手強いんですよね~

609:310
16/10/15 13:58:53.52 iZ3eY/zy.net
NPS低下問題はやはりハッシュ衝突のようで、ちょこっと直したら解消しました。

Connect4は手順前後しても同じ形になる事が多いゲーム(DAG問題多発)なので、
置換表を上手く使わないと、7兆種類あると言われている盤面を何度も重複探索して
しまう事になります。が、置換表探索と登録のオーバーヘッドは結構大きく、メモリ
パンクでスワップ多発の問題も起きます。

今の設定だと残り27手探索くらいなら難しい問題で1分程度で解けそうです。
NPSは20メガくらい。が、メモリパンクや重複探索の問題があるので、その速度を
もとに完全解析に要する期間を推計するのは無理っぽい感じです。

というわけで、完全解析はこの辺にして、MCTSの方に行きます。

610:535
16/10/15 20:55:10.85 jn3cHMWR.net
>>609
多分純粋なMCTSだけではあまり強くならず、
プレイアウトになにがしかの工夫を入れる必要が出てくると見てます。

逆にプレイアウトさえ改良できればMCTSはびっくりするくらい強くなる。

しかしそれでも完全ソルバには届かない。みたいな感じだと思います。

611:310
16/10/15 21:29:59.48 iZ3eY/zy.net
MCTS(UCT)多分できました。STL様様です。
探索時間1秒で40万プレイアウト。

playout部をnegamax的に書いたので、ちょっと混乱しました。
まだ終局判定とかいい加減で、引分近辺で落ちる可能性あります。

オセロでも1秒で10万プレイアウト以上いけるんじゃないかなぁ。
探索時間固定できるのでオセロ序盤~中盤で使えるかも。

>>535さんのプログラムはもうダウンロードできないですね。

612:535
16/10/15 21:54:42.38 jn3cHMWR.net
秒速40万プレイアウト!?すげぇぇぇぇ
1プレイアウト=1手てことですか?
1プレイアウト=1局てことですか?

613:535
16/10/15 22:17:47.78 jn3cHMWR.net
460氏もオセロで10000Knps~15000Knpsとか言ってるし、まじか~
やっぱ本気でやってる人達は違うのかな…

614:535
16/10/15 23:46:45.43 jn3cHMWR.net
NPSは20メガって書いてありますね…
すいません。

615:310
16/10/16 01:32:06.03 KTdXBWLt.net
プレイアウトなので1局です。色々ごにょごにょはありますが、ランダム着手で、
とりあえず勝負がつくまで打ちます。これで1プレイアウト。
速度が出るのはビットマップとBMI命令などのX64命令を使ってるからだと思います。

が、Perfect Solverに先手で勝てません(汗。5手目に必ず間違えます。
評価値を眺めても、当たり前のように、正解(真ん中列)が最下位になります。
パラメータをそこそこいじってみましたが、状況は変わらないです。
一本道には弱いって事かなぁ。

とはいえ、自分がやると、さっくりと負けてしまいます(汗

616:310
16/10/16 13:25:18.14 KTdXBWLt.net
mobility周りにバグがあって直したところ、1秒読みでPerfect Solverに先手で勝ちました。
昨夜は120秒読みでも同じ手順で負けていました。
とはいえ、乱数が絡むので引き分ける事もあります。

まだ若干問題があります。1本道を交互に着手していくと自動的に勝ちが確定する盤面
なのに、評価が引き分けになっています。プレイアウトの終局判定で何かの条件が抜け
ていて、勝ちと判定されていない感じです。

直したらまた勝てなくなったりして(汗

C++の診断ツールを今回初めて使ってみました。
関数ごとの使用時間がわかるようで、速度アップの検討に重宝します。
が、どうもUCB1の計算で使うsqrtとlogを使ってる箇所でCPUを9割くらい使っている
感じです。見方が良くわからないけど、多分そういう状況。速度アップ難しい。

617:535
16/10/16 16:43:19.50 Ts0NTtMt.net
一秒読みで完全ソルバに勝とかまじか~
やっぱ積み上げてきた基礎力が違うんだろうな~

618:310
16/10/16 17:19:15.26 KTdXBWLt.net
どもです。評価値問題は治りました。

乱数じゃなくて、ある手順で引き分けな手を選んでしまう事が判明したので探索時間
を延ばしてみたら、逆に序盤で負け手順を選んでしまうようになりました(汗。
ツリー部の地平線臭い感じなのかなぁ。

というわけで、たまたま選んだ1秒が良かっただけかも知れませんorz

MCTSも理論的には探索回数を∞にすると、最善手を必ず導き出す事は保証されて
いるらしいのですが、中途半端な回数の時は保証されていないんですよね。

619:535
16/10/16 21:36:30.64 Ts0NTtMt.net
なんか将棋で評価値を深く探索した時の評価値に近づけるっていう学習方法があるみたいですね。
ちょっと興味あります。

620:310
16/10/16 22:45:31.89 KTdXBWLt.net
なんか、デバッグ報告みたいな状況になってすみません。

地平線臭い状況を調べていたら、負ける寸前なのに評価値が勝ちになってます。
つまり負けを認識していない。

着手を間違えるのはこの辺も原因かも知れません。

ぱっと思いつく原因が見当たらないので、しばし長考します。

621:535
16/10/17 22:03:40.14 B9d5KHtX.net
connect 4序盤ブック作ってみようかな。
完全ソルバ丸パクリでw

622:310
16/10/18 00:57:04.06 k8M1GDOc.net
色々直して、ほぼバグは取れたと思います。
で・・・強くなったはずですが・・・PerfectSolverに先手で勝てなくなりました。
かつて勝てたのはたまたま上手くバグっていたという事みたいです。

1秒設定は途中で間違えて引き分け、10秒設定は初手で負け確定(真ん中以外に着手)。
1秒設定で初手真ん中を選択するのはたまたまかもしれません。
初手だけ調べると150万プレイアウトくらいで間違えはじめ、15億プレイアウトまで確認
しましたが、雰囲気的には当分正しい答えに戻ってこないようです。
評価値の推移を見ると、一本道問題に引っかかっているように見えます。

DAG問題がやっぱり気になるので、ハッシュと組み合わせて合流できるようにしてみます。
多少は改善するかも知れないし、逆にもっと早く真ん中から外れるかも。

623:名前は開発中のものです。
16/10/18 17:50:18.00 7idTlLLA.net
読めば読むほど弱くなるとは不思議
ucbの計算間違えてるとかでは?

624:名前は開発中のものです。
16/10/18 19:31:31.87 4bRvdGb+.net
ボードゲームのオリジナルオーダー制作
URLリンク(www.logygames.com)
簡単に本格自作ボードゲームが作れる時代到来!!
URLリンク(jellyjellycafe.com)
100円ショップでボードゲームを自作しよう
URLリンク(sites.google.com)
ノーアイデアでボードゲームを作ろう第1回「100円ショップで物を買う」
URLリンク(boardgamelove.com)
自作ゲームをゲームマーケットで売って来た
URLリンク(portal.nifty.com)
「街コロ」はカードゲームに興味ありな初心者の入門用に最適、サイコロを振って
カードを集めどんどん自分の街を発展させて勝利を目指せ
URLリンク(news.livedoor.com)
ようこそ「男の世界」へ。『ダンジョン オブ マンダム』試されるカードゲーム
URLリンク(www.moguragames.com)
かわいいひつじを増やして増やして増やしまくれ! “一人用”カードゲーム『シェフィ』
URLリンク(www.moguragames.com)

625:535
16/10/18 22:30:42.36 5rT5zFZw.net
完全ソルバから定石パクるの意外とめんどくさいな。
クローラーみたいにして自動でパクれるようにしようかな。
でも迷惑かかるかな?

626:535
16/10/18 23:07:54.58 5rT5zFZw.net
なんか本末転倒だからやめとくかw

627:310
16/10/19 02:53:35.54 YWnebdEb.net
まさかの場所にバグ発見。
プレイアウトでランダムに1手選ぶところがバグってました。
良く動いていたものだと思う反面、MCTSってそういう所がある事も薄々感じてます。

が、状況はほぼ変わらず。初手真ん中と、5手目真ん中。この2か所が鬼門。

まだバグがあるのかも知れない。やっぱり自分が一番信用できないですね。

DAG問題対策でノードの合流を実装しました。枝とノードを分離して、ノードをハッシュ
にして、ノードの下に次の枝をぶら下げました。同時に、ハッシュキーに細工して、
左右同形も合流させてます。あまり変化はない気が。
速度低下が酷いです。

628:310
16/10/20 00:37:06.99 yz39woaL.net
5手目真ん中以後どうなるのか1秒探索検証。6手目2列目に対しては、勝利(全て
最善着手)。6手目1列目に対しては、5列目着手で引き分け進行に入り、引分終了。
この時の手順では、全箇所が最善手という盤面ばかり通っていくように感じています。
つまり、MCTS的に勝利期待値が最大になりやすい手です。という事で、まあ、そんな
に間違った手は打っていないかなと。

また、プレイアウトを繰り返して手がどう変遷するのか見ていくと、最善手である真ん中
は、ある一定数からほとんど選択されなくなっています。結果、その手で枝の分岐が起き
ない事から、いつまでたっても評価が更新されず正解に戻らないと推測できます。

そこで、試行回数に圧倒的な差ができても、下位の手も一定回数は試行されるように
できないかと、手の選択基準をucb1の大きい順から、ソフトマックス関数を通して確率
分布に変えて、乱数で選択してみました。

結果は・・・。expの計算がある事からか、速度が激減。PVに割り当てられる試行回数は
2/3程度になり、その時点の最悪手でもそれなりに試行されるようになりましたが、それ
でも手の選択は微妙な感じです。この程度の効果なら、他のパラメータいじった方が
速度低下も無く良かったかも(汗

というわけで、本日のトライアルも失敗。
気が進まなかったけど、やっぱりucb1計算の検算をしてみます。
あと、部分的にmin-Maxを適用するとか。

629:310
16/10/23 09:58:44.72 qEEwIK82.net
UCB1の計算は合ってました。
プログラムがC++的に美しくない事が気になりだし始めて、全部書き直ししてました。
書いた端から美しくないのが気になりだしましたが(笑)

UCTで後方枝刈というか、小枝の勝敗が確定していたら、ツリーを縮小していく処理を
追加。一本道問題が多少緩和するかと期待。対戦はちゃんと動いているっぽい。
デバッグ情報をファイル出力する処理書いて確認。
間違え方はあまり変わっていないのが残念というか、安心というか(汗

モンテカルロで1手目から最善手順が確実にわかったら、それはそれでゲームが
簡単すぎるって事になっちゃうので、大きく間違えないんなら、それで仕方ないかな。
というわけで、COM1手目は真ん中に固定。

プレイアウト部を高速化できる気がしていますが、やってみないとわかりません。
プレイアウトの末端部分に完全読みを数段入れるのも良いかと思っています。
DAG問題対応と左右対称チェックを入れて毎秒20万プレイアウトくらい。

評価値の算出方法でちょっと悩み中。

そこそこ落ち着いたらオセロの中盤探索に応用してみます。

630:310
16/10/26 20:47:59.29 H5ji3apJ.net
また美しくない病が出て、書き直したところ、びっくりするほど弱くなってしまった。
しばらくデバッグで悩みそうです。

631:535
16/10/26 20:59:11.78 +YpzcPTO.net
Connect 4は一旦休止して別のゲームのAI書いてます。
マイナーゲームですが囲連星というゲームで囲碁と五目並べを混ぜたようなゲームです。
簡単に言うと、七目並べれば勝ち、囲った石は取れるというルールです。

ついさっき黒番で公式AIのLV0に1勝できました。
(;SZ[19]
;B[jj];W[kj];B[jl];W[ji];B[ik];W[km];B[kk];W[ki]
;B[ii];W[lj];B[ll];W[mm];B[hh];W[gg];B[im];W[ih]
;B[ig];W[jh];B[ij];W[in];B[lk];W[gi];B[hk];W[gk]
;B[mk];W[nk];B[hn];W[hl];B[jn];W[io];B[lm];W[jo]
;B[go];W[fp];B[gh];W[hi];B[fg];W[ko];B[gf];W[ln]
;B[hg];W[jg];B[ff];W[gj];B[gg])

囲連星AIはこちらで配布されてます。
URLリンク(www.vector.co.jp)

632:535
16/10/27 22:26:16.59 CgNWWTgQ.net
LV2からも黒番で一本取りました。
キセキが起きたw

(;SZ[19]
;B[jj];W[ik];B[ji];W[hj];B[jh];W[jk];B[kk];W[jl]
;B[gi];W[il];B[ll];W[hm];B[ii];W[hh];B[hi];W[ki]
;B[mm];W[nn];B[li];W[in];B[kh];W[fi];B[mi];W[io]
;B[kj];W[lj];B[ki])

633:535
16/10/27 22:53:05.70 CgNWWTgQ.net
黒番でLV3からも一本取りました。
なかなかいい感じ。
ここからどう高めるか。

(;SZ[19]
;B[jj];W[ji];B[ij];W[kj];B[kk];W[ii];B[ki];W[lj]
;B[lk];W[jk];B[ik];W[kh];B[li];W[mj];B[lh];W[hl]
;B[mk];W[hj];B[jl];W[hk];B[ok];W[nk];B[nj];W[hh]
;B[nl];W[km];B[jk];W[lm];B[nk])

634:310
16/10/27 23:41:56.56 KUg+LQ1A.net
バグ取れました。わかればどうという事はないですねorz

左右対称はデバッグが面倒くさいので省きました。どうせ序盤でした
意味がありませんので。

初手真ん中は、多分モンテカルロでは答えを出すのが相当厳しいです。
5手目真ん中は、乱数次第みたいな感じで、100万プレイアウトくらいまでに
出るか、1億プレイアウトしても出ないかみたいな感じになります。

一応、DOS窓ベースでプレイできるようにして、途中でMTCSのツリーを
色々と確認したり、追加のプレイアウトをしたりできるようにしましたが、
本質的にモンテカルロなので、完全に近いけど完全じゃないし、乱数の
具合によって着手する手もバラつくという事で勝手に納得してしまいまして、
せっかく作ったデバッグルーチンも禄に活用していません。

高速化も、一時期は40万プレイアウト毎秒くらいまで出たように感じて
ましたが、最終的に20万くらいで落ち着いてしまいました。

次のステップでオセロに応用と思ったのですが、その前に並列処理化を
してみようかと思います。上手くやれば探索ノード数は3倍強(自分のPC
では)くらいにはなりますが・・・数段深く読んだとて、結論にはあんまり大差
が無いのかなと。まあ練習ですな。

というか、min-Maxとモンテカルロのノウハウ、仕事で使えそうだなぁ。

635:名前は開発中のものです。
16/10/27 23:46:29.29 CgNWWTgQ.net
>>310氏はプロのプログラマなのか。
まあ納得。

636:310
16/10/28 10:50:00.21 /58y3Hfc.net
いや。趣味の深夜プログラマです。
物流業務改善の会議で提案してみて、わからんと言われたら
ソース見せて動作検証してやろうかなと。

システム屋さんからすると、とてつもなく面倒くさいクライアント
だと自覚しておりまするorz

637:535
16/10/29 21:09:01.77 4znFYNwN.net
囲連星、公式AIとガッツリ対戦してみました。
LV0はdll化されてないので対戦できませんでしたが。。。
結果はLV1には大きく勝ち越しましたがLV2,LV3には敵わなかったです。
airandom.dllが私のAIです。

50局目
黒(airandom.dll)の勝利回数: 44
白(ai-lv1.dll)の勝利回数: 6

50局目
黒(ai-lv1.dll)の勝利回数: 10
白(airandom.dll)の勝利回数: 40

50局目
黒(airandom.dll)の勝利回数: 20
白(ai-lv2.dll)の勝利回数: 30

50局目
黒(ai-lv2.dll)の勝利回数: 41
白(airandom.dll)の勝利回数: 9

50局目
黒(airandom.dll)の勝利回数: 15
白(ai-lv3.dll)の勝利回数: 35

50局目
黒(ai-lv3.dll)の勝利回数: 44
白(airandom.dll)の勝利回数: 6

私のAIが長考するのでこの対戦するのに丸一日以上かかってしまいましたw

638:310
16/10/29 21:13:21.87 hyv6QOjp.net
並列化してみました。

色々やり方ありますが、まあ順当なやり方という事で、ツリー単位の並列化です。
が、4コアに対して4並列でむしろ速度低下。排他で怪しいところを色々変えてみて
ようやく若干(10~20%程度)の速度アップにしかなりません。並列数を減らすと
速度低下していくので、排他待ちが原因ではなく、並列化オーバーヘッドの模様。
ノード&ツリーの構造で複雑な分、オーバーヘッドが大きくなっているのか、オセロの
時の効果には大きくおよびません。

ルート単位の並列化で、一定時間ごとにツリー統合(合算)というやり方もあるような
ので、次はこちらを試してみます。

もしかしたら、一番効果が無さそうな、プレイアウトのみ並列化の方が効果出たりして。

639:310
16/10/29 21:14:51.22 hyv6QOjp.net
MTCSは並列化と相性が良いとは思えないなぁ。

640:535
16/10/30 23:47:35.70 11nwLD7b.net
return文忘れててめちゃくちゃな値返してた。
この不可解なバグ潰すのに3時間かかったorz.
関数の終わりでreturn文無かったら警告だしてよコンパイラ(泣
まあコンパイラオプション付けてない俺が悪いんだがwww

641:310
16/10/30 23:54:19.10 vT6Vi1L+.net
結局ツリー部の並列化はやめてプレイアウトだけを並列化しました。
ツリー統合も気になりますが、とりあえずこれで末端の評価が正確になります。
プレイアウト部分は処理時間が短いので、プレイアウト回数は大幅に増えます。
MCTSは面倒でも、モンテカルロは並列化向きです。
100回プレイアウトして、そのスコアでまとめて更新。

ところが、バグを発見してしまいました。
勝ち手順で進めていたのに、最後の最後に1手間違えて引分。
もうプレイアウトではなくツリーの勝敗が確定している状態で、間違えるはずがない。
勝敗確定時のフラグ設定がおかしいようです。

そこから色々見直しを始めたら、negaMax的な処理の扱いに完全に混乱して
しまいまして…。これだと思って修正すると、おかしくなってしまいます。
どこか根本的に勘違いしているみたいなので、しばし長考に入りますorz

642:535
16/10/31 00:37:25.82 KdjBytFw.net
なかなかいい感じのルーチンが書けた。
まだ結果に結びついてないけどこれはあと一捻りいれればかなりいい線行くんじゃないか?

643:535
16/10/31 21:35:59.05 KdjBytFw.net
おかしいな。
石の流れは良くなってるのになかなか勝利に結びつかない。

644:535
16/10/31 22:47:38.80 KdjBytFw.net
パラメータ微調整地獄w
機械学習に切り替えないと限界が…

645:535
16/11/01 21:33:50.00 pQxzEPLf.net
あかん。
完全にバランスを失った。
一から出直しだな。orz

646:名前は開発中のものです。
16/11/03 03:15:09.64 x7yDYWU2.net
ボードゲームのオリジナルオーダー制作
URLリンク(www.logygames.com)
簡単に本格自作ボードゲームが作れる時代到来!!
URLリンク(jellyjellycafe.com)
100円ショップでボードゲームを自作しよう
URLリンク(sites.google.com)
ノーアイデアでボードゲームを作ろう第1回「100円ショップで物を買う」
URLリンク(boardgamelove.com)
ボードゲーム市場がクラウドファンディングの出現で急成長を遂げ市場規模を拡大中
URLリンク(gigazine.net)

647:310
16/11/04 15:36:30.74 zGiY9OSz.net
長考の結果、もう一度作り直し(笑)していたら、混乱の原因がわかりまして。
勝敗の持ち方を逆にしたらすっきりしました。

あと、終盤の手順の前後で、あと3手粘れるのに1手で負けるという現象を調べた
結果、ツリー部で負けと判定している以上、何手先に負けるか関係ないというプロ
グラムになっていた事も判明。バグじゃありませんでした。とはいえ気持ちが悪いので、
なるべく長く粘るようにしてみました。

そこでわかったのは、Perfect Solverの数字は、42手21ターン目の引分から何ターン
前に勝負がつくのかを表していて、プラスは勝ち、マイナスは負けという事です。先手で
+1と出たら最善を尽くせば41手目の自分の着手で勝つという事のようです。
つまりスコアを勝敗決定ターンにしたmin-Maxで、速度考えるとDB化してるんでしょう。

で、MCTSですが、まあやはりモンテカルロなので間違えます。試しに10手目程度
の間違えた局面から、シミュレーションを続行してみたところ、億単位の探索(プレイ
アウトとしては10倍)で、間違えた手が本当は悪かった事に気づいた様子で、そこから
正しい答えに向かって行きました。なので、まあプログラムは間違っていない模様です(汗。

DAG対応とか、自殺手禁止プレイアウトとか、色々やった結果、選択手のばらつきが
減って、「たまたま正解手順を引く」事がなくなって、自信満々に間違えるようになっ
た印象です。それでも、時間をかけて探索を続けると、いつかは正しい答えにたどり着くと。

今となってはあまり意味が無いですが、せっかくなので、ここまで積み上げて来た
ノウハウで、今一度Solver作ってみようかなと。

648:535
16/11/04 23:52:18.01 lKhN7bKh.net
色々ぐちゃぐちゃやってたら計算時間がとてつもないことになってしまった。

649:310
16/11/06 13:49:29.22 Z4kqE5wB.net
Solver作りました。
PerfectSolverにならって評価値を、42手目から何手手前で勝敗がついたかにしました。
お蔭さまで、null window searchが使えるようになり、mtd(f)で高速化しました。
あと、初段のみ単純な並列して、残り28手で6秒強となりました。

そろそろオセロに戻ります。

650:535
16/11/06 17:53:47.27 B23WCzGo.net
終盤28手読み6秒とか凄い
こっちはというとそろそろαβ刈りを習得しなければ…

651:535
16/11/07 00:12:13.27 vL8wkeAF.net
αβできたっぽいです。
というかwikiの疑似コードを完コピしたらうごいたっぽい?という感じで
理解したとはいいがたいですが。

652:535
16/11/07 22:06:07.74 vL8wkeAF.net
え、もしかしてminmaxに比べてαβめちゃめちゃ速い?
なんか間違ってんのかな…

653:310
16/11/08 00:02:22.02 CUgV7Bvg.net
安心してください。めちゃ早いですよw

後ろ向き枝刈系のアルゴリズムはほとんどがαβを前提にしています。
自分の最初は擬似コードコピペしました。
すぐ忘れちゃいますが、1回は真剣に動作を追っておくと良いですよ。

654:535
16/11/08 22:35:11.27 BlAmLHY6.net
評価関数が致命的に狂ってる気がする。
手動で直すのは限界があるから機械学習したいがさてどうするか。

655:310
16/11/10 20:55:19.87 gpSCAC4W.net
オセロでUCTをしてます。コピペでちょいちょいと思っていたらパスの処理が面倒で、
思った以上に動作速度が落ちてしまいました。

その後、デバッグしてたらおかしな現象を発見。探索ツリーでプラスになるべき数字が
マイナスに。しかも1か所だけ。発生条件を絞り込めず、なんだかんだと数日間。

原因は整数のオーバーフローでした。設定時間におけるプレイアウト回数でのスコア合計
がちょうど境目にきて、本当に微妙にオーバーフローしていたので、スコアの正負がひっく
りかえったように見えていたのでした。

俺の時間を返せorz

終盤5手読みくらいならすぐにUCTのツリーが終局まで達して、完全読み同等の答えを
返してくれるのですが、10手だと結構時間がかかり、20手だと全く歯が立たない。
評価関数を使った中盤探索の置き換えに使えないかと想定しているのですが、やはり
簡単に精度は出ない感じです。

プレイアウトでありがちな手を優先的に着手するように、ヒューリスティックな評価関数を
用意して、プレイアウトの精度を高められるか試してみたいと思います。あと、スピード
アップもしないと・・・。

656:535
16/11/10 23:14:15.10 4tjjzH07.net
Zenは治勲と三番勝負か~
Zen勝ちそうw

657:535
16/11/13 00:19:43.02 otFLKKMJ.net
doubleの有効桁数が足りなくておかしくなってたorz
評価値に差をつけようとして極端にデカい数値を設定してたら
小さい数値が無視されてた

658:310
16/11/13 00:47:25.03 Be0ooFvL.net
DeepZenGo楽しみですね。
ポストアルファ碁の今となってはZenが2勝できなかったらちょっと悲しいかな。


こちらはオセロのモンテカルロツリー探索がほぼできました。
当初かなり速度ダウンしていたのですが、何とか改良できました。vectorが遅かった。
数か所工夫して、テストデータで正解を早く導けるようにしてみましたが、調整が面倒そう。

とりあえずネタ切れなので、次は探索済ツリーを再利用できるようにして、対戦できるよう
にする予定です。で、今一度終盤読み切りルーチンと、序盤の定石DBつけて完成としたい。

しかし、相変わらず評価値をどう計算したら良いのかわからない。
単純に、着手する手の平均スコアだと、探索の進み具合によってあなりブレてしまい
意味がある数字になりそうにない。アルファ碁はDCNNの評価値を使ってるのかなぁ。

659:310
16/11/13 20:49:23.63 Be0ooFvL.net
ちょっと疑念が湧いてきたので数か所工夫したところを全てコメントアウトしてみたところ
やらない方が遥かにマシという結論に(汗。下手な考え休むに至りでした。
全部外してしまうと一旦最善手から外れてまた戻ってくるような事もなくなり、探索時間が
長い方が良いと単純に言えるようになります。

また、評価値ですが、モンテカルロならやはり点差を考慮しない「勝率」であるべきでは
ないかと思い始めています。今は、「点差」を返しています。「勝率」で選ぶ手は、「もっと
良い手があった」となりますし、「点差」で選ぶ手は「欲張りすぎた」となりそうです。

探索済ツリーの再利用の仕組みができました。まだパスがらみのテストはしてませんが、
多分大丈夫でしょう。

ボード関連のクラスをかなり作り直してしまったので、終盤読み切りルーチンや序盤定石
処理を作り直さないといけません。というか、評価関数を持ってないので、終盤探索は
オーダリングの仕方を変えないといけません。

あと、人間側入力待ちの間も探索を継続できるようにしてみたいと思っています。
モンテカルロだと、いつでも停止したり再開できるので、ぜひとも導入したいものです。

660:310
16/11/16 01:01:14.01 2m1pjf8n.net
人間の入力待ちの時のバックグラウンド探索を実装しました。
並列処理はPPLを使ってるので、思いのほか簡単にできましたが、入力待ちのまま
放置されると、数時間でメモリーを食いつぶしてしまう事に気づきました。
パンクしそうになったらツリーをルートに近い順に削除するようにしましたが、メモリー
リークしてそうでちょっと怖いです。

コンピュータ同士で対戦させてみたところ、まあそれっぽくは打ちますが、序盤で定石
から外れてしまいます。終盤は結構正確に見えます。

評価値の件、独自ロジックを外したところ、それっぽい値を表示するようになりました。

661:310
16/11/16 09:03:26.60 uZWbEwsE.net
自分のつたないオセロ力では、モンテカルロが着手した手が良いのか悪いのか
わからないので、どうしようかと寝ながら考えました。

まず考えたのは、完全読み切りルーチンを作って、終盤に限っては正解着手も
探索してみる事。でも、最終的には終盤は完全読み切り使った方が、正確で早い
ので、そちらを使用。中盤や序盤の具合がわからない以上、ほぼ意味なし。

続いて、WZebraにある「解析機能」を実現できないかと考えました。中身はわからない
ので想像。使用して感動した経験あり。
「後ろから解析」なら、αβを後ろから回し、自分が着手した手より良い手が無ければ
βカット、あればそれで生じたスコアの増減を記録という形で、中盤のある程度のところ
までは、遡りつつ誤着手を検出できるんじゃないかなと。棋譜にある着手はこのロジック
で評価が定まっているので、探索を省く事ができます。評価関数を持っていないので、
遡れても30~35手目くらいまでかと思いますが、読み切りルーチンをいじれば作れ
そうなので、トライしてみようと思います。

誤着手率がわかっても、簡単に直らないのがモンテカルロですが…。


次ページ
最新レス表示
レスジャンプ
類似スレ一覧
スレッドの検索
話題のニュース
おまかせリスト
オプション
しおりを挟む
スレッドに書込
スレッドの一覧
暇つぶし2ch