Paper: A Domain-Specific Embedded Language Approach for the Scripting of Game Artificial Intelligence

Yet again I have ignored this blog for quite some time – I’ve been really busy with an implementation of a game involving a Haskell back-end/Google Web Toolkit front-end (more on this in a future post)  and other deadlines. Anyways I thought I’d share more info on how 4Blocks’ AI was implemented using a DSL embedded in Haskell:

A Domain-Specific Embedded Language Approach for the Scripting of Game Artificial Intelligence, with Gordon Pace, in the Proceedings of the University of Malta Workshop in ICT (WICT’09), 2009.

More info on WICT can be found here. Co-incidentally thanks to Dr Pace’s Erdös Number of 4 I get to have one of at most 5. 🙂 Hope this short paper provides with some interesting lightweight reading. Also, any feedback is greatly appreciated!

4Blocks with AI

I’ve been wanting to write another blog post on the series on DSELs I’ve been planning, but I’ve been really swamped with work lately. So once more I’ll post a video or two on something I’ve been working on. It’s the 4blocks game again, this time playing on its own with an AI I’ve written for it. Here are the videos:

On the whole these were two good runs. I’ve had much better and much worse runs of course.

The AI is by no means perfect but it uses the DSEL techniques in Haskell. I have two languages acting here:
1. A Tetris DSEL
2. Haskell acting as a meta-language over the Tetris DSEL.

What is happening is that for every new brick the game state is queried by Haskell for certain information such as occupied blocks or number of lines. Using this information, by means of Haskell’s case statement I simply trigger one of a possible number of strategies. These strategies acquire certain information from the game state and generate a DSEL script. This script is then carried out by a DSEL script interpreter.

There are numerous problems with the AI and its mostly because I haven’t had time to write more strategies or a more intelligent way to select what according to the selected strategy is the best final brick destination.

That’s about it for now. Let me know what you think.

Domain-Specific Embedded Languages (DSELs) | Part 1 | Introduction

Hi to all, I decided to try once more at this blog thing. I want to share my thoughts with the people out there but it seems that I am able to do so in bursts, and random ones unfortunately. I decided to try once more, this time using WordPress.

I just finished my second draft of a literature review about Domain-Specific Embedded Languages (DSELs or EDSL in short, depending where you come from). For those of you who are unfamiliar with the notion, these are basically languages related to one particular domain (often referred to as Domain-Specific Languages or DSLs) which are embedded within another language. More often the host language is a fully-fledged language which acts as a compiler or interpreter for the embedded language. The embedded language itself usually consists of a data structure of the host language which adequately abstracts to the domain at hand and represents it completely. By means of appropriate functions the data structure is given a number of semantics related to the domain. A common example of a DSEL is one for creating circuits but the number of possible applications of the approach is dependent on the number of domains existent (so more or less infinite). There are DSELs for geometric region analysis, geometric constructions, images, animations, music composition, financial contracts, query languages, hardware description languages, testing, robotics, firewalls, business processes and so on. (Let me know if you want a number of papers about these and I will provide references.)

Let us make use of a circuit-creating domain-specific language embedded in the functional language, Haskell. Haskell has been used often for embedding due to many advantages it has which facilitate the embedding approach. (A post for another time maybe?) We start off with the syntax of our DSEL which we create by making use of a Haskell data type that we are going to call Wire. We shall make use of a high-valued wires, low-valued wires and two basic gates: a NOT gate and an AND gate, described in Haskell as follows:

data Wire
  = High
  | Low
  | Not Wire
  | And Wire Wire

Using this syntax we can describe circuits such as an OR gate as follows (using DeMorgan’s Theorem):

orGate wire0 wire1 = answer
  where not0   = Not wire0
        not1   = Not wire1
        and0   = And not0 not1
        answer = Not and0

This is pure Haskell code but which is now domain-focused on describing circuits. But what can we do with this code? As it is, on its own, well… nothing, apart from maybe describing how a circuit is composed. How can we render this code more useful? The answer is by means of functions which traverse the programs created using the above data type. In this way we attach semantics to the syntax. An example of this is a simulation function which when supplied with a circuit along with its input wires, gives us the result of the circuit:

simulate :: Wire -> Wire
simulate Low = Low
simulate High = High
simulate (Not w) =
  case (simulate w) of
    Low  -> High
    High -> Low
simulate (And w1 w2) =
  case (simulate w1, simulate w2) of
    (Low , _ )   -> Low
    (_ , Low)    -> Low
    (High, High) -> High

Calling simulate on orGate supplied with a Low and High input returns a High-valued wire:

> simulate (orGate Low High)

(Note: you need to derive the type-class Show or provide an instance of said type-class to view this in GHCI or Hugs)

Another possible semantics is counting the gates in the circuit or translating it into VHDL or Verilog. The possibilities are endless – one program may be interpretted in a million ways as long as the right function is supplied written in the host language.

I hope this blog post serves as a simplified starter to those who would like to know what a domain-specific embedded language is and how to create one quickly in Haskell. I also hope that in the next few days I can introduce other related stuff. Please feel free to comment on any mistakes, on what you think, or if you need any references to material on this.