Milt Reder By Milt Reder • November 20, 2014

Datalog at Play

By Milt Reder

This past weekend the Yet Analytics dev team took home the sponsor prize from Lookingglass Cyber Solutions for our clojurescript project at the third Baltimore Hackathon. Lookingglass' challenge provides a UI (in Om) and a messaging system (using core.async) for a game of checkers and asks the challengee to implement the game logic, suggesting features such as move validation, AI and a game state recorder.

Something that jumped out at us immediately was the challenge's suggestion to use Datascript to record and play back game state. Datascript could certainly do this handily, but it gives you so much more: Datalog queries and rules, transactions and listeners... Could we leverage these to implement our game logic? It wasn't exactly what the challenge was asking for, but we were the only team competing so we decided to go for it.

Everything is an Entity

We realized early on that if we were going to push Datascript to it's limits, we would have to store pretty much all of our game state in a Datascript conn atom. In the original challenge, the board state atom was initialized thusly:

Which derefs to:

Where the keys are the 32 valid spaces on the 8x8 board, 1-indexed left-to-right. The UI, (originally) written in Om uses these indices to draw the board. The author also helpfully included some very clever math to find the indices of neighbor spaces on the board for a given index which, as you will see, we ignored completely.

Since we wanted to store this state in Datascript, we had some decisions to make. In databases like Datascript (and Datomic) you can think of the stored data as a list of fact tuples in the format: [Entity Attribute Value Time] where:

  • Entity is a unique identifier in the database (ex. 1234)
  • Attribute identifies the fact being stored (ex. :person/firstname, :person/lastname)
  • Value is the value(s) of the fact (ex. "Bob", "Dobbs"), or refers to another entity id or ids.
  • Time is the time (or specifically in Datascript, which operates in constant time, the transaction ID) the fact was transacted into the database. Facts in the same transaction share this value.

The actual implementation adds a lot more (such as alternate indices like AEVT, AVET, etc), but in any case we needed to define our board and its state in these terms.

My first impulse was to only store the game pieces in the database, and update their positions as attributes. This was problematic, as Datascript does not yet have any upsert functionality that could ensure two pieces wouldn't occupy the same space. All of that would have to happen manually, as it would for the inverse (storing positions with their current piece as an attribute).

Jason's first impulse, which turned out to be spot on, was to make everything an entity, board positions and pieces. As it turned out, this let us leverage Datascript's lightweight schema, which is stored outside the database and only defines reference and cardinality-many attributes. Game pieces could express their state as a reference to the board position. The single cardinality of this reference ensures that our pieces obey the laws of (at least Newtonian) physics and don't try to occupy each other's space, or multiple spaces at once.

To make it even easier for ourselves we cheated a little and assigned cartesian coordinates to our board spaces (in addition to the original index from the challenge). Here is the (slightly simplified) function that sets up our database:

Query the Board

With our state initialized, we can now run a query to return the state of the board with Datascript's q fn:

Note that this only returns results for positions with pieces, so we turn it into a map and merge it with a skeleton of the board to get our state for the UI:

This query (and associated formatting fn) runs inside our UI code to get the board state, and React updates things accordingly (more about that later on). This is great, but so far we have only reproduced the original functionality of the challenge... actually less, as we have broken the facility for updating the board by updating the original board atom, as Datascript takes transactional updates. Our next task was to use Datascript to model not just the game state, but the logic as well.

Rules of the Game

One of the greatest strengths of datalog (as it is implemented by Datascript and Datomic) is the ability to compose small, easy-to-understand pieces of query logic into more complex ones. To this end, sets of query 'where' clauses can be stored in a vector of datalog 'rules' and then invoked during a query. As much as was possible, we wanted to express our game logic in a declarative fashion using these rules.

