指のゲーム(その2)

ちょっと時間が空いてしまいましたが 前回の続きです

(前回まで)夏のお盆休みに帰省したら姪っ子が両手の指でやる遊びを
もちかけてきた。その遊びは以前知っていた遊びにルールを追加した
ものだった。その遊びとは….

さて、姪っ子の言い出したゲームのルールは次のようなものでした。

プレーヤー:2人
初期状態:プレーヤーは両人とも 左右の手をだし、そのうち1本の指を立てる。
プレー:先手と後手を決め、交互につぎのいずれかの動作を行う。

  • 1)[攻撃] 自分の左右のどちらかの手で、相手のどちらかの手をタッチする。
    その際、相手のタッチされた手の指の本数は、タッチした手の指とタッチされた指の
    本数の合計になる。もしも合計が5だったらその手はdeadになる。また、もしも
    合計が5を超えていた場合には その合計を5で割ったあまりになる。

  • 2)[守備] 自分の手の好きに選んだ一方の手から もう一方の手に好きに指定した
    指の本数を移動することができる(移動する本数は1本からその手の指全部まで、すきに
    選んでいいらしい)。移動先の手の指の本数(移動前の本数と移動する本数の合計)が
    5以上であった場合には 5で割ったあまりになる。(そのため、一方の手が0本になる
    ということもありうる。これはDeadではなく、0本を保持する。)

  • 3)[リセット] 2)の動作の特別の場合として、移動の結果、両方の指が0本に
    なってしまうときは、両方の手を初期状態の1本ずつにしないといけない。

勝利条件:相手の両方の手を deadにしたら勝ち。


だそうです。えーと、第一印象としては そんなに動作の選択肢を多くしちゃったら
まず間違いなく引き分け(千日手状態)になるだろうな、と思いました。が、やっぱり
それを検証しなくては。
#小学校2年生の姪っ子相手の場合、彼女は相手の手が片方でもDeadにできるときは
#かならず攻撃してくるので、自分の手が片方だけDeadにされた後、カウンターで相手を
#攻撃できて、その後 互いに片方の手だけになったあとは自動的にこちらが勝利する
#というようなパターンを選べば 勝利できます。笑
そういうわけで、上記のゲームを解析するプログラムを書くことにしました。
基本的に こういうゲームの解析は 再帰的関数を利用することになるのだと
思います。が、千日手状態がありうるので、再帰がどこまでいっても帰ってこない
場合があります(というか今回の場合、そんなのばっかりww)。
こういう引き分け状態がありえるゲームを解析するプログラムをどうやって書けば
いいのか、を考えるのが とても面白そうだったのでやってみたのです。
#私、プログラミングは 素人に毛が生えた程度です。
考えた大まかなアルゴリズムは以下のとおりです。自分へのメモとして書いておきます。

  • I)必要とするグローバルなデータ構造
    • 1)ゲームの遷移木
      木のノードの構造体:構造体のメンバーは以下の通り
      ・次のゲーム状態のノードへのポインタ(20個の配列にした)
      ・次のゲーム状態への分岐がいくつあるか
      ・[盤面]ゲームの途中経過を格納する変数群
      ・[状態]このゲームの途中経過から始めたとき、先手必勝か後手必勝か引き分けかを格納する変数
      ・[状態]は 「未知」、「先手」、「後手」、「分け」、「解析中」の5通りの値を持ちうる。

    • 2)全ての[盤面]について [状態]を格納しておく配列Result
    • 3)各要素に[盤面]を格納できる配列。スタックのように使う。初期状態は空スタック。
  • II)アルゴリズム
    • 1)メイン関数
      内容:
      [盤面]にゲームの初期状態を格納したROOTノードをつくり、分岐は0とし、[状態]も未知にする。
      ROOTへのポインタを引数にして、次の関数を呼び出す

    • 2)与えられたポインタの示すノードの[盤面]が先手必勝か、後手必勝か、引き分けかを判別する関数
      引数(ノードへのポインタ)
      内容:
      ・配列Resultを参照して、引数の示すノードの[盤面]が 未知でないならその値を返す。
      ・現在の[盤面]が終了状態(先手の打つ手が存在しない)なら、「後手」を返す。
      ・スタックの中に 現在の[盤面]が無いか調べて、もしもあれば「解析中」を返す。
      ・スタックに 現在の[盤面]をプッシュする。
      ・[状態]を格納する配列Next を用意する。
      ・現在の[盤面]から先手ができるすべての次手を網羅して、その手を行った後の盤面の
      先手と後手を入れ替えた[盤面]を格納するノードをつくり、現在のノードからの分岐に加え、
      新たに作ったノードへのポインタを引数にしてこの関数を再帰呼び出しする。
      ・再帰呼び出しからの戻り値を 配列Nextに1つずつ格納していく。
      ・すべての可能な次のノードがすべて調べ終わったら、つぎのことを行う。
      ・スタックを1つポップ。
      ・配列Nextのなかに 「後手」が1つでもあれば 現在の[盤面]は先手必勝なので「先手」を返す。
      ・配列Nextのなかに「後手」がなく、かつ、1つでも「引き分け」があれば 現在の[盤面]は引き分けなので「分け」を返す。
      ・配列Nextのなかに「後手」も「分け」もなく、かつ、1つでも「解析中」があれば「分け」返す。
      ・以上のどれでもないときは 配列Nextはすべて「先手」つまり、どうやっても現在の先手が負けるので「後手」を返す。

