ボードゲームプログラム開発の記録（2014〜）

サンセット @Sunset_Yuhi

@DraughtsPlyrJpn ボードゲームのプログラムには割とテクニックがあって、自分の場合は黒キングを-2、黒ポーンを-1、空きマスを0、白ポーンを1、白キングを2で表現しています。そうすると8×8の表で局面を数値化することができます。

サンセット @Sunset_Yuhi

チェッカープログラムへのαβ探索組み込み、オセロで作ったやつを移植できたからもっと早くできたはずなんだけど、やる気が出ず実行するのに1年近くかかってしまった。しかも、少し忙しい時に現実逃避のように。テスト週間前に漫画とかが読みたくなるアレだ。

サンセット @Sunset_Yuhi

将棋に慣れてると、チェスのメイトの形が分かりづらすぎるな。移動範囲が広い駒が多いし、ポーンも前方2マスに効きがあるので、キングの周囲8マスがスカスカでもメイトになりやすい。頭金みたいにベタベタ駒を貼り付けて勝つことばかり考えてると、1手メイトすら見えない。

サンセット @Sunset_Yuhi

【入門リバーシ】ken1shogi.sakura.ne.jp/bbs/board_rev?… 自作プログラムでLv13を倒した

サンセット @Sunset_Yuhi

自作オセロプログラム、最初は1手読みしかできなくて作者より弱かったし、人と戦わせてもいい勝負だったけど、探索を入れて色々調整した最近は、打つ所無くして隅を取り、場合によっては全滅させたりするので、対戦させるのが申し訳なくなって秘密の存在になってしまった

サンセット @Sunset_Yuhi

チェスの駒は足が長いから、プロでもこういうことが起きやすいのかな。 twitter.com/tucc_chess/sta…

東京大学チェスサークル(TUCC) @tucc_chess

【解説】 白がKf4?? と指すと、黒のQb8#で一手メイトが決まります。互角の盤面から、唯一の一手メイトが決まる手筋を指してしまう、というのはGMでもやってしまうことなので、気を落とさずにいきましょう。 Beliavsky vs Johannessen(2002)より pic.twitter.com/2I0QuHu7Sm

2018-02-06 21:23:20

サンセット @Sunset_Yuhi

探索プログラムでは普通、1手読むごとに探索深さを1減らすけど、強制飛びや連続飛びの時だけ探査深さを減らさないようにしたら、局所的に長めに読んで評価値が安定した。下手に評価関数を追加するより、探索部を工夫した方がよさそう。これはワンチャン、オセロより作りこむのが簡単かもしれない。

サンセット @Sunset_Yuhi

やっぱ評価関数もちゃんと作らんとダメだ、チェッカーむずい

サンセット @Sunset_Yuhi

自作オセロプログラムで、終盤用の石数を完全読み切りするαβ探索には、Move Orderingが効かないと勝手に思い込んでたけど、やってみたらめっちゃ有効だった。13手読み切りの手数を伸ばして15手くらいでも余裕。これは惜しいことをしてた。多分チェッカーでも使えるな。

サンセット @Sunset_Yuhi

チェッカーで終盤の探索プログラムとかどう発動すればええねんと思ってたけど、両者とも駒数が3枚以下になったら終盤の探索プログラム発動、とかでイケそうな気がした。駒数や合法手数でMove Orderingしたαβ探索を使い、強制飛びや連続飛びになったら探索深さを減らさずに読み切るイメージ。

サンセット @Sunset_Yuhi

6手読みしてる現状だと、2vs1とかになっても隅での攻防には不十分で、隅から駒を追い出して仕留める所まで読めないことが多い。駒が3枚あると1局面の合法手数の平均は約10手だと思うけど、10手読みくらいならできると予想。

サンセット @Sunset_Yuhi

チェッカープログラムをある程度作ったら、チェスプログラムにさっさと移行したいけど、道のりは長い。機械学習までやる気はないけど、遺伝的アルゴリズムやディープラーニング自体の勉強は、そのうちやりたい願望はある。

サンセット @Sunset_Yuhi

Move Orderingしてもほとんど速度変わらんかむしろ悪くなってる説。オセロなら1手読みでも開放度で大体当たるけど、チェッカーは探索しないと好手か分かりづらいということか。でも終盤読み切りなら短期的な駒数変化の影響が大きいと思うので、上手く枝刈りされるはず。

