ゴドマチの詰め探索アルゴリズム - RK’s blog

ゴドマチの詰め探索をするプログラムを書きました。 結構頑張ったのと、個人的に面白かったので使ったアルゴリズムについて書いてみようと思います。 ゴドマチって？ 2人用の対戦型パズルゲームです。 ルールは考案された方のページでまとめられています。 単純なルールで気軽にできるゲームなので、やったことないという方は是非遊んでみてください。 j344.exblog.jp と、宣伝をしたところで本題へ。 ゴドマチは完全情報ゲームで引き分けがないので、あらゆる局面は先手勝ちか後手勝ちか、両者最善を尽くした場合の結果が決まっています。 そう言われるとどんな局面がどっち勝ちか知りたくなってきますよね？ ... 少なくとも僕はなりました。 それで5単位(ペントミノ)の全組合せ66通りと6単位(ヘキソミノ)の全組合せ595通りを手作業で解析したりしていたのですが*1、そんなことをするくらいならプログラムを書けば