多くの将棋ソフトで256手ルールの実装がバグっている件

256手ルールというのは、電王トーナメントなどで採用されていた、256手に達したら引き分けというルールである。強いプレイヤー同士の対局では平均手数が伸びる傾向にあるようで、最近ではコンピュータ将棋の対局でも入玉模様の将棋の割合が増えてきたため、WCSC29では320手、電竜戦では512手に変更されている。以下では規定の手数になれば引き分けとなるルールのことを「256手ルール」と書く。

256手ルールについて簡単におさらいしておこう。初手(76歩とか)が1手目である。そして256手指された時点で引き分け…と言いたいが、256手目で詰まされるパターンがある。そこで、「257手目の手番が巡ってくる」(実際には257手目の局面はサーバー側からは送られてこない)時点で引き分けが成立するという解釈である。

ただ、以前、電王トーナメントでは何故か257手目の局面がサーバー側から送られてきていて、おやおや?となったことはある。

まあ、電王トーナメントの256手ルールは良くない256手ルールであったと思う。

とりあえず、現在は、256手ルールと言えば、257手目の局面はサーバー側からは送られてこない。引き分けになるためには257手目の手番が巡ってくる必要はある、という解釈。

それで、やねうら王など多くの将棋ソフトでは、この引き分けルールを次のように実装してある。

やねうら王の通常探索部の場合

game_ply()は、現在の手数。(初期局面で1を返すので、257手目(を指す前)の局面はgame_ply()は257である)
Limits.max_game_plyは256手ルールでは256が設定されている。

つまり、ある局面について調べる時に257手目の局面ならば、引き分けのスコアを返している。

この処理は一見正しいように見える。

しかし、ここで一つ問題があって、256手目で詰まされていてはならないという条件がある。(引き分けになるためには257手目の手番が巡ってこないといけない。)

詰まされているかのチェックは、上のソースコードの時点までにやっていない。詰まされているかどうかのチェックはわりとコストがかかるので、このあと各種枝刈りをしたのちに、指し手生成をして、その指し手を一つずつ試していくループがあり、そのループを一つも合法手を指せずに抜けた時に初めて詰まされているという扱いをしている。(探索部は、そういう風に書いてあるのが普通である。)

なので、上の257手に到達しているかのチェックを行った時点では、詰んでいる可能性もある。この場合は引き分けではない。負けである。引き分けのスコアを返すのはおかしい。どう見てもバグである。

しかしながら、上にも書いたように詰まされているかのチェックをやるコストは馬鹿にならないので、256手ルールの正確な実装のためだけに、詰まされているかのチェックを行うわけにはいかない。おそらく他の将棋ソフトも同様になっているものが多いであろう。256手ルールには、わりとこのような地雷を多く抱えている。

私は先日、詰将棋ルーチンで引き分けの手数に達した時の処理を考えている時に上のようなケースがあることに気づいた。これに気づくのに5年も要したわけである。ついでに言うと、この件について、いままで誰からも指摘がなかった。やねうら王は、GitHubで90もforkされているというのに、である。

ただ、やねうら王では、探索の時に新規ノード(新規局面)では、1手詰めの詰め将棋ルーチンは必ず呼び出しているので、256手目で1手詰めルーチンで詰ませられない時だけ257目の局面の探索をすることになる。1手詰めルーチンが、必ずあらゆる一手詰めを解けるのであれば、256手目で詰むなら257手目の局面について探索することはないので、上の処理でも問題とならない。

ところが、やねうら王の1手詰めルーチンはあらゆる1手詰めを解けるわけではない。離し飛車で合駒を持っていなくて詰むケースや、両王手・開き王手が絡むケースは解けない。これは詰みのチェックに時間がかかるため、あえてそうしている。近接王手による詰みのチェックだけを行っているのである。

そこで、256手目の局面で離し飛車で合駒を持っていなくて詰むケースで、詰むと判定できずに、指し手生成したあとの1手ずつを試すループで飛車を打つ指し手を選択して257手目の局面に突入した時に、これを引き分けとして扱ってしまうわけである。つまり、255手目が自分の手番であった場合に、ある指し手のあと、256手目で実際には離し飛車で詰むのに257手目に突入するから引き分けと錯覚するわけである。

