古典的ソリティアというゲームの難しいバージョン

３２個のコマを所定の位置に置いて飛びこされた駒を一つずつ取り除き、最後に一つの駒を残すという古くからあるゲームですが、特定の駒を特定の位置で残せるかどうかを数学的に示すためにはどのような数学が使われるのでしょうか。

No.5 ベストアンサー 回答者： stomachman 回答日時： 2013/09/03 14:29

ANo.4へのコメントについて。

> このゲームにどのような条件を付ければ難しいもの(最後に一つの駒がどこかに残るというのがゴールとして)になるのか

　これはゲーム（勝負ごと）ではなく、パズル（puzzleの元々の意味は「難問」）です。それをさらに難しくせよと。それはかなり大変な注文ではないでしょうか。

　パズルの一般論として、条件を追加することで選べる手を制限すれば、(1)解がなくなる（つまり難問として成立しなくなる）か 、(2)制限が解を強く示唆するようになる（つまり易しくなる）か、のどっちかでしょう。むしろ、各局面で選べる手を増やすことが必要です。けれども、ただ選べる手を増やすと（難しくなる代わりに）易しくなってしまう。盤面の形や最初の配置を工夫して、解が少数しかないようにしなくてはなりません。
　盤面をもっと広くするということが考えられます。空所が多いと選べる手が増えます。ただし、これまでの回答No.3,4で示したように、かたまった広い空所の真ん中に駒を送り込めるためには広さに制限があります。ですから、空所のサイズが余り大きいと解がなくなってしまいます。なので、広い盤面に幾つか空所が散らばっているという形にせざるを得ない。すると、部分ごと、局所ごとにパズルを解けば良い。やたら時間が掛かるようにはなるものの、難しさがそれほど大きく変わるとは思えません。結局、あまり面白くなくなっちゃうでしょう。
　あるいは、ナナメに飛ぶという事を許すとか、盤を3次元にすることも考えられます。しかしこうすると、性質が全く変わってしまって別のパズルになってしまう。それがソリティアよりも難しいか、面白いか。やってみないと何ともね。

　長い歴史のあるパズルだということは、すなわち、様々な試行錯誤の結果としてこの形に落ち着いたのに違いありません。ということは、ちょっといじくったぐらいでナントカなるとは期待できないだろう、と推察できます。そもそも、ルールのシンプルさや最初の配置の対称性こそが大きな魅力なのであり、それを損なってしまうようじゃダメダメですよね。

この回答へのお礼

今回のご教示はよく理解できました。自分なりに考えてみたいことが出てきました。できればご教示の数学にも取り組めればとも思っております。いろいろありがとうございました。

お礼日時：2013/09/03 17:26

No.4 回答者： stomachman 回答日時： 2013/09/02 20:57

ANo.3へのコメントについて。

> とても難しくてまったく理解できません

　うーん、言葉や式だけではわかりにくかったな。図を出します。

　「裏ソリティア」について。
　図Aを左から右の順に見ると（太い黒の矢印）、「黒い駒(●)が、他の黒い駒を飛び越して空所(○)へ移動する動作」を表しています。（○も●も描いてない場所は変化しませんから、○があっても●があっても同じことであり、つまり無視できます。）ところが、この二つの図を逆順に（太い白の矢印に沿って）見れば「白い駒(○)が、他の白い駒を飛び越して空所(●)へ移動する動作」を表す図になっています。これが「裏ソリティア」です。
　だから「ソリティアを、ゴールから逆に考える」ということは、実は「裏ソリティアをフツーにやる」ということと全く同じなのです。

　盤面の評価値vについて。
　図Bは盤面の各場所(x,y)に、その場所でのw(x,y)=φ^(-|x|-|y|)の値を書き込んだものです。w(x,y)は、「y=3よりも上の部分を駒で埋め尽くした状態から出発しても、x軸とy軸の交点(0,0)の場所に駒を持って来ることは不可能だ」ということを証明するために使います。（ (φ^(-n))というのは「φの-n乗」、つまり「 (1/φ)のn乗」という意味です。）

　図Cは「評価値vは、駒を動かすことによって減ることはあっても増えることはない」ということの説明図です。図Cの上図の盤面では、黒い駒が2個あって、空所1個ある。（○も●も描いてない場所は変化しないから、評価値の増減には関係がありませんので無視します。）評価値vは駒がある場所のw(x,y)の総和なので、v=φ^(-5) + φ^(-4) である。ここで駒を動かして下図の盤面になると、評価値はv=φ^(-3) になります。
　ここでφの性質
　　φ^2 = 1+φ
を使えば
　　φ^(-5) + φ^(-4) = (φ^(-5)) (1+φ) = (φ^(-5)) (φ^2) = φ^3
です。だから、この駒の動きの場合、評価値vは動かす前後で変化しない訳です。
　この他に、駒を上へ移動する、左右に移動する、の3通りの動かし方の場合にどうなるか検討する必要があり、どの場合でも「評価値vは小さくなるか変化しないかであって、増えることはない」ということが確かめられます。

