Game Description Language
ゲーム記述言語 ##
ここで扱うGDLはStanford版である
特徴
Datalogに影響を受けた論理型言語
再帰を多用する
非オブジェクト指向
わずかなキーワード
ライブラリはない
四則演算などの基本的な機能もなし
標準出力がない
GGPのゲームサーバーを使用して擬似的に出力は可能
2つの記法(前置記法・中置記法)がある
機能を追加したいくつかの派生言語が存在する
Tools
Eclipse用プラグイン
シンタックスハイライト
エラー、文法ミス、その他潜在的な問題の検出
インデント支援
ファイルにある余白のリフォーマット
Prefix記法に対応
使い方
プロジェクトを右クリックしてConfigure > Add GDL Validiation
GDLの文法エラーを検出
Prefix記法に対応
文法
Datalogとはわずかに異なる
構文はだいたい同じ
ポーランド記法を使う
変数は?から始まる
ルール(もし～なら…)の定義は以下の通りである
(<= (p ?x) (q ?x) (r ?x)) = (q ?x)かつ(r ?x)ならば(p ?x)
同じ名前の文の引数の数は同一であるべきである (Griddleより)
(zero 0 0)と(zero 0)を定義することは非推奨
キーワード
distinct: 2つの項(Term)が構文上異なる
does(?r, ?m): 現在の状態でplayer(またはrole)?rが 手?mを打つ
goal(?r, ?n): 現在の状態でrole?rのゴールが?nと定義する
init: 初期状態を定義する
legal(?r, ?m): 現在の状態で?mがrole?rの合法手と定義する
next: 次の状態を定義する
role: プレイヤー名を追加する
terminal: 現在の状態が終局状態であると定義する
true: 現在の状態を定義する
not: 否定
ルール
以下の要素をそれぞれ完全に定義しなければならない。
Players
役割を定義するもの。
Initial State
初期状態を示すルール
Legal Moves
あるプレイヤーが現在の座標で打てる手をそれぞれ定義したルール
Game State Update
現在からみた次の状態や全てのプレイヤーが打てる手を定義したルール
Termination
現在の状態が終局状態の一つである条件を定義したルール
Goal States
終局状態でそれぞれのプレイヤーにおけるゴール
拡張
GDLでは任意のプレイヤーを用いる有限のゲームのみ記述できる。しかし不確定要素や不完全情報ゲームは記述できず、GDL-II(GDL-Incomplete Information)では以下の2つが追加されている。
sees(?r, ?p): 次の状態で?rは?pだと分かる
random: ランダムに手を選ぶ定義済みのプレイヤーという定数
PrefixとInfix
Infix GDL: 中置記法
= HRF
Prefix GDL: 前置記法(逆ポーランド記法)
大文字小文字を区別しない
変数の前には?をつける
= KIF (legal)
容易に相互変換できる
table:InfixとPrefixの比較
Infix Prefix
p(a, Y) (p a ?y)
~p(a, Y) (not (p a ?y))
p(a, Y) & p(Y, c) (and (p a ?y) (p ?y c))
q(Y) :- p(a, Y) & p(Y, c) (<= (q ?y) (and (p a ?y) (p ?y c)))
q(Y) :- p(a, Y) & p(Y, c) (<= (q ?y) (p a ?y) (p ?y c))
文法 (Infix)
名前
英数字、_などの記号が使える
定数
英語の小文字から始める
ex) empty_cell
変数
英語の大文字から始める
ex) X
関数
引数は,で区切る
ex) f(a, X)
f(a, X) != f(X, a)
f(a, X) != f(b, X)
否定は先頭に~
ex) ~f(X, Y)
ルールの定義
q(X, Y) :- p(X, Y) & ~r(Y)
pかつ~rならばq
head :- body と呼ぶ
body の要素はsubgoalと呼ぶ
キーワード
Wikipediaに記載のものに加えて以下の2語が追加
input(r, a): 役割rはaを実行することができる
base(p): pは基本的な定理である
入出力関係
role, base, input, initによって完璧な定義をすること
legal, goal, terminalはtrueにより定義すること
true, doesによってnextを定義すること
does, trueはheadで使用してはいけない
ゲームの要件
Termination
terminate: 初期状態から打った合法手が有限のターンを経て終局状態に達すること
Playability
playable: 初期状態から終局するまでの状態でどのプレイヤーにも少なくとも1つの合法手があること
Winnablity
strongly winnable: 他のプレイヤーが終局状態だったとしても、得点が最大値になる終局状態に持ち込むような一連の行動を何人かのプレイヤーが着手できること
他のプレイヤーが終局していてもそれ以外のプレイヤーの誰かが勝つ可能性があること
weakly winnable: 上記の行動を全てのプレイヤーが持ち合わせていること
Well-formedness
well-formed: terminate & playable & weakly winnable
全てのwell-formedなシングルプレイヤーはstrongly winnableであることが望ましい
well-formedでない定義をすることはできる
ゲームがwell-formedかどうかをチェックするには一般的にはしらみつぶしにゲームツリーを探索する必要がある
憶測
キーワード
(or (p a ?y) (p ?y c))
(p a ?y) または p ?y c
(<= (q ?y) (or (p a ?y) (p ?y c))) と (<= (q ?y) (p a ?y)) (<= (q ?y) (p ?y c)) は同義
and , orのsubgoalには順序がある
記述順に処理される
再帰するsubgoalをbodyの先頭に記述すると無限ループを起こすので注意
GDL-II
II = Incomplete Information
論文
書籍より
以下のキーワードが追加
percept(r, p): プレイヤーrはpを知っている
input(r, a)が有効な手の範囲を記述できるように、プレイヤーの認知可能な範囲を定義できる
sees(r, p): プレイヤーrは次の状態でpと分かる
next(f)と同じように次の状態でプレイヤーが認知可能な範囲が定義できる
認知できることは現在の状態と打った手に依存する
random: ランダムに打つ手が予め定義された役割
GDL-III
III = Imperfect Information and Introspection
論文
System Description Language (SDL)
従来の制約に縛られたマルコフ連鎖構造ではないGDL
Validator
Once your game has been added to the local game repository, you can run the Validator app, select the "Local Game Repository" as your source of games, and choose your game from the list.
ゲームをローカルゲームリポジトリに追加した後、Validatorを起動し、ゲームの参照元としてLocal Game Rpositoryを選択してゲームを選んでください。
This app will run a number of validation steps to identify any possible problems in the game.
このツールはゲームの中で想定しうる問題を特定するためにいくつかの検証ステップを踏みます。
For example, if the game has a state where a player doesn't have any legal moves, but the game isn't over, that's a validation error: that will never happen in a well-formed game.
例えばもしゲームオーバーになっていないのに合法手が打てなくなった場合は、検証エラーを返します。 このエラーは適正なゲームでは起きてはいけません。
Likewise, if a game has states where the game is over but a player isn't assigned a score, that's another validation error.
また、もしゲームオーバーなのにプレイヤーの得点が未定だった場合も検証エラーになります。
The Validator app isn't guaranteed to find all validation errors, but you should fix any errors that it does find.
この検証ツールは全ての検証エラーを発見する保証はありません。しかし見つかればエラーは直さなければいけません。
関連言語
Datalog
Prolog
かなり詳しい
より高級でゲームが限定されている
予め基本的な機能が備わっている