チェスアプリのバグを見つけてしまいました

　チェス入門というサイトのステイルメイトの問題集をチェスアプリで解いてみると８問中１問間違えてしまいました。ステイルメイトの問題集はあまり見かけないので、十分なテストをしてなかったのが原因です。マンカラアプリもそうですが（詰めマンカラ問題集なんて聞いたことがありません）、問題集が手に入らないのである程度のところでテストを打ち切ってリリースしていたのですが、実際に解けない問題を見つけてしまった以上、対処することにしました。

PINが絡む問題に問題がある

　解けなかったのはチェス入門サイトの問題７で、以下の局面です。

　正解手は以下のようにQueenをc4に移動するQc4+です。先手（白）劣勢ですが「王手クイーン取り」を掛けてステイルメイト（引き分け）に持ち込むという問題です。

でも、初期盤面からチェスアプリに指させてみると、以下のようにQxd5と黒のクイーンを取ります。

　クィーンは取れるのですが次に後手（黒）がルークをa1に移動（Ra1）して合い駒効かずでチェックメイトされて先手（白）が負けます。

正解手が指せないからといってバグとは限らないのですが、この問題の場合は３手の読みでステイルメイトに気付いて５手読めばRa1からの負けに気付くので、候補手を絞っている可能性があるので一概には言えませんが５手読めば正解できるはずです。
　では、手動で先手（白）がQc4+と指した局面でチェスアプリに指させてみると

相手のクィーンを取って（Qxc4）ステイルメイトと判定してゲーム終了となるのでこれも問題ありません。
　しかし、手動で先手（白）がQc4+と指した局面から後手（黒）も手動でQxc4と指すと以下のようになります。

　これはイケマセン。ステイルメイトなのに「後手の勝ちです」と判定してしまってます。これは明らかなバグです。
どうやらチェスでPINと呼ばれる状態の時にSTALEMATEの判定を間違うようです。 このステイルメイトの問題７のミソは他の問題とは違って、単に「王手クィーン取り」を掛けてステイルメイトに持ち込むだけではなく、PIN状態に持ち込むところです。初手はQd4+でもQe4+でもダメで、Qc4+でなければならないのです。

将棋ではPINは大した問題ではない

　上の図の終局の局面は将棋でも珍しくない形だと思います。将棋なら先手（白）は指す手が無くて投了するしか無い局面です。もし将棋初心者が指す手に困ってPINされているe2の駒（ポーン）を前に動かしたとしても、後手（黒）がクィーンでf1の玉（キング）を取れば済む話です（以前の記事参照）。その場合、将棋でも王手放置は反則と規定されているので正確に言えば先手（白）の反則負けと言うべきですが、いずれにしても後手（黒）の勝ちは揺るぎません。でも将棋と違ってチェスの場合は劣勢だった先手が引き分け（ステイルメイト）に持ち込んだことになります。将棋なら先手（白）負けなのにチェスだと引き分けになります。
　PINに対応する将棋用語は何かよく分かりませんが、「串刺しにされてる」とか「角の効きに入ってる」とかの表現はありますが、ピッタリした用語が無いのが将棋というゲームがPINをそれほど重要視していないことの証拠にもなるでしょう。
　将棋アプリを開発する立場で見てもPINなんて全然気にしていませんでした。チェスのソフトや昔からある将棋ソフトがPINをチェックするアルゴリズムを使っているのは知ってましたが、それはStockfish由来のアルゴリズムを流用して作っていたからであって、自分のように一からアルゴリズムも考えて開発するのなら関係のない話だと思っていたし実際に作ることも出来ました。でも、今回のチェスアプリのバグの修正に取り掛かってみて想像以上に面倒臭い作業を強いられて、チェスのステイルメイト（特にPIN絡み）に対応するためには将棋とは別のやり方（別のデータ構造と別のアルゴリズム）で作る方がスマートに出来るのだろうということが想像できました。何がそんなに面倒くさいかと言うと長くなるので省略しますが、チェス盤のマス目を一つ一つ移動しながらPINのチェックをするのはかなり無理があるのです。
　将棋ソフト開発関連の本などをチラ見すると「データ構造にPIN用のフラグを持たせる」とか「合法手を列挙する」とか言う表現をよく見かけますが、自分の将棋関連アプリ（３三将棋、５五将棋、７七将棋）はデータ構造にPIN用のものはありませんし、「合法手を列挙する」作業も一切していませんが困ることは何もありませんでした。人間が実際に駒を動かすイメージで一つ一つの駒を８方向に動かす作業を想定したアルゴリズムになっていて、普通はそうしたやり方を採用するだろうと思われる極普通のやり方（アルゴリズム）です。「合法手を列挙する」と聞いて、昔から「何でそんなやり方してるのかなぁ？」と不思議に思ってました。もしかして、Stockfishを作った人は、最初私のようなやり方でチェスアプリを作り始めてステイルメイトの実装に掛かった時に「こりゃダメだ！」「こんなことやってられない！」と感じて新しいやり方（データ構造とアルゴリズム）を捻り出したんじゃないでしょうか？私の勝手な想像ではありますが、今回のバグ修正に取り組んでStockfishを作った人の気持ちが分かったような気がしました。
　今回のバグ修正はPINが絡むステイルメイトに関わる部分だけが下膨れした感じになっていて、幸いそういうケースはあまりないので全体の処理が重くなったということはありません。

