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

**名前は開発中のものです。** · 03/07/10 00:10

比較的地味なボードゲーム専用のスレが欲しくて立ててみました。

私はc言語で作ったデータベースを使って人間と対戦できる将棋かチェス
みたいなソフトを作りたいと思ってますが、グラフィックインターフェースの
作り方がわからなくてつっかえているレベルです。

**４０６** · 2016/05/13(金) 22:42:29.22

やはりポーリングだけでは限界があるか？

**310** · 2016/05/16(月) 21:32:31.63

モチベーションダダ下がりだったけど、なんとなくソースの整理していたら、
直したいところがいろいろ出て来て、見直し中。

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

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

**310** · 2016/05/26(木) 16:01:37.05

遅々として進んでいます。
ソースを一から組みなおして、いろいろと綺麗にしてます。
並列探索を入れない段階で、FFO#40が結構速くなった。

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

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

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

**310** · 2016/05/27(金) 00:36:10.52

早々に状況が判明しました。ここに書くと進むんだよなぁ。

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

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

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

**406** · 2016/06/27(月) 22:12:32.72

対局場は結構難しいorzので一旦横に置いておいて
手始めにもうすこし簡単な１人ゲームからPHPで作ろうと思ってます。

具体的にはこれ

http://www.vector.co.jp/soft/winnt/game/se513226.html

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

**406** · 2016/07/02(土) 23:28:52.20

http://textuploader.com/5iagw

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

**406** · 2016/07/02(土) 23:40:37.16

なんか文字化けしてんなぁ
なんでだ？
まあいいか

**名前は開発中のものです。** · 2016/07/14(木) 21:31:20.75

必殺技が使えるリアルタイムアクションオセロまだですか

**名前は開発中のものです。** · 2016/07/17(日) 23:40:28.28

とりあえず公開しました。
ランキングはまだ未実装です。

http://nagata442000.xxx.ne.jp/EngelDevil.html

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

**455** · 2016/07/18(月) 00:05:57.51

455=406です。

**406** · 2016/07/21(木) 23:55:32.48

うーんアクセスがないぜ。
検索エンジンにも引っかからないし。
SEOとかいうのに手を染めるしかないのか？

**406** · 2016/07/27(水) 00:25:34.27

結果を保存できるようにした。

**406** · 2016/07/27(水) 22:44:58.98

棋譜を登録＆閲覧＆再生できるようにした。
そろそろ宣伝かな～。

**名前は開発中のものです。** · 2016/08/01(月) 12:39:59.89

このようなスレがあるとは…
自作でオセロソフトを作成している者です
現在は自己対局による学習中です
初手f5
以降ランダム7手～8手、
中盤8手読み
中盤で次善手を85%の確率で一手のみ打つ
終盤20マス空き読み切り
で300万棋譜集めようかと
この設定であれば一局1～3秒程度なので２ヶ月半くらいで達成できる予定です
まだ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

**406** · 2016/08/02(火) 00:17:59.05

だれかSEOのやりかた教えてくれ。

**460** · 2016/08/02(火) 09:44:26.07

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

**406** · 2016/08/02(火) 20:37:12.35

Google検索で引っかかるようになったみたいです。
でもコンウェイの天使と悪魔なんてワード検索する人そんなにいないだろな。

**310** · 2016/08/03(水) 14:35:23.97

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

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

**名前は開発中のものです。** · 2016/08/03(水) 22:36:32.67

>>464
ディープラーニングってライブラリ使ってんの？
それとも自家製？

**310** · 2016/08/04(木) 01:59:01.51

>>465
最初はGitHUBのDeepLearningの参考プログラムを元に自家製でAutoEncoderにDropoutをつけ
たりしてました。

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

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

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

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

**名前は開発中のものです。** · 2016/08/04(木) 22:03:08.50

壮絶やな。
その情熱がうらやましいぜ。

**310** · 2016/08/05(金) 20:44:21.05

楽しんでやってますので（笑

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

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

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

**460** · 2016/08/08(月) 01:32:00.53

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

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

**名前は開発中のものです。** · 2016/08/10(水) 01:12:31.39

310と460はホントに別人なのか？
ディープにオセロＡＩに取り組む人が２人も現れるとはにわかには信じがたいｗ

**310** · 2016/08/10(水) 22:37:11.88

