[過去ﾛｸﾞ] 【オセロ,将棋】ボードゲーム【囲碁,War】 (1002ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
638: 310 2016/10/29(土)21:13 ID:hyv6QOjp(1/2) AAS
並列化してみました。
色々やり方ありますが、まあ順当なやり方という事で、ツリー単位の並列化です。
が、４コアに対して４並列でむしろ速度低下。排他で怪しいところを色々変えてみて
ようやく若干（１０〜２０％程度）の速度アップにしかなりません。並列数を減らすと
速度低下していくので、排他待ちが原因ではなく、並列化オーバーヘッドの模様。
ノード＆ツリーの構造で複雑な分、オーバーヘッドが大きくなっているのか、オセロの
時の効果には大きくおよびません。
ルート単位の並列化で、一定時間ごとにツリー統合（合算）というやり方もあるような
ので、次はこちらを試してみます。
もしかしたら、一番効果が無さそうな、プレイアウトのみ並列化の方が効果出たりして。
639: 310 2016/10/29(土)21:14 ID:hyv6QOjp(2/2) AAS
MTCSは並列化と相性が良いとは思えないなぁ。
640: 535 2016/10/30(日)23:47 ID:11nwLD7b(1) AAS
return文忘れててめちゃくちゃな値返してた。
この不可解なバグ潰すのに３時間かかったorz.
関数の終わりでreturn文無かったら警告だしてよコンパイラ（泣
まあコンパイラオプション付けてない俺が悪いんだがｗｗｗ
641: 310 2016/10/30(日)23:54 ID:vT6Vi1L+(1) AAS
結局ツリー部の並列化はやめてプレイアウトだけを並列化しました。
ツリー統合も気になりますが、とりあえずこれで末端の評価が正確になります。
プレイアウト部分は処理時間が短いので、プレイアウト回数は大幅に増えます。
MCTSは面倒でも、モンテカルロは並列化向きです。
１００回プレイアウトして、そのスコアでまとめて更新。
ところが、バグを発見してしまいました。
勝ち手順で進めていたのに、最後の最後に１手間違えて引分。
もうプレイアウトではなくツリーの勝敗が確定している状態で、間違えるはずがない。
勝敗確定時のフラグ設定がおかしいようです。
そこから色々見直しを始めたら、negaMax的な処理の扱いに完全に混乱して
しまいまして…。これだと思って修正すると、おかしくなってしまいます。
どこか根本的に勘違いしているみたいなので、しばし長考に入りますorz
642: 535 2016/10/31(月)00:37 ID:KdjBytFw(1/3) AAS
なかなかいい感じのルーチンが書けた。
まだ結果に結びついてないけどこれはあと一捻りいれればかなりいい線行くんじゃないか？
643: 535 2016/10/31(月)21:35 ID:KdjBytFw(2/3) AAS
おかしいな。
石の流れは良くなってるのになかなか勝利に結びつかない。
644: 535 2016/10/31(月)22:47 ID:KdjBytFw(3/3) AAS
パラメータ微調整地獄ｗ
機械学習に切り替えないと限界が…
645: 535 2016/11/01(火)21:33 ID:pQxzEPLf(1) AAS
あかん。
完全にバランスを失った。
一から出直しだな。orz
646: 2016/11/03(木)03:15 ID:x7yDYWU2(1) AAS
ボードゲームのオリジナルオーダー制作
外部ﾘﾝｸ[html]:www.logygames.com
簡単に本格自作ボードゲームが作れる時代到来！！
外部ﾘﾝｸ:jellyjellycafe.com
100円ショップでボードゲームを自作しよう
外部ﾘﾝｸ:sites.google.com
ノーアイデアでボードゲームを作ろう第1回「100円ショップで物を買う」
外部ﾘﾝｸ:boardgamelove.com
ボードゲーム市場がクラウドファンディングの出現で急成長を遂げ市場規模を拡大中
外部ﾘﾝｸ:gigazine.net
647: 310 2016/11/04(金)15:36 ID:zGiY9OSz(1) AAS
長考の結果、もう一度作り直し（笑）していたら、混乱の原因がわかりまして。
勝敗の持ち方を逆にしたらすっきりしました。
あと、終盤の手順の前後で、あと３手粘れるのに１手で負けるという現象を調べた
結果、ツリー部で負けと判定している以上、何手先に負けるか関係ないというプロ
グラムになっていた事も判明。バグじゃありませんでした。とはいえ気持ちが悪いので、
なるべく長く粘るようにしてみました。
そこでわかったのは、Perfect Solverの数字は、４２手２１ターン目の引分から何ターン
前に勝負がつくのかを表していて、プラスは勝ち、マイナスは負けという事です。先手で
＋１と出たら最善を尽くせば４１手目の自分の着手で勝つという事のようです。
つまりスコアを勝敗決定ターンにしたmin-Maxで、速度考えるとDB化してるんでしょう。
で、MCTSですが、まあやはりモンテカルロなので間違えます。試しに１０手目程度
の間違えた局面から、シミュレーションを続行してみたところ、億単位の探索（プレイ
アウトとしては１０倍）で、間違えた手が本当は悪かった事に気づいた様子で、そこから
正しい答えに向かって行きました。なので、まあプログラムは間違っていない模様です（汗。
DAG対応とか、自殺手禁止プレイアウトとか、色々やった結果、選択手のばらつきが
減って、「たまたま正解手順を引く」事がなくなって、自信満々に間違えるようになっ
た印象です。それでも、時間をかけて探索を続けると、いつかは正しい答えにたどり着くと。
今となってはあまり意味が無いですが、せっかくなので、ここまで積み上げて来た
ノウハウで、今一度Solver作ってみようかなと。
648: 535 2016/11/04(金)23:52 ID:lKhN7bKh(1) AAS
色々ぐちゃぐちゃやってたら計算時間がとてつもないことになってしまった。
649: 310 2016/11/06(日)13:49 ID:Z4kqE5wB(1) AAS
Solver作りました。
PerfectSolverにならって評価値を、４２手目から何手手前で勝敗がついたかにしました。
お蔭さまで、null window searchが使えるようになり、mtd(f)で高速化しました。
あと、初段のみ単純な並列して、残り２８手で６秒強となりました。
そろそろオセロに戻ります。
650: 535 2016/11/06(日)17:53 ID:B23WCzGo(1) AAS
終盤28手読み6秒とか凄い
こっちはというとそろそろαβ刈りを習得しなければ…
651: 535 2016/11/07(月)00:12 ID:vL8wkeAF(1/2) AAS
αβできたっぽいです。
というかwikiの疑似コードを完コピしたらうごいたっぽい？という感じで
理解したとはいいがたいですが。
652: 535 2016/11/07(月)22:06 ID:vL8wkeAF(2/2) AAS
え、もしかしてminmaxに比べてαβめちゃめちゃ速い？
なんか間違ってんのかな…
653: 310 2016/11/08(火)00:02 ID:CUgV7Bvg(1) AAS
安心してください。めちゃ早いですよｗ
後ろ向き枝刈系のアルゴリズムはほとんどがαβを前提にしています。
自分の最初は擬似コードコピペしました。
すぐ忘れちゃいますが、１回は真剣に動作を追っておくと良いですよ。
654: 535 2016/11/08(火)22:35 ID:BlAmLHY6(1) AAS
評価関数が致命的に狂ってる気がする。
手動で直すのは限界があるから機械学習したいがさてどうするか。
655: 310 2016/11/10(木)20:55 ID:gpSCAC4W(1) AAS
オセロでUCTをしてます。コピペでちょいちょいと思っていたらパスの処理が面倒で、
思った以上に動作速度が落ちてしまいました。
その後、デバッグしてたらおかしな現象を発見。探索ツリーでプラスになるべき数字が
マイナスに。しかも１か所だけ。発生条件を絞り込めず、なんだかんだと数日間。
原因は整数のオーバーフローでした。設定時間におけるプレイアウト回数でのスコア合計
がちょうど境目にきて、本当に微妙にオーバーフローしていたので、スコアの正負がひっく
りかえったように見えていたのでした。
俺の時間を返せorz
終盤５手読みくらいならすぐにUCTのツリーが終局まで達して、完全読み同等の答えを
返してくれるのですが、１０手だと結構時間がかかり、２０手だと全く歯が立たない。
評価関数を使った中盤探索の置き換えに使えないかと想定しているのですが、やはり
簡単に精度は出ない感じです。
プレイアウトでありがちな手を優先的に着手するように、ヒューリスティックな評価関数を
用意して、プレイアウトの精度を高められるか試してみたいと思います。あと、スピード
アップもしないと・・・。
656: 535 2016/11/10(木)23:14 ID:4tjjzH07(1) AAS
Zenは治勲と三番勝負か〜
Zen勝ちそうｗ
657: 535 2016/11/13(日)00:19 ID:otFLKKMJ(1) AAS
doubleの有効桁数が足りなくておかしくなってたorz
評価値に差をつけようとして極端にデカい数値を設定してたら
小さい数値が無視されてた
658: 310 2016/11/13(日)00:47 ID:Be0ooFvL(1/2) AAS
DeepZenGo楽しみですね。
ポストアルファ碁の今となってはZenが２勝できなかったらちょっと悲しいかな。
こちらはオセロのモンテカルロツリー探索がほぼできました。
当初かなり速度ダウンしていたのですが、何とか改良できました。vectorが遅かった。
数か所工夫して、テストデータで正解を早く導けるようにしてみましたが、調整が面倒そう。
とりあえずネタ切れなので、次は探索済ツリーを再利用できるようにして、対戦できるよう
にする予定です。で、今一度終盤読み切りルーチンと、序盤の定石DBつけて完成としたい。
しかし、相変わらず評価値をどう計算したら良いのかわからない。
単純に、着手する手の平均スコアだと、探索の進み具合によってあなりブレてしまい
意味がある数字になりそうにない。アルファ碁はDCNNの評価値を使ってるのかなぁ。
659: 310 2016/11/13(日)20:49 ID:Be0ooFvL(2/2) AAS
ちょっと疑念が湧いてきたので数か所工夫したところを全てコメントアウトしてみたところ
やらない方が遥かにマシという結論に（汗。下手な考え休むに至りでした。
全部外してしまうと一旦最善手から外れてまた戻ってくるような事もなくなり、探索時間が
長い方が良いと単純に言えるようになります。
また、評価値ですが、モンテカルロならやはり点差を考慮しない「勝率」であるべきでは
ないかと思い始めています。今は、「点差」を返しています。「勝率」で選ぶ手は、「もっと
良い手があった」となりますし、「点差」で選ぶ手は「欲張りすぎた」となりそうです。
探索済ツリーの再利用の仕組みができました。まだパスがらみのテストはしてませんが、
多分大丈夫でしょう。
ボード関連のクラスをかなり作り直してしまったので、終盤読み切りルーチンや序盤定石
処理を作り直さないといけません。というか、評価関数を持ってないので、終盤探索は
オーダリングの仕方を変えないといけません。
あと、人間側入力待ちの間も探索を継続できるようにしてみたいと思っています。
モンテカルロだと、いつでも停止したり再開できるので、ぜひとも導入したいものです。
660: 310 2016/11/16(水)01:01 ID:2m1pjf8n(1) AAS
人間の入力待ちの時のバックグラウンド探索を実装しました。
並列処理はPPLを使ってるので、思いのほか簡単にできましたが、入力待ちのまま
放置されると、数時間でメモリーを食いつぶしてしまう事に気づきました。
パンクしそうになったらツリーをルートに近い順に削除するようにしましたが、メモリー
リークしてそうでちょっと怖いです。
コンピュータ同士で対戦させてみたところ、まあそれっぽくは打ちますが、序盤で定石
から外れてしまいます。終盤は結構正確に見えます。
評価値の件、独自ロジックを外したところ、それっぽい値を表示するようになりました。
661: 310 2016/11/16(水)09:03 ID:uZWbEwsE(1) AAS
自分のつたないオセロ力では、モンテカルロが着手した手が良いのか悪いのか
わからないので、どうしようかと寝ながら考えました。
まず考えたのは、完全読み切りルーチンを作って、終盤に限っては正解着手も
探索してみる事。でも、最終的には終盤は完全読み切り使った方が、正確で早い
ので、そちらを使用。中盤や序盤の具合がわからない以上、ほぼ意味なし。
続いて、WZebraにある「解析機能」を実現できないかと考えました。中身はわからない
ので想像。使用して感動した経験あり。
「後ろから解析」なら、αβを後ろから回し、自分が着手した手より良い手が無ければ
βカット、あればそれで生じたスコアの増減を記録という形で、中盤のある程度のところ
までは、遡りつつ誤着手を検出できるんじゃないかなと。棋譜にある着手はこのロジック
で評価が定まっているので、探索を省く事ができます。評価関数を持っていないので、
遡れても３０〜３５手目くらいまでかと思いますが、読み切りルーチンをいじれば作れ
そうなので、トライしてみようと思います。
誤着手率がわかっても、簡単に直らないのがモンテカルロですが…。
662: 535 2016/11/19(土)18:30 ID:X8ZFdPyh(1) AAS
ん〜Zen負けちゃった。
期待してたんだが。
663: 310 2016/11/19(土)20:47 ID:F+e1LSRb(1) AAS
とりあえずWZebra相手に戦ってみたのですが、全滅しない程度に負けますｗ
評価値が全然違うというか、自分は有利なつもりで進んでいても、Zebra的には
＋５０とかになってます。４０〜５０手目付近で末端までツリーを展開してようやく
気づくみたいな。そこまで行くと、ほぼ間違えなくなる（当たり前）のですが、序盤
中盤があまりに酷いので、定石ルーチンで助けられないレベルかなと。
そもそも評価値が間違いまくりで、自分のAIは少し有利くらいの勝率になっている
のに、zebraは既に＋３０とか＋５０とか。形を見ても、素人目にも全く不利な形に。
ランダム着手で勝率や平均スコア求めても意味が無いかも、という本質的な
課題に突き当たってしまいました。
ツリー依存度を上げようと閾値を下げてツリー展開しやすくすると、あっという間に
メモリが溢れてしまいますので非現実的。本来はucb1の計算が機能して、変な
ツリーに手を回さないのですが、むしろ変な手にロックオンしてしまいがち。
囲碁みたいに、１手の価値や、最終的な形が同じなら着手する順番関係ないよう
なゲームじゃないと厳しいのかなと思い始めています。
相手の入力待ちの時のバックグラウンド探索では、敢えて初手についてのみ全て
の手に均等に割り振って、ツリー展開を進めさせてみたのですが、これもやりすぎ
ると簡単にパンクしてしまうので、ほどほどにという感じです。
アンドゥ機能を消して、終わったツリーをバサバサ消す仕様に変更です。
というわけで、解析とか後回しして、強さを上げられないか検討です。
ヒューリスティックな手法で、プレイアウトをもう少し現実的に。同様にUCB1に多少
細工して、よさそうな手の割り当てを増やせないか検討してみます。といっても、
相手の着手可能位置の数を減らすような手を優先するくらいしか、アイデアはあり
ませんが。
664: 310 2016/11/20(日)16:54 ID:4i7ILKOH(1) AAS
「相手の打てる箇所が少ない手を確率的に増やす」程度では全くダメでした。むむむ。
脳内では、プレイアウトの次の１手を決めるのにDCNNでみたいな…本末転倒な対策が
渦巻いてきています（汗。手元にある囲碁のモンテカルロ本（彩の解説、技術的な種本）
でも、自分の石の周辺のパターンを統計的に処理して着手確率を計算みたいな事をして
いまして。オセロでいうと評価関数みたいな事をしていたりします。
オセロは、着手する石の価値が重すぎるので、モンテカルロが向かないって当たり前の
結論ではあるのですが。それにしても、あまりに弱い。
というわけで、ダメ元でプレイアウト時に開放度で着手確率を変える方法を試してみつつ、
技術的勉強で、もう一度、きちんとツリー並列で並列化を実装してみようかなと思ってます。
665: 535 2016/11/20(日)21:28 ID:gm8FgHLO(1) AAS
も〜インテルさん早く１ThｚのCPU出してよ〜w
666: 535 2016/11/23(水)19:46 ID:/Z9U4oFa(1) AAS
Zen負けちゃったか〜
でも一勝しただけでもすごい。
667: 310 2016/11/23(水)23:37 ID:wq9OFZ+n(1) AAS
うむぅ。アルファ碁があるから期待高いけど、互先で１勝したのは凄いよね。
まだ伸びしろありそうだから、次回に期待ですね。
こちらは、モンテカルロがあまりにダメダメで悩み中です。
煮詰まってしまったので、ツリー並列をきちんと実装したり、終盤探索作ったりしてました。
終盤探索は、ようやく>>460さん指摘の偶数理論を実装しました。どうやるのかなかなか
思いつかなかったけど、手を動かしだしたらわかるものですね。Zebraとかのソース見て
いないので、もっと良いやり方があるかも知れませんが。
上下前次1-新書関写板覧索設栞歴
あと 335 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ
ぬこの手 ぬこTOP 0.019s