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

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

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

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

**310** · 2015/12/29(火) 10:52:28.77

>>372
やったりやらなかったりで、いろいろ比較して試してます。

MTD(ｆ）では、ワーストケースではウィンドウ中心が評価値の最少単位で動く関係で、
１石以下の少数計算をする中盤探索では、よけいに時間がかかる事が多いです。
そのため、アスピレーションウィンドウ導入前はただのnegaScoutにしてました。
終盤探索は、最少単位が１石になりますので、許容範囲です。

MTD(ｆ）もアスピレーションウィンドウも、所詮本チャンのnegaScoutを呼び出すための
ドライバーにすぎないので、どちらも用意して、何かの折に速度比較しています。
今回は、ボツりましたが、ぴったりの値が見つかったら後の探索を省略する際には、
MTD(ｆ）の方がマッチングが良かったので、そうしました。

ボツになりましたので、またアスピレーションウィンドウに戻りましたが。

#40ではzebraよりはるかに高速化できましたが、#43など遅いケースでは、数倍の時間が
かかります。こういうタイプの時間差は、単純な高速化じゃなくて、何らかのアルゴリズム
の違いがあるのかなと想像しています。

**310** · 2015/12/30(水) 00:01:33.75

結局、本日は探索速度アップばかりやってました。

中盤探索というか評価関数の計算でBMI2命令を徹底的に使ってみました。
また、ボードの回転操作系も見直しました。
１０％程度は高速化できたと思います。でも、期待したほどではなかった。
あと、速度アップするなら、ボードの対角線転置かなぁ。あと効果は微妙だけど、１８０度
回転がビットオーダーの逆転なので、これも何か組み込み関数があったらうれしいなと。

終盤探索では、FFO#59問題に対処。
スコア計算の修正と、全滅など６４石の差がついた時に、βカットと同様に後続の探索を
パスして時短。minMaxで言うところのα値の更新があり得なくなるからです。

浅い探索が１１手だと３秒程度で解けるのに、１５手だと６０秒かかったりと、いまいち動き
に納得がいかないので、まだ何か問題があるかも知れません。

中盤探索をあと５０％は高速化したいなぁ。というか、zebra見てるとできるはず。

**310** · 2015/12/31(木) 21:04:10.05

2015年の年の瀬は、MPC計算のメモリーリークの原因探しで更けていく・・・
置換表クラスあたりっぽいんだけど、デバッグの仕方が良くわからないという・・・

**310** · 2015/12/31(木) 23:46:42.84

ギリギリ１２時前に直った。
メモリリークではなく、不正なアクセスでした。
多分直ったと思う・・・

来年の抱負は、MPCの計算をする事と、GUIを作る事です。
元々VBのGUIからDLLで呼び出すつもりでしたが、なんとなくC++でやってみようか
という気になってきています。

**310** · 2016/01/03(日) 11:08:48.54

バグは解消してました。なんとも不可思議な事になっていました。
スタック領域を破壊していて、破壊された箇所がたまたまdepth（残り探索深さ）だったため、
探索深さがマチマチになってました。計算時間やメモリ使用量が異常になる以外は、そこそこ
それっぽい探索結果が出ていたため、メモリリークだと思ってしまったという。

中盤探索の置換表適用範囲も、ちゃんと効くようになって深さ１１～１２まで置換表を使用
するのが効果的と出て、探索値のバラツキもそこそこ揃って、探索時間も予想できる範囲に。
メモリ使用量も安定しました。

ある棋譜に対し、２０手目から終局まで順に、深さ１～１７の探索を、反復深化を活用しながら
探索値を求めるプログラムを用意して、１４棋譜を対象に実行したところ凡そ７時間で完了。
速度的にはこんなものかなぁという感じ。もっとも、深さ１７だと結構、探索時間・ノード数の
バラツキが大きいので、１０件前後だと終了時刻もバラツクはず。

とりあえず、棋譜からランダムに１０件程度を抽出し、この探索結果を貯めていくところまで
作りました。トータル１００件程度集めれば、MPCパラメータ計算には十分だと思う。
探索結果を貯めてあるので、毎晩１０件くらいづつ追加し、直説法で都度パラメータ再計算
して精度を上げていく事ができる。

**310** · 2016/01/04(月) 22:22:10.63

MPCのための探索データ蓄積の間に、並列処理について調べてみました。
VC++だとopenMPとPPLってのが使えるみたいです。
?concurrent_unordered_mapが便利そうなので、PPLにしよううかなと。

で、脳内コーディングであれこれ考えていたら、AIの中でBoardクラスを参照渡しして、
差分型で盤面を進めたり戻したりしているのが、とても並列処理と相性が悪い事に
思い至りまして・・・。コピー型に戻して、何をクラス化するのかとか見直してみようかと
言う事に。

多分数日がかりになるかなと。

**名前は開発中のものです。** · 2016/01/04(月) 22:36:46.74

Boardはスレッドごとに持てばいいんでない
スレッドを生成するときだけコピーすれば

**名前は開発中のものです。** · 2016/01/05(火) 01:07:47.45

自分の場合は将棋作ってて、並列にしたけどstockfishのソースとか参考になるよ
スレッド待機させてノードの終わりの方で判定して、OKなら分割させて
そこで上でも言われてるけど、盤の情報をコピーして走らせるの

自分は盤面作成とか更新巻き戻しなどを最初スレッドとか考えてなく直にアクセスしてて
全てポイントにからに変更するのが、かなりだるかった

**名前は開発中のものです。** · 2016/01/05(火) 20:35:26.92

へーこのスレって意外と人いるんだなぁ
将棋作ってる人がいるとは驚き

**310** · 2016/01/09(土) 02:12:28.10

どもです。

とりあえず、コピー方式に変えてましたが、変にバグを仕込んだりして、時間がかかって
ました。ようやくデバッグもあらかた終わったのですが、まだ原因不明・解釈不能な速度
差があって、終盤探索のみ速度が１０％以上低下した状態です。
というか、コピー版を書きながら気づいた箇所を、ボードクラス版にも反映すると、ボード
クラス版が高速化して、差が広がるという。
で、クラス版がFFO#40で１．４０～１．４２秒になりました。

>>380さん
おっしゃる通りですorz

プログラム直しながら、ネットでVC++の解説をつまみ読みしながらのコーディングに
限界を感じたので、オライリーさんの出番という事で、アマゾンに本を数冊注文しました。
到着待ちの間にやるなら、適当に作っていったクラスの整理統合かなぁ。
あと、openMPのお勉強。

**名前は開発中のものです。** · 2016/01/09(土) 02:32:30.66

最近のvc++使ってるのなら普通にstd::threadでやるのもいいかも

**310** · 2016/01/10(日) 01:14:26.88

うわ。色々やり方あるのね。
VC++だとPPL、openMP、std::threadか。

PPLについては、逐次処理のまま置換表で使っているunordered_mapをconcurrent版に
変えてみたところ、置換表付探索の速度がおおよそ半分になってしまったので、結構
微妙な印象を持っています。
とりあえずopenMPでどこまでできるか試してみて、気に入らなかったらstd::threadで
細かく制御できないか考えてみます。

先ほど、コピー版で置換表登録に影響するバグ発見。直したところ、FFO#40が1.26秒
とかになってしまいました（汗）。不可思議な速度差の原因はこれで間違いないと思います。
edaxまであと１０倍の速度アップかぁ。並列化で３倍くらいまで詰められないかと期待。

一応、Boardクラスのポインタ渡し版（差分方式）も試してみましたが、今のところ、若干
速度低下しています。もともとの差分方式は、Boardクラスを継承したAIクラスのメンバ
関数として実装してます。
これらの一見無駄な作業も、バグ探し＆逐次探索の速度アップに有効だったという事でorz

**310** · 2016/01/11(月) 20:31:40.39

とりあえずopenMPで並列化トライしてみましたが、コンパイル中に内部エラーになる。
ネットで見ると最適化オプションがらみらしいけど、なんかよくわからなかったのでパス。

PPLを使って、とりあえず並列化のテスト。オセロでは標準的と思われるｎ段YWBCに
してみました。forループみたいな特定の形ではPPLは結構簡単という印象。

バグは一通りとれた状態だと思いますが、FFO#40で１．２５秒が０．８５秒程度になり
３０％強の高速化。あと少しだけソース修正するつもり。

使ってるパソコンは２コアでした。昨夜まで４コアのつもりでいましたが（汗）、２コアなら
こんなものなのかな。

**名前は開発中のものです。** · 2016/01/11(月) 21:53:26.50

2コアYBWCにしてはまあまあ並列化されてるような感じ
もちろんもっと効率化はできるけど

**310** · 2016/01/13(水) 13:02:44.01

どもです。

コア数２だと、理屈の上では２倍近くまでは速度アップできるのかなぁと思います。
一般的にはどのくらいの倍率をターゲットにしているのでしょうか。

YBWCの適用のパターンをいくつか試しましたが、タスクマネージャーで見たCPU使用率
は、ほぼ１００％になってるので、単純にはスピードアップは難しい感じがしてます。
PPL自身のオーバーヘッドなのか。
PPLは楽ちんだけど、チューニング箇所がなさすぎな感じ。

あと、YBWCやってる以上、YBの着手をmove orderingする意味が無い感じなので、
sortが一つ省けるかなぁというところ。ルートに近いので、あまり効果は無いと思うけど。

ここまで来ると、８コアのパソコン持ってきたら・・・
SIMD拡張命令だBMI命令だを使っておきながら、コア数２で頑張るのもどうかみたいな。

**310** · 2016/01/16(土) 09:10:45.76

PPLはMicrosoftのDeveloper Networkくらいしか情報が無いので、ひたすらリンクを
たどって情報収集してますが、ほとんど機械翻訳で、結局カーソルあてて英文読ま
ないと意味が分からないという・・・

で、排他制御とかいい加減にしていたノード数カウントなどをきちんとして、ソースの見易さ
と効率を上げようと色々と細かく修正。combinableとかcritical_sectionとかInterlockedとか。

と・・・思ったら・・・中盤探索で確率１０％程度で違う答えが返ってくる・・・
並列探査のバグはわかりにくくて時間を食ったのですが、どうもcombinableの動作が変。
期待した動作をしていない。でも、情報が無さすぎで、どこを直せば良いのかわからず、
結局同等の機能を動的配列にしてしまった。

**310** · 2016/01/16(土) 11:37:48.70

中盤探索を１万回程度回して、違った答えが返ってこない事を確認できました。

ノード数カウントはInterlockedIncrementを使っているんだけど、やはり排他待ちロスが
大きいようで、ノードカウントありだと０．８秒前後、無しだと０．７秒前後になる。
使えなかったcombinableみたいな形にして、一つの再帰関数内はローカル変数で加算
して、最後にまとめて１か所で排他加算するようにしてみようかな。

並列タスクの起動順で、探索ノード数が違ってくる関係で、実行時間のバラつきが±０．５
秒くらいになっている。

**310** · 2016/01/18(月) 09:54:27.64

結局、ノード数・リーフ数カウントは、戻り値を構造体にして返す方向にて検討。
普段の探索には不要だけど、solverだと表示したいので。
これで完全にローカル変数になり、排他ロスを気にする必要がなくなる。

デバッグ用の置換表回りの統計は、所詮デバッグ用なので、一旦全削除。
必要になったら、こちらは#ifdefで囲って、排他加算する。

で、構造体の形であれこれ悩んでいたら、戻り値をクラスにできる事に気が付いて・・・
あらためてC++すげーと感心中。

けど、かなり全面的な修正になるので、時間食ってます。
まずは中盤探索を修正して、ノード数がおかしくない事を確認。
終盤探索の修正はこれから。探索を使う系の統計処理も変更しなきゃならないけど、
MPC以外は、次いつ使うかわからないｗ

**310** · 2016/01/19(火) 00:13:53.27

終盤探索の修正完了。

０．８秒±０．０５秒と、結局、Interlockedでグローバル変数のノード数を加算するのと、
大して時間が変わらないか、もしかしたら微妙に遅くなったかも。元に戻すのが面倒
なので、他で改良点を探すしかないかなと。

**310** · 2016/01/21(木) 10:04:20.88

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

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

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

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

**310** · 2016/01/23(土) 01:31:00.95

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

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

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

**310** · 2016/01/27(水) 01:18:29.98

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

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

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

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

**310** · 2016/01/29(金) 11:31:08.14

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

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

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

**310** · 2016/01/30(土) 20:51:37.62

囲碁がすごい事になってますね。オセロで一通り勉強したら小さい盤の囲碁をやって
みようと思っていたので、モチベーション低下中。とはいえ、ああいうのをオセロに応用
しようとしたら、あそこまでマシンパワーいらないんじゃないかとか・・・。

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

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

**310** · 2016/02/07(日) 21:48:19.14

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

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

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

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

**310** · 2016/02/09(火) 01:09:41.58

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

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

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

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

**名前は開発中のものです。** · 2016/02/15(月) 00:14:34.50

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

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

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

**310** · 2016/02/20(土) 13:43:08.30

GUIできた。昔作った序盤定石部分と合体。
中盤探索を反復深化にして、３秒を超えて新しい深さに入らないあたりで調整。
MPCで２５手くらいまで読めるように調整。
終盤完全読みは３８手から。３６手からMPC付で完全読み（つまり完全ではない）。

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

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

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

**310** · 2016/02/20(土) 23:06:47.33

zebra先生にならって定石の評価を表示するオプションをつけてみました。
ロジック的には間違いなさそうですが、定石DBがおかしいというか、定石に登録がない
手順に正しい変化があって、それを無視しているため、間違った判断をしているみたい。

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

**310** · 2016/02/21(日) 01:04:17.33

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

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

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

**310** · 2016/02/25(木) 21:06:56.39

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

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

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

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

**310** · 2016/02/28(日) 01:10:48.52

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

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

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

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

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

**じょげなら** ◆kXDiHQuNQ2 · 2016/02/29(月) 19:18:07.19

ライフゲーム囲碁というゲームのネット対局場を作りたいです。
囲碁でいうKGSみたいなのが理想です。
プログラムはある程度わかりますが、ネット関連の知識が乏しいです。
何から始めればいいですか？

**名前は開発中のものです。** · 2016/02/29(月) 19:21:39.28

ＵＲＬがＮＧワードに引っかかる…

**名前は開発中のものです。** · 2016/02/29(月) 19:34:26.59

好きな言語
C++
C#
Ruby

嫌いな言語
Java
Python
Perl

**４０６** · 2016/03/01(火) 20:52:33.32

とりあえずHTML5の本買ってきた

**406** · 2016/03/03(木) 19:44:49.47

http://fast-uploader.com/file/7012557196681/
碁石をぽちぽち置けるところまで作った

**310** · 2016/03/04(金) 10:15:09.55

>>410
一晩考えてみた。

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

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

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

**406** · 2016/03/04(金) 18:58:38.77

>>411
レスありがとうございます。
確かにセッション管理とか知らないです。
チャット調べてみます。

**406** · 2016/03/07(月) 21:05:27.22

RoRの本買ってきた。
チャットはまだ調べてない。

**名前は開発中のものです。** · 2016/03/09(水) 19:45:29.94

うおおおおセドルがああああぁぁぁ

**310** · 2016/03/10(木) 02:00:10.79

うむむ。
これにて、オセロができたら次は囲碁という目標が雲散霧消してしまいました。

どうしよう。

**310** · 2016/03/10(木) 18:05:03.79

AlphaGO強すぎ・・・orz

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

**名前は開発中のものです。** · 2016/03/10(木) 19:38:43.78

３１０氏もalpha碁注目してたか。
セドル一発入れてほしいなぁ

**名前は開発中のものです。** · 2016/03/11(金) 09:04:36.30

浮上

**名前は開発中のものです。** · 2016/03/12(土) 12:19:15.41

おお、このスレ生きてたんだ

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

**名前は開発中のものです。** · 2016/03/13(日) 18:01:59.50

せどるううううッよくやったあああああぁっ
人類の勝利やあああぁぁっ

**名前は開発中のものです。** · 2016/03/13(日) 19:02:49.19

お、第四局はセドル勝ったか

**310** · 2016/03/13(日) 20:47:23.70

うむ。なんか期待を裏切られっぱなしｗ

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

**406** · 2016/03/15(火) 20:44:49.53

RoRとjavascriptの連携がよくわからん。
でもちょっとづつだけど進んでる。

**310** · 2016/03/16(水) 23:06:52.43

アルファ碁ロスまっただ中ですｗ

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

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

**406** · 2016/03/19(土) 20:06:25.11

railsでdeviseとかいうgemをつかってユーザー認証機能実装したけど、
複数ユーザーがログインして対局させる方法がサッパリわからん。

**406** · 2016/03/24(木) 20:20:54.97

ブラウザ閉じたときに自動ログアウトのやり方がわからん

**名前は開発中のものです。** · 2016/03/25(金) 13:51:48.34

ブラウザは通信があった時にしかクライアントの消息が確認できない。

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

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

**名前は開発中のものです。** · 2016/03/25(金) 14:16:19.46

１行目おかしかった。

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

に修正。

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

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

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

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

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

**406** · 2016/03/25(金) 17:43:19.31

丁寧にありがとうございます。
javascriptのwindow.oncloseからなんとかならないかといろいろ調べていましたが、無理筋なんでしょうか。
タイムアウト検討してみます。

**名前は開発中のものです。** · 2016/03/26(土) 21:27:54.24

>>429
そういう事を考えるんなら、Javaアプレットとか、ActiveXとかの、
ブラウザ上で動いて通信できる方法を試した方が良いかもね。

**406** · 2016/03/30(水) 21:45:07.64

すいません、教えてください。

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

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

**名前は開発中のものです。** · 2016/03/30(水) 23:26:15.10

>>431
そうです。別にしなくても良いし、月１回手作業で削除しても良いけどね。

**406** · 2016/03/31(木) 20:31:39.10

>>432
手作業ですかうーん。
まあ、頭の片隅に置いておきます。
ありがとうございます。

**名前は開発中のものです。** · 2016/04/01(金) 19:52:02.46

隠しコマンド受け付けるようにしておいて
管理者のクライアントから定期的にコマンドを投げればいい

**310** · 2016/04/05(火) 10:45:13.03

久々登場。アルファ碁ロスがでかすぎて、やる気がでないです。

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

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

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

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

**406** · 2016/04/06(水) 22:31:38.47

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

**406** · 2016/04/08(金) 22:18:30.78

棋譜ツリー表示すんの結構メンドクサイような希ガス
いいライブラリはないんか

**406** · 2016/04/09(土) 23:59:42.58

KGSのレーティングシステム難しい。
まだそんなこと考える段階じゃないけど。

**406** · 2016/04/11(月) 21:25:49.37

javascriptでオブジェクトの比較ってjsonで変換してそれを比較しろとか某ページで見たけど
そんな事せにゃならんの？

**406** · 2016/04/12(火) 23:02:53.74

http://textuploader.com/5w3sq
棋譜ツリーだいぶ形になってきた。

**406** · 2016/04/16(土) 22:59:10.60

Rails側とjavascript側の連携がやっぱわからん。
色々めんどくさすぎ。

**406** · 2016/04/23(土) 00:16:56.63

エンコード間違えてて動かなかったわ。
railsがログ吐いてくれてなきゃ一生気づかなかっただろうな。

**406** · 2016/04/27(水) 21:48:14.23

開発に使ってたノートのキーボードが一部効かなくなったわorz.
windowsにログインできなくて焦った。
アカウントでも乗っ取られたのかと思ったらソフトキーボード使ったらログインできた。
ＵＳＢキーボードとかで代用できればいいんだがどうかな～。

**406** · 2016/05/02(月) 21:58:59.67

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

**406** · 2016/05/02(月) 23:06:51.86

以下のログが出るんだけど、だれか原因わかる人いない？

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)>'

**４０６** · 2016/05/03(火) 11:00:58.43

すいません、解決しました。

**４０６** · 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さんと情報交換したところ、末端ノードの高速化の
方向性が全く逆だったのが意外でした。