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

[過去ﾛｸﾞ] 【オセロ,将棋】ボードゲーム【囲碁,War】 (1002ﾚｽ)
上下前次 1-新

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索歴削→次ｽﾚ栞削→次ｽﾚ過去ﾛｸﾞﾒﾆｭｰ

596: 2016/10/05(水)22:05 ID:KcSrUkxH(4/5) AAS
まあ、こんな過疎スレでわざわざ嘘をついて騙るひともいない気もしますが…

597: 2016/10/05(水)22:31 ID:KcSrUkxH(5/5) AAS
>>590の書き込み時間からすると学校や職場から書き込んだ可能性もありますね。
とすると>>590のIDでは今は書きこめないかもしれませんね。

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

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

599: 535 2016/10/06(木)21:04 ID:/7+JrWaw(1) AAS
>>598
ん〜そうですか。
それは失礼しました。

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

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

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

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

601: 310 2016/10/08(土)22:22 ID:wBSLMo4h(1) AAS
あ、MTCSじゃねー。MCTSだ。

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

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

602: 535 2016/10/10(月)19:51 ID:WonRpXhk(1/4) AAS
なんかモチベーションあがらんなぁ
三連休まるまるさぼってしまった。

603: 2016/10/10(月)22:22 ID:WonRpXhk(2/4) AAS
将棋電王戦あったみたいですね。

604: 2016/10/10(月)22:38 ID:WonRpXhk(3/4) AAS
優勝はポナンザか。
一発勝負のトーナメントなのに強え。

605: 2016/10/10(月)23:10 ID:WonRpXhk(4/4) AAS
ん？
一発勝負じゃないのか？

606: 310 2016/10/13(木)11:06 ID:f6Nd8WJL(1) AAS
ここ数日、気分転換でConnect4やってました。

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

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

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

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

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

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

607: 2016/10/13(木)21:15 ID:XMNeJMFS(1/2) AAS
310氏もConnect 4 参戦か〜

608: 535 2016/10/13(木)21:53 ID:XMNeJMFS(2/2) AAS
名前書き忘れた。

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

609(1): 310 2016/10/15(土)13:58 ID:iZ3eY/zy(1/2) AAS
NPS低下問題はやはりハッシュ衝突のようで、ちょこっと直したら解消しました。

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

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

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

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

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

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

611: 310 2016/10/15(土)21:29 ID:iZ3eY/zy(2/2) AAS
MCTS（UCT）多分できました。STL様様です。
探索時間１秒で４０万プレイアウト。

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

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

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

612: 535 2016/10/15(土)21:54 ID:jn3cHMWR(2/4) AAS
秒速40万プレイアウト！？すげぇぇぇぇ
1プレイアウト=1手てことですか？
1プレイアウト=1局てことですか？

613: 535 2016/10/15(土)22:17 ID:jn3cHMWR(3/4) AAS
460氏もオセロで10000Knps〜15000Knpsとか言ってるし、まじか〜
やっぱ本気でやってる人達は違うのかな…

614: 535 2016/10/15(土)23:46 ID:jn3cHMWR(4/4) AAS
NPSは２０メガって書いてありますね…
すいません。

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

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

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

616: 310 2016/10/16(日)13:25 ID:KTdXBWLt(2/4) AAS
mobility周りにバグがあって直したところ、１秒読みでPerfect Solverに先手で勝ちました。
昨夜は１２０秒読みでも同じ手順で負けていました。
とはいえ、乱数が絡むので引き分ける事もあります。

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

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

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

617: 535 2016/10/16(日)16:43 ID:Ts0NTtMt(1/2) AAS
一秒読みで完全ソルバに勝とかまじか〜
やっぱ積み上げてきた基礎力が違うんだろうな〜

618: 310 2016/10/16(日)17:19 ID:KTdXBWLt(3/4) AAS
どもです。評価値問題は治りました。

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

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

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

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

620: 310 2016/10/16(日)22:45 ID:KTdXBWLt(4/4) AAS
なんか、デバッグ報告みたいな状況になってすみません。

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

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

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

621: 535 2016/10/17(月)22:03 ID:B9d5KHtX(1) AAS
connect 4序盤ブック作ってみようかな。
完全ソルバ丸パクリでｗ

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

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

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

623: 2016/10/18(火)17:50 ID:7idTlLLA(1) AAS
読めば読むほど弱くなるとは不思議
ucbの計算間違えてるとかでは？

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

625: 535 2016/10/18(火)22:30 ID:5rT5zFZw(1/2) AAS
完全ソルバから定石パクるの意外とめんどくさいな。
クローラーみたいにして自動でパクれるようにしようかな。
でも迷惑かかるかな？

上下前次 1-新書関写板覧索設栞歴

あと 377 ﾚｽあります
ｽﾚ情報赤ﾚｽ抽出画像ﾚｽ抽出歴の未読ｽﾚ

ぬこの手ぬこTOP 0.015s