サンセット @Sunset_Yuhi

そう言えば、Qiitaとかでニューラルネットを使ったオセロAIをたまに見るけど、自分でも勝ててしまうくらいのものしか見たことないな。ゲーム木の枝が比較的少ないから、モンテカルロ木探索よりαβ探索の方が効果的ということなのか。 twitter.com/ken1shogi/stat…

Ken1 @ken1shogi

AlphaGo Zeroの方式でリバーシを作っているプロジェクトを定期的にチェックしてる。スマホアプリ(リバーシLv99)と対戦した結果を載せてるんだけど中々苦戦しているみたいだ。 github.com/mokemokechicke…

2018-03-14 02:48:53

サンセット @Sunset_Yuhi

将棋AIで学ぶディープラーニング 山岡 忠夫 amazon.co.jp/dp/4839965412/… @amazonJP ついにこんな本が出た。隔世の感があるな……

サンセット @Sunset_Yuhi

駒数差の評価方法を少し変えただけで、めっちゃ強くなったかもしれん。単に差を取るだけだと「3対2」と「2対1」の局面に違いが出ないので、指数関数を使って「3対2」より「2対1」の局面を大差と評価するようにした。結果、1駒でも差が出れば、互いに1駒ずつ消費していく手を積極的に指すようになった。

馬場七尾 @DraughtsPlyrJpn

@Sunset_Yuhi それは、理にかなってるかもしれません。不利な方はなるべくコマ交換をしないまま、複雑な形に持ち込もうとしますので。ただ、あまり数を減らすと（例えば、２ｖｓ１だと）引分に持ち込まれる確率がたかくなる感じがしています。

馬場七尾 @DraughtsPlyrJpn

@Sunset_Yuhi このあたりは、私ではうまく説明できないです。「５ｖｓ４くらいにしといて、自分の４コマで中央に防御ラインを引き、相手の４コマと相対させる。そうしておいて、残った１コマを後方で動かしていると、相手は動かすコマがなくて自滅せざるをえない。」っていうのが割と勝ちやすいかも

馬場七尾 @DraughtsPlyrJpn

@Sunset_Yuhi ３ｖｓ２とか２ｖｓ１とかになると、うまくオポジッションで相手の進路を妨害できないと、通り過ぎてキングを作り合う展開になって、引分になりやすい印象を持っています。あくまで、そんなに強くないプレーヤーの感覚ですが

サンセット @Sunset_Yuhi

@DraughtsPlyrJpn 少し考えなおして、駒数の平方根で比べることにしました。白の駒数をnw、黒の駒数をnbとすると、√nw-√nbを評価値として使うイメージです。ひとまずそれで3vs2<2vs1<4vs2みたいな評価をさせることにします。 自滅する局面については、探索を使わずに判断できればいいですがパッと思いつきません……

サンセット @Sunset_Yuhi

@DraughtsPlyrJpn オポジッションとかもよく分からなくて申し訳ないのですが、2vs1になったら基本的に、1駒の方が打ち取られるものだと思っていました。1vs1に持ち込めれば引き分けにしやすいと思いますが。

サンセット @Sunset_Yuhi

【入門リバーシ】ken1shogi.sakura.ne.jp/bbs/board_rev?… 50手辺りの時点では負けてたけど、入門リバーシはLv13でも完全読み切りはしないようで、自作プログラムが逆転勝ちできた。

サンセット @Sunset_Yuhi

チェスや将棋のモンテカルロ木探索でプレイアウトとかどうやるねんと思ってたけど、噂によると何百手かで上限を設けてそこで打ち切ってるらしい。単純だけどなるほどという感じ。

サンセット @Sunset_Yuhi

チェッカープログラムの知見を活かして、オセロプログラムでも合法手が少ない場合に探索深さを伸ばすようにした。序盤や終盤など、差が付きそうな局面で探索を打ち切らず、ポカが減ることを期待。

サンセット @Sunset_Yuhi

軽い気持ちで探索延長すると組み合わせ爆発にすぐ行き当たるので怖い。あとプログラミングで、ド・モルガンの法則が初めて役に立ったぜ。