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

サンセット @Sunset_Yuhi

OpenProcessingから囲碁のプログラムを拾ってきて、最低限必要そうな要素だけ残したら200行くらいになってしまった。まだルール通りに指すには不十分と思うけど、意外と短いプログラムでいけるんだなあ。

サンセット @Sunset_Yuhi

合法手数で1手読みしかしないプログラムにすら負けるくらいにはチェス弱いので何とかしたい

サンセット @Sunset_Yuhi

ちげーわ、勝敗判定がついてないじゃないか。地とかどうやって数えりゃいいんだ……。ランダムに打ってもせめて、終局してくれないと困る。あとそれの関連で、二眼を作れてるかの判定も欲しい。二眼を作れればそれだけで、ランダムプレーヤーには勝てるんじゃないか？

サンセット @Sunset_Yuhi

囲碁のプログラム作るとしたら9路盤でいいな。19路盤は色々とツラすぎる。あとコミの設定をどうしたらいいのか分からない。モンテカルロ木探索を使うなら評価関数は要らんかもだけど、簡単な詰碁は解けるようになってほしい。

サンセット @Sunset_Yuhi

コウの着手禁止ルールがないとか、ちょっと不備があるプログラムっぽいことがだんだん分かってきたけど、正しい囲碁のルールがよく分からん所がある。自分の石で作った一眼の所に、相手が打って石を取れる場合、先に自分が打ってしまうのは自殺手と見なされ禁じ手らしい。

サンセット @Sunset_Yuhi

1998年公開、アシスト機能など付きつつ328KiBしかないのに案外強い、「ヲセロ道場」というソフトがあるのだが、自作オセロプログラムでやっと勝てた。序盤はまだこっちが不利っぽいけど、モヤモヤを一つ晴らせた。 pic.twitter.com/SudGgyQKVP

拡大

サンセット @Sunset_Yuhi

モンテカルロ木探索 (Monte Carlo Tree Seach) ライブラリ - nodchipのTopCoder日記 @nodchip topcoder.g.hatena.ne.jp/nodchip/201412… オセロで100回プレイアウトするのに必要な配列は、盤面[100][8][8]、試行回数[100]、勝数[100]、次局面へのindex[100]でいいのかな？　ルートに向かって勝率を更新するのが面倒。

nodchip@tanuki- @nodchip

@Sunset_Yuhi 実装方法にもよりますが、盤面[8][8]、試行回数[100×終局までの手数]、勝ち数[100×終局までの手数]、次局面へのindex[100×終局までの手数][合法手数]といった感じになると思います。

サンセット @Sunset_Yuhi

@nodchip 書かれたのはたぬきさんでしたか……！　C++や構造体もあまり理解しておらず恐縮ですが、各ノードの盤面[8][8]の情報は保存しておく必要がありませんか？　それで、100回試行する場合は盤面[100][8][8]の配列を用意すべきかと思ったのですが。

nodchip@tanuki- @nodchip

@Sunset_Yuhi ゲーム木の各エッジに指し手を保存しておけば、各ノードの盤面は探索開始盤面から一意に復元できます。各ノードごとに盤面を保持する必要はありません。あと、MCTSはゲーム木をたどるステップと、ゲーム木の末端ノードでプレイアウトするステップに別れているのですが、盤面の配列が使い回せます。

サンセット @Sunset_Yuhi

人工知能とかでいう「技術的特異点」って、「パラダイムシフト」みたいな曖昧さがあるな。 あと「人間を超える」の定義にしても、例えば将棋とかで言えば、プロ棋士じゃないと勝てないレベルのプログラムなら、割と人間越えてんじゃないかと感じるけど。

サンセット @Sunset_Yuhi

Course In Draughtsというドラフツの入門テキストを読んでたら、「連続飛びで盤の端に止まらない場合はキングになれない」とか書いてある～～ そこもチェッカーのプログラム書き直さんといかんやんけ～～ fmjd.org/promo/cid.php

サンセット @Sunset_Yuhi

@nodchip ありがとうございます。試行する時は毎回現局面から辿っていけばいいのですね。モンテカルロ木探索の説明は何度か見てるつもりでしたが、理解できてませんでした。 あと何度も申し訳ないのですが、試行回数などの配列長さに「終局までの手数」が関係するのはなぜでしょうか……

nodchip@tanuki- @nodchip

@Sunset_Yuhi あ…　一部間違えていました。試行回数[100]、勝ち数[100]、次局面へのindex[100][合法手数]でした…。失礼しました…。

サンセット @Sunset_Yuhi

@nodchip すみません、もう一点だけ質問させてください。未試行の手ならば展開するようにプログラミングすると、ずっと展開し続けていつまでもプレイアウトしてくれないと思うのですが、プレイアウトをし始める条件はどのように設定していますでしょうか。

サンセット @Sunset_Yuhi

将棋AIの進捗 その7(詰み探索の有効性) - TadaoYamaokaの日記 tadaoyamaoka.hatenablog.com/entry/2017/09/… 連続王手しか探索しないと詰みを見逃す可能性があると。詰将棋は連続王手必須だけど、チェスプロブレムだと連続チェック必須じゃないし、文化的な理由で詰み探索の実装をミスる可能性はあるのかも。

nodchip@tanuki- @nodchip

@Sunset_Yuhi 当該ソースコードでは、プレイアウトを始める条件を「未試行の手であること」にしています。

サンセット @Sunset_Yuhi

チェッカープログラムでtempiの評価を入れたら結構強くなった気がする。というのも、端を破ってキングを作ることとかを期待してたけど、相手の駒を取ってもtempiに差ができるので、tempiだけで駒の取り合いも考慮できてるらしい。何手か先を見ないといけないのが人間には難しそうだが。

サンセット @Sunset_Yuhi

1手読みで並び替えるなら何が効率いいかなあ。tempiとキングを作る手とペア数と駒の位置と合法手数を律儀に計算するのか。それよりも合法手数が少ない時に探索深さを延長する方が、終局まで読むようになって強くなりそうだけど。

サンセット @Sunset_Yuhi

チェッカープログラム、キングを作る手を高評価すると相手ポーンにブレークスルーされる手が増える気がするが、ブレークスルーしてる駒の判定が意外と難しい。

サンセット @Sunset_Yuhi

キングに機動力があるドラフツならともかく、チェッカーは駒数を最重視して局面を評価すればいいかと思ってたが、底辺の駒をあまり動かさないでキングを作り、キングを適当に遊ばせて相手の行き場所を無くして自滅させるのが、必勝パターンなのかな。駒数の評価は、駒数が減ってから長手数読みしたい。

馬場七尾 @DraughtsPlyrJpn

@Sunset_Yuhi こうできれば、勝ちパターンですね！チェッカーは詳しくないので、どうなれば優勢とか、詳しくないのですが。

サンセット @Sunset_Yuhi

@DraughtsPlyrJpn ドラフツの場合も、同じ考えで勝ちを狙うのは有効そうですか？　強いコンピュータなどにどういう傾向があるのか把握していないのですが。

サンセット @Sunset_Yuhi

ボードゲームでCOMと戦ったら強くなれることを考えると、恋愛で卒なく振舞うためにラブプラスをプレイするのは効果があるのではないか（名案）

馬場七尾 @DraughtsPlyrJpn

@Sunset_Yuhi 最奥を守りつつキングを作るのは、相手と力が競ってるときは、なかなかな難しいです。 相手がミスしてショットを決めさせてくれればキングを作れるのですが、そうでない場合 キングを作る=コマが前に進んでて、それが取られてない=単騎で前進すると相手に取られてしまうのでそれなりの援軍が必要