Wednesday, November 4, 2015

Bases and inputs

I don't know if there are any clear full descriptions of how base and input sentences work in GDL. (They were added to GDL since the last full specification was written.) So, here's a brief write-up of how they work.

The base and input keywords are used to specify the possible true sentences (i.e., components of the game state) and legal moves that could occur over the course of the game.

Unlike true sentences and legal moves, the sentences that begin with base and input do not depend on the state of the game; they are constant. This means they can be easily and quickly queried.

If a game description uses base sentences, then every game state (true) sentence that could be true over the course of the game must have a corresponding true base sentence. For example, if some series of events in a game of chess could lead (true (cell d 5 black knight)) to be true, then (base (cell d 5 black knight)) must always be true regardless of the state of the game.

Similarly, if it's possible for (legal white (castle queenside)) to ever be true, then (input white (castle queenside)) must always be true (if the game uses input sentences).

What about the converse, if a base or input sentence is true but the corresponding game state sentence or move can't ever be true in game play? This is discouraged but may be unavoidable, depending on the game. Game designers should keep the bases and inputs as close to the actual set of possibilities as is reasonably achievable.

By contrast, if a base sentence is missing but its corresponding true sentence can be true, this is a bug in the game description. (Unless, of course, the game does not include any base sentences.) This is not intended to be a way to impose new restrictions on possible sentences or moves.

The Validator in GGP-Base includes a BasesInputsValidator that looks for validations of this type, where a base or input sentence is missing for a true sentence or legal move.

What's the value of being able to ask about these? Well, there are approaches to analyzing the game (including propnets, but also heuristic methods) where it helps to start with a complete set of possibilities. Furthermore, it can be difficult or time-consuming to compute this directly from the game description, and this process could result in a prohibitively high false positive rate. The OptimizingPropNetFactory, for example, takes advantage of base sentences as a starting point for propnet construction. The alternative would be to create a much larger initial propnet and pare it down afterwards, which is both slower and unreliable.

Although this is not in the specification, the level of adoption is fairly high; I believe these are used in all games in rotation on Tiltyard, and are used consistently in Stanford's tournaments. They will also be used in games in the upcoming Tiltyard Open.

No comments:

Post a Comment