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

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

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

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
完全ソルバから定石パクるの意外とめんどくさいな。
クローラーみたいにして自動でパクれるようにしようかな。
でも迷惑かかるかな？

626: 535 2016/10/18(火)23:07 ID:5rT5zFZw(2/2) AAS
なんか本末転倒だからやめとくかｗ

627: 310 2016/10/19(水)02:53 ID:YWnebdEb(1) AAS
まさかの場所にバグ発見。
プレイアウトでランダムに１手選ぶところがバグってました。
良く動いていたものだと思う反面、MCTSってそういう所がある事も薄々感じてます。

が、状況はほぼ変わらず。初手真ん中と、５手目真ん中。この２か所が鬼門。

まだバグがあるのかも知れない。やっぱり自分が一番信用できないですね。

DAG問題対策でノードの合流を実装しました。枝とノードを分離して、ノードをハッシュ
にして、ノードの下に次の枝をぶら下げました。同時に、ハッシュキーに細工して、
左右同形も合流させてます。あまり変化はない気が。
速度低下が酷いです。

628: 310 2016/10/20(木)00:37 ID:yz39woaL(1) AAS
５手目真ん中以後どうなるのか１秒探索検証。６手目２列目に対しては、勝利（全て
最善着手）。６手目１列目に対しては、５列目着手で引き分け進行に入り、引分終了。
この時の手順では、全箇所が最善手という盤面ばかり通っていくように感じています。
つまり、MCTS的に勝利期待値が最大になりやすい手です。という事で、まあ、そんな
に間違った手は打っていないかなと。

また、プレイアウトを繰り返して手がどう変遷するのか見ていくと、最善手である真ん中
は、ある一定数からほとんど選択されなくなっています。結果、その手で枝の分岐が起き
ない事から、いつまでたっても評価が更新されず正解に戻らないと推測できます。

そこで、試行回数に圧倒的な差ができても、下位の手も一定回数は試行されるように
できないかと、手の選択基準をucb1の大きい順から、ソフトマックス関数を通して確率
分布に変えて、乱数で選択してみました。

結果は・・・。expの計算がある事からか、速度が激減。PVに割り当てられる試行回数は
2/3程度になり、その時点の最悪手でもそれなりに試行されるようになりましたが、それ
でも手の選択は微妙な感じです。この程度の効果なら、他のパラメータいじった方が
速度低下も無く良かったかも（汗

というわけで、本日のトライアルも失敗。
気が進まなかったけど、やっぱりucb1計算の検算をしてみます。
あと、部分的にmin-Maxを適用するとか。

629: 310 2016/10/23(日)09:58 ID:qEEwIK82(1) AAS
UCB1の計算は合ってました。
プログラムがC++的に美しくない事が気になりだし始めて、全部書き直ししてました。
書いた端から美しくないのが気になりだしましたが（笑）

UCTで後方枝刈というか、小枝の勝敗が確定していたら、ツリーを縮小していく処理を
追加。一本道問題が多少緩和するかと期待。対戦はちゃんと動いているっぽい。
デバッグ情報をファイル出力する処理書いて確認。
間違え方はあまり変わっていないのが残念というか、安心というか（汗

モンテカルロで１手目から最善手順が確実にわかったら、それはそれでゲームが
簡単すぎるって事になっちゃうので、大きく間違えないんなら、それで仕方ないかな。
というわけで、COM１手目は真ん中に固定。

プレイアウト部を高速化できる気がしていますが、やってみないとわかりません。
プレイアウトの末端部分に完全読みを数段入れるのも良いかと思っています。
DAG問題対応と左右対称チェックを入れて毎秒２０万プレイアウトくらい。

評価値の算出方法でちょっと悩み中。

そこそこ落ち着いたらオセロの中盤探索に応用してみます。

630: 310 2016/10/26(水)20:47 ID:H5ji3apJ(1) AAS
また美しくない病が出て、書き直したところ、びっくりするほど弱くなってしまった。
しばらくデバッグで悩みそうです。

631: 535 2016/10/26(水)20:59 ID:+YpzcPTO(1) AAS
Connect 4は一旦休止して別のゲームのＡＩ書いてます。
マイナーゲームですが囲連星というゲームで囲碁と五目並べを混ぜたようなゲームです。
簡単に言うと、七目並べれば勝ち、囲った石は取れるというルールです。

ついさっき黒番で公式ＡＩのLV0に１勝できました。
(;SZ[19]
;B[jj];W[kj];B[jl];W[ji];B[ik];W[km];B[kk];W[ki]
;B[ii];W[lj];B[ll];W[mm];B[hh];W[gg];B[im];W[ih]
;B[ig];W[jh];B[ij];W[in];B[lk];W[gi];B[hk];W[gk]
;B[mk];W[nk];B[hn];W[hl];B[jn];W[io];B[lm];W[jo]
;B[go];W[fp];B[gh];W[hi];B[fg];W[ko];B[gf];W[ln]
;B[hg];W[jg];B[ff];W[gj];B[gg])

囲連星AIはこちらで配布されてます。
外部ﾘﾝｸ[html]:www.vector.co.jp

632: 535 2016/10/27(木)22:26 ID:CgNWWTgQ(1/3) AAS
LV2からも黒番で一本取りました。
キセキが起きたｗ

(;SZ[19]
;B[jj];W[ik];B[ji];W[hj];B[jh];W[jk];B[kk];W[jl]
;B[gi];W[il];B[ll];W[hm];B[ii];W[hh];B[hi];W[ki]
;B[mm];W[nn];B[li];W[in];B[kh];W[fi];B[mi];W[io]
;B[kj];W[lj];B[ki])

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

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

ぬこの手ぬこTOP 0.034s