20手引き分け人力探索の過程

こんにちは。べるです。
今回は20手引き分け手順のひとつを人力探索で発見した試行錯誤の過程を書こうと思います。

本日(2024/7/29)オセロの最短引き分け手順が20手であることが証明されました。

【オセロ最短引き分け】

オセロで最短の引き分けは20手だと証明できました！(多分)
20手引き分けは4通り(終局結果は2通り)だけでした！(棋譜はリプへ)

近々詳しく記事に書いて投稿します！ pic.twitter.com/4f4Mwi34XJ

— 山名琢翔(にゃにゃん) (@takuto_yamana) July 29, 2024

2通りある終局図の1つは私が発見していた手順で到達できるものでした。

人力探索の記録はたぶん私の20手引き分けです。より短い手順が発見されるか、これが最短であることが示されるか、誰かやってくれたらと思っていましたがついに…！わくわくします。
棋譜F5F4C3F6G7F7F3H7F8B2H6E3A1E7F2F1H8E2D7C5 https://t.co/5LhJV44v45 pic.twitter.com/RwDZM2O7tE

— bellchan (@bellchan99) July 25, 2024

この手順の発見には長い時間がかかっているのですが、その概要を記録します。
時はさかのぼり2019年5月。
対局で暴走牛を打たれました。棋譜検討で隅周りを調べていたときに、これはひょっとしたらたくさん空きマスを残して終局できるのでは？と思いました。そこで試しにあれこれと並べていくと…

44手引き分け

棋譜
F5F6F7G7H7H8C4C3C2B2D3E7F8C1B3B4A5B5C5D2H6H5D8G5G6G8H4H3A4E8E1E2E3G4A1A2A3C8B1D7D1F4E6D6

44手で終局できました。
ここで考えたのは、両方の隅周りを確定するだけならまだまだ石を省けそうだということでした。
そして省けそうな石にアタリをつけ、いろいろ並べてみると…

40手引き分け

棋譜
C4C3C2B2F5F6F7G7D3F8B3G5A1B1H5E6E7A2E3E2C5B5H7H8C1E8B4H6D8G8D2G6A3C8D7C7A5G4E1H4

4手短縮できました。
しかし、まだまだ省けそうです。
ここからはしばらくトントンと手数が短くなっていきます。

34手引き分け

棋譜
F5F6E6D6G7H8C4F4F7C3C2B2D7B4B3D8D3A2A5A4A3G8G6C1G4D2E1D1B1H4A1H7B5E2

32手引き分け

棋譜
F5F6E6D6G7H8C4F4G6C3G4B3B4D3C2H4B2H7D7B1F7A2C1A3A1D1D2G8A4D8B5E1

32手時点で省ける石がなくなり、これで終わりかと思いました。しばらくして、対角の隅をとるのではなく片方が中央に固まる構想にすればさらに短くできるのでは？と思いつきました。

24手引き分け

棋譜F5D6C4G5G6D3G4H7C5B5C2B1G7H5A5G3G2H3E3C6E2G8C7G1

22手引き分け

棋譜F5D6C7F4G3D7D3H2E7D8C4F7G7D2D1B8B7G5H5B6E3H7

斜めの固定にCラインを利用する構想では２２手引き分けが限界でした。途中、11-12で終局する手順はありましたが、引き分けにはなりませんでした。

11-12終局

それからしばらくして、対角線を利用するのが最後の可能性か？となりました。
そして試行錯誤の末誕生したのが…

20手引き分け

棋譜
F5F4C3F6G7F7F3H7F8B2H6E3A1E7F2F1H8E2D7C5

20手引き分けでした。これ以上短い手順が存在するのか？は疑問でしたが、ついにこれが最短であることが証明されました。

私はこの引き分け手順を探す過程で確定石についてたくさんの学びを得ました。空きマスを残して終局するためには盤上の石がすべて確定石になる必要があるからです。競技とは離れた遊び方ですが、このような試行錯誤はオセロの理解が深まる可能性があると思いました。

おわり