k-takahashi's blog

個人雑記用

どうぶつしょうぎ

8月1日にちょこっと触れた「どうぶつしょうぎ」(http://d.hatena.ne.jp/k-takahashi/20090801/1249139183)だが、後手必勝であることが証明済みでした。

情報処理学会の、研究報告「ゲーム情報学(GI)」 Vol.2009-GI-022 に掲載されている「どうぶつしょうぎの完全解析」(田中哲朗)がその報告で、総局面数は約2億5千万、その半分以上が末端局面(ゲームの決着がついている局面)で、それをのぞくと約1億局面。
初期局面は後手必勝で、78手で勝てるそうだ。

メモリ16Gだと、全局面がオンメモリに展開可能なので、プログラミング自体は比較的容易らしい。