ゲームの抽象化の各種アプローチの整理メモ

[stepney141]

ゲームの分類

• 人数
  • 2人が基本 (3人以上も当然ありうる)
  • プレイヤーの存在しない0人ゲームも存在する (ex. ライフゲーム)
  • パズルやクイズは1人ゲーム (ex. ソリティア)
• 利得の合計
  • ゼロ和 or 非ゼロ和
• 有限 or 無限
  • 有限なら、ゲームが終了するために満たすべき条件が与えられている
  • 無限ゲームの実装は現実的に難しい（やるとしたら一時停止ボタンを付けるとかが必要）
• 確定 or 非確定
  • ゲームの進行が確定的ではない (≒ランダム性が存在しない or する)
  • 着手が (局面, プレイヤーの選択) => 局面 という純粋関数ではないものとも解釈できる？
• 完全情報 or 不完全情報
  • ゲームの局面状態や他プレイヤーの行動など、全ての情報がプレイヤーに開示されている or いない

ボードゲームフレームワークは、以上のように表現される各要素を再現・実装できなくてはならない

ゲームの定式化

ゲーム木としての解釈

• 各盤面：ノード
• 着手：エッジ
• ※同時手番ゲームはどうやって表現する？

ゲーム情報学的な解釈

• ゲームにおける対象を表現するためのデータ構造と、対象を変化させるためのアルゴリズムの複合体とみなす
• データ構造：ゲームの状態(state) := 局面(position)
  • 局面 := 特定時刻におけるゲームの状態を過不足なく表現する情報の構造
  • どんな情報を「局面」として管理すべきかはゲームによって様々
  • 盤面の駒/石の配置、 手番、持ち駒、アゲハマ、etc...
  • 厳密には、開始からの局面の履歴もゲームの進行に必要である(千日手やコウの判定に必要)ため、特定時刻の局面だけで全てが説明できるわけではない
• アルゴリズム：各種手続きを組み合わせる
  • 合法な着手の列挙：(現在局面) => (可能な着手の集合)
  • 着手の合法性の判定：(現在局面, 着手) => (合法 or 非合法)
  • 勝ち負けの判定：(現在局面) => (勝ち or 負け or 未決着)
  • 次局面の生成：(現在局面, 着手) => (次局面)
  • 前局面の生成：(現在局面, 着手) => (前局面)
    • 実装によっては不要
    • 巨大なゲームの場合：一回の着手による局面の変化は微小→局面をthe single source of truthとして着手の度に書き換えていく方が効率的（前局面を求める手続きによって元に戻す）

Dagaz v1における解釈

• 盤面状態をdesignとboardに分ける
  • design：クライアント（ユーザー）が記述した情報をもとに生成・管理される、ゲームの情報
    • まずdesignクラスをインスタンス化し、メソッドを叩いてゲームの情報を設定する
    • designに含まれる情報：
      • 盤上の移動方向・マス目の位置
      • プレイヤーの情報（名前、移動方向の回転対称性）
      • move modes
      • 盤上の特殊エリア
      • 駒の名前・価値・動き
      • 盤面の初期状態
      • プレイヤーの着手順番
      • ゲームの挙動に関するオプション
    • designのメソッド
      • 新しい駒インスタンスの生成
      • マス目情報をIDから文字列に変換
  • board：ある時点におけるゲームの盤面状態
• API
  • games.model.getDesign() で design を初期化
  • design.getInitBoard() で board を初期化
  • board.generate() で board.moves: Array を生成
  • board.apply(move) で新しい board を生成

boardgame.ioにおける解釈

• 盤面状態をGとctxに分ける
  • G：クライアント（ユーザー）が記述する局面状態
    • TypeScript実装ではany型→局面状態はどんな形式にして扱ってもいい
    • チュートリアルのティクタクトーのように、マルバツの情報を持つマス目の配列としてもいいし、チェスならSGFやFENの文字列で盤面を表現してもいい
    • Gを変更するのがmove（着手）
  • ctx：フレームワークの中で生成・管理されるゲームのメタ情報
    • TypeScript実装ではちゃんと型が決まっている（ユーザーが好き勝手に形式を決めるようなものではない）
    • ユーザーはctxを書き換えることができないが、ctxを参照することはできる
    • ctxに含まれる情報：プレイヤー人数、現在が何ターン目か、現在の手番プレイヤー、プレイする順番、ゲーム終了後の勝敗結果、etc...
    • ctxを変更するのがevent
  • 盤面状態をGとctxのふたつに分けることにより、 ユーザーが考えるべきことを削減している
• 着手：move: G => G：現在局面から次局面への写像（純粋関数）
  • immer.jsを使っているため、return GをせずGを直接書き換える形でmoveを記述することも可能（内部でよしなに変換してくれる）
  • ただし、ひとつのmoveの中で、return GとGの変更とを同時に行うことはできない
