feature image

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

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

例の手遊び

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

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

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

解析しよう

やること

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

考え方

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

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

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

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

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

ゲームは、5つ組で与えられる。ここで

  1. は初期状態から到達可能な全ての状態の有限集合である。
  2. はプレイヤー関数であり、この関数は状態が与えられたときに、その状態を遷移させることができるプレイヤーを与えるものである。
  3. は状態遷移関数[5]であり、この関数は状態が与えられたときに、次に遷移することができる状態の集合を与えるものである。
  4. は勝者関数であり、この関数は状態が与えられたときに、その状態に至ることで片方のプレイヤーが勝利するならば勝者のプレイヤーを、そうでなければゲーム継続を与えるものである。
  5. はゲームの初期状態である。

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

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

  1. 任意のについて、ならば、明らかにである。
  2. 任意のについて、かつ、あるが存在してならば、先手がからに状態を遷移させることで先手の勝利が確定するから、である。
  3. 任意のについて、かつ、すべてのについてならば、後手は先手の勝利が確定する状態に遷移させるしかないので、である。

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

  1. かつ、あるが存在して
    または
    かつ、すべてのについて
    を満たす[7]が存在する限り、を繰り返す
  2. が求めるである。

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

実践

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

そのために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、分身結合が常に可能、自分への攻撃も可能ルールの先手勝利
素晴らしい!!!私が小中学生のとき探し求めた勝利法の全てが解き明かされたわけです。
グラフの読み方ですが、赤色の矢印が先手プレイヤーの選択で、青色の矢印が後手プレイヤーの選択です。また、赤色に塗りつぶされたノードは先手の勝利状態(となること)を示しています。
グラフを読んでいると「自分が{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. のべき集合の表記で、の部分集合全体の集合を表します。 ↩︎

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

  7. からを引いた差集合で、です。 ↩︎

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

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

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

shirodoni icon
この記事を書いた人
shirodoni

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

この記事をシェア

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

関連する記事

2019年12月21日
モデリングを始めてみたい君へ、MagicaVoxelのススメ
isak icon isak
2019年12月13日
ゲーム紹介「League of Legends」【AdC2019 44日目】
Yataka_ML icon Yataka_ML
2019年12月25日
TensorFlow.jsでwasmを使ってみるためにコントリビュートした【AdC2019 56日目】
sappi_red icon sappi_red
2019年12月25日
無料でDTM環境構築 電子音系編
liquid1224 icon liquid1224
2019年12月22日
部内製チャットサービス「traQ」UIのこれから 【AdC2019 53日目】
sigma icon sigma
2019年12月23日
無料でDTM環境構築 生音系編
kashiwade icon kashiwade
記事一覧 タグ一覧 Google アナリティクスについて