>>470
他のスレで出会って、誘導させていただきました。
ほんと絶滅危惧種ですよね（汗

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

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

**名前は開発中のものです。** · 2016/08/10(水) 22:53:03.62

>>310はかなりハイレベルだと俺は思ってるが
>>310からみて>>460はいい線行ってるの？

**310** · 2016/08/11(木) 23:18:44.20

>>472
僕は全然ハイレベルじゃないですよ。
すぐ脱線して役に立たないことばかりやってるだけです。

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

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

**名前は開発中のものです。** · 2016/08/12(金) 00:22:58.37

ほほう
460さんも期待出来そうですな

**460** · 2016/08/12(金) 02:42:42.36

>>472
自分はディープランニングなどの人工知能系はさっぱりなので・・・
310さんはよく勉強されていると思います。

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

**460** · 2016/08/12(金) 04:26:50.73

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

**460** · 2016/08/12(金) 07:59:35.21

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）

**460** · 2016/08/12(金) 08:01:32.72

>>477
FFO#56はH2:+0ではなくH5:+2に訂正です。。

**310** · 2016/08/12(金) 15:16:23.38

がーん。今まで、こちらはノートPCだしと、密かに思っていましたが、32bitでしたか・・・。
完全に脱帽です。

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

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

**名前は開発中のものです。** · 2016/08/12(金) 16:41:11.53

仲間が出来ていいのう

**460** · 2016/08/12(金) 17:56:57.44

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

**310** · 2016/08/12(金) 20:50:39.55

>>481
YBWCはnegascoutのnull window searchを並列化して一括処理する
ようなものだと解釈して実装しました。

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

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

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

**310** · 2016/08/13(土) 14:18:44.65

あ、考え方がnegascoutみたいだという事で。

**名前は開発中のものです。** · 2016/08/13(土) 20:35:07.80

avx2って256bitだよな
オセロだと128bitしか使えないような？

**310** · 2016/08/13(土) 20:47:52.09

方向が８つあって、それぞれの処理を８回計算するとき、

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

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

**460** · 2016/08/14(日) 16:41:37.52

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

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

**460** · 2016/08/14(日) 16:42:16.06

>>310は>>482の間違いです。。

**名前は開発中のものです。** · 2016/08/17(水) 21:19:58.40

俺もボードゲーム系ＡＩでディープラーニング書いてみたいと思ってるけど難しいんだろな。
論理もそうだけど膨大なデータが必要そうだし。

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

**310** · 2016/08/18(木) 15:43:08.07

>>488
まだ細々やってます（汗

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

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

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

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

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

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

**488** · 2016/08/19(金) 23:15:11.39

>>489
手動評価関数はかなり昔五目並べで書いたことあります。
min-maxで思考時間が１手５分くらいかかったけど、
自分でプレーして負かされることもあるくらいの強さにはなりました。

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

**488** · 2016/08/19(金) 23:23:27.55

ぐぐったらこんなのがあったけど多すぎ。
https://skatgame.net/mburo/publications.html

**310** · 2016/08/20(土) 16:51:13.03

>>490
Buroさんが作った伝説のオセロプログラムがLogistelloです。
Thellというオセロプログラムの作者の方が日本語で解説してくれています。
http://sealsoft.jp/thell/learning.pdf

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

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

**488** · 2016/08/20(土) 20:33:47.55

>>492
パターンの重みの線形和が評価関数になる的なことが書いてあるっぽいですけど、
パターンというのは人間が与えてやるわけですよね？

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

**310** · 2016/08/20(土) 21:29:23.21

>>493
ですです。

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

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

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

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

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

**488** · 2016/08/21(日) 00:04:33.21

>>494

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

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

**名前は開発中のものです。** · 2016/08/21(日) 21:39:11.08

いくらオセロの盤面が小さいからってシングルスレッドで
10000Knps～15000Knpsというのはとてつもなく速く感じるんだが。
どうやったらそんな速度がでるんだ？
オセロ業界じゃ普通なのか？

**310** · 2016/08/22(月) 02:41:50.59

Kが余計で３桁間違えているんじゃないかと（汗

**310** · 2016/08/22(月) 02:46:41.58

あ、違った。自分が３桁間違えていた。

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

**460** · 2016/08/22(月) 08:13:03.66

