ペグソリティア
1人用ボードゲーム
ソリティアをするスービーズ公女、 1697年

ペグ・ソリティア、ソロ・ノーブル、ソロ・ゴリ、マーブル・ソリティア、あるいは単にソリティアと呼ばれるゲームは、穴の開いたボード上でペグを動かす1人用のボードゲームです。セットによっては、くぼみのあるボードにビー玉を並べるものもあります。このゲームはイギリスではソリティア、アメリカではペグ・ソリティアと呼ばれています。アメリカでは「ソリティア」は「忍耐」の一般的な呼び名です。

このゲームに関する最初の記録は、ルイ14世の宮廷、そして1697年という具体的な日付まで遡ることができます。10年後、クロード・オーギュスト・ベレーがスービーズ公女アンヌ・ド・ロアン＝シャボのために制作した版画には、パズルが添えられていました。フランスの文芸誌『メルキュール・ガラン』 1697年8月号には、ボードの説明、ルール、サンプル問題が掲載されています。これが、このゲームに関する印刷物での最初の言及です。

標準的なゲームでは、中央の穴を除くボード全体をペグで埋めます。目的は、有効な動きをすることで、中央の穴にあるペグ1本を除いてボード全体を空にすることです。

ボード

伝統的なボードが 2 つあります (最初のペグとして「.」、最初の穴として「o」)。

英語 ヨーロッパの 
     · · ·
     · · ·
 · · · · · · ·
 · · · お · · ·
 · · · · · · ·
     · · ·
     · · ·

     · · ·
   · · · · ·
 · · · · · · ·
 · · · お · · ·
 · · · · · · ·
   · · · · ·
     · · ·

遊ぶ

ペグソリティアをプレイする
三角ペグソリティアで遊ぶ男性

有効な動きは、ペグを隣接するペグを直角に飛び越えて 2 つ離れた位置の穴にジャンプし、その後、ジャンプしたペグを取り外すことです。

以下の図では、は·穴にペグが入っていることを示し、*太字は移動先のペグ、 はo空の穴を示します。青色¤は現在のペグが移動した穴、赤色*はそのペグの最終位置、赤色はo移動して取り除かれたペグの穴を示します。

したがって、4 つの直交方向のそれぞれにおける有効な動きは次のようになります。 

* · o →   ¤  o  *  右へジャンプ

o · *   →   *  o  ¤  左へジャンプ

*      ¤ 
· →   o  ジャンプダウン
o      *

o      * 
· →   o  ジャンプアップ
*      ¤

英語のボードでは、最初の 3 つの動きは次のようになります。 

    · · · · · · · · · · ·
    · * · · ¤ · · o · · * ·
· · · · · · · · · · o · · · · ¤  o  * · · · · · o o · · ·
· · · o · · · · · · * · · · · · · · · · · · · · ¤ · · ·
・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・
    · · · · · · · · · · ·
    · · · · · · · · · · ·

戦略

標準的な問題にはさまざまな解法があり、それらを説明するために使用される表記法の 1 つでは、穴に文字を割り当てます (数字も使用できます)。 

   英語 ヨーロッパ
    abcabc
    デファイデフズ
ghijklmghijklm
ノップスPON ノップスPON
MLKJIHGMLKJIHG
    フェズフェディ
    CBACBA

この鏡像表記法が用いられる理由はいくつかありますが、ヨーロッパ式ボードでは、ある位置に穴を開けた状態で開始し、その鏡像位置に1本のペグを置いて終了するという代替ゲームの組み合わせが存在するためです。一方、イギリス式ボードでは、穴を開けた状態で開始し、同じ位置にペグを置いて終了するという代替ゲームの組み合わせが存在します。

直交移動のみが許可されている場合、最初の穴が中央にあるヨーロッパ盤には解は存在しません。これは、ハンス・ザンテマの議論によって次のように簡単に示されます。盤の位置をA、B、Cの3つの位置に分けます。 

    ABC
  ABCAB
ABCABCA
BCABCAB
キャブABC
  BCABC
    ABC

最初は中央の位置のみが空いており、覆われたAの位置の数は12、覆われたBの位置の数は12、覆われたCの位置の数はそれぞれ12です。移動するたびに、覆われたAの位置の数は1ずつ増減し、覆われたBの位置と覆われたCの位置の数も同様に増減します。したがって、偶数回の移動後には、これら3つの数字はすべて偶数になり、奇数回の移動後には、これら3つの数字はすべて奇数になります。したがって、1つのペグだけが最終位置に到達することはできません。なぜなら、そのためには、これらの数字のうち1つが1（ペグの位置、1は奇数）で、他の2つの数字が0（つまり偶数）である必要があるからです。

