2018年12月16日

ボードゲームの数学

下はオープンソースの自作プログラムです。よければ遊んでみてください。 リバーシ: https://www.openprocessing.org/sketch/513394 チェッカー: https://www.openprocessing.org/sketch/637050
5
サンセット @Sunset_Yuhi

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

2018-12-15 23:02:18
サンセット @Sunset_Yuhi

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

2018-12-15 23:15:52
サンセット @Sunset_Yuhi

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

2018-12-15 23:22:37
サンセット @Sunset_Yuhi

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

2018-12-15 23:34:41
サンセット @Sunset_Yuhi

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

2018-12-15 23:46:35
サンセット @Sunset_Yuhi

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

2018-12-16 00:51:21
サンセット @Sunset_Yuhi

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

2018-12-16 13:22:18
サンセット @Sunset_Yuhi

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

2018-12-16 13:33:49
サンセット @Sunset_Yuhi

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

2018-12-16 14:06:29
サンセット @Sunset_Yuhi

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

2018-12-16 14:19:21
サンセット @Sunset_Yuhi

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

2018-12-16 16:17:58
サンセット @Sunset_Yuhi

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

2018-12-16 20:27:25
サンセット @Sunset_Yuhi

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

2018-12-16 20:52:56
サンセット @Sunset_Yuhi

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

2018-12-20 01:04:33

コメント

奥山犛牛 @bogyu 2018年12月16日
囲碁で眼を自分の石で埋めるのは禁止されているので「一番の問題」ではないはず。問題は三劫や長生だが、中国ルールでは将棋の千日手と同じように同型反復となる手を禁じているそうだ。
1