In practice this meant that, since the lg-checkers ui returns very little information, simply firing an event when a space on the board is clicked with the position of the click, we would have to construct a rather complex query to validate a given move. Once we wrote the code to aggregate two consecutive clicks from the user (we won't look at it here, but you can check the source), we set about translating the rules of checkers to datalog so we could use them in our queries.

Simple Movement

In checkers/draughts, a simple move (ignoring king pieces) has the following characteristics:

  • A piece must move to a diagonally adjacent dark space.
  • The space moved to must be empty.
  • A piece must move 'forward', that is to say away from the player making the move towards the enemy.

Though all we get initially is two board positions (from user clicks), we made it easier for ourselves by ensuring that the first click is on a space with a piece... Otherwise the click is thrown out. This check could be refactored into the main validation query, but currently it is separate.

So, given two positions, the first of which is on a square occupied by a (red or black) piece, how do we compose a query to validate that the second click is a legal simple move?

Diagonal Movement

This is the first thing we added to our validation query and, to our surprise, one of the easiest. If you recall, we added cartesian coordinates to our positions when we set up the db, :position/x and :position/y. This means that a query to find the diagonal 'neighbors' of a space with coordinates [x, y] would look for spaces with coords:

First off, we define what is essentially a helper in our rules to easily get the coordinates of a position:

This saves us the trouble of explicitly looking up coords for a given position. Here's an example query using the rule to find the entity id and coords of every position on the board:

Not very useful by itself, so let's make another rule to keep it company:

Huh? This seems like an odd rule... It doesn't do anything with our database, and only seems to contain functions. Also, why is it declared twice with different logic? Declaring a rule twice like this indicates a logical OR between two sets of query logic. So the inc-dec rule, when run inside a query, takes an integer ?i and returns a set of #{(inc ?i) (dec ?i)}. See where we're going with this? Using this OR and our coordinates rule, we can find the diagonally adjacent spaces (neighbors) for a given space:

Of course, we are still a ways off here from anything resembling checkers. For starters, we are not checking that the space we are moving to is empty. The neighbors rule will return any diagonally adjacent space, but notice that we already have something handled for us: it will not return any spaces that are not on the board. This eliminates the need for edge checking or the use of constants outside of our data.

Vacant Neighbors

Now that we can find the neighbors for a position, let's define a rule that limits our query results to empty spaces:

In this rule positions bound to ?pos are run through a built-in Datascript predicate, missing?, which checks for the presence of a given attribute on a given entity in a given db ($). The attribute :piece/_position is not a typo, but indicates (by the _ keyword name prefix) that we are checking for the reverse-relationship between position and piece. If this predicate returns true for a board position it can stay in our result set, otherwise it is thrown out. From there, it is trivial to compose this rule with our neighbors rule to get the set of empty, diagonally adjacent squares:

With empty-neighbors we almost have what we need to validate a basic move, we just lack... Direction.

Direction Introspection

While we thought (incorrectly) that finding neighbors would be hard, we (also incorrectly) expected validation of movement direction to be easy. My first idea was to write another OR rule like this:

But it didn't work at all. I still think there might be a more idiomatic way to write this, but we eventually got directional validation to work by passing a higher order function that returns a comparator based on the color of a piece:

Astute readers may note that our direction rule has a ?piece binding when we should be able to safely infer the moving piece from the starting position ?pos. This is intentional: it allows us to enforce direction in hypothetical move sets where ?piece has not yet moved to ?pos... More on those later.

Begin the Advance

Let's define one more helper rule to easily get that ?piece based on a ?pos:

With that in hand, we can complete our basic movement rule:

The moves rule will serve as the base for our movement validation. On its own it provides a very passive aggressive game of checkers where neither player can take the other's pieces, but recall that we can declare multiple rules with the same name (as we did with inc-dec) to achieve a logical OR... And what's that ?jumped-piece we bind but don't use?

The Jumpoff

Our next challenge was to implement jumping. Jump moves add the following criteria:

  • Pieces jump 2 squares diagonally
  • Pieces must jump over an enemy piece (of the opposing color)
  • Pieces can (and must) jump multiple times in one move if the first two criteria are met after a jump.

Distant Neighbors

Again, we start with the building blocks. Let's be lazy and just define modified versions of two of our previous rules, inc-dec and neighbors:

Looking good. Now we need something to jump!

Know Your Enemy

Before we can jump the enemy, we must identify the enemy:

They're over there!

Find Your Enemy

To find the piece being jumped we forge new depths of laziness and just re-use (abuse?) our neighbors rule:

Which is the intersection of the neighbor position sets, ?pos-between, of ?pos1 and ?pos2. Combine this with enemies, and you can ensure that a piece can be jumped.

Jump Your Enemy

At this point we've done all the hard work, all that is left is to combine our new component rules with some of those we defined for simple moves:

Notice that, as before with direction, we bind the piece originating the move, but this time we also have access to the piece being jumped, ?jumped-piece. Our application can save this after validation and remove the piece from the board! A few more rules and we've completed our moves:

Which, when combined with the simple move rules, forms the basis of our move validation function:

Since this was a toy project we chose to stop there with our validations, and there's a lot missing:

  • Players who can jump the enemy must do so. We don't enforce this
  • Kinging is not addressed
  • No victory state
  • We have no concept of turns, just moves.
  • Multiple jumps would have to occupy the same turn

We did write a little code that could help with that last one...

You Thought This Was a Clojure Post Without Recursion

As if datalog rules didn't give us enough to play with, we can also write recursive rules. You may recall the seemingly superfluous ?piece binding earlier... it was to enforce compatibility with one such rule:

r-jumps wraps n-jumps in a recursive logical OR. Note that we don't bind the ?jumped-piece here as the result would be inaccurate, only returning the last jumped piece. But it will (slowly) find multiple jumps.

Endgame

We learned a lot about Datascript/Datomic datalog working on the challenge, but our simple query only scratches the surface. Beyond expressing the rest of the checkers ruleset, you could:

  • Project and a query hypothetical future game state with Datascript's with fn.
  • Display possible moves on the board.
  • Provide the basis for AI player decision making.
  • Arbitrarily change the size and shape of the board while playing.

Though at times it felt like we were mis-using Datascript, I hope we have given you some fun ideas to hack on!

You can check out the running app here, and the source here.

Thanks again to Wes and the gang at Lookingglass for the challenge!

Subscribe for Weekly Updates

Posts by Tag

see all

Popular Posts