Solving logic game Uluru with Prolog

Before starting to learn Prolog I used various logic based systems, such as the SPIN model checker, or reasoners that work on ontologies encoded in OWL. The latter of them to have it reason about (visual) objects in RoboCup.

Prolog however seems to encode many problems in a more natural and fluent way, so I set out to make a few toy examples to test how well I could make it work and get a feel for its advantages and limitations.

Many concepts in AI are implicitly based on specific formulations / terminology as used for Prolog or its derivatives. Vague sounding words / expressions, often taken from general contexts, really mean something rather specific, and learning about Prolog sharpens the understanding of these wordings.

Current approaches in machine learning predominantly use these Symbolic artificial intelligence (GOFAI) concepts to point out differences with “the old ways”. Yet it remains useful to know for this reason alone: the differences (not to mention a better intuition for the limitations of each approach, trendy or not).

While Prolog isn’t without fault, it has a compelling syntax for formulating constraints, that feels terse and efficient to enter, yet more intuitive than logical formulas in mathematics.

The interpreter interface, together with the debugging capability, allows for quick testing and finding model errors, and feels a lot more natural compared to building or reasoning over ontologies. (And this is not just because of the closed-world assumption in Prolog.)

The syntax overall is simple and declarative: you specify the constraints and let the Prolog solver figure out how to satisfy them. At the same time however you are limited by its depth-first search (DFS) and backtracking solution finding strategies. An important limitation of DFS is handling state spaces, that contain infinite paths, since you may never hit a termination condition, before you can backtrack. Alternative solvers are necessary then, such as BFS, informed search algorithms such as A*, or completely different approaches such as used by SAT solver, hill climbing, or whatever specific algorithm is appropriate to the problem at hand.

There are add-ons which allow for more or less natural extensions of Prolog (such as for constraint programming), and using various reasoners. But writing such extensions is not trivial, and they are less fluent to use than sticking to the basics. How easy and natural this is (to me at least), is still something to be explored.

An especially interesting variation is Problog, which allows to express beliefs / probabilities about facts and rules. I plan to explore Problog for another game, which is not strictly combinatorial, and where you have to work with incomplete knowledge / uncertainty, such as Cluedo.

Reasoning under uncertainty is another big topic in AI and often solved with machine learning methods. But a probabilistic logic based solution makes the models easier to debug and evaluate, and experience in more structured modeling certainly does not hurt when designing machine learning models.

Regarding non-symbolic approaches, there has been interesting research in helping to make machine learning models more understandable.

Uluru

Uluru is a board game where the goal is to fulfill the (possibly contradictory) wishes of 8 birds. Each bird’s wish is expressed by drawing a card from a pile, which gives a constraint about where the bird wants to be placed around the big rock Uluru. Players compete by placing the birds on a playing field that has 8 places around the rock, limited to about 1 minute by an hour glass / sand timer.
For each unfulfilled wish card, the player gets a negative point.

The point of this program is not to replace the game (which would not be much fun to play against a computer), but to find solutions to complex wishes, find out if they are unsolvable, or what the best partial solution would be.

Possible future

An interesting idea for future expansion might be to drive a robot arm to actually place the game tokens according to the found solution. Placing the wish cards and waiting for the robot to place the solution (as a set of tokens on their playing field places), would be the most natural Prolog query interface.

In a way this would unite abstract planning (i.e., finding a logical solution) with practical planning and problem solving (for moving the arm, and visually recognizing the tokens and their position in space / relative to the playing field). The latter is more typically implemented as some kind of controller, using signal processing, and possibly using machine learning methods.

Finding perfect and partial solutions

Some wishes / constraints are hard to fulfill, because of the complex interdependencies with other wishes. Some wish combinations are not possible to fulfill at all, so the next best thing is to find a solution with minimal negative points.

Implementation in Prolog and Delphi

I used Prolog to express the constraints of the game and find solutions to them, and Delphi to make a GUI to easily enter the constraints and present the solution. For testing I enter the constraints directly in Prolog, but it is a lot to type and a bit tedious, so I keep using some standard test examples. Maybe there is still a trick to figure out how to abbreviate some expressions for quick testing, but entering the constraints over the GUI is definitely the fastest.

GUI

Uluru’s main window.

The top left blue rectangle shows the empty “slots” for the 8 wish cards. The right brown / orange rectangle shows the playing field, where the 8 bird tokens (each one having a different color) gather around the rock. The “bird places” will be filled with colored circles to show which bird token goes where.

