たかが３×３の狭い空間でも完全読み切りは大変だ

　Twitterで９マス将棋発売というニュースが流れていたので、検索してみると同じ９マス（３×３）と言えどもいろいろなパターンがあるようです¹。Androidアプリで見つけた「３×３将棋」というのをやってみると玉頭戦を戦っている気分になれて、想像していた以上に楽しめました。他にも一番シンプルなものでは盤上には玉だけを配置して、持ち駒に銀と歩を持ったところからゲームを開始する「３三将棋」というルールもあるようです。

　以前の記事でShoesとRubyで作成した将棋プログラムの記事を書きましたが、この３三将棋のルールなら先手必勝あるいは後手必勝の手順が見つけられるかもと思い、ちょっとだけ試してみました。
　やり方は以前ちょっと変わった三目並べの記事で書いた方法と同じで、先読みの制限手数を指定して徐々にその先読み手数を伸ばしていくというやり方です。先読み手数を制限せずに勝負がつくまでという条件で先読みを続けたいところ（通常の三目並べならそれが可能）ですが、おそらく何年経ってもプログラムが終了しない状況になってしまうでしょう。MIN-MAX法（＋αβ法）で先読み手数を指定して、その手数に達するまでに先手勝ち（あるいは後手勝ち）の評価値を返してくれば、必勝手順があるという確認方法です。現れ得るすべての局面を読む（手数を制限せずに先読みする完全読み切り）ことをしなくていいので、必勝手順があるかどうかの結論を得るにはこの方法が一番簡単です。この時先読みに使用する評価関数は先手勝ち（最大値）、後手勝ち（最小値）、それ以外（０）の３値だけを返す評価関数を使います。局面が有利か不利かは関係ないので玉の硬さがどうとか「と金」の評価値がどうとかは計算する必要はありません。また、初型からの詰将棋を解くのとも少し違います、王手を続けなければいけないわけではありませんし、自玉が詰まされなくても指す手が無くて負けることもあるからです。どうやら３三将棋は王手が掛かってなくても指す手が無くなって負けるパターンが多いようです。
　で、結論から先に言うと、先手必勝なのか後手必勝なのか千日手になるのか結局はっきりした結論は得られませんでした。たかだか十数手の先読みしか試せなかったのでその手数内では必勝手順はないということです（詰み手順もありません）。たかが３×３の盤上の変化と言えども、将棋はオセロや囲碁と違って一手毎にマス目が埋まり徐々に終局が近づいていくゲームと違うのでマス目が少ないからと言ってもなかなか結論を出すのは難しそうです（オセロや囲碁なら簡単と言ってるわけではありません）。
　対戦の手順の一例を示すと以下の様な感じです。

　　

　最終局面は後手の指す手が無くなって、先手勝ちになってます。この例のように自分が試した多くの結果が先手か後手か一方が指す手が無くなって負けるパターンでした。一度形勢を損ねたら指す手が悪手しかなくなり更に形勢を悪くしていく感じです。
　また、自分が試したプログラムは千日手対応をしていないのですが、指定した先読み手数内に必勝手順があるなら千日手を避けてその手順を選ぶはずなので関係ありません。もっと深く読めば「先手必勝」あるいは「後手必勝」の結論が出る可能性がありますが、逆に「先手勝ち」あるいは「後手勝ち」の評価が得られたけど、実はもっと深く読めば「千日手」の結論に変わるということはあり得ないということです。この辺りの事情は以前の記事にも書いた通りですが、「お互いに最善手を選ぶと千日手になる」という結論を出すには、完全読み切りするしかないのかもしれません。自分としては以前の記事の時と同様に、試しにやってみて結論が出れば面白いなと思ってやってみただけなのでこれで良しとします。

思わぬ収穫が

　３三将棋の結論が出なかったのでわざわざこの記事を書く気はなかったのですが、いろいろプログラムを弄っている最中に以前書いた変則三目並べの記事²の「先手必勝」の結論が追認されるような発見があったので書いておこうという気になりました。どちらかというと自分にとってはこちらの話の方が本題です。「無限三目並べは先手必勝」というお話です。９マス将棋のタイトルに惹かれて訪問された方、すいません。
　この記事を書いた時は「ArrangeLine」というアプリを使っていたのですが、同様のアプリで「無限○×」、「無限三目並べ」というものがあることを知り、それぞれダウンロードして試してみました。やはり自分のソフトと対戦させてみるとアプリの設定を最強にしていても先手では自分のソフトが必ず勝ちますし、やはりこのゲーム（無限三目並べ）は先手必勝のゲームなんだなと思って遊んでいると、「無限三目並べ」というアプリではなんと以下のように先手の場合は初手に辺の位置（以前の記事の2,4,6,8の位置）を選択できないようになっていたのです。

　やはりこのゲーム（三手前に打った駒が消えるルールの三目並べ、無限三目並べ）は辺の位置に初手を打てば先手必勝ということでしょう。私は記事に書いたとおり、自作プログラムを弄っていてたまたま無限三目並べというゲームが先手必勝なのではないかという結論を得たのですが、どうやらテーブルゲーム業界（実際にあるかどうか知りません）では公然の秘密（ネタバレ防止目的？）として知られていたことなのかもしれません。私はこのゲームの作者を知りませんし、この分野の研究者（そんな人がいる？）の知り合いもいませんのでわかりませんが、既に誰かが結論を出してどこかに論文でも存在するのかもしれません。
　とにかく自分で行き着いた結論が間違ってなかったようなので嬉しくなってこの記事を書くことにしました。
　※その後自作のアプリもリリースしました→消える三目並べ

思うこと

　自作の将棋プログラムはRuby製（動的型付け）なので速度的に限界があるので、C++で一から３×３の将棋プログラム（いずれはスマホアプリ）を作ってみようかなどと考えてます³。でも将棋はルールを反映させるだけでも一苦労なんですよねぇ。オセロなら一から作りなおしても大した手間は掛からないのですが…。