終盤MPCを実装完了してFFOを測定してみました。。
残すのはFFO#57のみですが、この時点で9364秒と1万秒を割ってるので
10%程度の高速化は期待できそうです。（評価テーブルは64ビット移行＋120万局から変更なし）

**460** · 2016/08/22(月) 09:20:01.85

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

**496** · 2016/08/22(月) 21:10:28.52

2000万ノード/sとかってsseやavx使って始めて可能になるレベル？
オセロの合法手の実装になにかすごい効率的なビット演算やってるとか？

**460** · 2016/08/23(火) 11:44:32.28

>>501
終盤探索だと合法手生成は葉ノードの近くでは使わないので、ループや条件分岐を使ったコードでなければアセンブラでなくても速度はそれなりに出ますよ。
こことかが参考になります。
http://d.hatena.ne.jp/ainame/touch/20100426/1272236395

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

**460** · 2016/08/23(火) 11:47:50.11

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

**310** · 2016/08/23(火) 13:54:12.88

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

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

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

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

**名前は開発中のものです。** · 2016/08/23(火) 19:39:22.88

>>502
ループはおろか条件分岐すらいらんのか（驚愕）

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

**名前は開発中のものです。** · 2016/08/23(火) 21:26:59.10

文系の俺には全然分からん｡
もっと簡素な3目並べなら勝てるAIとか作れないかな(´；ω；｀)

**名前は開発中のものです。** · 2016/08/23(火) 21:47:29.66

ちょっと興味が湧いたんでとあるオセロアプリ落としてやってみた。
弱設定ＡＩが程よく負けてくれて嬉しいｗ
一方的にボコされたら詰まらんよな一般人は。
オセロＡＩはもう神の領域だし。

**460** · 2016/08/24(水) 01:02:17.32

色々チューニングしてトライしましたが、FFO57を大きく落としてしまい、放心中ですｗ
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]

**310** · 2016/08/24(水) 10:40:19.04

こちらも大バグを見つけて放心中です（汗

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

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

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

**460** · 2016/08/24(水) 14:56:52.40

>>509
学習プログラムのバグはやっかいですよね。
自分も何回ひどい目に遭ったか…
今でもまだありそうな気がして怖いですw

**460** · 2016/08/24(水) 22:16:05.70

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]

**310** · 2016/08/25(木) 00:17:23.06

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

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

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

**460** · 2016/08/25(木) 11:20:22.96

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

**460** · 2016/08/27(土) 00:02:49.98

学習プログラムのバグが怖くなって見直してたら超大バグを見つけました・・・
パターンモデルのうち、triangle(Thellが用いているモデル)だけが
局面出現数のカウントリセットされておらず延々と増え続けていましたｗ

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

**460** · 2016/08/27(土) 13:15:04.86

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

**460** · 2016/08/27(土) 13:18:13.50

WZebra24手読みBOOK無し評価誤差なしとの対局結果

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

牛定石[f5f6d6]

黒持ち：+2
白持ち：+0

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

金魚[f5d6c3d3c4f4c5b3c2e6]

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

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

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

**名前は開発中のものです。** · 2016/09/01(木) 22:33:13.77

マイナーゲームで良質の棋譜が大量にない場合、どうやって学習させればいいんだろう？

**名前は開発中のものです。** · 2016/09/02(金) 09:47:35.76

事前学習じゃなくて、強化学習な手法を試したら良いのではないかな。
何をどうすれば良いのか、俺はわからんけど。

**名前は開発中のものです。** · 2016/09/03(土) 00:54:14.21

うおお線形回帰とか最小二乗化とかわかんねぇぇ

**名前は開発中のものです。** · 2016/09/03(土) 20:21:58.46

とりあえず自己対戦棋譜が１０００局集まりそう。
まだ足りないかな？
ここからどう学習させればいいのか…

**名前は開発中のものです。** · 2016/09/03(土) 21:00:16.00

自分も機械学習とか興味あって細々作ってるけど、とても難しい
学習以外の部分も難しくて辛かったけど、学習はなかなか思い通りにするのに苦労する

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

**名前は開発中のものです。** · 2016/09/03(土) 22:28:55.42

今ブラッドリーテリーのモデルとやらを調べてる
数式ムズイＴ△Ｔ

**460** · 2016/09/04(日) 01:59:20.91

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

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

**460** · 2016/09/04(日) 02:00:39.37

レス番号間違えました。。>>523は>>517宛てです。。