この回答へのお礼

大変な労力を費やしていただいたご親切を粗末にしたくありませんが、いかんせん全く私には理解できません。理解できないにもかかわらずこのようなお願いもしづらいのですが、申し訳ございませんが、このゲームにどのような条件を付ければ難しいもの(最後に一つの駒がどこかに残るというのがゴールとして)になるのか具体的に教えていただけないでしょうか。

お礼日時：2013/09/03 12:56

No.3 回答者： stomachman 回答日時： 2013/09/02 17:42

　ANo.1です。

　この問題が解かれているかどうかは知りません。ご質問の

> どのような数学が使われるのでしょうか

について、ごく漠然と「離散数学」とか「組み合わせ数学」と呼ばれる括りに入る話ではありますが、特定の手法にすっぽり嵌るという話ではないように思います。（逆に言えば、どんな手を使っても良いわけです。）

　たとえば：
　このパズルに取り組む際に、多くの方が「最後の状態から逆戻りして考えてみよう」という発想に至るんじゃないでしょうか。
　あらゆる盤面をノード、駒を動かす操作をアークとする有向グラフを考える。そして、駒を動かすことを「ノードからノードへアークに沿って移動する」という風に捉えます。そうすると、「ある盤面Aから始めてある盤面Bへ到達できるか？」という問いは、「ノードAからノードBへ至るパスが存在するか？」と言い換えられます。この問いは、全てのアークの向きを逆にしたグラフを考えれば「ノードBからノードAへ至るパスが存在するか？」という問いの答と、当然一致します。これはどういうことか。
　駒は全て黒にします。次に、黒い駒が無いところには全て白い駒を置くことにします。そして、（ある盤面Aから始めてある盤面Bへ到達する）一つの解を実行したとしましょう。さて、この実行のプロセスを逆順で見ると、「駒は全て白にします。次に、白い駒が無いところには全て黒い駒を置くことにします。そして、一つの解を実行する。（ただし駒の動かし方のルールはソリティアとは逆）」ということをやっていることになります。これを「裏ソリティア」と呼ぶことにしましょう。（すなわち裏ソリティアとは、上記の「全てのアークの向きを逆にしたグラフ」で表されるパズルという訳です。）
　すると、「一つ決めた場所pだけに白駒を置いて他を黒駒で埋め尽くした状態から始めて、一つ決めた場所qだけに黒駒があって他は白駒で埋め尽くされた状態にする」というソリティアは、「一つ決めた場所qだけに黒駒を置き他を白駒で埋め尽くした状態から始めて、一つ決めた場所pだけに白駒があって他は黒駒で埋め尽くされた状態にする」という裏ソリティアと完全に同等である。だから、「最後の状態から逆戻りして考えて」も問題は変わっていないということが分かります。

