自動無限ジャンケンカードゲーム問題
どうも、108Hassiumです。
突然ですが、私が昔思い付いた「自動無限ジャンケンカードゲーム問題」という問題群を紹介します。
無限ジャンケンカードゲーム
無限ジャンケンカードゲームは、ジャンケンの手(以下、G、C、P)が描かれたカードを用いて行う対戦ゲームです。
各プレイヤーは有限枚のカードを手札として持ち、手札以外にはカードの種類ごとに∞枚のカードが山札として用意されます。
ゲームの各ターンにおいてプレイヤーは同時に1枚のカードを出し合い、出したカードの手による勝敗によって以下のような行動をとります。
あいこの場合：各プレイヤーは自分が出したカードを手札に戻し、続いてそのカードに負けるカードを山札から引いて手札に加える。
あいこではない場合：勝ったプレイヤーは自分が出したカードを捨て、相手が出したカードを手札に加える。
さらに、これを用いて「自動無限ジャンケンカードゲーム」を以下のように定義します。
プレイヤーは二人。
各プレイヤーの手札は一列に並べられ、カードを出すときは列の先頭から取り、手札に加えるときは末尾に加える。
片方のプレイヤーの手札が無くなると終了。
自動無限ジャンケンカードゲームは、ライフゲームと同じように初期状態を決めるとルールに従って自動的に結果が決まる「0人ゲーム」の一種です。
例えばプレイヤーの手札がGPとCP(左が先頭)の場合、以下のようにゲームが進みます。
GP:CP
↓
PC:P
↓
CPG:PG
↓
PGP:G
↓
GPG:
右のプレイヤーの手札が無くなったので、これでゲーム終了です。
GP:CPの対局はすぐに終わりましたが、少ない初期手札でも終了までのターン数は非常に長くなることがあります。
例えばGG:GPという組み合わせでは約4000ターンに渡ってゲームが続き、手札の最大枚数は160枚を超えます。
なお、両方のプレイヤーの手札が全く同じ並びになった場合は、以下のように無限にゲームが続きます。
G：G
GC：GC
CGC：CGC
GCCP：GCCP
CCPGC：CCPGC
CPGCCP：CPGCCP
PGCCPCP：PGCCPCP
GCCPCPPG：GCCPCPPG
CCPCPPGGC：CCPCPPGGC
・・・
無限にあいこだけが続き、両プレイヤーの手札が増え続けていきます。
疑問
疑問1：ゲームが無限に続くケースって手札の並びが同じになるパターン以外にないの？
考えられるパターンとしては、
一定ターン数ごとに全く同じ手札の並びに戻る
あいこだけの繰り返しではないものの、何らかの意味での繰り返しが起きて手札が増え続ける
何の規則性もなく、カオス的な挙動で手札が増え続ける
・・・というものがあります。
5枚以下の初期手札から始まるゲームを全パターン調べたのですが、どのパターンも見つかりませんでした。
疑問2：「$${n}$$枚以下の初期手札から始まって有限ターンで終了するゲームの最大ターン数」の増加速度ってどのくらい？
「$${n}$$枚以下の(中略)最大ターン数」を$${f(n)}$$として、現在知られている値は以下の通りです。
$${f(1)=1}$$ (G:P)
$${f(2)=12895}$$ (GG:GC)
$${f(3)=37809}$$ (GGC:PGG)
$${f(4)=775206}$$ (GGGP:GCPG)
$${f(5)=15045171}$$ (GGCCG:GGGCP)
※初期状態を第0ターンとし、一方のプレイヤーの手札が無くなったターンを最終ターンとしてカウントしています。
この手の関数の最高到達点として、「計算不可能関数」というものがあります。
計算不可能関数とは文字通り「その関数の値を有限時間で必ず計算できるようなアルゴリズムが存在し得ないような関数」で、計算不可能関数の中にはいかなる計算可能関数よりも速く増加する関数もあります。
私は個人的に$${f(n)}$$は計算不可能関数なんじゃないかと予想しているのですが、この予想の真偽には疑問1も関わっています。
もし疑問1が真である、つまり両プレイヤーの手札の並びが一致する以外にゲームが終了しないケースが存在しない場合、手札が同じかどうかを毎ターンチェックしながらゲームを実行することで任意の初期手札によるゲームが終了するかを有限時間で判断でき、結果として$${f(n)}$$の値を有限時間で計算できてしまいます。
周期性のあるパターンも有限時間で非停止性を確認できてしまうため、$${f(n)}$$が計算不可能関数であるためには判定困難な非停止パターンが存在しなければならないことになります。
ちなみに、自動無限ジャンケンカードゲームに似ていて計算不可能関数と関係のある概念として「タグシステム」と「ルール110セル・オートマトン」というものがあります。
タグシステムは単純な計算模型(計算機を模した数学的概念)の一種で、文字列を端から読んで逆の端に文字列を付け足すという動作をするという点が似ています。
ルール110は、有限種類の記号(2種類)からなる文字列(1本)に対する固定の計算規則からなるシステムである点が似ています。
どちらのシステムもチューリング完全(あらゆる機械的計算ができる)であり、計算終了までの時間などを使って計算不可能関数を作ることができます。
疑問3：カードの種類を増やしたら疑問1・2の真偽ってどうなるの？
例えば、5種類の手を使うジャンケンとして以下のようなものが考えられます。
最下段の2つが新たに追加された手で、どの3つの手の組み合わせでも元からあるG・C・Pと同じような3すくみになっています。2023/07/18追記：よく見たら違いました。
あいこのときの処理の「そのカードに負けるカード」を「先程の図で反時計回りで隣にある手のカード」に書き換えて、「$${n}$$枚以下の初期手札から始まって有限ターンで終了するゲームの最大ターン数」(以下、$${f_5(n)}$$)を計算すると以下のようになりました。
$${f_5(1)=1}$$
$${f_5(2)=2296}$$
$${f_5(3)=4578}$$
$${f_5(4)=11431}$$
手が3種類のときと比べると、全体的に小さめの値になっています。
これはおそらく、手の数が増えたことによりあいこの発生確率が下がったためだと思われます。
$${k}$$が奇数のとき、$${k}$$種類の手を使うジャンケンは以下のように定義できます。(使用可能な手を$${0～k-1}$$の整数で表します)
手$${a}$$と手$${b}$$に対して$${a=b}$$が成り立てばあいこである。
手$${a}$$と手$${b}$$に対して$${a\neq b}$$かつ$${a-b+k}$$を$${k}$$で割った余りが奇数ならば$${a}$$の勝ち、偶数ならば$${b}$$の勝ちである。
これを基に、疑問2の7手バージョンを計算してみました。
$${f_7(1)=1}$$
$${f_7(2)=2150}$$
$${f_7(3)=4286}$$
$${f_7(4)=8613}$$
やはり、手の数を増やすと最大ターン数は減るようです。
ちなみに、2枚：2枚の最大ターン数の対局を図示すると以下のようになります。
疑問1については、5手でも7手でも4枚以下の初期手札では非自明な非停止パターンに辿り着くことはありませんでした。
一方、手の数を4種類にした場合は状況が違いました。
手の数が偶数の場合は上手く3すくみのルールを作れないので、以下のようなルールにしました。
$${a}$$と$${b}$$を2で割った余りが等しければあいこである。
あいこでない場合、$${a-b+4}$$を4で割った余りが1なら$${a}$$の勝ち、3なら$${b}$$の勝ち。
このルールだとあいこになる確率が3手のじゃんけんより高いからか、カオス的な挙動でカードが増え続けるケースが存在します。
最後に
「手の数を増やしたときのルールの別パターン」や「プレイヤー数を増やしたときの挙動」など、気になる問題はたくさんあるのですがキリがないのでこの辺で終わりたいと思います。
それでは、さようなら。
・・・さすがに残っている話題が多いので、多分いつか続きを書くことになると思います。
追記(2023/11/10)
Twitterで@ackvyさんから「非自明なループを発見した」との報告をいただきました。
「GGC:CPCPGPGCGCPCPGPGC」という手札でゲームを進めると、
GGC:CPCPGPGCGCPCPGPGC
↓
GCC:PCPGPGCGCPCPGPGC
↓
CC:CPGPGCGCPCPGPGCG
↓
CCP:PGPGCGCPCPGPGCGCP
↓
CPP:GPGCGCPCPGPGCGCP
↓
PP:PGCGCPCPGPGCGCPC
↓
PPG:GCGCPCPGPGCGCPCPG
↓
PGG:CGCPCPGPGCGCPCPG
↓
GG:GCPCPGPGCGCPCPGP
↓
GGC:CPCPGPGCGCPCPGPGC
・・・と、9ターンで元の手札の組み合わせに戻って無限にゲームが続くようです。