Find Legal Moves in Brass Birmingham With Logic Programming

Have you ever tried expressing board game rules in code? Does it sound a bit tedious? I bet it does, I implemented a few board game rulesets in Python and JavaScript to write a simulator or implement a version of the board game playable in a browser. It felt like implementing an overcomplicated business process with plenty of exceptions, discontinuities and generous use of state machines. The same rules that take a lot of Python code can be expressed pretty succinctly and not ambiguously in their instruction manuals, which suggests there should be a better way.

Take for example Brass Birmingham, it is an acclaimed strategic board game set during the British Industrial Revolution. Players compete as industrialists, building logistical networks and developing industries like cotton mills and breweries. Most of the rules of the game pertain to when you are allowed to build factories, railway links or when you are allowed to sell your goods. Let's have a look at one such rule:

Taken from Roxley Rules Highlights

How would you implement this rule in an imperative paradigm? Let's write some pseudo-code (that might smell a bit of Python)

def can_consume_beer(player, sell_location, beer_location) -> bool:
    if not has_beer(beer_location):
        # first the obvious, there has to be beer in the targeted location
        return False
    if sell_location == beer_location:
        # regardless of the ownership, you can always consume beer
        # that is present in the same location
        return True
    if is_connected(sell_location, beer_location):
        # if the two nodes are connected,
        # the ownership also does not matter
        return True
    if owner(beer_location) == player:
        # if the beer location and sell location are not connected
        # then the plyer must own the brewery
        return True
    return False

Not too bad. But how do we find all legal combinations of sell and beer locations?

legal_moves = []
for player in players:
    for location1 in locations:
        for location2 in locations:
            if can_consume_beer(player, location1, location2):
                legal_moves.append((player, location1, location2))

I guess this would work ... But how would it look if we keep adding new rules and for each of them we want to know what are the legal moves for the given player for a given state of the game? We probably need to come up with some clever abstraction for the rule itself, and its parameters and then iterate through them all checking if they are satisfied for the given input domain, which likely would be brute-forcing all possible combinations of their parameters.

Is Logic Programming a better tool to express board game rules?

Logic programming is a rather obscure (as in - not commonly used) programming paradigm. It is declarative - you describe the rules and facts of your program and rely on the interpreter to find solutions. A more mainstream example of a declarative language is SQL. Let's have a look at the same rule for consuming beer but implemented in Datalog (a logic programming language).

can_consume_beer(player, sell_location, beer_location) :- 
    has_beer(beer_location),
    is_connected(sell_location, beer_location).
can_consume_beer(player, sell_location, beer_location) :- 
    has_beer(beer_location),
    owns(player, beer_location).

The syntax might look foreign to you so the benefit is not obvious yet. can_consume_beer is a rule and its conditions are listed after the so-called horn clause :- .The commas stand for logical AND, a full stop stands for logical OR, so either of the two implementations of can_consume_beer needs to be satisfied.

How about finding all legal moves for this rule? This is where logic programming starts to shine:

.output can_consume_beer(IO=stdout, delimiter="\t")

Depending on the game state (or in logic programming parlance: facts) you might get the following output from this program:

---------------
can_consume_beer
Player    SellLocation    BeerLocation
===============
Player1    Birmingham    Birmingham
Player2    Nuneaton    Birmingham
===============

What would a complete running program look like for this specific rule?

.decl has_beer(Location:symbol)
// the following is a fact, a piece of data that 
// describes state of the game in our case
has_beer("Birmingham").

.decl is_connected(Location1:symbol, Location2:symbol)
// simplified fact-based implementation, only 1-hop connections
// for a more complete example of is_connected graph rule
// see https://souffle-lang.github.io/tutorial
is_connected("Birmingham", "Birmingham").
is_connected("Birmingham", "Nuneaton").
is_connected("Nuneaton", "Birmingham").

// ownership facts simplified from Brass Birmingham rules perspective
// in brass players own only given slots, not entire locations
.decl owns(Player:symbol, Location:symbol)
owns("Player1", "Birmingham").
owns("Player2", "Nuneaton").

.decl has_unflipped_factory(Player:symbol, Location:symbol)
has_unflipped_factory("Player1", "Birmingham").
has_unflipped_factory("Player2", "Nuneaton").


.decl can_consume_beer(Player:symbol, SellLocation:symbol, BeerLocation:symbol)
can_consume_beer(player, sell_location, beer_location) :- 
    has_unflipped_factory(player, sell_location),
    has_beer(beer_location),
    is_connected(sell_location, beer_location).
can_consume_beer(player, sell_location, beer_location) :- 
    has_unflipped_factory(player, sell_location),
    has_beer(beer_location),
    owns(player, beer_location).
.output can_consume_beer(IO=stdout, delimiter="\t", headers=true)

Which produces the following output:

---------------
can_consume_beer
Player    SellLocation    BeerLocation
===============
Player1    Birmingham    Birmingham
Player2    Nuneaton    Birmingham
===============

This tells us that Player1 can sell in Birmingham using beer from Birmingham and Player2 can sell in Nuneaton with beer from Birmingham (supposedly not at the same time!).

If you want to run the above program yourself or play around with Datalog, have a look at Souffle, pretty easy to install and run locally the Datalog dialect I used for this blog post.

Let me know if you find this use case convincing, follow this blog to read more write-ups like this one, I will likely continue implementing more Brass rules in Datalog.