ヒキガエルとカエル
組み合わせゲーム「ヒキガエルとカエル」の例

組み合わせゲーム「ヒキガエルとカエル」は、リチャード・K・ガイによって考案されたパルチザンゲームです。この数学ゲームは、『数学的遊びで勝つ方法』という書籍の入門ゲームとして掲載されています。[ 1 ]

シンプルさとルールの簡潔さで知られる「ヒキガエルとカエル」は、組合せゲーム理論の主要な概念を説明するのに役立ちます。特に、ヒキガエルとカエルがそれぞれ1匹ずつしかいない単純なゲームであれば、開始位置のゲーム木を構築することで評価することは難しくありません。 [ 1 ]しかし、任意の位置を評価する一般的なケースはNP困難であることが知られています。いくつかの注目すべき位置の値については、未解決の予想がいくつか存在します。

ゲームの1人用パズルバージョンも検討されています。

ルール

ヒキガエルとカエルは、1× n の正方形の帯状のマスでプレイします 。各マスは常に空いているか、ヒキガエルまたはカエルが 1 匹ずつ配置されています。ゲームはどの配置から開始しても構いませんが、通常はヒキガエルが帯状のマスの左端の連続したマスを占め、カエルが右端の連続したマスを占めた状態から開始します。

左プレイヤーの番になった時、左プレイヤーはヒキガエルを1マス右の空きマスに移動させるか、ヒキガエルを2マス右のカエルを飛び越えて空きマスに移動させることができます。空きマス、ヒキガエル、または複数のマスを飛び越えることはできません。右プレイヤーにも同様のルールが適用されます。右プレイヤーは、ターン中にカエルを左の隣接する空きマスに移動させるか、カエルを1匹のヒキガエルを飛び越えてヒキガエルのすぐ左の空きマスに移動させることができます。組み合わせゲーム理論における通常のプレイルールでは、自分のターンで最初に移動できなくなったプレイヤーが負けとなります。

表記

ヒキガエルとカエルの配置は、3つの文字列（ヒキガエル、カエル、空白）で表すことができます。例えば、この文字列は4つの正方形の帯を表し、最初の正方形にヒキガエル、最後の正方形にカエルが配置されてい ます。T{\displaystyle T}F{\displaystyle F}◻{\displaystyle \square}T◻◻F{\displaystyle T\square\square F}

組合せゲーム理論では、あるポジションは、その選択肢、つまり左プレイヤーと右プレイヤーが移動可能なポジションを用いて再帰的に記述できる。左プレイヤーがあるポジションから、 、… のポジションへ、右プレイヤーがあるポジションから、、… のポジションへ移動できる場合、そのポジションは慣例的に次のように記述される。P{\displaystyle P}L1{\displaystyle L_{1}}L2{\displaystyle L_{2}}R1{\displaystyle R_{1}}R2{\displaystyle R_{2}}P{\displaystyle P}P＝{L1、L2、…|R1、R2、…}。{\displaystyle P=\{L_{1},L_{2},\dots |R_{1},R_{2},\dots \}.}

この表記では、たとえば、 となります。これは、Left はヒキガエルを 1 マス右に移動でき、Right はカエルを 1 マス左に移動できることを意味します。 T◻◻F＝{◻T◻F|T◻F◻}{\displaystyle T\square \square F=\{\square T\square F|T\square F\square \}}

ゲーム理論的価値

ヒキガエルとカエルに関する研究のほとんどは、特定のヒキガエルとカエルのポジションのゲーム理論的価値を決定すること、またはゲームで特定の価値が生じる可能性があるかどうかを判断することに重点が置かれてきました。

数学的プレイの勝利方法は、まず多数の可能な値を示しました。例えば：

T◻◻F＝0{\displaystyle T\square \square F=0}
TF◻◻＝1{\displaystyle TF\square \square =1}
T◻F◻＝12{\displaystyle T\square F\square ={\frac {1}{2}}}
TFT◻F＝{0|0}＝⋆{\displaystyle TFT\square F=\{0|0\}=\star }
T◻TFF＝{0|⋆}=↑{\displaystyle T\square TFF=\{0|\star \}=\uparrow }

1996年、ジェフ・エリクソンは、任意の二項有理数q（有限ゲームで出現しうる唯一の数）に対して、値qを持つヒキガエルとカエルの局面が存在することを証明した。彼はまた、 のようないくつかの注目すべき局面に対する明示的な公式を発見し、他の局面の値とゲームの困難性に関する6つの予想を定式化した。[ 2 ]T1つの◻bF{\displaystyle T^{a}\square ^{b}F}

これらの予想はさらなる研究の推進力となった。ジェシー・ハルは2000年に予想6を証明した[ 3 ]。これは、任意のヒキガエルとカエルの位置の値を決定することはNP困難であることを示す。ドロン・ツァイルバーガーとトサポーン・エーク・タナティパノンダは2008年に予想1、2、3を証明し、予想4の反例を発見した[ 4 ]。最後の未解決の予想5は、(3, 2)を除くすべての(a, b)に対して、 が無限小値であることを示す。T1つの◻bF1つの{\displaystyle T^{a}\square ^{b}F^{a}}

シングルプレイヤーパズル

シングルプレイヤーのヒキガエルとカエルの問題の解決タイムライン。各両生類の1、2、3。縦軸は時間を表します。

ヒキガエルとカエルのゲームは、早く終わる可能性があります。1883年にエドゥアール・リュカによって出版された、一人用パズル版のヒキガエルとカエルのゲームでは、標準的な開始位置から始まり、可能な限り長く動き続け、すべてのヒキガエルが右側に、すべてのカエルが左側に揃うまでの動きが求められます。動きは、ヒキガエルとカエルが交互に動く必要はありません。[ 5 ]

参考文献

  1. ^ a bエルウィン・R・バーレカンプ、ジョン・H・コンウェイ、リチャード・K・ガイ(2001). 「ヒキガエルとカエル」.数学的遊びの必勝法. 第1巻（第2版）. AKピーターズ. pp.  12– 13.
  2. ^エリクソン, ジェフ (1996). 「新しいヒキガエルとカエルの研究結果」. リチャード・J. ノワコウスキー編. 『偶然のゲーム』 . 数学科学研究所出版. 第29巻. ケンブリッジ大学出版局. pp.  299– 310.
  3. ^エリックソンのウェブサイトとタナティパノンダの論文の両方で言及されている通り。
  4. ^ Thanatipanonda, Thotsaporn (2011). 「ヒキガエルとカエルのさらなる跳躍」. Electronic Journal of Combinatorics . 18 (1): P67:1–P67:12. arXiv : 0804.0640 . doi : 10.37236/554 . MR 2788684. S2CID 35020735 .  
  5. ^レヴィティン、アナニー (2011). 「ヒキガエルとカエル」.アルゴリズムパズル. オックスフォード大学出版局. p. 53.
「 https://en.wikipedia.org/w/index.php?title=Toads_and_Frogs&oldid=1327932737」より取得