ボードゲームの数学

サンセット @Sunset_Yuhi

二人・零和・有限・確定・完全情報と言われるボードゲームは色々あるけど、厳密に考えだすと分類はかなり細かくなる。 よく言われるのは、リバーシ（オセロ）、チェッカー（ドラフツ）、連珠（五目並べ）、チェス、将棋、囲碁、とかだけど。

サンセット @Sunset_Yuhi

二人（プレーヤーが二人）、零和（両プレーヤーの利得の合計がゼロ）、確定（着手以外に偶然の要素が入り込まない）、完全情報（各プレーヤーが他プレーヤーの状況を常に把握できる）辺りはどれも共通だけど、「有限」の部分を考えると割と違いがあると思う。

サンセット @Sunset_Yuhi

リバーシと連珠は、ただ有限なだけでなくて、最大手数も分かる。どちらも盤面を石で埋めていって、取られて無くなる訳ではないので。 リバーシは8×8マスで、最初に石が4つ置かれてるので、60手以内で必ず終わる。連珠は15×15マスなので、225手以内で必ず終わる。

サンセット @Sunset_Yuhi

チェッカーやチェスや将棋では、何も考えずにやると同じ局面を繰り返してしまう。なので同形反復を禁止するルールがないと（千日手など）、無限に着手できてしまう。 ゲームによっては、プレーヤーの指摘や提案によって引き分けが成立するそうだけど、ルールが少し曖昧だと思う。

サンセット @Sunset_Yuhi

一番の問題は石を取れる囲碁で、ちゃんと二眼を作ったりしないとゲームが無限に続いてしまう。コンピュータでランダムに着手して（ランダムプレーヤー）、眼を自分の石で埋めたりすると、自滅してまともに終局しない。 囲碁はコウの話とかも面倒だけど、パスも駆使しないと終局できない特殊なゲーム。

サンセット @Sunset_Yuhi

そんな訳で、囲碁は厳密には有限ではないように思える。個人的には、現状のルールはやや欠陥だと感じる。 そう言えば将棋でも、「最後の審判」という詰将棋で、「連続王手の千日手でしか王手を外せない局面は詰みなのか」という面倒な問題が…… ja.wikipedia.org/wiki/%E6%9C%80…

サンセット @Sunset_Yuhi

6×6オセロでは、1993年にイギリスのJ. Feinsteinに完全解析して、黒16白20で後手勝ちが分かってるけど、8×8オセロがどうかは実はまだ分かっていない。 調べたら2015年に、Feinsteinの結果を追試してる人がいた。 縮小盤オセロにおける完全解析 ipsj-kyushu.jp/page/ronbun/hi…

サンセット @Sunset_Yuhi

8×8オセロの完全解析も、頑張ればできそうな気はしてしまう。 ただ、4×4オセロは最終局面数が218、計算時間が0.001秒なのに対して、6×6オセロは最終局面数が約8844億、計算時間が5日12時間16分とある。 組み合わせ爆発の犠牲になった数え上げおねえさんを思い出す。

サンセット @Sunset_Yuhi

Checkers Is Solved science.sciencemag.org/content/317/58… CiNii 論文 -  チェッカー解明秘話 ci.nii.ac.jp/naid/110006530… #CiNii チェッカーでは2007年に、カッコいい論文がScienceから出て、最善手を指し続けると、双方引き分けになることが分かった。意外だけどこの研究には、日本人も絡んでいる。

サンセット @Sunset_Yuhi

チェッカーは日本ではマイナーだけど、元々引き分けになりやすいゲームなので、結果はある程度予想されてたと思う。 「Checkers Is Solved」と聞いた時、最善手順も分かったのかと思ったけど、どうも終盤データベースを作ることで「解いた」ということらしい。調べると、結構泥臭いこともやっている。

サンセット @Sunset_Yuhi

とにかく、チェッカーは一応解かれたことになっているので、リバーシ（オセロ）よりチェッカーの方が簡単、と世間的には思われてるかもしれない。でも話はそう単純ではない。 リバーシや連珠では起きないけど、チェッカーとかで起きるものにGHI問題がある。所々でゲーム木がループしてるのが原因。

サンセット @Sunset_Yuhi

非力ながら自作したチェッカープログラムでも、チェッカーが同形反復でゲーム木がループする影響で、同じ局面を繰り返さないようにする工夫をいくつかした。リバーシはそんなこと気にしなくていいんだけど。 openprocessing.org/sketch/513394 openprocessing.org/sketch/637050

サンセット @Sunset_Yuhi

HEXは先手必勝である - フィボナッチ・フリーク fibonacci-freak.hatenablog.com/entry/2017/08/… 他に面白いと思うのはヘックス。これは具体的な必勝手順は分からないのに、背理法によって先手必勝が分かっているらしい。 厳密な証明は読んだことないけど、証明したのはゲーム考案者でもある数学者ナッシュ。流石です。

サンセット @Sunset_Yuhi

「どうぶつしょうぎ」の完全解析　tanaka.ecc.u-tokyo.ac.jp/ktanaka/dobuts… そう言えば有名な話かもしれんけど、どうぶつしょうぎは完全解析されている。終局図から後退解析して5時間半で計算が終わったと書いてるけど、ちゃんと理解しようと思うと自分には難しい……。