Loading article…
ペグ ソリティア、ソロ ノーブル、ソロ ゴリ、マーブル ソリティア、または単にソリティアは、穴の開いたボード上でペグを動かす 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 つは、穴に文字を割り当てることです (数字も使用できます)。
英語 ヨーロッパ
アブカアブ
デファイデフズ
ギイクルム
ノーピクセルPON ノーピクセルPON
MLKJIHGMLKJIHG
フェズフェディ
CBACBA
この鏡像表記法が使用される理由はいくつかありますが、ヨーロッパのボードでは、代替ゲームの 1 セットは、ある位置の穴から始まり、その鏡像の位置にある 1 つのペグで終わります。イギリスのボードでは、同等の代替ゲームは、穴から始まり、同じ位置のペグで終わります。
直交移動のみが許可されている場合、最初の穴が中央にあるヨーロッパのボードには解決策はありません。これは、Hans Zantemaの議論によって次のように簡単にわかります。ボードの位置を次のように A、B、C の位置に分割します。
ABC
ABCAB
ABCA
BCABCAB
ABCABC
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 本のライン、2.3 本のブロック、および長さ 3 のベースと長さ 4 の垂直部を持つ 6 本のペグの L 字型で使用できます。
他の代替ゲームとしては、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 の異なる解決方法があることが示されました。この分析の結果の 1 つは、最初に占められていたセルが空のままになり、その逆も起こる可能性のある「逆位置」問題のサイズに下限を設けることです。このような問題の解決には、問題の正確な詳細に関係なく、最低 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
標準的な英語のペグソリティアに対するブルートフォース攻撃
単一のペグで終わる可能性がある唯一の場所は、中央、またはいずれかの端の中央です。最後のジャンプでは、中央で終わるか端で終わるかを選択するオプションが常にあります。
以下は、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 · · · o · · ·
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 方向すべてにジャンプできる三角形のボードでもプレイされています。このバリエーションが適切な「パリティ」を持ち、十分な大きさである限り、おそらく解けるでしょう。
（1）フランス（ヨーロッパ）スタイル、37穴、17世紀。
（2）JC Wiegleb、1779年、ドイツ、45穴。
（3）ジョージ・ベルが説明した非対称3-3-2-2、20世紀[10]
（4）英国スタイル（標準）、33穴。
（5）ダイヤモンド、41穴。
（6）三角形、15穴。
灰色=生存者の穴。
一般的な三角形のバリエーションでは、1 辺に 5 つのペグがあります。最後のペグが最初の空の穴に到達するという解決法は、3 つの中央位置のいずれかの穴では不可能です。空の角穴の設定は 10 手で解決でき、空の中央穴の設定は 9 手で解決できます (Bell 2008)。
ビデオゲーム
1992 年 6 月 26 日、ペグ ソリティアをベースにしたビデオ ゲームがゲームボーイ向けにリリースされました。単にSolitaireと題されたこのゲームは、Hect によって開発されました。北米では、DTMC がLazlos' Leapとしてこのゲームをリリースしました。
大衆文化では
PC ゲームShivers は、ホラーをテーマにしたポイント アンド クリックパズル ゲームで、プレイヤーがクリアできるパズルやゲームが多数用意されています。「Chinese Checkers」と呼ばれるパズルは、実際にはペグ ソリティアです。
クラッカーバレルでは、店舗内のすべてのテーブルでこのゲームを提供しています。ボードは三角形で、合計 15 個の穴があります。
『カウボーイビバップ ザ・ムービー』では、主な敵役であるヴィンセント・ヴォラージュは、自由時間のほとんどをペグソリティアで過ごしています。彼が計画しているバイオテロ攻撃の媒介物であるナノボットの一種は、ペグソリティアのビー玉の中に保存されています。
参考文献
- ^ Berlekamp, ER ; Conway, JH ; Guy, RK (2001) [1981],数学的遊びの勝利の方法(第2版)、AK Peters/CRC Press、ISBN 978-1568811307、OCLC 316054929
- ^ ab 清見 正; 松井 孝 (2001)、「ペグソリティア問題に対する整数計画法に基づくアルゴリズム」、第 2 回国際会議コンピュータとゲーム (CG 2000) 論文集: ペグソリティア問題に対する整数計画法に基づくアルゴリズム、コンピュータサイエンスの講義ノート、第 2063 巻、pp. 229–240、CiteSeerX 10.1.1.65.6244、doi :10.1007/3-540-45579-5_15、ISBN 978-3-540-43080-3
- ^ 上原 亮; 岩田 誠 (1990). 「一般化Hi-QはNP完全である」.電子情報通信学会論文誌. 73 : 270–273.
- ^ Avis, D. ; Deza, A. (2001)、「ソリティア円錐と多商品フローとの関係について」、数学プログラミング、90 (1): 27–57、doi :10.1007/PL00011419、S2CID 7852133
- ^ アイヒラー;イェーガー; Ludwig (1999)、1999 年 7 月を参照 Spielverderber、Solitaire mit dem Computer lösen (ドイツ語)、vol. 7、p. 218
- ^ 「数学と脳の働き」、数学ノート、2012年8月28日、 2018年9月6日閲覧。
- ^ Beasley の証明については、Winning Ways、第 4 巻 (第 2 版) を参照してください。
- ^ "solboard". github . 2020-08-31 . 2020-08-31閲覧。
ペグソリティアゲームのブルートフォース計算の実装
- ^ Brassine、Michel (1981 年 12 月)、「Découvrez... le solitaire」、Jeux et Stratégie (フランス語)
- ^ 一般化されたクロスボードについては、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-09にオリジナルからアーカイブ(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
外部リンク
ウィキメディア・コモンズには、ペグ・ソリティアに関連するメディアがあります。
- Bogomolny, Alexander、「Peg Solitaire and Group Theory」、Interactive Mathematics Miscellany and Puzzles 、2018 年9 月 7 日閲覧
- ホワイトピクセル（2017年10月24日）、ペグソリティア：覚えやすい対称解法（動画）、Youtube、2021年12月11日にオリジナルからアーカイブ