ただし、最初の 1 つの穴を 1 つのペグに減らすことができる他の構成もいくつかあります。

使える戦術の一つは、盤面を3つずつに分割し、1つの追加のペグ（触媒）を使ってそれらを完全に除去することです。触媒は飛び出してまた戻ってきます。以下の例では、*が触媒です。 

* · o       ¤  o  *       o * ·       *  o  ¤ 
  · → · →      o      → o
  · ·           ¤           o

このテクニックは、長さ 3 のベースと長さ 4 の垂直部を持つ 6 本のペグの L 字型、2 本 × 3 のブロックで使用できます。

他にも、2つの空いた穴から始めて、そこに2本のペグを入れて終了するゲームがあります。また、ここに1つの穴があって、あそこに1本のペグを入れて終了するゲームもあります。英語のボードでは、穴はどこにあっても構いませんが、最後のペグは3の倍数になる場所にしか置けません。つまり、 aに穴が開いている場合、 a、p、O、Cのいずれかに1本のペグしか残りません。

ペグソリティアに関する研究

このゲームの徹底的な分析は知られている。[1]この分析ではパゴダ関数 と呼ばれる概念が導入され、これは与えられた一般化ペグソリティア問題の実行不可能性を示す強力なツールである。

与えられた問題の実行不可能性を証明するパゴダ関数を求める解は線形計画問題として定式化され、多項式時間で解くことができる。[2]

1990年の論文では、ペグソリティア問題と同等の一般化Hi-Q問題を取り上げ、そのNP完全性を示した。[3]

1996年の論文では、ペグソリティア問題を組み合わせ最適化問題として定式化し、「ソリティアコーン」と呼ばれる実行可能領域の特性について議論しました。[4]

1999年、ペグ・ソリティアは、あらゆるバリエーションを網羅的に探索することでコンピュータ上で完全に解かれました。これは、対称性、ボードの配置の効率的な保存、そしてハッシュ化を利用することで達成されました。[5]

2001年にペグソリティア問題を解く効率的な方法が開発されました。[2]

1989年に行われた未発表の研究では、英語盤上のゲームの一般化版について、英語盤には9つの異なる3×3の小マスがあるため、一般化ゲームの各問題には対称性を除いて2 9通りの異なる解が存在することが示されました。この分析の結果、当初占有されていたマスが空のままになり、その逆もまた同様となる「反転配置」問題の数に下限が設けられました。このような問題の解は、問題の正確な詳細にかかわらず、最低11手から構成されます。

抽象代数を用いて、ゲームが1つのペグで正常に終了できる固定されたボードの位置は5つしかないことが証明できます。 [6]

英語ゲームの解決策

イングリッシュ ペグ ソリティアのインタラクティブな解答ガイド。

標準的な英語のゲームの最短の解決方法は、複数のジャンプを 1 回の移動としてカウントして 18 の動きを伴います。

この解は1912年にアーネスト・ベルゴルトによって発見され、1964年にジョン・ビーズリーによって最短であることが証明されました。[7]

この解答は、解答をより簡単に記憶できるように設計された Wolstenholme 表記法を紹介するページでも見ることができます。

その他の解法としては、以下のリストが挙げられます。これらの表記法は以下のとおりです。

  • スタートホール一覧
  • 結腸
  • エンドターゲットペグのリスト
  • 等号
  • 元のペグと目的の穴（飛び越えたペグは読者の練習問題として残しておきます）
  • 、または / （スラッシュは、6つのパージアウトなどの「チャンク」を区切るために使用されます）
