[過去ﾛｸﾞ]
【オセロ,将棋】ボードゲーム【囲碁,War】 (1002ﾚｽ)
【オセロ,将棋】ボードゲーム【囲碁,War】 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/
上
下
前
次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索
歴削→次ｽﾚ
栞削→次ｽﾚ
過去ﾛｸﾞﾒﾆｭｰ
651: 535 [sage] 2016/11/07(月) 00:12:13.27 ID:vL8wkeAF αβできたっぽいです。 というかwikiの疑似コードを完コピしたらうごいたっぽい？という感じで 理解したとはいいがたいですが。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/651
652: 535 [sage] 2016/11/07(月) 22:06:07.74 ID:vL8wkeAF え、もしかしてminmaxに比べてαβめちゃめちゃ速い？ なんか間違ってんのかな… http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/652
653: 310 [sage] 2016/11/08(火) 00:02:22.02 ID:CUgV7Bvg 安心してください。めちゃ早いですよｗ 後ろ向き枝刈系のアルゴリズムはほとんどがαβを前提にしています。 自分の最初は擬似コードコピペしました。 すぐ忘れちゃいますが、１回は真剣に動作を追っておくと良いですよ。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/653
654: 535 [sage] 2016/11/08(火) 22:35:11.27 ID:BlAmLHY6 評価関数が致命的に狂ってる気がする。 手動で直すのは限界があるから機械学習したいがさてどうするか。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/654
655: 310 [sage] 2016/11/10(木) 20:55:19.87 ID:gpSCAC4W オセロでUCTをしてます。コピペでちょいちょいと思っていたらパスの処理が面倒で、 思った以上に動作速度が落ちてしまいました。 その後、デバッグしてたらおかしな現象を発見。探索ツリーでプラスになるべき数字が マイナスに。しかも１か所だけ。発生条件を絞り込めず、なんだかんだと数日間。 原因は整数のオーバーフローでした。設定時間におけるプレイアウト回数でのスコア合計 がちょうど境目にきて、本当に微妙にオーバーフローしていたので、スコアの正負がひっく りかえったよう
に見えていたのでした。 俺の時間を返せorz 終盤５手読みくらいならすぐにUCTのツリーが終局まで達して、完全読み同等の答えを 返してくれるのですが、１０手だと結構時間がかかり、２０手だと全く歯が立たない。 評価関数を使った中盤探索の置き換えに使えないかと想定しているのですが、やはり 簡単に精度は出ない感じです。 プレイアウトでありがちな手を優先的に着手するように、ヒューリスティックな評価関数を 用意して、プレイアウトの精度を高められるか試してみたいと思います。あと、スピード アップもしないと・・・。 http://mevius.5
ch.net/test/read.cgi/gamedev/1057763418/655
656: 535 [sage] 2016/11/10(木) 23:14:15.10 ID:4tjjzH07 Zenは治勲と三番勝負か〜 Zen勝ちそうｗ http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/656
657: 535 [sage] 2016/11/13(日) 00:19:43.02 ID:otFLKKMJ doubleの有効桁数が足りなくておかしくなってたorz 評価値に差をつけようとして極端にデカい数値を設定してたら 小さい数値が無視されてた http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/657
658: 310 [sage] 2016/11/13(日) 00:47:25.03 ID:Be0ooFvL DeepZenGo楽しみですね。 ポストアルファ碁の今となってはZenが２勝できなかったらちょっと悲しいかな。 こちらはオセロのモンテカルロツリー探索がほぼできました。 当初かなり速度ダウンしていたのですが、何とか改良できました。vectorが遅かった。 数か所工夫して、テストデータで正解を早く導けるようにしてみましたが、調整が面倒そう。 とりあえずネタ切れなので、次は探索済ツリーを再利用できるようにして、対戦できるよう にする予定です。で、今一度終盤読み切りルーチンと、
序盤の定石DBつけて完成としたい。 しかし、相変わらず評価値をどう計算したら良いのかわからない。 単純に、着手する手の平均スコアだと、探索の進み具合によってあなりブレてしまい 意味がある数字になりそうにない。アルファ碁はDCNNの評価値を使ってるのかなぁ。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/658
659: 310 [sage] 2016/11/13(日) 20:49:23.63 ID:Be0ooFvL ちょっと疑念が湧いてきたので数か所工夫したところを全てコメントアウトしてみたところ やらない方が遥かにマシという結論に（汗。下手な考え休むに至りでした。 全部外してしまうと一旦最善手から外れてまた戻ってくるような事もなくなり、探索時間が 長い方が良いと単純に言えるようになります。 また、評価値ですが、モンテカルロならやはり点差を考慮しない「勝率」であるべきでは ないかと思い始めています。今は、「点差」を返しています。「勝率」で選ぶ手は、「もっと 良い手があ
った」となりますし、「点差」で選ぶ手は「欲張りすぎた」となりそうです。 探索済ツリーの再利用の仕組みができました。まだパスがらみのテストはしてませんが、 多分大丈夫でしょう。 ボード関連のクラスをかなり作り直してしまったので、終盤読み切りルーチンや序盤定石 処理を作り直さないといけません。というか、評価関数を持ってないので、終盤探索は オーダリングの仕方を変えないといけません。 あと、人間側入力待ちの間も探索を継続できるようにしてみたいと思っています。 モンテカルロだと、いつでも停止したり再開できるので、ぜひと
も導入したいものです。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/659
660: 310 [sage] 2016/11/16(水) 01:01:14.01 ID:2m1pjf8n 人間の入力待ちの時のバックグラウンド探索を実装しました。 並列処理はPPLを使ってるので、思いのほか簡単にできましたが、入力待ちのまま 放置されると、数時間でメモリーを食いつぶしてしまう事に気づきました。 パンクしそうになったらツリーをルートに近い順に削除するようにしましたが、メモリー リークしてそうでちょっと怖いです。 コンピュータ同士で対戦させてみたところ、まあそれっぽくは打ちますが、序盤で定石 から外れてしまいます。終盤は結構正確に見えます。 評価値の件
、独自ロジックを外したところ、それっぽい値を表示するようになりました。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/660
661: 310 [sage] 2016/11/16(水) 09:03:26.60 ID:uZWbEwsE 自分のつたないオセロ力では、モンテカルロが着手した手が良いのか悪いのか わからないので、どうしようかと寝ながら考えました。 まず考えたのは、完全読み切りルーチンを作って、終盤に限っては正解着手も 探索してみる事。でも、最終的には終盤は完全読み切り使った方が、正確で早い ので、そちらを使用。中盤や序盤の具合がわからない以上、ほぼ意味なし。 続いて、WZebraにある「解析機能」を実現できないかと考えました。中身はわからない ので想像。使用して感動した経験あり。 「
後ろから解析」なら、αβを後ろから回し、自分が着手した手より良い手が無ければ βカット、あればそれで生じたスコアの増減を記録という形で、中盤のある程度のところ までは、遡りつつ誤着手を検出できるんじゃないかなと。棋譜にある着手はこのロジック で評価が定まっているので、探索を省く事ができます。評価関数を持っていないので、 遡れても３０〜３５手目くらいまでかと思いますが、読み切りルーチンをいじれば作れ そうなので、トライしてみようと思います。 誤着手率がわかっても、簡単に直らないのがモンテカルロですが…。 htt
p://mevius.5ch.net/test/read.cgi/gamedev/1057763418/661
662: 535 [sage] 2016/11/19(土) 18:30:11.32 ID:X8ZFdPyh ん〜Zen負けちゃった。 期待してたんだが。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/662
663: 310 [sage] 2016/11/19(土) 20:47:46.55 ID:F+e1LSRb とりあえずWZebra相手に戦ってみたのですが、全滅しない程度に負けますｗ 評価値が全然違うというか、自分は有利なつもりで進んでいても、Zebra的には ＋５０とかになってます。４０〜５０手目付近で末端までツリーを展開してようやく 気づくみたいな。そこまで行くと、ほぼ間違えなくなる（当たり前）のですが、序盤 中盤があまりに酷いので、定石ルーチンで助けられないレベルかなと。 そもそも評価値が間違いまくりで、自分のAIは少し有利くらいの勝率になっている のに、zebraは
既に＋３０とか＋５０とか。形を見ても、素人目にも全く不利な形に。 ランダム着手で勝率や平均スコア求めても意味が無いかも、という本質的な 課題に突き当たってしまいました。 ツリー依存度を上げようと閾値を下げてツリー展開しやすくすると、あっという間に メモリが溢れてしまいますので非現実的。本来はucb1の計算が機能して、変な ツリーに手を回さないのですが、むしろ変な手にロックオンしてしまいがち。 囲碁みたいに、１手の価値や、最終的な形が同じなら着手する順番関係ないよう なゲームじゃないと厳しいのかなと思い始めています。
相手の入力待ちの時のバックグラウンド探索では、敢えて初手についてのみ全て の手に均等に割り振って、ツリー展開を進めさせてみたのですが、これもやりすぎ ると簡単にパンクしてしまうので、ほどほどにという感じです。 アンドゥ機能を消して、終わったツリーをバサバサ消す仕様に変更です。 というわけで、解析とか後回しして、強さを上げられないか検討です。 ヒューリスティックな手法で、プレイアウトをもう少し現実的に。同様にUCB1に多少 細工して、よさそうな手の割り当てを増やせないか検討してみます。といっても、 相手の着手可能位置の
数を減らすような手を優先するくらいしか、アイデアはあり ませんが。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/663
664: 310 [sage] 2016/11/20(日) 16:54:24.84 ID:4i7ILKOH 「相手の打てる箇所が少ない手を確率的に増やす」程度では全くダメでした。むむむ。 脳内では、プレイアウトの次の１手を決めるのにDCNNでみたいな…本末転倒な対策が 渦巻いてきています（汗。手元にある囲碁のモンテカルロ本（彩の解説、技術的な種本） でも、自分の石の周辺のパターンを統計的に処理して着手確率を計算みたいな事をして いまして。オセロでいうと評価関数みたいな事をしていたりします。 オセロは、着手する石の価値が重すぎるので、モンテカルロが向かないって当たり
前の 結論ではあるのですが。それにしても、あまりに弱い。 というわけで、ダメ元でプレイアウト時に開放度で着手確率を変える方法を試してみつつ、 技術的勉強で、もう一度、きちんとツリー並列で並列化を実装してみようかなと思ってます。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/664
665: 535 [sage] 2016/11/20(日) 21:28:29.17 ID:gm8FgHLO も〜インテルさん早く１ThｚのCPU出してよ〜w http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/665
666: 535 [sage] 2016/11/23(水) 19:46:23.65 ID:/Z9U4oFa Zen負けちゃったか〜 でも一勝しただけでもすごい。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/666
667: 310 [sage] 2016/11/23(水) 23:37:07.28 ID:wq9OFZ+n うむぅ。アルファ碁があるから期待高いけど、互先で１勝したのは凄いよね。 まだ伸びしろありそうだから、次回に期待ですね。 こちらは、モンテカルロがあまりにダメダメで悩み中です。 煮詰まってしまったので、ツリー並列をきちんと実装したり、終盤探索作ったりしてました。 終盤探索は、ようやく>>460さん指摘の偶数理論を実装しました。どうやるのかなかなか 思いつかなかったけど、手を動かしだしたらわかるものですね。Zebraとかのソース見て いないので、もっと良いやり方が
あるかも知れませんが。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/667
668: 535 [sage] 2016/11/25(金) 20:21:12.84 ID:udjtSdAy 終盤の打ち方はまあまあいいんだが序盤が致命的すぎる。 思考時間もめちゃめちゃ長いし。 あと強化学習やりたいけどアイディア湧いてこないなぁ。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/668
669: 535 [sage] 2016/11/26(土) 14:07:56.90 ID:3TEfCPcy LV2が思考速くて強いからってLV2の棋譜大量に集めたら学習が偏りそう？ http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/669
670: 310 [sage] 2016/11/28(月) 13:44:46.30 ID:moEHPVOW >>669 やってみないとわからないけど、棋譜は質が良くて偏らないってのが基本だからね。 間違えたら間違えたなりに、負けてくれる棋譜じゃないと、変な学習しちゃうかも。 この辺の兼ね合いが難しい。 ただ、スタートの棋譜をその辺にして、だんだん更新しつつ、強くしていくって方法も あるかと思う。 こちらは、終盤探索に手こずっています。 AVX2命令をオペレーターオーバーロードして使っているのですが、グローバルなのが 気持ち悪くて、クラスに変更。ついでに見直しをして
いたら、過去にどうしてもわからなくて 別の方法で逃げてしまったバグをようやく解消。速度には大した影響ないですが。 一番の問題は、評価関数を持っていないので、MPCが使えない事。MPCのスレッショルド を広げながら置換表使って、moveorderを最適化していたので。他の方法で速度アップを 考えないといけない。逃げてを考えると、結局、NNなりなんなりで別の評価関数なり、次の １手ヒューリスティックが欲しくなります。もともとNN方面に行ったのは、そこが目的だった 事を思い出しました（汗 モンテカルロは、プレイアウトを疑っているので、い
ずれきちっとやり直してみます。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/670
671: 535 [sage] 2016/11/28(月) 22:46:28.36 ID:nf8GSvVi NN興味ありますねぇ。 Zenチームの人とかがわかりやすい解説本書いてくれないかなぁ。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/671
672: 535 [sage] 2016/12/02(金) 21:41:56.73 ID:Vv9WnV3F モンテカルロはやはりプレイアウトの質がカギか？ 軽くて良いヒューリスティックが欲しいところだ。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/672
673: 535 [sage] 2016/12/02(金) 22:02:53.36 ID:Vv9WnV3F モンテカルロは良い枝をカットしないこともかなり重要とみた。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/673
674: 310 [sage] 2016/12/04(日) 20:20:17.67 ID:E6FCgpFL うーん。モンテカルロはFFOなんかで残り２０手くらいから戦うと、結構まともな着手を するんだけど、１０〜３０手目付近がわざとじゃないかというくらい悪い手ばかり選択する。 残り１０手くらいまで行けば完璧。 序盤は次の１手が多すぎるのと、プレイアウトで回す回数が単純に多いので、ツリー部が なかなか深くならないし、あまり簡単に深くするとすぐにメモリーオーバーフローしちゃうし で難しい。 >>673 UCTではカットはしません。単純にプレイアウトの割り当ての順番が
なかなか回ってこなく なるだけです。良い手に優先的に割り当てさせるためには、やはりプレイアウトで良い手は 良いと、悪い手は悪いと評価できなきゃならんわけで。それが難しいからモンテカルロだと 言う矛盾。 まあ、オセロの場合は、伝家の宝刀評価関数があるので、プレイアウトを２０手くらいで 打ち切って、評価値を返すとか…MPCみたいな事をして無駄な着手を回避させるか… と、本末転倒な妄想をしてます（汗。良くなる点は、時間管理が易しくなるくらいかな（涙。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/674
675: 310 [sage] 2016/12/06(火) 00:37:18.95 ID:zUbz1knV モンテカルロが弱い理由を探ってます。 WZebraと対戦させると、一番顕著なのは、モンテカルロは辺に着手したがり、その結果 WZebraに内側に潜りこまれて選択肢が減っているという事です。流石に×とかCには 簡単には打ちませんが、序盤からあっさり中辺に出て行き、更にあっさり辺に打ちます。 相手もランダムに着手したとすると、辺の石は１方向からしか返せない（内側は４方向） ので、プレイアウトでは残りやすくなると言う仮説を立ててみました。つまり全部で２８石 ある辺の攻防が相
対的に下手くそになるため、プレイアウトの結果が楽観的になりすぎ ているのではないかと言う事です。 残り２０手切ってくると、ツリー展開できているので、min-Max的に攻防できるけど、それ より前の段階ではプレイアウトで、相手のミスを咎めるような手を打たないといけないと 言う事かなと思います。 これをどう次の１手の確率分布に表現するかですね。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/675
676: 310 [sage] 2016/12/11(日) 01:06:32.29 ID:8cq3+Gjk なんか袋小路に入ってます（汗 プレイアウトの改良は速度低下との戦いになり、効果が出ません。 結局、とにかく無駄をそぎ落とし、単純化してプレイアウト回数を稼いで、なおかつ ツリー展開の閾値を下げて、ツリーに頼る形になりました。 が、ここでメモリーパンクとの戦いが始まります（涙 中盤の分岐が多い局面だと、あっという間にツリー部で８ギガくらい使ってしまいます。 更に処理を単純化してメモリー使用量削減に走る事に。 結局、４０手目以後なら使えるけど、それ以前ではあま
り精度が期待できないという、 当初やりたかった、少しマシな序盤・中盤探索という目論見は崩れてしまいました。 評価関数があるんだったらαβの方がマシという当たり前の結論に傾きつつあります（汗 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/676
677: 310 [sage] 2016/12/11(日) 23:57:52.07 ID:8cq3+Gjk たった一晩で楽観してきました。 今までsoftmaxで確率分布を変えていましたが、あまり大きな差はついていないようだった ので、この際、思いっきり割り切ってみました。１位に７０％、２位に２５％、残り５％で他の 手に均等割り。イメージとしては１σ、２σ、その他って感じです。ヒューリスティックは αβのmoveorderのものを使用。 もちろんzebraにはぼろ負けですが、今までと違うのは、相手を囲んで着手可能位置を 減らしてしまう事が無くなりました。ちょっとした手ごたえを感じて
います。これをスタート に、ヒューリスティックに終盤変化を組み込んだり、序盤は開放度にしてみたりして検証 しようかと思っています。プレイアウトの精度があがったら、無駄にツリー展開しなくて 済むので、メモリーにも優しくなれるかも。 また、敗勢での発狂モードや、勝勢での手抜きモードの原因は、勝敗が明らかになり、 手毎の勝率の差がなくなる事が原因です。プレイアウト回数が多いからか、評価値は かなりデジタルに変化するので、２５％、７５％などを境目に、石差評価に変更すると、 ある程度回避できるんじゃないかと思います。 http
://mevius.5ch.net/test/read.cgi/gamedev/1057763418/677
678: 310 [sage] 2016/12/19(月) 00:57:35.60 ID:V27xPT8O 地味に色々改良。素UCTに色々追加してます。 ・uctの終盤にsolverを組み込んだ ・手の割り振りに全手均等な部分を作って読み抜けの可能性を減らした の２点が主な追加点です 当初想定していたより結構強くなったと思います。 AI黒番３０秒探索。zebra思考中にもMAX３０秒探索で、zebraに対しては２０石強負け くらい。序盤１回間違えて、中盤ジワジワ差が広がって、４０手前後で読み切りできず に間違う感じ。序盤は定石で回避できると思いますが、中盤の間違いは２番手の手を 選んでしま
います。修正は難しい感じ。終盤はチューニングか、探索時間延長で対応 できないか検討。 テストで作った２０手目で黒＋１２（zebra評価値）程度の盤面からは、zebraが間違える のか、終盤に入るところまで、かなり押してまして、読み切りミスで２２石差→１６石差と ぬるい手を打ちましたが、勝ち切る事ができるようになりました。 ここから先は、レーティングが欲しいなぁ。 オセロでAI使用OKなところないですかね？ http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/678
679: 310 [sage] 2016/12/22(木) 01:29:32.37 ID:4YVdXlZ1 地味に色々改良した結果、あらかたボツにしてます（汗 発狂モード対策でスコア最大化を図ろうとしていましたが、極端なスコアが悪さしている ようなので、結局勝率のみに限定しました。この時点で終盤はsolver任せに方針転換。 で、勝敗のみにした事で、solverの探索範囲を+-1のシングルウィンドウにできて スピードアップしたのでプレイアウトのラスト７手くらいでも使用する事にしました。 プレイアウトでは、moveorder順の下位はバッサリカットしました。酷い手が混入する とスコアが散
らかるので。 uctのif分ネストがスパゲッティ化したので、処理順を大幅に見直したら、時々落ちるように なってしまった。並列化が原因かそれともshared_ptrの使い方が悪いのか、散々調べた 結果、ちゃんと全体をリビルドすれば回避できる事が判明。俺の時間を返せorz テストで使用している引分手順３０手目から開始すると、たいていは負けてしまうけど、 希にzebraが認識していない勝利手順を見つけて勝つようになった。乱数の具合なので 再現性は低いけど、zebraの評価値にも間違いがある事を実感した。 ここのところ３０手目〜４０手目をタ
ーゲットに改善していたけど、それなりに成果が出た。 ４０手目以後はsolverを使用し、対局開始は定石DBを２０手分くらい用意したら、まあまあ なAIになるかなぁと思い始めました。ただ、１手３０秒考えるのは長すぎるなぁ。 あと、正しい手順を見つけ勝率も上回って来ているのに、探索時間が足りずにプレイアウト 回数で負けて最善手が選ばれないケースが散見されます。ものの本だと、そういう時は 探索時間を延長するとか書かれていますので、対応してみようかと思っています。 というわけで、なんか行けそうな気がしてきた。 http://mevius.5ch.
net/test/read.cgi/gamedev/1057763418/679
680: 310 [sage] 2016/12/27(火) 01:58:53.16 ID:lSRXuhfg uctの探索部分がある程度できたので、とりあえずDOS窓ベースでゲームとして成り立つ ようにしました。edax-pvbook_2009.wtbから作った４０手分の定石DBをつけて、終盤探索 は４０手目からsolverで。multi probe cutできないので、FFO#40で１．３秒程度の性能です。 その他諸々。探索時間延長とか。タイマーを作り直してプログレスバーつけたり。 WZebraの２０手読み、定石DB変化大相手に、まれに勝ちます。直接対決はまだして ませんが、以前自分が作ったmin-Max版よりちょっと弱いくらいか
なという感触です。 モンテカルロは乱数がらみで、ナチュラルに変化しちゃうので、５〜１０手に１回程度は ミスをしちゃう感じです。 プレイアウトはもう少し詰められそうだけど、まあこの辺が潮時かなぁ。 次は何しようかな。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/680
ﾒﾓ帳
(0/65535文字)
上
下
前
次
1-
新
書
関
写
板
覧
索
設
栞
歴
あと 322 ﾚｽあります
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.018s