Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Find Legal Moves in Brass Birmingham with Datalog

blog.pzakrzewski.com

Post reply on HN
Print view View original

21–26 of 26 posts

Re: Find Legal Moves in Brass Birmingham with Datalog

#21

Post by DylanSp »

monlockandkey wrote: post #19

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.

Re: Find Legal Moves in Brass Birmingham with Datalog

#22

Post by efferifick »

monlockandkey wrote: post #16

Is there an equivalent Python library to model these rules?

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/

Re: Find Legal Moves in Brass Birmingham with Datalog

#24

Post by dr_kiszonka »

nchammas wrote: post #14

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 straightfo…

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.

Re: Find Legal Moves in Brass Birmingham with Datalog

#25

Post by klavinski »

DylanSp wrote: post #17
mock-possum wrote: post #2

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.

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…

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.

Re: Find Legal Moves in Brass Birmingham with Datalog

#26

Post by mock-possum »

DylanSp wrote: post #17
mock-possum wrote: post #2

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.

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…

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
Post reply on HN