オセロが解決される、双方が最善手を打った場合最終局面は引き分けになることが明らかに
2023年10月30日に「オセロが解決された」というタイトルの論文が世界最大のプレプリント(査読前論文)サーバーarXivに投稿されました。論文によると、双方が最善手を打った場合の最終局面は引き分けになると述べられています。
[2310.19387] Othello is Solved
https://arxiv.org/abs/2310.19387
オセロは約10の58乗通りの棋譜数と10の28乗通りの局面数をもつボードゲームで、1997年時点で人類よりも強いAIが誕生していましたが、完全な解析は行われておらず、双方が最善手を打った場合に先手必勝・後手必勝・引き分けのどれになるのかが分かっていませんでした。
ただし、オセロ日本代表選手の佐谷哲が2019年に「『オセロは最善進行で引き分け』という説が今後覆ることはほぼ無いだろう」と述べるなど、プレイヤーの間ではオセロは最善進行で引き分けになる可能性が高いと予想されていました。
今回の論文ではアルファ・ベータ法を用いて計算対象とする局面の数を減らしたり、アルファ・ベータ法で効率よく計算対象の局面数を減らすための「move ordering」というテクニックを使用したり、最初の10手の進行について既存のプレイヤーの知識を元にあらかじめ評価値を与えたりすることで計算量を減らし、オセロを「解決」することに成功したとのこと。
こうしたゲームの解析において、解決には「弱解決」と「強解決」という2つの解決の種類があります。「弱解決」は初手から双方が最善手を打った場合にゲームの最終局面がどうなるのかが解明されることで、一方「強解決」はゲームの全ての局面においてその局面から双方が最善手を打つとどうなるのかが解明される事を意味しています。
今回の論文は「弱解決」を扱っており、自分は常に最善手を打つという前提で計算が進められています。相手の手については悪手も計算対象に入っており、先手・後手それぞれで計算を進めたところどちらの手番で始めても「勝つか引き分けになる」という計算結果になりました。従って、双方が最善手を打つと最終局面は引き分けになることが明らかになったというわけです。
今回の論文で使用されたコードはGitHub上で公開されているほか、論文には最善進行の棋譜の一つが例として下記の通り掲載されています。こうした棋譜は棋譜再生用のサイトやアプリに入力することで再生できるので、興味がある人は確認してみてください。
f5d6c3d3c4f4f6f3e6e7d7c5b6d8c6c7d2b5a5a6a7g5e3b4c8g6g4c2e8d1f7e2g3h4f1e1f2g1b1f8g8b3h3b2h5b7a3a4a1a2c1h2h1g2b8a8g7h8h7h6
0 件のコメント:
コメントを投稿