ヒキガエルとカエル

組み合わせゲーム 「ヒキガエルとカエル」はリチャード・ガイが考案したパルチザンゲームです。この数学ゲームは『数学的ゲームで勝つ方法』という本の中で入門ゲームとして使われました。^[1]

ヒキガエルとカエルは、その単純さとルールの優雅さで知られており、組み合わせゲーム理論の主要な概念を説明するのに役立ちます。特に、開始位置のゲームツリーを構築することにより、1匹のヒキガエルと1匹のカエルだけが関与する単純なゲームを評価することは難しくありません。 ^[1]しかし、任意の位置を評価する一般的なケースはNP困難であることが知られています。いくつかの注目すべき位置の値については、未解決の推測がいくつかあります。

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

ヒキガエルとカエルは、1 × nの正方形のストリップでプレイします 。各正方形は、常に空か、1 匹のヒキガエルまたはカエルが占めています。ゲームは任意の構成で開始できますが、通常は、ストリップの左端の連続する正方形にヒキガエルが、右端の連続する正方形にカエルが占めるところから開始します。

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

ヒキガエルとカエルの位置は、ヒキガエル、カエル、空きスペースの 3 つの文字の文字列で表すことができます。たとえば、文字列は、最初の正方形にヒキガエル、最後の正方形にカエルがある 4 つの正方形のストリップを表します。 ${\displaystyle T}$${\displaystyle F}$${\displaystyle \square}$${\displaystyle T\square \square F}$

組み合わせゲーム理論では、ポジションはオプション、つまり左プレイヤーと右プレイヤーが移動できるポジションによって再帰的に記述できます。左プレイヤーがポジションからポジション、、…に移動でき、右プレイヤーがポジション、、…に移動できる場合、ポジションは慣例的に次のように記述されます。${\displaystyle P}$${\displaystyle L_{1}}$${\displaystyle L_{2}}$${\displaystyle R_{1}}$${\displaystyle R_{2}}$${\displaystyle P}$${\displaystyle P=\{L_{1},L_{2},\dots |R_{1},R_{2},\dots \}.}$

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

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

数学的プレイの勝利方法は、まず多数の可能な値を示しました。たとえば、次のようになります。

${\displaystyle T\square \square F=0}$

${\displaystyle TF\square \square =1}$

${\displaystyle T\square F\square ={\frac {1}{2}}}$

${\displaystyle TFT\square F=\{0|0\}=\star }$

${\displaystyle T\square TFF=\{0|\star \}=\uparrow }$

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

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

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