こんにちは。学生スタッフのA.S.です。こちらは以前に書いた「解決済みゲーム」の番外編です。本編とはあまり関係がありませんので、別物として本編も是非読んでください。さて、こちらではいつも以上に私の趣味全開で数学の面白さを発信するために書かせていただいております。

本編ではオセロを主としたボードゲーム（厳密には二人零和有限確定完全情報ゲーム）について書きましたが、電子機器を用いたビデオゲームについて気になった方はいませんか？実はそういったゲームでも研究がされています。皆さんご存知のぷよぷよについては様々な条件下で最適化について研究されていますが、多くがNP困難以上と結論付けています。NP困難というのは、ある決まった時間で正誤判定可能な問題たちのことです。簡単に言えば、ぷよぷよにおける正しい攻略法を見つけるのは大変ということです。他にもスーパーマリオブラザーズ、テトリスなどについても証明されています。余談ですが、3Dのゲームに関する正確な研究を私は確認できませんでした。次元が変わると自由度が増えることもあり、多項式時間や多項式時間還元などが劇的に難しくなるのでしょう。

本編の補足として、解決済みゲームの解決には種類があるということについて書きます。具体的には、超弱解決、弱解決、強解決の三種類に分けられています。

• 超弱解決：最初の場面においてのみ結果が証明されたこと
  ※具体的な手は判明していないが、結果のみが数学的に示されている
• 弱解決：互いに最善手を打ち続けた結果が証明されたこと
• 全ての場面において結果が証明されたこと
  最善手以外を打っても結果が分かっている

私の印象としては、多くのボードゲームが弱解決までは進んでいますが、強解決へのハードルはとても高いようです。なお本編で紹介した”Othello is Solved”*1では弱解決と強解決の間に新たな指標として「"semi-strong solving"」(滝沢拓己 2023: 13)　を提案しています。準強解決といった意味合いで、常に最良の手を打つコンピュータが作成できることを基準にしているようです。強解決との違いは、相手が最善手以外を打った場面においても最善手を打てることにあります。コンピュータの技術が大きく発展した現代において新たな指標が生まれてもおかしくありませんね。

引用

*1 “Othello is Solved” https://arxiv.org/abs/2310.19387