To quickly select the wish cards you press the button “select card” which pops up the window below, for each wish card slot. (This entry method saves you the step to first click on a slot then select a card, or having to drag and drop awkwardly — this could be added to easily fix wrong entries, to further improve UX, but this is a Prolog learning exercise).

Window for selecting one wish card.

This lists each card category. If one category, like the bottom left one, comes in more than one color, you can select directly it by clicking on a colored rectangle. (That’s why the uncolored cards are framed by a black rectangle, and the colored ones not: to show the click “sensitive” region.)

This reduces the number of cards visible on the screen to a minimum, avoids the need for scrolling, and allows to select a card quickly by only one click.

Unfortunately, the cards I used here have a fixed color on them, which can be confusing. I might fix it by scanning in each card of each color, but again, I am not sure it’s worth the effort for a toy example.

Main window with selected cards.

After all the wish cards were selected, the screen looks similar to above. In this example I chose a card of each type. The wishes are:

  • White (bird) doesn’t know what it wants.
  • Pink wants to be in the boomerang region.
  • Yellow want to be on Uluru’s long side.
  • Orange wants to be on Uluru’s short side.
  • Red wants to be in a solitary place.
  • Green wants to be next to yellow. (The bird on the card is white, but as mentioned above, what counts is the rectangle’s color.)
  • Blue wants to be opposite to red. (Same comment as above.)
  • Black wants to share a corner with blue. (Same comment as above.)

The names for each region of the playing field are not always too obvious, but when you look at each card, you will notice that the allowed places are highlighted. The colored cards describe spacial relationships between two birds, if they want to be next to each other, facing each other, or share a corner.

The full Uluru game has even more wish card types, but adding them wouldn’t change anything about the principle problem solution in Prolog or Delphi. (And the full game is harder to play without a computer ;).

It would however be a good example of how easy it is to extend the rule set, while the rest (in Prolog, not the GUI) would remain the same.

Finally, when pressing on “Solve”, the entered problem is translated to Prolog clauses that are asserted (next to the unchanging base program), and a query is formulated to solve the constraints/clauses. The results are then displayed, both in text and graphically, as below.

Main window with placement that fulfills all wishes.

In the above example, a perfect solution could be found, with no penalty points (no point deductions). However when there is no perfect solution, the Prolog query is written such that the partial solution with the least negative points is found.

For partial solutions, some bird places may remain empty. But sometimes a partial solution can fill every place, yet we still get negative points, due to unfulfilled wishes (but removing some bird tokens that are causing wish conflicts, would lead to even more negative points).

For example in the solution below, the white bird (place 4) does not share a corner with the red bird (place 7), as required by the first wish card. (It only shares a corner with the orange one, i.e., place 3.) Strictly speaking, the white bird is in the wrong place. However sharing a corner with the orange bird is a requirement of the fourth wish card, so removing the white bird from the playing field would cause 2 negative points (2 unfulfilled wishes), instead of just 1.

Example of a complete placement, still having one negative point.

This solution confused me at first, and I thought there was an actual error. But it proves to be a valid solution, when rechecking the game rules (which are slightly vague). This shows also how logically precise systems can surprise you with their inferences, questioning or precising your own mental models. This is opposed to many machine learning based models, which regularly leave you in a state of unknowing hope (or unwarranted overconfidence ;). Though some research is improving the situation, such as this (TODO: link to above).

Prolog

The formulation in Prolog is quite simple, while the efficiency of the search for a solution depends on the cleverness of the Prolog engine. Usually it is a simple DFS with backtracking, but other algorithms could be implemented, as mentioned in the introduction.

The eight possible game tokens are defined by the following assertions, using only their colors as unique ids. Technically speaking, we define all the cases where the color predicate returns true.

color(white).
color(pink).
color(yellow).
color(orange).
color(red).
color(green).
color(blue).
color(black).

The playing field has eight places, as can be seen in the pictures, above. Following the same strategy as for the tokens, we define a place predicate.

place(place1).
place(place2).
place(place3).
place(place4).
place(place5).
place(place6).
place(place7).
place(place8).

To express the constraints specified by a wish card, we need to define a set of basic relations, out of which more complex relations are formed. The wish cards express positional/place constraints (where a bird wants to be located), but also color constraints (how a bird is placed related to another bird).