x:x=ex,lj,ck,Pf,DP,GI,JH,mG,GI,ik,gi,LJ,JH,Hl,lj,jh,CK,pF,AC,CK,Mg,gi,ac,ck,kI,dp,pF,FD,DP,Pp,ox
 x:x=ex,lj,xe/hj,Ki,jh/ai,ca,fd,hj,ai,jh/MK,gM,hL,Fp,MK,pF/CK,DF,AC,JL,CK,LJ/PD,GI,mG,JH,GI,DP/Ox
 j:j=lj、Ik、jl/hj、Ki、jh/mk、Gm、Hl、fP、mk、Pf/ai、ca、fd、hj、ai、jh/MK、gM、hL、Fp、MK、pF/CK、DF、AC、JL、CK、LJ/Jj
 i:i=ki,Jj,ik/lj,Ik,jl/AI,FD,CA,HJ,AI,JH/mk,Hl,Gm,fP,mk,Pf/ai,ca,fd,hj,ai,jh/gi,Mg,Lh,pd,gi,dp/Ki
 e:e=xe/lj,Ik,jl/ck,ac,df,lj,ck,jl/GI,lH,mG,DP,GI,PD/AI,FD,CA,JH,AI,HJ/pF,MK,gM,JL,MK,Fp/hj,ox,xe
 d:d=fd,xe,df/lj,ck,ac,Pf,ck,jl/DP,KI,PD/GI,lH,mG,DP,GI,PD/CK,DF,AC,LJ,CK,JL/MK,gM,hL,pF,MK,Fp/pd
 b:b=jb,lj/ck,ac,Pf,ck/DP,GI,mG,JH,GI,PD/LJ,CK,JL/MK,gM,hL,pF,MK,Fp/xo,dp,ox/xe/AI/BJ,JH,Hl,lj,jb
 b:x=jb,lj/ck,ac,Pf,ck/DP,GI,mG,JH,GI,PD/LJ,CK,JL/MK,gM,hL,pF,MK,Fp/xo,dp,ox/xe/AI/BJ,JH,Hl,lj,ex
 a:a=ca,jb,ac/lj,ck,jl/Ik,pP,KI,lj,Ik,jl/GI,lH,mG,DP,GI,PD/CK,DF,AC,LJ,CK,JL/dp,gi,pd,Mg,Lh,gi/ia
 a:p=ca,jb,ac/lj,ck,jl/Ik,pP,KI,lj,Ik,jl/GI,lH,mG,DP,GI,PD/CK,DF,AC,LJ,CK,JL/dp,gi,pd,Mg,Lh,gi/dp
白く丸で囲まれた穴に注目して、最初にエッジをクリアするという覚えやすい解決策 - 図1では、ペグは取り外す順にラベル付けされています

標準的な英語のペグソリティアに対するブルートフォース攻撃

単独のペグで終わる可能性がある唯一の場所は、中央、またはいずれかの端の真ん中です。最後のジャンプでは、中央で終わるか端で終わるかを選択するオプションが常にあります。

以下は、n回のジャンプ後の可能な盤面の位置の数（可能な盤面位置）と、同じペグをさらにジャンプするために移動できる可能性（さらにジャンプしない回数）を示す表です。注目すべき興味深い点は、ゲームに失敗する最短方法は6手であり、その解法（回転と反射を除く）は一意であるということです。この例は次のとおりです。4 → 16; 23 → 9; 14 → 16; 17 → 15; 19 → 17; 31 → 23。（この表記では、ペグには左から右へ0から番号が付けられ、各行がマークされると左端に移動します。）

注意: あるボードの位置を別のボードの位置に回転または反転できる場合、ボードの位置は同一としてカウントされます。

ジャンプは31回しかできないため、現代のコンピュータは妥当な時間内にすべてのゲームポジションを簡単に調べることができます。[8]

上記のシーケンス「PBP」は、OEISでは A112737 として入力されています。到達可能な盤面の位置の総数（シーケンスの合計）は 23,475,688 であるのに対し、可能な盤面の位置の総数は 8,589,934,590 (33bit-1) (2^33) であるため、中央が空いている状態から開始して到達できる盤面の位置は、全可能な盤面の位置の約 2.2% に過ぎないことに注意してください。

すべての盤面を生成することも可能。以下の結果はmCRL2ツールセットを使用して得られたものです（配布物に含まれるpeg_solitaireの例を参照）。

以下の結果では、中央の空いているところから始まり、中央の穴で終わるまで、 実際に到達したすべてのボードの位置を生成しています。

ヨーロッパのゲームへの解決策

解が存在する非合同な初期位置が3つあります。[9]これらは以下の通りです。

1) 

          0 1 2 3 4 5 6
        0時 · ·
        1 · · · · ·
        2 · · · · · · ·
        3 · · · · · · ·
        4 · · · · · · ·
        5 · · · · ·
        6 · · ·