えーと、いまこうやってアルゴリズムを見返すと恥ずかしいかぎりですが、まぁいいや公開しちゃお。
[状態]を格納する配列があれば データ木の構造はいらない気もしますね。まぁ、それはあとあと
いろいろ解析するために、あるのだ、ということにしておいてください。その他細かい部分ははしょって
核心部分だけを書いています。(実際には ノードには他にもデータを格納している)
ポイントとなるのは 次の点です。

定理:解析したい盤面に対して、次が成り立つ。

  • 1)その盤面での先手が打つ手のどれか1つに対して、打った状態から始めると「後手必勝」なら、もともとの盤面は「先手必勝」。
  • 2)その盤面での先手が打ついかなる手に対しても(打つ手が無いときを含む)、打った状態から始めると「先手必勝」なら、もともとの盤面は「後手必勝」。

ここまではいいのですが、引き分けがありえる場合、上の2つの性質だけでは盤面が先手必勝か後手必勝か決まりません。初期状態から初めて各局面での分岐をたどっていくと、ループに陥ってしまいます。
そこで、次の場合が問題となります。

3)その盤面で先手が打つ手のどれをとっても 次局面で「後手必勝」にはならないが、先手のうつ手の1つに対して 次局面は 初期状態から現在の局面までに現れた局面であるとき。

このとき、どうすればいいのか、が問題です。結果から言うと、そのときは「引き分け」にしてしまっていいのです。つまり つぎの性質を追加します。

3’)その盤面で先手が打つ手のどれをとっても、次局面で「後手必勝」にはならないが、先手の打つ手の1つに対して 次局面は 現在までに現れた盤面もしくは「分け」であるとき、もともとの盤面は「分け」

3’)をアルゴリズムに加えても、初期状態の局面解析には悪影響を与えません。
なぜか、、は説明するのが面倒なので 省こうかな。。。
一言だけ書くと、3)の状態のときは「本当に引き分け」もしくは「最善で打つならそのような盤面にはならない解析不要な分岐」のどちらかだからです。
P.S. 問題:
もしも相手が姪っ子のアルゴリズム(相手をDeadにできるときは必ずする)で動くと仮定するとき、
次の局面から必ず勝つにはどうすればいいでしょうか?
自分:4本、4本、 --- 相手:4本、3本
(つづく)

広告

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中