ステイルメイトは最善手なのか？

　上に挙げたチェス入門サイトの問題７はPINの問題以外にも興味深い変化を含んでいます。上記のバグをなんとか無理がある方法で修正して過去のテストも全部通過してデグレード（リグレッション）が無いところまでなんとか辿り着いて、問題７も含めてすべての問題に正解することも確認しました。
　そして、試しに先程の先手がQc4+と指した下の正解局面から

修正済みのチェスアプリに後手を指させてみると

なんと、先手のクィーンを取らずにQe4と指して王手（チェック）を回避しました。修正する前はちゃんと先手のクィーンを取っていたので、修正前より悪化してるような気もがしますがそうではなく、正しくステイルメイトの局面だと判断できるようになって、後手（アプリ）が「優勢なのにステイルメイトなんかにしてたまるか！」とクィーンを犠牲にしてキングが逃げる手を選んだわけです。その後先手は当然後手のクィーンを取って（Qxe4+）以下Kg5、Qa8となり後手のキングは大海に逃げ出すことは出来ますが、駒をボロボロ取られて十数手後に結局先手が勝ちます。結局そうなるのなら「ステイルメイトで妥協しておくべきだったんじゃないの？」と言いたくなりますが、自分のチェスアプリは深く読めていない（３〜５手）こともあってこうなります。
　このステイルメイトを無理やり避ける現象は以前の記事で書いたステイルメイトの局面をどのように評価するか（ステイルメイトの局面に掛ける係数-0.7をどのように決めるか問題）とも関わってくるのですが、自らステイルメイト（引き分け）を受け入れて確定させるより、少しでも勝つ可能性がある手を選ぶ方が最善手と言えなくもないような気もします。
　それにしても詰めチェス（チェス・プロブレム）の中には問題の趣旨以外の有効な着手が存在するもの、将棋で言えば余詰めがある詰将棋のような感じの問題が多いですね。それとも自分がチェス初心者だからそう感じるだけで、ベテランチェスプレイヤーなら上記の局面でステイルメイト（Qxc4）以外は考えられないって感じでしょうか？身近にチェスに詳しい人がいないのでよく分かりません。
　以前の記事に書きましたが、そもそもステイルメイトの局面評価値に係数を掛けようと思ったのは、ステイルメイトの評価値を引き分けなのだからという理由で0にすると以下の局面で先手がBf6という手を選んだからです。

　先手はビショップとナイトを持っていて後手はルークだけで形勢は先手有利のはずなのに先手から進んでステイルメイト（引き分け）にするのはおかしいだろうと考えたのが事の発端です。この局面の後、指し手を進めても後手玉は捕まらないからステイルメイトにするのが最善手なのでしょうか？自分は優勢なのに自ら進んでステイルメイトにするのはおかしいと考えたので、形勢が有利な時はステイルメイトの評価値にマイナスの値を掛けてやや反転？する仕様にした（Kf7の手を指します）のですが、もしBf6（ステイルメイト）が最善手というのがチェスプレイヤーの共通認識であるのならステイルメイト局面の評価値は0のままでいいかもしれません。でも、上の局面で先手のポーンが一つでもb5辺りに残っていれば敢えてステイルメイトにする人はいないと思います。そのような局面とも比較するためにもステイルメイトの局面に掛ける係数は必要だと思います。
　あと、念の為もう一度書いておきますが、チェスアプリは「チェス入門サイトのステイルメイトの問題は全問正解します」、正解するけどその後の指し手が問題の趣旨通りには進まないと言うことです。

他にも見えてきた問題

