「３人石とりゲームには必勝戦略がない」の編集履歴（バックアップ）一覧はこちら
「３人石とりゲームには必勝戦略がない」(2013/01/07 (月) 15:45:38) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
一回きりの３人石取りゲームは結託以外の必勝戦略がないことの証明。
２人石取りゲームとは石がｎ個積まれてそこから交互に１～３個ずつ石を取っていき、最後に石を取った人のまけというゲームである。
これを３人で遊んだ場合、必勝戦略があるのかという質問がＹａｈoo知恵袋に上がっていました。
直感的に考えれば、どのプレーヤも自分の手の後、２手行われて自分の番に戻ってきます。
なのでどのプレーヤから見ても自分以外のプレーヤを２人で一人とみなして、相手は一人で二手取れる２人ゲームに見えます。
相手二人に結託されたら残りの一人に勝利がないのは明白です。
このゲーム結託がなくても一回きりの勝負には、必勝戦略が存在しません。
石の数ｎ<=7まで検討すればゲームの構造が判明します。
ゲーム展開を2,3,1,1のように記述するとします。
これはプレーヤ１が２個、プレーヤ２が３個、プレーヤ３が１個、プレーヤ１が１個で１の負けというゲーム展開を表します。
ｎ<=4の場合
プレーヤ１は２か３取ればいいのでプレーヤ１の勝利。
２が負けるか３が負けるかは１次第。
プレーヤ１だけ必勝戦略を持ちます。
n=5の場合。
プレーヤ１は自分が負ける可能性を排除するため
3,1,1
というゲーム展開しかありません。
プレーヤ１、２が必勝戦略を持ちプレーヤ３が負けます。
n=6の場合
3,2,1プレーヤ３の負け
3,1,1,1プレーヤ１の負け
2,3,1プレーヤ３の負け
2,2,1,1プレーヤ１の負け
各人自分が負ける場合を回避すると上記のゲーム展開しかありません。
三個取りで始めた場合プレーヤ１、３どちらが負けるかはプレーヤ２にゆだねられます。
２個取りで始めた場合もプレーヤ１、３どちらが負けるかはプレーヤ２にゆだねられます。
１個取りでは1,3,1,1でプレーヤ１は必ず負けます。
プレーヤ２は自分の負けを100％回避するために３個取るからです。
よってプレーヤ２が必勝戦略を持ち誰が負けるかはプレーヤ２にゆだねられます。
ｎ=7の場合
ｎ＝7の場合を検討すればそれ以上は検討する必要がありません、これは後で説明します。
7個の場合。
1個取りで始めるとプレーヤ２、石６個で始まったのとゲームが同じになります。
よってこれは６個の場合を思い出して、プレーヤ３が敗者を決定する権利を手に入れたのと同じになります。
２個取りで始めた場合、残り5個ですからその後3,1,1のパターンでプレーヤ１の負けとなるのでこの手はありません。
３個取りの場合、残り４個ですのでその後3,1か2,1,1の展開となります。
プレーヤ１が負けるかプレーヤ３が負けるかはプレーヤ２次第となります。
つまり７個で始めた場合、プレーヤ１はプレーヤ２、３どちらかに誰を敗者にするか決定する権利を貸与するゲームと同値となります。
プレーヤ２，３にしてみればプレーヤ１に決めてもらえないと必勝戦略は持てませんし、1にしてみれば２，３どちらが自分を敗者にしないか（両方とも１を敗者にする気かも）分からないので必勝戦略は持てません。
よってｎ＝7には必勝戦略を持つプレーヤは存在しません。
n>7の場合
一度に三個しか取れませんからn>7から開始したゲームは必ず5,6,7のどれかを通ります。
５にしてしまった場合、５にした人はその後3,1,1の展開で必ず負けます。
よって6か7しかありません。
自分の手版で６にした場合、その次の人から石６個でゲームが始まったのと同じとなります。
すると自分の二人先の手版の人が誰を敗者にするか決定することが可能となります。
７にした場合、敗者を決定する権利を持つ人が誰になるかを次のプレーヤが決定できることになります。
6にしても7にしても他のプレーヤに運命を委ねることになり１回ゲームでは運任せ他人任せとなります。
誰も必勝戦略を持ちません。
何回も行って勝利を競うゲームでは少し事情が代わります。
一番勝ってる人を負けに持っていきたいという無言の結託。
これが負けている２プレーヤの間に成立する可能性が高いからです。
この場合結託した２プレーヤの取る２手は協力した結果一人で二手取ってから、勝ってるプレーヤに手が戻る二人ゲームのようなものです。
石取りゲームの構造からいってｎが十分大きければ確実に結託できた二人は勝てます。
ｍ回繰り返しゲームにおいて長期的にも圧勝する戦略はないことが分かります。
一回きりの３人石取りゲームは結託以外の必勝戦略がないことの証明。
２人石取りゲームとは石がｎ個積まれてそこから交互に１～３個ずつ石を取っていき、最後に石を取った人のまけというゲームである。
これを３人で遊んだ場合、必勝戦略があるのかという質問がＹａｈoo知恵袋に上がっていました。
直感的に考えれば、どのプレーヤも自分の手の後、２手行われて自分の番に戻ってきます。
なのでどのプレーヤから見ても自分以外のプレーヤを２人で一人とみなして、相手は一人で二手取れる２人ゲームに見えます。
相手二人に結託されたら残りの一人に勝利がないのは明白です。
このゲーム結託がなくても一回きりの勝負には、必勝戦略が存在しません。
石の数ｎ<=7まで検討すればゲームの構造が判明します。
ゲーム展開を2,3,1,1のように記述するとします。
これはプレーヤ１が２個、プレーヤ２が３個、プレーヤ３が１個、プレーヤ１が１個で１の負けというゲーム展開を表します。
ｎ<=4の場合
プレーヤ１は２か３取ればいいのでプレーヤ１の勝利。
２が負けるか３が負けるかは１次第。
プレーヤ１だけ必勝戦略を持ちます。
n=5の場合。
プレーヤ１は自分が負ける可能性を排除するため
3,1,1
というゲーム展開しかありません。
プレーヤ１、２が必勝戦略を持ちプレーヤ３が負けます。
n=6の場合
3,2,1プレーヤ３の負け
3,1,1,1プレーヤ１の負け
2,3,1プレーヤ３の負け
2,2,1,1プレーヤ１の負け
各人自分が負ける場合を回避すると上記のゲーム展開しかありません。
三個取りで始めた場合プレーヤ１、３どちらが負けるかはプレーヤ２にゆだねられます。
２個取りで始めた場合もプレーヤ１、３どちらが負けるかはプレーヤ２にゆだねられます。
１個取りでは1,3,1,1でプレーヤ１は必ず負けます。
プレーヤ２は自分の負けを100％回避するために３個取るからです。
よってプレーヤ２が必勝戦略を持ち誰が負けるかはプレーヤ２にゆだねられます。
ｎ=7の場合
ｎ＝7の場合を検討すればそれ以上は検討する必要がありません、これは後で説明します。
7個の場合。
1個取りで始めるとプレーヤ２、石６個で始まったのとゲームが同じになります。
よってこれは６個の場合を思い出して、プレーヤ３が敗者を決定する権利を手に入れたのと同じになります。
２個取りで始めた場合、残り5個ですからその後3,1,1のパターンでプレーヤ１の負けとなるのでこの手はありません。
３個取りの場合、残り４個ですのでその後3,1か2,1,1の展開となります。
プレーヤ１が負けるかプレーヤ３が負けるかはプレーヤ２次第となります。
つまり７個で始めた場合、プレーヤ１がプレーヤ２、３どちらかに誰を敗者にするか決定する権利を貸与するゲームと同値となります。
プレーヤ２，３にしてみればプレーヤ１に決めてもらえないと必勝戦略は持てませんし、1にしてみれば２，３どちらが自分を敗者にしないか（両方とも１を敗者にする気かも）分からないので必勝戦略は持てません。
よってｎ＝7には必勝戦略を持つプレーヤは存在しません。
n>7の場合
一度に三個までしか取れませんからn>7から開始したゲームは必ず5,6,7のどれかを通ります。
５にしてしまった場合、５にした人はその後3,1,1の展開で必ず負けます。
よって6か7しかありません。
自分の手版で６にした場合、その次の人から石６個でゲームが始まったのと同じとなります。
すると自分の二人先の手版の人が誰を敗者にするか決定することが可能となります。
７にした場合、敗者を決定する権利を持つ人が誰になるかを次のプレーヤが決定できることになります。
6にしても7にしても他のプレーヤに運命を委ねることになり１回ゲームでは運任せ他人任せとなります。
誰も必勝戦略を持ちません。
何回も行って勝利を競うゲームでは少し事情が代わります。
一番勝ってる人を負けに持っていきたいという無言の結託。
これが負けている２プレーヤの間に成立する可能性が高いからです。
この場合結託した２プレーヤの取る２手は協力した結果一人で二手取ってから、勝ってるプレーヤに手が戻る二人ゲームのようなものです。
石取りゲームの構造からいってｎが十分大きければ確実に結託できた二人は勝てます。
ｍ回繰り返しゲームにおいて長期的にも圧勝する戦略はないことが分かります。
