[過去ﾛｸﾞ] 【オセロ,将棋】ボードゲーム【囲碁,War】 (1002ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
589(1): 460 2016/10/05(水)00:36 ID:JvSO0BT6(1/2) AAS
>>588
結果ですが、ぼこぼこにされましたｗ
ヒューリスティックだとやはり限界ありますね〜
590(3): 460 2016/10/05(水)11:21 ID:WWXbBFqc(1) AAS
オセロは大体やることはやったので、そろそろ将棋か囲碁に着手してみようかと思っています。
ルールの実装が楽なのは囲碁なのかな…
自身が囲碁を打ったことがないのでルールから調べないとですがw
591(1): 310 2016/10/05(水)12:08 ID:Iif/OHnc(1) AAS
やっぱ囲碁行きたいですよね。
昔調べた感じでは、日本ルールと中国ルールで勝敗の判定が微妙に違って、日本
ルールだと曖昧なところがあるので、AI開発は中国ルールでしているみたいです。
ルールの実装は着手禁止点が少なくて拍子抜けするくらいですが、その先が・・・
色々と一筋縄ではいかないようです。
オセロの評価関数ですが、AutoEncoderの限界を感じ、DCNNの実装を始めていますが、
バックプロパゲーションがスパゲッティでわけわからん状態になっています。しばらくは
紙と鉛筆で考える必要がありそうです。DCNNがある程度できたら、僕も囲碁に行って
みようかな。
その前にConnect4に脱線してみたい気も（汗
592(1): 535 2016/10/05(水)19:29 ID:KcSrUkxH(1/5) AAS
>>589 >>590
ん。ＩＤが違いますね。
>>589は偽物ですかね?
593: 535 2016/10/05(水)19:48 ID:KcSrUkxH(2/5) AAS
>>591
囲碁は終局判定させるのも結構難しいみたいですね。
セキの判定とか。
Connect 4は易しすぎず難しすぎずいい塩梅のゲームだと思います。
完全解析も狙えますしｗ
594: 460 2016/10/05(水)21:34 ID:JvSO0BT6(2/2) AAS
>>592
同一ですよ！
スマホから書き込んだのでID変わってしまいました
595: 535 2016/10/05(水)21:53 ID:KcSrUkxH(3/5) AAS
ん〜そっちのＩＤ使って同一って言われても。
>>590のIDで書き込みお願いします。
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も理論的には探索回数を∞にすると、最善手を必ず導き出す事は保証されて
いるらしいのですが、中途半端な回数の時は保証されていないんですよね。
上下前次1-新書関写板覧索設栞歴
あと 384 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ
ぬこの手 ぬこTOP 0.013s