2019年12月2日 | ブログ記事

例の手遊びを解析する【AdC2019 33日目】

shirodoni

例の手遊び

本記事で取り扱う「例の手遊び」は、交互に指の本数を増やしていくアレのことです。

ヴォルデモート卿やペニーワイズみたいな呼び方をしているのはなんでかというと、私の文化圏ではそれに名前が与えられていなかったからです。
地域によっては「マッチ棒」「割り箸」「電信棒」などと呼ぶらしいですね。闇の帝王が雑貨に成り下がってしましました。[1]

ゲームの基本的なルールは手を用いた遊び - Wikipediaを参照してください。

解析しよう

やること

やることは次の2つです。

考え方

「双方のプレイヤーの指の本数」と「そのターンに行動できるプレイヤー」をまとめてゲームの「状態」として、全ての状態について調べるというのが基本の考え方です。

指の本数が0~4本のルールについて考えてみると、状態数は多くても44×2=5124^4\times2=512個であり、余裕で全ての状態について調べられそうなことがわかります。左右の手の区別をなくせばさらに状態数が減りそうです。

つぎに「勝利が確定」とは何かということを考えます。
とりあえず「先手の勝利が確定する状態」とはどのような状態であるかを考えてみましょうか。

先手の勝利が確定する状態とは……
それ以降後手がどのような操作をしても……先手が適切に操作することによって……有限回?のターンで先手が勝利することができる状態……???

よくわかりません。数式を全く使わず物事を考えるのはたいへん難しい[3]ので、まず例のゲーム自体を雑に定式化[4]してしまいましょう。

ゲームは、5つ組G=(S,p,T,w,s0)G = (S, p, T, w, s_0)で与えられる。ここで

  1. SSは初期状態から到達可能な全ての状態の有限集合である。
  2. ppはプレイヤー関数S{先手,後手}S\to\{\text{先手},\text{後手}\}であり、この関数は状態が与えられたときに、その状態を遷移させることができるプレイヤーを与えるものである。
  3. TTは状態遷移関数S2SS\to 2^S[5]であり、この関数は状態が与えられたときに、次に遷移することができる状態の集合を与えるものである。
  4. wwは勝者関数S{,,}S\to\{先手,後手,ゲーム継続\}であり、この関数は状態が与えられたときに、その状態に至ることで片方のプレイヤーが勝利するならば勝者のプレイヤーを、そうでなければゲーム継続を与えるものである。
  5. s0Ss_0\in Sはゲームの初期状態である。

できました。オートマトンっぽくてかわいいですね!これで(S,p,T,w,s0)(S, p, T, w, s_0)を適切に設定することで、例の手遊びを表現することができます。

いま求めたいのは、先手の勝利が確定する状態全てからなる集合W先手W_\text{先手}です。ここで、次のことがいえます。

  1. 任意のsSs\in Sについて、w(s)=先手w(s)=\text{先手}ならば、明らかにss\inW先手W_\text{先手}である。
  2. 任意のsSs\in Sについて、p(s)=先手p(s)=\text{先手}かつ、あるtT(s)t\in T(s)が存在してtW先手t\in W_\text{先手}ならば、先手がssからttに状態を遷移させることで先手の勝利が確定するから、sW先手s\in W_\text{先手}である。
  3. 任意のsSs\in Sについて、p(s)=後手p(s)=\text{後手}かつ、すべてのtT(s)t\in T(s)についてtW先手t\in W_\text{先手}ならば、後手は先手の勝利が確定する状態に遷移させるしかないので、sW先手s\in W_\text{先手}である。

逆に、1番をもとにして2, 3番を根拠にW先手W_\text{先手}に含まれる状態の集合WWを広げていけば、最終的にW=W先手W=W_\text{先手}となりW先手W_\text{先手}が求められそうな気がします[6]。考え方はミニマックス法に非常に近いです。これを擬似コードにすると以下のようになります。

  1. W{sSw(s)=先手}W\gets\{s\in S\mid w(s)=\text{先手}\}
  2. p(s)=先手p(s)=\text{先手}かつ、あるtT(s)t\in T(s)が存在してtWt\in W
    または
    p(s)=後手p(s)=\text{後手}かつ、すべてのtT(s)t\in T(s)についてtWt\in W
    を満たすsSWs\in S\setminus W[7]が存在する限り、WW{s}W\gets W\cup\{s\}を繰り返す
  3. WWが求めるW先手W_\text{先手}である。

W後手W_\text{後手}も同様にして求めることができそうです。
また、SSからこれらを除外した状態の集合S(W先手W後手)S\setminus(W_\text{先手}\cup W_\text{後手})に含まれる状態では、双方のプレイヤーが最前を尽くした場合にゲームが終了しないことがわかります。千日手です。

実践

勝利が確定するような状態の求め方がわかりましたが、状態を列挙して文字を吐き出すだけだとあまり面白くありません。ここはどうにかして可視化したいです。

そのためにgraphvizというツールを使いました。
graphvizはDOT言語というグラフを記述する言語を画像化してくれるすごいやつで、つまるところ

digraph {
  a [label="first\nf{1, 1}\ns{1, 1}"]
  b [label="second\nf{1, 1}\ns{1, 2}"]
  c [label="second\nf{1, 2}\ns{1, 1}"]
  d [label="second\nf{0, 2}\ns{1, 1}"]
  a -> b
  a -> c
  a -> d
}

↑これが
graph
↑こうなります。