考えられる解決策: [2:2-0:2, 2:0-2:2, 1:4-1:2, 3:4-1:4, 3:2-3:4, 2:3-2:1, 5:3-3:3, 3:0-3:2, 5:1-3:1, 4:5-4:3, 5:5-5:3, 0:4-2:4, 2:1-4:1, 2:4-4:4, 5:2-5:4, 3:6-3:4, 1:1-1:3, 2:6-2:4, 0:3-2:3, 3:2-5:2, 3:4-3:2, 6:2-4:2, 3:2-5:2, 4:0-4:2, 4:3-4:1, 6:4-6:2, 6:2-4:2、4:1-4:3、4:3-4:5、4:6-4:4、5:4-3:4、3:4-1:4、1:5-1:3、2:3-0:3、0:2-0:4]

2) 

          0 1 2 3 4 5 6
        0 · · ·
        1 · · o · ·
        2 · · · · · · ·
        3 · · · · · · ·
        4 · · · · · · ·
        5 · · · · ·
        6 · · ·

考えられる解決策: [1:1-1:3, 3:2-1:2, 3:4-3:2, 1:4-3:4, 5:3-3:3, 4:1-4:3, 2:1-4:1, 2:6-2:4, 4:4-4:2, 3:4-1:4, 3:2-3:4, 5:1-3:1, 4:6-2:6, 3:0-3:2, 4:5-2:5, 0:2-2:2, 2:6-2:4, 6:4-4:4, 3:4-5:4, 2:3-2:1, 2:0-2:2, 1:4-3:4, 5:5-5:3, 6:3-4:3, 4:3-4:1, 6:2-4:2, 3:2-5:2、4:0-4:2、5:2-3:2、3:2-1:2、1:2-1:4、0:4-2:4、3:4-1:4、1:5-1:3、0:3-2:3]

そして3） 

          0 1 2 3 4 5 6
        0 · · ·
        1 · · · · ·
        2 · · · お · · ·
        3 · · · · · · ·
        4 · · · · · · ·
        5 · · · · ·
        6 · · ·

考えられる解決策: [2:1-2:3, 0:2-2:2, 4:1-2:1, 4:3-4:1, 2:3-4:3, 1:4-1:2, 2:1-2:3, 0:4-0:2, 4:4-4:2, 3:4-1:4, 6:3-4:3, 1:1-1:3, 4:6-4:4, 5:1-3:1, 2:6-2:4, 1:4-1:2, 0:2-2:2, 3:6-3:4, 4:3-4:1, 6:2-4:2, 2:3-2:1, 4:1-4:3, 5:5-5:3, 2:0-2:2, 2:2-4:2, 3:4-5:4, 4:3-4:1、3:0-3:2、6:4-4:4、4:0-4:2、3:2-5:2、5:2-5:4、5:4-3:4、3:4-1:4、1:5-1:3]

ボードのバリエーション

ペグ・ソリティアは他のサイズのボードでもプレイされてきましたが、上記の2つが最も人気があります。また、三角形のボードでもプレイされ、3方向すべてへのジャンプが認められています。適切な「パリティ」を持ち、十分な大きさであれば、おそらく解けるでしょう。2025年、YouTuberのマイケル・スティーブンスは、これらのバリエーションを1つのボードに並べました。彼はそれを「オムニジャンプ」と名付けました。[10]

ペグソリティアのゲームボードの形状：
(1) フランス（ヨーロッパ）スタイル、37穴、17世紀。
(2) JC Wiegleb、1779年、ドイツ、45穴。
(3) ジョージ・ベルが考案した非対称3-3-2-2、20世紀。[11]
(4) イギリススタイル（標準）、33穴。
(5) ダイヤモンド型、41穴。
(6) 三角形、15穴。
灰色＝生存者の穴。

一般的な三角形のバリエーションでは、1辺に5本のペグが配置されます。中央の3つの位置のいずれかにペグが配置されている場合、最後のペグが最初の空の穴に到達する解法は不可能です。角の空穴配置は10手で、中央の空穴配置は9手で解くことができます（Bell 2008）。

ビデオゲーム

1992年6月26日、ペグソリティアをベースにしたビデオゲームがゲームボーイ向けに発売されました。「Solitaire」というシンプルなタイトルのこのゲームは、Hect社によって開発されました。北米では、DTMC社が「Lazlos' Leap」というタイトルで発売しました。

『レイトン教授と悪魔の箱』には、英語のペグ ソリティア ボードを異なる初期位置から解くパズルが 6 つあり、最後のパズルは従来の構成です。

