Find Legal Moves in Brass Birmingham with Datalog | Hacker News Reader

Find Legal Moves in Brass Birmingham with Datalog

blog.pzakrzewski.com

62 pointsgieksosz25 comments

I've become a big fan of datalog and souffle. We wrote a territory assignment application for a large healthcare organization with multiple overlapping marketing teams, where each team defines territories with various geographic and account attributes such that there's a hierarchy of precedence for the territory that should be assigned to each account.

The datalog application that replaced an existing imperative solution is so much easier to understand and maintain.

Souffle generates c++ from the datalog program. We use SWIG to compile the c++ code into a Go application. So we have a Go application that deals with getting data in and out, and all of the business logic is defined in datalog.

this is a pretty interesting workflow. I was indeed thinking how one would integrate Souffle into a bigger application.

Here's a simple example: https://github.com/cwarden/souffle-go-example

It illustrates how you can have the Souffle program load its data from SQLite databases, or how you can work with tuples and relations from Go.

This is pretty neat, and it reminds me of my experiment solving the water jug problem from Die Hard 3 using Hypothesis [1] (a Python library for property-based testing).

Though I doubt Hypothesis's stateful testing capabilities can replicate all the capabilities of Datalog (or its elegance for this kind of logic problem), I think you could port the author's expression of the game rules to Hypothesis pretty straightforwardly.

[1]: https://nchammas.com/writing/how-not-to-die-hard-with-hypoth...

Neat! For a while, I have been looking for software that could tell whether my reasoning about things other than code is correct. And it looks like Hypothesis might be worth giving it a shot.

I've implemented rules of https://en.wikipedia.org/wiki/Whist in prolog https://github.com/scolex/prolog-whist/blob/master/whist.pl some yeas ago as school project. Unfortunately comments are in czech language.

My university has an infamous project of implementing Euchre (another trick-taking game) in C++ in one of the early programming courses. It's a nice fundamental problem for dealing with objects, agents, and logic.

Aside from the article, I do really like the idea of implementing board game rules as a coding exercise. The only one I’ve ever been confronted with was tic tac toe, and I remember really having fun with the detecting winning moves part.

I've been playing around with making a version of tic-tac-toe that's interesting to grown-ups. Experimenting with rules a lot as you'll see. (I think 1357 is probably the best but not sure.)

https://5-by-5.edjohnsonwilliams.co.uk

https://github.com/edjw/5_by_5_tictactoe

That's really cool! Need to find someone to play this with now :)

Though the counting seems a bit weird. Two overlapping lines of 5 seems to count as "1 two, 2 five". I also managed to get two overlapping fours to count as "2 two, 2 four". Maybe I just don't understand how it's supposed to work?

Thanks! It’s kind of hard to understand what you mean without screenshots. Also there are so many variations that I’m not sure which rules you’re playing with. My dad is the only person who’s played it apart from me and so far if he finds something he thinks is a counting error it’s actually been counting right and it was a UX thing about the rule-writing

Did you find a clever/elegant way of detecting tic-tac-toe winning moves? I wrote a simple implementation in Typescript several years ago; I tried some approaches with representing the cells as a 2D array and looping over the rows/columns, but I ended up just using a flat array and hardcoding the sets of cells to check [1]. If memory serves, using a flat/1D array made other parts of the code easier, not just the game logic, though that might have been due to my inexperience; I was just starting to learn React/frontend dev at the time.

[1] https://github.com/DylanSp/tic-tac-toe-react/blob/master/src...

The most clever way I have found is through a mathematic structure with the same shape, i.e., a magic square:

  2 7 6
  9 5 1
  4 3 8

Here, if a triplet of one player's cells sums to 15, that player has won.

2D array was my approach, it wasn’t super clever or anything, but it got the job done - and it worked for n-size boards with n players, not just the traditional 2 player 3x3 board, that was the fun part

> Have you ever tried expressing board game rules in code? Does it sound a bit tedious?

I expressed the logical rules of Go, which are already phrased in a concise yet mathematically rigorous way, pretty much directly into Haskell [1], which was more fun than tedium.

[1] https://tromp.github.io/go/SimpleGo.hs.txt

That was an issue I encountered when writing the logic for Shogi so that I could build my own engine. Writing Python to express the logical dependencies was surprisingly unintuitive.

My original attempt was clunky and I rewrote the logic from scratch 2 or 3 times until I could bear look at the code and not wince.

Did you publish the code somewhere?

mai-shogi in GitHub

I implemented the rules of Ora et Labora. Every card's ability is some fun puzzle of enumerating all the legal ways to play it. Some are simple like "go here and you get an amount of sheep", others are "you can convert an amount peat to coal here" so if you have 5 coal, you can offer 0, 1, 2, 3, 4, or 5 peat as input. The more fun problems are like "convert 3 different resources into 6 of any one type of basic resource" or "convert four to bread for 0.5 energy each" and wood is worth 1 energy, peat 2, and coal 3 energy. Lots of fun combinatorics.

It's all open source and playable at https://ora.kennerspiel.com

Wait, so can this be used to model a card game like Magic The gathering?

My guess is that fully modeling MtG's rules in Datalog would take a lot more work, because MtG's rules are a lot more complex. Looking through the source for one of the freely-available game engines like https://github.com/magefree/mage would probably be more informative, though.

EDIT: I found an old project working on implementing the MtG rules in Prolog: https://github.com/stassa/Gleemin. It's definitely more concise than XMage's Java, but you can still get an idea of how much work it would take, especially since that project notes some pretty significant limitations that it didn't get to.

Is there an equivalent Python library to model these rules?

you can try this: https://github.com/yuce/pyswip

I recommend `egglog` which is Datalog + Equality Saturation. It has python bindings and has allowed me to optimize programs in a custom programming language.

https://egg-smol-python.readthedocs.io/en/latest/

https://pypi.org/project/pyDatalog/

Reply on news.ycombinator.com