　また、たとえば：
　盤を、無限に広がる碁盤に取り替えます。Zを整数全体の集合として、{(x,y) | x∈Z, y∈Z}が「場所」の集合です。そして、「最初に駒があって良いのはy≧nの場所だけだとする。駒を旨く配置して、ソリティアの駒を動かすルールに従って(x,y) = (0,0)に駒を送り込むことはできるか？（他に駒が残っていても構わない）」という問題を考えます。n=1, n=2なら簡単。n=3だとなかなか大変。n=4ならどうでしょう？
　場所(x,y)に
　　w(x,y) = φ^(-|x|-|y|), ただし φ=((√5) + 1)/2 （φは黄金比、約1.6です)
という値を対応させ、駒が置いてある場所(x,y)全てについてw(x,y)を合計したものをその盤面pの「評価値」v(p)とします。(x,y) = (0,0)だけに駒がある盤面をPとすると、その評価値v(P)はv(P)≧w(0,0)= 1です。(0,0)以外にも駒が残っている盤面P'では、評価値v(P')はv(P)よりも大きくなります（∵ w(x,y)＞0）。
　さて、ルールに従って駒を1回動かすと、明らかに、どうやってもvは増えません。これは
　　φ^2 + φ = 1
であることを使えば簡単に証明できます。したがって、何度駒を動かしても、最後の盤面の評価値は、最初の盤面の評価値よりも大きくなりません。
　一方、y≧nの場所にどんな風に有限個の駒を並べた盤面p(n)でも、その評価値v(p(n))は、y≧nの場所を全て無限個の駒で埋め尽くした（そしてy＜nの場所には駒がない）盤面Q(n)の評価値v(Q(n))よりも小さい（∵ w(x,y)＞0）。そして、
　　v(Q(n)) = Σ{y=n～∞}Σ{x=-∞～∞}w(x,y)
　　= Σ{y=n～∞}( 1 + 2Σ{x=1～∞}φ^(-x) )φ^(-y)
等比級数
Σ{x=1～∞}φ^(-x) = (1/φ)/(1-1/φ) = 1/(φ-1)
とφの性質
　　φ = 1/(φ-1)
を使って
　　v(Q(n)) = Σ{y=n～∞}( 1 + 2φ)φ^(-y)
　　= (1 + 2φ) Σ{y=n～∞}φ^(-y)
さらにφの性質
　　φ^3 = 1 + 2φ
を使って
　　v(Q(n)) =(φ^3) Σ{y=n～∞}φ^(-y)
再び、等比級数と上記のφの性質のひとつめから
Σ{y=n～∞}φ^(-y) = (φ^(-n))/(1-1/φ) =φ^(1-n)
である。以上をまとめて
　　v(Q(n)) = (φ^3)(φ^(1-n)) = φ^(4-n)
と分かります。明らかに、v(Q(4)) = 1であり、nが大きいほどv(Q(n))は小さくなります。
　つまり、n≧4のとき
　　v(P')＞1=v(P)=v(Q(4))≧v(Q(n))＞v(p(n))
である。そして、p(n)から始めて駒を動かすと、vは減る事はあっても決して増えない。だから、n≧4のとき、(x,y) = (0,0)に駒を送り込むことは不可能だと分かります。


というふたつの分析をご覧になれば「特定の手法にすっぽり嵌るという話ではない」と申し上げる意味が多少ともお分かりになるかと。

この回答へのお礼

予想通り私にはとても難しくてまったく理解できませんが、数学的思考の対象になるということは納得できました。どうもありがとうございました。

お礼日時：2013/09/02 18:50

No.2 回答者： nobrain_nopain 回答日時： 2013/09/02 13:08

回答する能力はないけど以降の回答者の為に　質問者に補足要求。

参考URL確認の上、そこの内容が質問者の題意に沿ったものか補足頂きたい。

参考URL：http://ja.wikipedia.org/wiki/%E3%83%9A%E3%82%B0% …

この回答へのお礼

ご親切なコメントありがとうございます。ＵＲＬ拝見いたしました。まさにこれです。私はもっぱらフランス式しか知りませんでした。試行錯誤の結果一つの駒だけ残る道筋は見つけましたが、数学を使えばもっといろいろなことが分かるのではないかと思いました。

お礼日時：2013/09/02 14:01

No.1 回答者： stomachman 回答日時： 2013/09/02 02:43

「solitaire」とは「一人遊び」というだけの意味。

様々なパズルやゲームが同じ名で呼ばれますんで、「古典的ソリティア」という語でどんなゲーム（むしろパズルっぽいですが）を指していらっしゃるのか、明示して戴かねば。

この回答への補足

縦と横にそれぞれ並行する３本の線分を交差させ、全体として十字形にします。重なっている部分に正方形が４つできます。重なっていない部分が４つありますが、それぞれに正方形が４つできるように線分の長さを調整します。要するに田の字の部品を５枚使って十字を作ることになります。中心の田の字のさらに中心以外の３２個の頂点（？）にそれぞれ駒を置き、ひとつの駒で隣接する駒を飛び越させ、飛び越されたほうの駒は取り除きます。このとき飛び越す方の駒は空の頂点でないと着地できません。また斜めに飛び越すこともできません。ですから始まりは中心の空の頂点に着地することしかできません。だんだん空の頂点が増えてきますが、どの駒を動かしてもかまいません。初めに動かしたと同じ駒を使い続ける必要はありません。このようにしてうまくやれば、最後は一つの駒が残るのですが、この過程を数学で扱うとどのような数学になるのかというのが私の質問でした。ちなみに古典的ソリティアは、貴族は宝石、庶民は石ころを使って楽しんだという、万人のゲームだったようです。現在はトランプのかたちでパソコン上で楽しむものにも同じ名前が付いているようです。

補足日時：2013/09/02 06:27

この回答へのお礼

対応いただきありがとうございます。補足欄に書き込んでみました。ソリティアを文字で説明することのむずかしさを実感いたしました。ご理解いただければ幸いです。置換群とかそういう種類の数学でしょうか。

お礼日時：2013/09/02 06:30