PCゲーム「Shivers」は、ホラーをテーマにしたポイントアンドクリックパズルゲームで、プレイヤーがクリアできるパズルやゲームが数多く用意されています。「 Chinese Checkers 」と呼ばれるパズルは、実際にはペグソリティアです。

クラッカーバレルでは、全店舗のテーブルでこのゲームを提供しています。ボードは三角形で、合計15個の穴があります。

『カウボーイビバップ THE MOVIE』では、主要な敵役であるヴィンセント・ヴォラージュは、自由時間のほとんどをペグソリティアで過ごしています。彼が計画しているバイオテロ攻撃のベクターであるナノボットは、ペグソリティアのビー玉の中に保存されています。

参考文献

  1. ^ Berlekamp, ER ; Conway, JH ; Guy, RK (2001) [1981], Winning Ways for your Mathematical Plays (第2版), AK Peters/CRC Press, ISBN 978-1568811307、OCLC  316054929
  2. ^ ab 清見, M.; 松井, T. (2001), "Integer Programming Based Algorithms for Peg Solitaire Problems", Proc. 2nd Int. Conf. Computers and Games (CG 2000): Integer programming based algorithms for peg solitaire problems , Lecture Notes in Computer Science, vol. 2063, pp.  229– 240, CiteSeerX 10.1.1.65.6244 , doi :10.1007/3-540-45579-5_15, ISBN  978-3-540-43080-3
  3. ^ 上原 亮; 岩田 誠 (1990). 「一般化Hi-QはNP完全である」.電子情報通信学会論文集. 73 : 270–273 .
  4. ^ Avis, D. ; Deza, A. (2001)、「ソリティア円錐と多商品フローとの関係について」、数学プログラミング、90 (1): 27– 57、doi :10.1007/PL00011419、S2CID  7852133
  5. ^ アイヒラー;イェーガー; Ludwig (1999)、1999 年 7 月を参照 Spielverderber、Solitaire mit dem Computer lösen (ドイツ語)、vol. 7、p. 218
  6. ^ 「数学と脳の働き」『数学ノート』 2012年8月28日、 2018年9月6日閲覧。
  7. ^ Beasley の証明については、Winning Ways、第 4 巻 (第 2 版) を参照してください。
  8. ^ "solboard". github . 2020年8月31日. 2020年8月31日閲覧.ペグソリティアゲームのブルートフォース計算の実装
  9. ^ Brassine、Michel (1981 年 12 月)、「Découvrez... le solitaire」、Jeux & Stratégie  [fr] (フランス語)
  10. ^ Vsauce のペグソリティアに関する YouTube 動画。https://www.youtube.com/shorts/HdX6dNIlCQI
  11. ^ 一般化されたクロスボードについては、George's Peg Solitaire Page を参照してください。

さらに読む

  • ビーズリー、ジョン・D.（1985） 『ペグ・ソリティアの奥深さ』オックスフォード大学出版局、ISBN 978-0198532033
  • Bell, GI (2008)、「三角ペグソリティアの解法」、Journal of Integer Sequences、11：Article 08.4.8、arXiv：math.CO/0703865、Bibcode：2007math......3865B。
  • Bruijn, NG de (1972)、「ソリティアゲームと有限体との関係」（PDF）、Journal of Recreational Mathematics、5 : 133– 137、 2022年10月9日時点のオリジナルよりアーカイブ（PDF）
  • クロス, DC ( 1968)、「スクエアソリティアとそのバリエーション」、レクリエーション数学ジャーナル、1 : 121–123
  • ガードナー、M.、「数学ゲーム」、サイエンティフィック・アメリカン 206 (6): 156–166, 1962年6月; 214 (2): 112–113, 1966年2月; 214 (5): 127, 1966年5月。
  • ジェファーソン、クリス他 (2006年10月)、「イングリッシュ・ペグ・ソリティアのモデリングと解決法」、Computers & Operations Research、33 (10): 2935– 2959、CiteSeerX  10.1.1.5.7805、doi :10.1016/j.cor.2005.01.018
ウィキメディア コモンズには、ペグ ソリティアに関連するメディアがあります。
  • ボゴモルニー、アレクサンダー、「ペグソリティアと群論」、インタラクティブ数学雑学とパズル、 2018年9月7日閲覧。
  • White Pixels (2017年10月24日)、ペグソリティア：覚えやすい対称解法（動画）、YouTube、2021年12月11日時点のオリジナルからアーカイブ
「https://en.wikipedia.org/w/index.php?title=ペグソリティア&oldid=1324265652」より取得