For example, the predicate next_to_ expresses which places are considered to be next to each other (a translation to Prolog from the explanations in the game manual).

next_to_(place2, place3).
next_to_(place4, place5).
next_to_(place6, place7).
next_to_(place7, place8).

/* make next_to_ commutative */  
next_to(X, Y) :- next_to_(X, Y).
next_to(X, Y) :- next_to_(Y, X).

Similarly, there are predicates opposite_to_ and share_corner_.

Some places get assigned special region names, which we again define by exhaustively specifying a predicate, as exemplified by in_boomerang_group below.

in_boomerang_group(place4).
in_boomerang_group(place5).
in_boomerang_group(place6).
in_boomerang_group(place7).
in_boomerang_group(place8).

Other region names are at_solitaire_place, at_ulurus_long_side, at_ulurus_short_side.

Now that some basic predicates are defined, more complex relations can be built. One for each type of wish card.

Starting with the simplest card, which is essentially a joker card, saying the bird does not mind where it will be placed, we define the following predicate.

wishIdkWhatIWant(WisherColor, WisherPlace) :-
     valid_color_and_place(WisherPlace, WisherColor).

The only constraint is that WisherPlace is a valid place, WisherColor is a valid color. Essentially, this is a kind of type checking, by ensuring that the atoms that are passed in as parameters return true for the place and color predicates:

valid_color_and_place(Place, Color) :- color(Color), place(Place).
wishIdkWhatIWant(WisherColor, WisherPlace) :-
     valid_color_and_place(WisherPlace, WisherColor).

A slightly more constraining wish card, requires that the token be placed in the boomerang group.

wishInBoomerangGroup(WisherColor, WisherPlace) :-
    valid_color_and_place(WisherPlace, WisherColor),
    in_boomerang_group(WisherPlace).

The colon after valid_color_and_place should be read as a logical and. Therefore the predicate above requires that both valid_color_and_place and in_boomerang_group return true for the given parameters. Implicitly, it is also required that WisherPlace is the same in every occurrence of wishInBoomerangGroup. So valid_color_and_place(WisherPlace, …) and in_boomerang_group(WisherPlace) refer to the same place.

Predicates defined in a similar manner are wishSolitaire, wishUlurusLongSide, and wishUlurusShortSide.

Finally, there are color based wish cards, where the bird does not just care about where but also next to which bird it wants to be placed. wishNextToColor for example requires that the wishing bird (WisherColor) be placed next to a bird with a given color (PartnerColor).

wishNextToColor(WisherColor, PartnerColor, WisherPlace, PartnerPlace) :-
     valid_color_and_place(WisherPlace, WisherColor),
     valid_color_and_place(PartnerPlace, PartnerColor),
     next_to(WisherPlace, PartnerPlace).

wishNextToColor(WisherColor, PartnerColor, WisherPlace, PartnerPlace) :-
     valid_color_and_place(WisherPlace, WisherColor),
     valid_color_and_place(PartnerPlace, PartnerColor),
     WisherColor == PartnerColor.

This predicate defines a logical or relation (separated visually by a blank line). When trying to satisfy wishNextToColor the definitions of this predicate are checked in order of appearance. When the first definition of wishNextToColor fails, Prolog backtracks, and checks the second one. If that fails as well, the whole predicate fails (returns false).

The second wishNextToColor is there to catch the special case of having a wish card express that it want a token to be next to itself (WisherColor == PartnerColor). This can happen because cards are placed randomly and contradictory constraints can result. In that case, we simply want to ignore this wish (according to the game manual) and return true.

Again, there are analogously defined wish cards, wishOppositeToColor and wishShareCornerWithColor. What remains to be done now, is to formulate the combined constraints in Prolog, as specified by the eight wish cards laid out on the playing field.

Perfect solutions

Finding a perfect solution (where every wish card is satisfied) is pretty simple (when ignoring the run-time complexity).

example(WhiteP, PinkP, YellowP, OrangeP, RedP, GreenP, BlueP, BlackP) :-
    wishUlurusLongSide(white, WhiteP),
    wishSolitaire(pink, PinkP),
    wishNextToColor(yellow, red, YellowP, RedP),
    wishUlurusShortSide(orange, OrangeP),   
    wishIdkWhatIWant(red, RedP),
    wishInBoomerangGroup(green, GreenP),
    wishShareCornerWithColor(blue, red, BlueP, RedP),
    wishNextToColor(black, white, BlackP, WhiteP),
    
    different_positions(WhiteP, PinkP, YellowP, OrangeP, RedP, GreenP, BlueP, BlackP).