このように、グラフのノード(頂点)をゲームの状態、矢印を状態遷移としてゲームの流れを可視化してしまいましょう。
ゲームを解析してDOT言語として出力するプログラムを書きました。
https://github.com/roodni/finger-game-solver

ついに記事の目標が達成されます。手始めに、私の文化圏で最も流通していたmod5、分身結合が常に可能、自分への攻撃も可能ルールにおける先手の勝ちパターンを可視化しましょう。
mod5、分身結合が常に可能、自分への攻撃も可能ルールの先手勝利
素晴らしい!!!私が小中学生のとき探し求めた勝利法の全てが解き明かされたわけです。
グラフの読み方ですが、赤色の矢印が先手プレイヤーの選択で、青色の矢印が後手プレイヤーの選択です。また、赤色に塗りつぶされたノードは先手の勝利状態(w(s)=先手w(s)=\text{先手}となること)を示しています。
グラフを読んでいると「自分が{3,3}で相手が{1,4}のときに勝利確定」など意外と発見があります。感動的ですね。また、グラフに初期状態が含まれていないので、このゲームは先手必勝ではないということもわかります。

次は千日手の可視化です。これで私はこの手遊びの全てを理解……
mod5、分身結合が常に可能、自分への攻撃も可能ルールの千日手
なんだこれは。読めたものではありません。
仕方がないので初期状態から千日手の流れを幅優先探索して、既出の状態を灰色の輪郭で示し探索を打ち切るようにグラフの作りを変えてみます。
mod5、分身結合が常に可能、自分への攻撃も可能ルールの千日手改
今度はやたら横に長くなってしまいました……こちらは拡大すれば読めるのですが、ブログに写真を貼るのは難しそうです。興味のある方はプログラムを実行する[8]か、解析プログラムを自作するかしてみてください。

面白かったグラフをいくつか紹介します。
mod4ルールの千日手
↑これは指を1本減らしたmod4ルールにおける千日手のグラフです。相手が勝ちパターンをすべて把握していれば、当然このグラフから外れた瞬間に負けが確定します。
指を一本減らすだけでゲームの規模が極端に小さくなってしまうのです。mod5ルールがよくできていることがわかります。

mod5ルール、後手必勝
↑これは自分への攻撃および分身を禁止し、さらに指本数が5以上になったらその手は消滅というルールにおける後手の勝ちパターンです。初期状態が含まれているので、このルールでは後手が必勝であることがわかります。
調べてみると、分身、自分への攻撃、mod5がどれか一つでも可能なルールでは必勝法が存在しないということがわかります。このゲームが先手必勝または後手必勝となるのはルールが非常に厳しいときに限られるということです。

おわり

おわりです。ありがとうございました。
本当はコンピュータと対戦できるブラウザゲームを作って公開したかったんですが、2日前までゲーム制作を放置していたので間に合いませんでした。愚かですね。[9]
あるいは、ゲームを作り慣れていれば間に合わせることができたのかもしれません……[10]

明日はtarorynさんとEruさんの記事です。お楽しみに!


  1. ペニーワイズからはオススメピエロのイメージが抜けなくなってしまいました。 ↩︎

  2. ここでいう「グラフ」は「棒グラフ」や「円グラフ」のグラフではなく、状態遷移図やフローチャートに近いものです。 ↩︎

  3. 私の国語力がないだけかもしれません。 ↩︎

  4. 私はゲームの理論やAIのことを勉強したことがないので、表し方が一般的なそれと大きく異なっているかもしれません。お許しください。おそらくこのゲームは「二人零和有限確定完全情報ゲーム」に属するのですが、二人零和有限確定完全情報ゲーム - Wikipediaを調べても一般的な定式化の方法が見つからず、面倒になってそれ以上調べることを諦めてしまいました。 (2019.12.3追記: 「有限」ではありませんでした) ↩︎

  5. 2S2^SSSのべき集合の表記で、SSの部分集合全体の集合を表します。 ↩︎

  6. 求められそうな「気がします」と書いたのは、この方法によって求めたW先手W_\text{先手}が本当に勝利が確定する状態「全て」からなる集合であるかどうかを示していないからです。証明を考えていたら頭が爆発してしまいました。すみません、たぶん大丈夫だと思うので、どうか見逃してください…… ↩︎

  7. SWS\setminus WSSからWWを引いた差集合で、SW={xSx/W}S\setminus W=\{x\in S\mid x\notin W\}です。 ↩︎

  8. 実行にはC++のコンパイラ、make、graphivzが必要です。 ↩︎

  9. 私はつい1週間前にもギリギリまで放置したレポートで苦しんでいました。経験から何も学んでいないようです。 ↩︎

  10. ゲームをたくさん作ろう! | 東京工業大学デジタル創作同好会traP ↩︎

この記事を書いた人
shirodoni

すきなものは振り子です。

この記事をシェア

このエントリーをはてなブックマークに追加

関連する記事

2019年12月11日
円周率が無理数であることの証明【AdC2019 42日目】
Tarara
2019年12月11日
ぷよぷよってナンですか?【AdC2019 42日目】
arahi10
2019年12月10日
ブログ投稿ツイートを無理やり自動化した話【AdC2019 41日目】
xecua
2019年12月10日
理工系科目英語クラスについて【AdC2019 41日目】
kano
2019年12月9日
大学生活を豊かにする自己管理ツール集【AdC2019 40日目】
Deka
2019年12月8日
ハッカソンに参加して素材を作った話
NABE

活動の紹介

カテゴリ

タグ