Game Description Language

はじめに

今回は何もできないけど何でも表現できる言語を紹介します。

なお本記事は私が大学で研究していた時の資料や海外の論文を元に執筆しているので、不確実な情報や誤訳が含まれている可能性があります。

Game Description Language

ゲームを記述するための論理型言語です。

論理型言語自体あまり知名度はないと思いますが、ひたすら定義を積み重ねていき与えられた命題を解くようにプログラミングしていきます。
Prologという言語がその中で最も有名です。

Game Description Language (以下GDL)はGeneral Game Playingというスタンフォード大学のプロジェクトで使用されています。
まずこちらのプロジェクトについて簡単に説明します。

General Game Playing

未知のゲームをプレイするエージェントの設計を目標とするプロジェクトです。
(エージェント ≒ コンピュータープレイヤー)

例えば少し前に将棋や囲碁の人工知能がプロ棋士と同等かそれ以上の強さを持つようになり話題になりました。
そのような人工知能は特定のゲームに特化して膨大な学習を行い、強化していく特化型です。
一方、General Game Playing (以下GGP)はどんなゲームでもそれなりにプレイできる汎用型の人工知能を目指しています。
つまり未知のゲームだとしてもそれを解析して、最適な手を打つように学習させる必要があります。

このGGPにおいてゲームのルールやコンポーネントを記述するための規格としてGDLが採用されています。

GDLの特徴

• 宣言的記述
• 再帰による繰り返し
• わずかなキーワード
• ライブラリがない(概念がない)
  • 標準出力がない
  • 数学的概念がない (つまり四則演算もできない)
• 2つの記法
  • 前置記法 prefix
  • 中置記法 infix

このような特徴をみれば、この言語のつらさが想像できると思います。
一見複雑なゲームなんて定義できなさそうですが、実際には○×ゲーム(三目並べ)から将棋まであらゆるゲームを定義することができます。

記法についてはprefixの方がメジャーなので、以降はprefixで説明します。

要素

コードは英数字と_で構成されます。数字も全て文字列として扱われます。
prefixは大文字小文字を区別しません。(基本的に小文字で書きます)

• object constant: 事物
  • a, game_id
• variable: 変数
  • ?x, ?pos
  • ?から始める
• functional term: 事実
  • (cell 0 0 b)
  • cellが事実の名前(キーワード)、それ以降が引数
• term: an object constant, a variable, or a fuctional term

(日本語の資料がないので訳はPrologから引用してます)

Rule

GDLはtermを組み合わせて作るruleで構成されています。

(<= (cell ?x ?y)
    (one ?x)
    (two ?y))

(cell ?x ?y)の?xと?yは変数ですが、それぞれ(one ?x)の?xと(two ?y)の?yは同じtermが入ります。
前半の(cell ?x ?y)の部分をhead、後半をbodyといいbodyのtermをsubgoalと呼びます。

この場合、(one ?x)かつ(two ?y)のとき(cell ?x ?y)が成り立つという意味です。
つまり(one 1) (two 2)という2つのtermが与えられた場合、(cell 1 2)という事実も成り立つことになります。

論理演算子

先ほどのruleはこう書くこともできます。

(<= (cell ?x ?y)
    (and (one ?x) (two ?y)))

またこの2つは等価です。

(<= (cell ?x ?y)
    (or (one ?x) (two ?y)))

(<= (cell ?x ?y)
    (one ?x))