The code above shows an example problem (a round in the Uluru game) formulated in Prolog. The eight lines following the predicate name “example”, each express one wish card. The different_positions predicate ensures that the found solution does not assign a place to more than one token.

When executing the query “example(WhiteP, PinkP, YellowP, OrangeP, RedP, GreenP, BlueP, BlackP).”, Prolog will do a DFS until it found a solution, and return it in the parameters (WhiteP, PinkP, YellowP, OrangeP, RedP, GreenP, BlueP, BlackP). The user can then choose if to search the next solution or to stop.

From the Delphi side, the game is entered by using the GUI, which is then translated into assertions similar to the predicate “example”, using a plugin interface to SWI-Prolog. This works similarly to database queries, or any kind of web query.

If interested I can point you to the Delphi translation of the SWI-Prolog interface I made, which works with current Delphi versions (Unicode, 64 bit, etc.).

Amzi! Prolog can be more comfortable to debug, and has a great tutorial as well, which makes it fun to learn Prolog.

Partial solutions

Sometimes the wish cards contradict each other, and should not simply be ignored. When a constraint cannot be satisfied (either by running out of time, which is not considered here, or because it is impossible to satisfy), the player will receive a negative point.

The obvious goal then is to find a solution with the minimal possible penalty. Let’s see an example with some contradictory wishes.

prove(X, NegPts) :-
     call(X), NegPts is 0; NegPts is 1.

example2(NegPts, WhiteP, PinkP, YellowP, OrangeP, RedP, GreenP, BlueP, BlackP) :-
    prove(wishInBoomerangGroup(white, WhiteP), NegPts0),
    prove(wishSolitaire(pink, PinkP), NegPts1),
    prove(wishUlurusLongSide(yellow, YellowP), NegPts2),

    prove(wishShareCornerWithColor(orange, orange, OrangeP, OrangeP), NegPts3),
    prove(wishShareCornerWithColor(red, white, RedP, WhiteP), NegPts4),
    prove(wishOppositeToColor(green, white, GreenP, WhiteP), NegPts5),

    prove(wishSolitaire(blue, BlueP), NegPts6),

    prove(wishNextToColor(black, orange, BlackP, OrangeP), NegPts7),

    NegPts is NegPts0 + NegPts1 + NegPts2 + NegPts3 + NegPts4 + NegPts5 + NegPts6 + NegPts7,

    different_positions(WhiteP, PinkP, YellowP, OrangeP, RedP, GreenP, BlueP, BlackP).

Notice how we have a new parameter NegPts, which is assigned the sum of negative points resulting for unsatisfied constraints in the current solution. To be able to track negative points, each wish is wrapped in a call to a prove predicate, as opposed to the perfect solution, where the wish is stated directly. This works by relying on backtracking of Prolog. prove calls the predicate (with its parameters) and if it succeeds return 0 negative points. If it fails it tries to satisfy the alternative assertions given after the semicolon, which will force NegPts to become 1.

Now we still want to find a solution with minimal negative points. We do that by sorting the solutions based on their score (NegPts), and assigning the head of the sorted list to the parameter BestSol.

get_best_solution(Goal, BestSol) :-
     term_variables(Goal, GoalVars),
     findall(GoalVars, Goal, Sols),
     sort(Sols, SolsSorted),
     [BestSol|_] = SolsSorted.

term_variables, findall, and sort are all built-in predicates. term_variables extracts the goal variables/parameters from a predicate, findall finds all solutions to a query, and sort sorts a list.

The complete query to find the solution with the least penalty therefore becomes:

get_best_solution(example2(NegPts, WhiteP, PinkP, YellowP, OrangeP, RedP, GreenP, BlueP, BlackP), BestSolution). 

The query result would look something like this:

BestSolution = [1, place4, _862380, place8, place7, place3, place1, place2, place6].

1 is the amount of negative points, _862380 is the id of a goal variable which was left unbound, and the rest are the assigned places. There might be other solutions with an equal amount of negative points, but this query just lists the first one found.

Sometimes solutions can also assign every token a place, yet there are still conflicts regarding the wish cards. However leaving a place empty would satisfy even less constraints, which is why there can be solutions with negative points, yet all goal variables being bound.

Leave a Reply

Your email address will not be published. Required fields are marked *