まあ、レアケースだし、歩の不成で詰むケース同様、これをきちんと対処すると(探索速度が低下して)勝率が落ちるのだから仕方があるまい。

冒頭でも書いたように256手ルールは、WCSC29では320手、電竜戦では512手になったので、この手数直前で詰まされるケースは非常に稀である。(双方、入玉しているだろうし…)

なので、現実的には問題とならないと思うが、気になる大会参加者は、320手ルールならば、エンジンオプションのMaxMovesToDraw(この手数で引き分け)を320ではなく322ぐらいに設定することで、やねうら王を322手ルール(323手目で引き分け成立)と思わせ、320手目付近での頓死を防ぐことはできる。こう設定するのが私のお勧めである。

畢竟人間とは、いかに高遠な理想を掲げようともこのような単純なコードすらもバグなしに書けない生き物なのである。 ← 私も含まれる。(私も)人間だもの。うらを。

2021/01/13 13:00追記

やねうら王、ふかうら王のこのバグ自体は修正した。dlshogiにも同様のバグがあったので山岡さんに報告しておいた。

ただ、やねうら王の場合、置換表が絡むと、256手ルールが絡んで決まった引き分けのスコアを256手以前の局面で信じてしまい、引き分けだと錯覚するパターンはありうるので、やはり256手ルールならMaxMovesToDrawは258ぐらいに設定するのがお勧めである。

2021/01/14 0:30追記

電竜戦の実行委員長のカツ丼将棋さんより。

「wcscのことはよくわかりませんが、電竜戦では、512手目の詰みは引き分け、512手目の宣言は宣言側の勝ちとなります。なので先手と後手の詰みの機会が不平等ではありますが、512手目近傍では詰みよりも宣言できるかどうかがメインテーマとなっているのと、宣言の機会は平等なんで許してちょんまげというわけです。」

多くの将棋ソフトで256手ルールの実装がバグっている件」への17件のフィードバック

  1. 手数制限入れなくても最後まで全力を尽くしてくれればいいんじゃないかなぁと思ってます。それでアレがそういう具合になったわけです。
    時間制御では考慮した方がいいかとは思ってます。

  2. 24時間営業なのに、24:00という表記ができないために0:00〜23:59と書かないといけなくなって、それじゃ23時間59分営業じゃないかと突っ込まれるようなアレと似たような感じですか?w

  3. WCSCの大会ルールと、floodgateサーバで判定されるルールでも最大手数の扱いは多少異なったように思います。具体的にどう異なったかのSlack上での議論のログが流れてしまっていて今は確認できませんが…

  4. 素人臭い質問で申し訳ありませんが
    例えば
    https://shogipic.jp/v/ivx
    のような局面を243手目で迎えることがどっかのタイミングで確定した場合、ソフト的には「引き分けだー!」
    って判定するものなのでしょうか。

    • 19飛に後手は歩の連打で256手超えが確定するということですね。ソフトがそこまで読み切れば引き分けのスコアが返ってきますね。

      • 返信ありがとうございます。
        図の局面って詰将棋の本とかだと1手詰めって言われちゃうと思うんですけど合駒利かずってどういう判定なのかなぁと思ったのと、すみません。
        仮に先手玉が詰めろじゃなければ
        ▲19飛△18歩▲同飛△17歩に▲13歩と打って
        必死掛けて
        「手数内に勝っちゃうじゃん!」
        とかまで読むようにするの難しそうだぁとか
        思った次第です。

        • > 合駒利かずってどういう判定

          無駄合いの処理はしてないです。(してる将棋ソフトはないと思われます。詰将棋用のソフトであれば柿木将棋がやってたと思いますが)

          > 仮に先手玉が詰めろじゃなければ

          先手が詰めろでなければやねうら王はこの変化を読むと思いますよ。

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です