(<= (cell ?x ?y)
    (two ?y)

否定はnotを使います。

(<= (cell ?x ?y)
    (not (one ?x)))

and or notは予約されているキーワードで、functional termの名前として使うことはできません。

ゲームのルール

ゲームのルールは以下の6つの要素を定義することで表現します。

• Players: プレイヤー
• Initial State: 初期状態
• Legal Moves: ある状態においてプレイヤーが取り得る手 (合法手)
• Game State Update: 現在の状態とプレイヤーが選択した手によって示される次のターンの状態
• Termination: ゲームが終了する条件
• Goal States: 勝利条件

ゲームを定義するキーワード

ゲームのルールをGDLで表現するには、以下に示したfunctional termのキーワードを使います。
どのように使うかは次の章で実際のゲームの例を元に解説しているので、雰囲気を知りたい方は読み飛ばしてください。

• $role(a)$: $a$ というrole(プレイヤー)が存在する
  • $a$: roleを示すobject constant
• $input(r, a)$: role $r$ は $a$ という手を選択できる
  • 合法手の定義
• $base(p)$: $p$はゲームの状態を示す
  • $p$: functional term (以下同様)
• $init(p)$: $p$がゲームの初期状態である
• $legal(r, a)$: role $r$ は現在 $a$ という手を選択できる
• $next(p)$: 次の状態は $p$ である
• $goal(r, n)$: role $r$ の勝利条件は $n$ である
• $terminal$: 終了条件を定義する
• $true(p)$: 現在の状態は $p$ である
  • $next$ や $legal$, $terminal$ のsubgoal(条件)として使用する
• $does(r, a)$: 現在の状態でrole $r $が $a$ という手を選択するということ
  • $next(p)$ のsubgoalとして使用する
• $distinct(a, b)$: $a$ と $b$ は異なる
  • subgoalとして使用する

サンプルコード

三目並べ(○×ゲーム)は次のように定義できます。
;で始まる行はコメントです。

tic-tac-toe.kif

;; Roles

(role xplayer)
(role oplayer)

;; Base & Input

(index 1) (index 2) (index 3)
(<= (base (cell ?x ?y b)) (index ?x) (index ?y))
(<= (base (cell ?x ?y x)) (index ?x) (index ?y))
(<= (base (cell ?x ?y o)) (index ?x) (index ?y))
(<= (base (control ?p)) (role ?p))

(<= (input ?p (mark ?x ?y)) (index ?x) (index ?y) (role ?p))
(<= (input ?p noop) (role ?p))

;; Initial States

(init (cell 1 1 b))
(init (cell 1 2 b))
(init (cell 1 3 b))
(init (cell 2 1 b))
(init (cell 2 2 b))
(init (cell 2 3 b))
(init (cell 3 1 b))
(init (cell 3 2 b))
(init (cell 3 3 b))
(init (control xplayer))

;; Game State Update

; Cell

(<= (next (cell ?m ?n x))
(does xplayer (mark ?m ?n))
(true (cell ?m ?n b)))

(<= (next (cell ?m ?n o))
(does oplayer (mark ?m ?n))
(true (cell ?m ?n b)))

(<= (next (cell ?m ?n ?w))
(true (cell ?m ?n ?w))
(distinct ?w b))

(<= (next (cell ?m ?n b))
(does ?w (mark ?j ?k))
(true (cell ?m ?n b))
(or (distinct ?m ?j) (distinct ?n ?k)))

; Turn

(<= (next (control xplayer))
(true (control oplayer)))

(<= (next (control oplayer))
(true (control xplayer)))

;; Legal Moves

(<= (legal ?w (mark ?x ?y))
(true (cell ?x ?y b))
(true (control ?w)))

(<= (legal xplayer noop)
(true (control oplayer)))

(<= (legal oplayer noop)
(true (control xplayer)))

;; Goal States

(<= (row ?m ?x)
(true (cell ?m 1 ?x))
(true (cell ?m 2 ?x))
(true (cell ?m 3 ?x)))

(<= (column ?n ?x)
(true (cell 1 ?n ?x))
(true (cell 2 ?n ?x))
(true (cell 3 ?n ?x)))

(<= (diagonal ?x)
(true (cell 1 1 ?x))
(true (cell 2 2 ?x))
(true (cell 3 3 ?x)))

(<= (diagonal ?x)
(true (cell 1 3 ?x))
(true (cell 2 2 ?x))
(true (cell 3 1 ?x)))


(<= (line ?x) (row ?m ?x))
(<= (line ?x) (column ?m ?x))
(<= (line ?x) (diagonal ?x))


(<= open
(true (cell ?m ?n b)))

(<= (goal xplayer 100)
(line x))

(<= (goal xplayer 50)
(not (line x))
(not (line o))
(not open))

(<= (goal xplayer 0)
(line o))

(<= (goal oplayer 100)
(line o))

(<= (goal oplayer 50)
(not (line x))
(not (line o))
(not open))

(<= (goal oplayer 0)
(line x))

;; Termination

(<= terminal
(line x))

(<= terminal
(line o))

(<= terminal
(not open))

参考: ggp.org

要所解説

論理型言語を初めて読んだ方はこのあたりで絶望していると思うので、分かりづらいところを解説していきます。

(index 1) (index 2) (index 3)
(<= (base (cell ?x ?y b)) (index ?x) (index ?y))
(<= (base (cell ?x ?y x)) (index ?x) (index ?y))
(<= (base (cell ?x ?y o)) (index ?x) (index ?y))
(<= (base (control ?p)) (role ?p))

(cell ?x ?y ?p)は盤の状態を表しています。
?p = {b, x, o} ?x = {1, 2, 3} ?y = {1, 2, 3}が入ります。
baseはいわば型定義のようなものです。baseで定義したtermはtrueやnextで使用することができます。

(base (control ?p))はどちらのプレイヤーのターンかを表しています。
GGPではターンの管理をしないので1ターンにどちらのプレイヤーも手を打つことができてしまいます。

(<= (input ?p (mark ?x ?y)) (index ?x) (index ?y) (role ?p))
(<= (input ?p noop) (role ?p))

これらは手の選択肢を表していますが、このnoopというのは何もしないという意味です。
自分のターンでないプレイヤーにnoopという選択肢を与えることで「自分のターンしかmarkできない」ように制御しているのが以下のコードです。

(<= (legal xplayer noop)
(true (control oplayer)))

(<= (legal oplayer noop)
(true (control xplayer)))

次のコードにはdistinctというキーワードが登場します。

(<= (next (cell ?m ?n ?w))
(true (cell ?m ?n ?w))
(distinct ?w b))

?wはbでないという意味なので、?wにはoまたはxが入ります。
つまり既に○×が書かれているマスは次のターンも同じ状態ということです。
そんな自明なことを定義して意味があるのかというと、残念ながらGGPでは前の状態を引き継ぐようにはなっていないので全ての状態遷移を定義する必要があります。

(<= (next (cell ?m ?n b))
(does ?w (mark ?j ?k))
(true (cell ?m ?n b))
(or (distinct ?m ?j) (distinct ?n ?k)))

こちらは空のマス (つまり(cell * * b))の状態遷移を定義しています。
(or (distinct ?m ?j) (distinct ?n ?k))は ?m == ?j && ?n == ?kでないという意味なので、即ちこのコードはmarkした座標以外の空マスを次の状態に引き継ぐことを意味しています。

(<= (line ?x) (row ?m ?x))
(<= (line ?x) (column ?m ?x))
(<= (line ?x) (diagonal ?x))

lineは三目並んでいる状態を表します。

拡張言語

GDL-II

= Game Description Language for games with incomplete information

• 不完全情報ゲームを記述できるGDL
• 次のキーワードが追加
  • $percept(r, p)$: role $r$ は $p$ を知っている
  • $sees(r, p)$: role $r$ は次の状態で $p$ と分かる
  • $random$: ランダムに打つ手が予め定義されたrole

Ludi GDL

• GDLより高級な言語
• 予め基本的なコンポーネントが用意されている
• Ludiというゲームをデザインするフレームワークで使用されている

三目並べの記述例

(game Tic-Tac-Toe
	(players White Black)
	(board
		(tiling square i-nbors)
		(size 3 3))
	(end (All win (in-a-row 3))))

• Ludiまとめ
• Ludiについて書いた記事 → ゲームを生み出す人工知能に学ぶ論理的ゲームデザイン

おわりに

GDLはGGPプロジェクト以外ではほぼ活用されておらず、またGGP自体も最近の活動は下火のようです。

GDLを動作させる環境としてggp-baseというOSSがあり、任意のゲームをコンピュータとプレイすることができます。
またエージェントや人間がプレイするためのUIも開発することができるようです。

参考文献

• 自分のScrapbox
  • General Game Playing
  • Game Description Language
  • Ludi
• General game playing - Wikipedia
• General Game Playing (Synthesis Lectures on Artificial Intelligence and Machine Learning)
  • Google Bookで一部のページが公開されています
  • Amazonで購入できます
• ggp.org/base
  • 将棋やチェスなど様々なゲームのGDLが公開されています