　上記の問題７の正解手の後の後手の一手（Qe4）はあまりにも無理してステイルメイトを避けているような気もしたので、試しにステイルメイトの局面の評価値に掛けている係数（-0.7）を変更したら、後手（アプリ）はQxc4と着手してステイルメイトを選ぶことを確認しました。そして、将棋とは違って局面の評価値に使っている最大値や最小値が悪影響を与えてることが見えてきました（あくまでも私が作った評価関数についての話です）。
　チェスアプリでは局面を評価する際の先手勝ちの局面の評価値を50000、後手勝ちの局面の評価値を-50000にしているのですが、駒の重みはこの記事のようになっていて、クィーンが90、ルークが50…という感じで相手の駒を全部取っても50000なんていう大きな数値にはなりません。この先手勝ち局面（50000）と後手勝ち局面（-50000）のような大きな値にマイナスの係数（-0.7）を掛けても、自分の思惑通りには比較出来ていなかったようです。
　それでも問題７以外は正解出来ていたのは、問題７のような紛れがなく明快な手しか無かったのでステイルメイトの局面を勝ちあるいは負けとほぼ同等の評価をしていたからでした。問題７のように紛れがある問題だと、負けるぐらいなら他の手を選ぼうとAIが考えてステイルメイトを避けたということです。ということで、問題７で正解後の後手の一手をQe4ではなくQxc4を選ぶように調整した結果、ステイルメイトの局面に掛ける係数を-0.0009にしました。これで勝敗の決着がつく大きな値（50000や-50000）と、形勢判断時の評価値（駒の重みや駒の働きの合計値）との比較が出来ているようです。ちなみに係数を-0.001にすると元通りQe4と指してステイルメイトを避けます。

  === intro07-2
    --- problem -7-2

8|♜| | | | | | | |
7| | | | | | | | |
6| | | | | | | | |
5| | | |♛| | | |♟|
4| | |♕| | | | |♚|
3| | | | | | |♟| |
2| | | | |♙|♟|♙| |
1| | | | | |♔| | |
  a b c d e f g h

      ✔ expects stalemate -7-2 (686ms)
♕
8|♜| | | | | | | |
7| | | | | | | | |
6| | | | | | | | |
5| | | | | | | |♟|
4| | |♛| | | | |♚|
3| | | | | | |♟| |
2| | | | |♙|♟|♙| |
1| | | | | |♔| | |
  a b c d e f g h

これでようやく問題７の正解後も問題の趣旨通りに後手がステイルメイトの手を選ぶようになりました。
　局面の最大値や最小値なんて閉じたアプリの中での相対的な評価値でしかないので何でもいいと思っていました。将棋アプリも先手の勝ちは50000、後手の勝ちは-50000を使っていますし、昔作ったオセロでもよくINT型のMAX値とMIN値を使っていました。でも将棋やオセロと違って勝ちと負け以外のステイルメイトという勝ちと負けの間にある局面を評価するには工夫する必要があるようです。このステイルメイトの局面に掛ける係数は、その意図は昔書いた記事（「チェスだけに必要な局面評価属性」）の通りですが、もし評価関数が完璧なものであるなら必要ないのだと思います。ステイルメイトは引き分けとして評価値0でいいと思うのですが、完璧な評価関数なんて有り得ないので必要になってくるものだと思います。
　それと一つのケースだけを見て-0.0009に決めてしまっていいのかと思うかも知れませんが、どのように決めるべきか分かってませんし最大値や最小値も駒の重みに関しても言ってみれば適当に決めた値なので、数は少ないですが過去のステイルメイトのテストケースも通過したことですし当面これで様子見ようと思います。
　今回、上記の点を弄って個人的にはスッキリしましたが、評価関数は少し変わっただけですし読みの深さも変わっていないので、ステイルメイトの判定が以前より正確になっただけで強くなったわけではないのが残念なところです。

アプリのアップデートについて

　今回の修正でもうバグは無くなったのでは？と思ってますが、将棋関連アプリに較べるとチェスアプリに関してはステイルメイトというルールのおかげで安心感が無いというのが本音です。何か問題を見つけた場合はメールかBoothサイトからご連絡下さい。
　取り敢えず、現在Boothで販売しているミニチェスアプリは近いうちに一度今回の修正を反映させてアップデートするつもりです。Amazon App Storeで公開しているチェスアプリに関してはいつ削除されるかも知れませんし、今後はAmazonでは更新しないつもりです。無料のお試し版として残しておきますが、今後はチェスアプリもBoothで販売する予定です。→Boothで最新版公開しました。