• ゲームのルール記述
  • ゲーム名(必須)
  • ゲームの初期状態生成(必須)：setup: (ctx, setupData) => G
    • ctxを参照することで、例えばプレイヤー数などの情報によって初期状態が変化する場合に対応する
  • moveの定義(必須)
    • 着手の名称
    • move: (G, ctx, ...args) => G：現在局面から次局面への写像（純粋関数）
    • 着手をやり直し可能か
    • クライアントから実行可能か
    • 何手目でも実行可能か
    • プレイヤーが把握できる盤面情報の制限：playerView: (G, ctx, playerID) => G
  • turnの定義
    • turnの名前
    • turnの順番
    • turnの最初に実行する処理：onBegin: (G, ctx) => G
    • turnの最後に実行する処理：onEnd: (G, ctx) => G
    • turnの終了条件(これがtrueになったら現turnを抜ける)：endIf: (G, ctx) => true
    • moveの最後に実行する処理：onMove: (G, ctx) => G
    • 一回のturnの中で実行できるmoveの数の下限：minMoves: number
    • 一回のturnの中で実行できるmoveの数の上限：maxMoves: number
    • そのturnにおいて着手できるプレイヤー？
    • stageの定義
      • stageの名前
      • そのstageにおいて有効なmoveの定義
      • このstageの終了後、次に実行されるstageの名前：next: 'nextStageName'
  • phaseの定義
    • phaseの名前
    • phaseの最初に実行する処理：onBegin: (G, ctx) => G
    • phaseの最後に実行する処理：onEnd: (G, ctx) => G
    • phaseの終了条件(これがtrueになったら現phaseを抜ける)：endIf: (G, ctx) => true
    • このphaseの中だけで有効なmoveの定義
    • このphaseの中だけで有効なturnの定義
    • ゲーム開始時にこのphaseから始めるか否か
    • このphaseの終了後、次に実行されるphaseの名前：next: 'nextPhaseName' | (G, ctx) => 'nextPhaseName'
  • プレイヤーの最小人数
  • プレイヤーの最大人数
  • ゲームの終了条件：endIf: (G, ctx) => obj
    • この返り値は ctx.gameover から参照可能
  • ゲーム終了時に実行する処理：onEnd: (G, ctx) => G
  • ゲーム内の全てのmoveをやり直し不可能にするか
  • マルチプレイ時に状態の差分のみをJSONで送受信するか否か

Stockfish系の将棋ソフト類における解釈

• e.g. やねうら王
• 盤面状態をPositionクラスとBitboard構造体で持っている
  • Position: ゲーム進行全般に関する状態を管理
    • 一度しか作られず、盤面を進めたり戻したりする際は部分的にのみ更新する
    • 内部的にBitboardを呼び出す
  • Bitboard: 局面の状態のみを管理

Ludiiにおける解釈

• the "ludemic" approch

所見

• こうして考えてみると、ZRFのアプローチはあまりにも命令的だったのではないか
• DagazはZRFを出発点にしたことによって、ZRFの弱点をそのまま受け継いでしまった
• boardgame.ioにおける宣言的なゲーム記述の優位性
  • 汎用的であるがゆえに少々とっつきにくくはある
  • でも定式化がめっちゃスマート
• boardgame.ioはルール記述・Viewの実装にほぼ制約がないが、プログラミングの知識がないと使えない
  • 自由であるからこそ自分でプログラミングしなければならない部分が多い
  • 「ターン制」という概念に焦点を当てた抽象化
  • 「ターン」「フェーズ」「ステージ」という『ゲームの構造』に則ってゲームの状態遷移を記述する枠組みを提供し、ゲームの詳細なルールの記述はプログラマに任せる
  • ターン制という『ゲームの構造』に乗っかることによって、プログラマがゲームを実装しやすくなる
  • あくまでも『フレームワーク』であり、プログラマの開発を支援するためのもの
  • bgioが提供するのは、ゲームの全体的な流れをターン制（状態遷移）という普遍的な骨組みの上にドメイン知識を肉付けして得られるシステムとして記述する仕組みであり、ルールの記述は完全にプログラマの自由（流体力学で言うところのオイラー型）
  • 状態遷移に主眼を置いていることから、ゲームの表現力は「石」「駒」「カード」など使う道具によって左右されないし、人狼のようなそもそも道具を使わないゲームにも対応できる
• ZRF/Ludiiなど、既存のGGPエンジン/GDL文法は、ゲームの全体的な流れを各ゲームのルール（ドメイン知識）という流動的な要素の集合として記述する思想であり、提供するのはルールを記述する仕組みである
  • ターン制という「構造」は、各ゲームの「石」「駒」「カード」といった要素の織り成すダイナミクスの中に捨象される
  • ZRFは「ひとつひとつの駒の挙動」に注目してルールを記述させる（流体力学で言うところのラグランジュ型）
  • 「構造」に焦点を当てていない分、bgioのある種極端なほどの汎用性には欠ける
• Ludiiはルール記述・Viewにある程度の制約があるが、プログラミングの知識がなくても使える
  • ZRFなど既存のGame Description Languagesもこの路線
    • GDL自体、どこかで記述の制約がどうしても生まれてしまう概念であるといえる
    • Class Grammarの仕組みはこの制約を最小化するためのもの
  • プログラマの開発を支援するというよりも、ゲームデザイナーの制作を支援するもの

参考文献

• ゲーム計算メカニズム : 将棋囲碁オセロチェスのプログラムはどう動く(コロナ社, 2010)
• https://speakerdeck.com/qsona/game-model

[stepney141]

Dagaz v2における案

• ゲームルールを与えると、ゲームの初期状態・ゲーム計算の基本手続きを返すような関数を作る
• 状態: 2つ
  • ゲームの局面情報：v1のboard, bgioのG
  • ゲームのメタ情報：v1のdesign, bgioのctx
• 手続き: 4つ
  • 合法な着手の列挙：(現在局面) => (可能な着手の集合)
  • 着手の合法性の判定：(現在局面, 着手) => (合法 or 非合法)
  • 勝ち負けの判定：(現在局面) => (勝ち or 負け or 未決着)
  • 次局面の生成：(現在局面, 着手) => (次局面)