WingNews logo WingNews
top | item 46509838

(no title)

Scaevolus | 1 month ago

The site uses Answer Set Programming with the Clingo engine to compute the optimal solutions for smaller grids. Maximizing grids like this is probably NP-hard.

Note that traditional SAT and SMT solvers are quite inefficient at computing flood-fills.

The ASP specifications it uses to compute optimal solutions are surprisingly short and readable, and look like:

  #const budget=11.
  horse(4,4).
  cell(0,0).
  boundary(0,0).
  cell(0,1).
  boundary(0,1).
  % ...truncated for brevity...
  cell(3,1).
  water(3,1).
  % ...
  
  % Adjacent cells (4-way connectivity)
  adj(R,C, R+1,C) :- cell(R,C), cell(R+1,C).
  adj(R,C, R-1,C) :- cell(R,C), cell(R-1,C).
  adj(R,C, R,C+1) :- cell(R,C), cell(R,C+1).
  adj(R,C, R,C-1) :- cell(R,C), cell(R,C-1).
  
  % Walkable = not water
  walkable(R,C) :- cell(R,C), not water(R,C).
  
  % Choice: place wall on any walkable cell except horse and cherries
  { wall(R,C) } :- walkable(R,C), not horse(R,C), not cherry(R,C).
  
  % Budget constraint (native counting - no bit-blasting!)
  :- #count { R,C : wall(R,C) } > budget.
  
  % Reachability from horse (z = enclosed/reachable cells)
  z(R,C) :- horse(R,C).
  z(R2,C2) :- z(R1,C1), adj(R1,C1, R2,C2), walkable(R2,C2), not wall(  R2,C2).
  
  % Horse cannot reach boundary (would escape)
  :- z(R,C), boundary(R,C).
  
  % Maximize enclosed area (cherries worth +3 bonus = 4 total)
  #maximize { 4,R,C : z(R,C), cherry(R,C) ; 1,R,C : z(R,C), not cherry(  R,C) }.
  
  % Only output wall positions
  #show wall/2.

discuss

order

freakynit|1 month ago

Im over 35 years of age. I have 15+ years of programming experience. And I generally consider myself as someone who has good breadth of tech in general. Yet, this is the first time in my life I've heard of ASP. And gosh. I was completely blown away by this as I read more about it and went through some examples (https://github.com/domoritz/clingo-wasm/blob/main/examples/e...)

Therefore, like a good little llm bitch that I have become recently, I straight away went to chatgpt/sonnet/gemini and asked them to compile me a list of more such "whatever this is known as". And holy cow!! This is a whole new world.

My ask to HN community: any good book recommendations related to "such stuff"? Not those research kinds as I don't have enough brain cells for it. But, a little easier and practical ones?

Thanks..

tgamblin|1 month ago

The more recent Lifschitz book is the easiest to learn from IMO:

- https://www.cs.utexas.edu/~vl/teaching/378/ASP.pdf

It starts with basics of using ASP and gives examples in clingo, not math.

The Potassco book is more comprehensive and will help you understand better what is going on:

- https://potassco.org/book/

Things I don't like include that it's more dense, doesn't use clingo examples (mostly math-style examples so you kind of have to translate them in your head), and while the proofs of how grounding works are interesting, the explanations are kind of short and don't always have the intuition I want.

I still think this is the authoritative reference.

The "how to build your own ASP system" paper is a good breakdown of how to integrate ASP into other projects:

- https://arxiv.org/abs/2008.06692

The Potassco folks are doing amazing work maintaining these tools. I also wish more people knew about them.

EDIT: I forgot to mention that specifically for games stuff like enclose.horse, look at Adam Smith's Applied ASP Course from UCSC:

- https://canvas.ucsc.edu/courses/1338

Forgot to mention that one... we use clingo in Spack for dependency solving and other applications frequently slip my mind.

Scaevolus|1 month ago

The pre-machine-learning formulations of AI focused on symbolic reasoning through the dual problems of search and logic. Many problems can be reduced to enumerating legal steps, and SAT/SMT/ASP and related systems can churn through those in a highly optimized and genetic manner.

ctxc|1 month ago

Has to be my favourite comment, haha!