人生ゲーム


4-Jul-2013
Nobuhide Tsuda

自己紹介

名前:津田伸秀

サイト: http://vivi.dyndns.org/

facebook:https://www.facebook.com/nobuhide.tsuda

twitter:vivisuke

ぼちぼちソフト作家、年齢不詳のおじさん、自宅研究員(主席)

趣味:テニス、オセロ、思考ゲーム・パズル類

Qt/C++ 使い, 一応webアプリ(PHP, JS, jQ, SQL)も出来るよ

Windows用テキストエディタ ViVi を延々開発中

Android・tmlib のパズルアプリも公開中だよ

迷走中、お仕事募集中でござるぞ

Geme of Life

  • ルール詳細
  • ランダムパターン→定常状態の分類
    • 定常状態(固定物体)
    • 周期パターン(振動子)
    • 移動パターン(移動物体)
  • ペントミノ
  • 導火線
  • シャトルの元
  • コンウェイの予想

ほげ

  1. ほげ
  2. ふが
  3. ふー
  4. ばー

人生ゲームと言えば・・・


ではなくて・・・

Conway's Game of Life


  • 1970年に英国数学者 Conway が考案
    • 現在はプリンストン大学教授
  • サイエンス誌に紹介され、大ブームに
    • http://ja.wikipedia.org/wiki/ライフゲーム
    • 生命の誕生、進化、淘汰などのプロセスを簡易的なモデルで再現したシミュレーションゲーム
    • ゲームと言っても、通常のゲームの様なゴールは無い
    • 日本語では何故か「ライフゲーム」

    「ハウエ ケスマ」


    「デモプログラムである」

    「無害なソフトと推測」



    デモンストレーション

    ルール詳細

    • 2次元 2値セル・オートマトン
    • 自分自身、8近傍セル状態により次の状態が決まる
    • 8近傍セルについて値がONのセル数をNとする
      • N==3 ならばON (誕生・維持)
      • N==2 ならば現状維持
      • N<2 or N>3 ならばOFF (過疎・過密)

    ライフゲームの性質

    • 確定的
    • 不可逆
    • 情報伝達は1セル/世代が最大
      • → (特殊相対論的な)光速と呼ばれる
    • 対称性保存
    • 安定状態は3種に分類される
      • 固定物体
      • 振動子
      • 移動物体

    固定物体

    • 4セル
      • ブロック
      • タブ
    • 5セル
      • ボート
    • 6セル
      • 蜂の巣
      • 空母
      • へび
    • 7セル
      • パン
      • イーター

    振動子

    • 周期2~
    • 周期数千を超えるものもある
      • ブリンカー
      • ヒキガエル
      • ビーコン
      • パルサー
      • ギャラクシー
      • ペンタデカスロン

    移動物体

    • グライダー
    • 宇宙船

    できるかな?



    ・導火線

    Conway の予想


    • ペントミノ等を体系的に調査
    • 予想:生きたセル数が無限に増え続けるパターンは無い
    • 肯定的 or 否定的に証明したものに賞金 $50 
      • 期限:1970年末
    • 否定的に証明するには?
    • 無限に増え続けるパターン
      • 移動物体生成
      • 移動しながら痕跡を残す

    グライダーガン

    • MITのゴスパーらのグループが挑戦
    • シャトルの元
    • シャトル
    • 衝突パターンの自由度
      • 間隔
      • 横方向のズレ
      • 位相、位相差
      • 90度ずらす?
    • 一ヶ月程度で「グライダーガン」発見
      • 見事に $50 ゲット

    教訓


    • エレガントな証明が不可能 → エレファントな証明
    • 組み合わせ爆発を抑えることが肝要
    • 対象の理論的・実験的な調査分析が必要


    GameOfLife

    By Nobuhide Tsuda