**460** · 2016/09/04(日) 02:14:06.21

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

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

**310** · 2016/09/04(日) 17:00:43.77

実際、開発中ってアドレナリン出てるから、ほとんどノーテストで行けるところまで
行っちゃって後で何やってるの俺？って事がしばしば（汗

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

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

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

**460** · 2016/09/05(月) 19:53:28.81

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

**460** · 2016/09/05(月) 20:11:21.05

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

**名前は開発中のものです。** · 2016/09/05(月) 20:52:57.56

学習始めたら速いPCが欲しくなってしまった
結果が出るまで時間掛かるなあ

**310** · 2016/09/05(月) 22:33:11.28

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

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

参考）
http://postd.cc/optimizing-gradient-descent/#gradientdescentoptimizationalgorithms
http://qiita.com/skitaoka/items/e6afbe238cd69c899b2a
※）数式で、ただの変数のように書いてますが、行列だったりベクトルだったり解読が必要です

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

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

**名前は開発中のものです。** · 2016/09/05(月) 22:36:42.16

remi coulomの書いたMM法のコード見つけたが難しくて読めないorzorzorz
頑張って読むか

**310** · 2016/09/05(月) 22:41:44.52

いかなディープラーニングでも評価関数をいきなり作るのは厳しい気がしてきてます。

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

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

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

**460** · 2016/09/07(水) 01:48:41.72

自己対局ですが、８手読みの２０マス空き完全読み設定だと、２日で大体２０万局終わることが分かりました。
ここまで速いと１０手読みの２２マス空き読みにランクアップしてみたいところ。。
体感だと1/3くらい遅くなっているのですが、２２マス空き読みだと偏りもひどくて、
１～２日やってみないとなんとも言えない感じです。
２日で７万局程度終えられるなら、それでのんびりやろうかと思います。

**460** · 2016/09/07(水) 03:02:28.63

今しがた動かし中ですが、４００局完了まで１６～１７分でした。
１時間で１４００局程度できそうなので、１か月で１００万局くらい行けそうです。
とりあえずこのまま１００万局集めようと思いますｗ

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

**名前は開発中のものです。** · 2016/09/07(水) 23:27:08.71

誰かヘルプ！
このページのmm.tar.bz2の使い方わかる人いない？

http://www.remi-coulom.fr/Amsterdam2007/

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

**460** · 2016/09/07(水) 23:57:41.97

>>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は下５行だけが出力されるみたいです。

**535** · 2016/09/08(木) 00:10:42.63

>>536
おお、返信ありがとうございます。
mm.exe < input.datやってみましたが何も出ないです。
もしかしてinput.datはなにか編集しないといけないのでしょうか？

**535** · 2016/09/08(木) 00:16:47.92

すいません。
makefileからコンパイルオプションを取り除いたところ結果が出力されました。
-O3がダメなのかなぁ。

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

**460** · 2016/09/08(木) 00:21:28.75

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

**460** · 2016/09/08(木) 00:23:56.75

>>538
動いてよかったです。
最適化が悪さしていましたか。。-O1程度の方がいいかもですね。

**460** · 2016/09/10(土) 21:06:28.42

>>534の読みを深くさせた自己対局棋譜ですが、１５万程度集まったので
無理やり学習してWZebraと対局させてみたところ、黒持ちで＋１２、白持ちで＋２でした！
次善手や序盤ランダムの考慮と読みを深くした効果が現れてて安心しました。。１００万達成した時の結果が楽しみです。

**460** · 2016/09/11(日) 09:03:13.98

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

**名前は開発中のものです。** · 2016/09/11(日) 11:41:57.36

>>542
やっぱり最終目標は完全解析なんですか？

**460** · 2016/09/11(日) 15:25:12.97

>>543
いえ、さすがにそこまでは・・・ｗ
Edaxの作者が完全解析を先行してやってるみたいですし、そこは任せようかなと。
最終的にEdaxやMasterReversiと同等の評価関数やBOOKを作成できるレベルまで持っていきたいです。

**535** · 2016/09/12(月) 21:36:16.05

>>535です。
<number of gammas for this feature>というのがよくわからん。
とりあえず１にしとけばＯＫみたいな？
input.dat色々いじってみたけど確かにそれっぽい値はに出る。

**310** · 2016/09/12(月) 22:52:49.52

>>460さん、着実に進んでいてうらやましい。

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

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

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

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