CODEWITHSUNDEEP
prologlogicclpfd
Tim
Tim

Reputation: 31

Prolog: each player in a game plays a card. With partial knowledge of who played which cards, deduce who played the others

I'm trying to use Prolog to solve a simple game in which there are 3 players: Alice, Bob and Charlie. Each player secretly chooses a card to play, where cards can either be red or blue. The cards are then shuffled and turned over.

Assuming Alice's viewpoint, we know which card she played. Therefore if the revealed cards are blue, blue and red, and Alice played red, then she can deduce that both Bob and Charlie played blue. I'm struggling to define the appropriate causes for this. Here are my basic facts:

player(alice).
player(bob).
player(charlie).

color(blue).
color(red).

% The overturned cards -- all players can see these. Order is unimportant.
cards([blue, red, red]).

played(alice, blue).

From this, we should be able to deduce that Bob and Charlie each played red. I'm unsure how to tell Prolog that each of the three players played exactly one of the cards in the cards([blue, red, red]) fact. Or perhaps something along the lines of num_cards(blue, 1), num_cards(red, 2) would be better?

As a slightly more difficult example, it should be possible for the following facts to be used in deducing that Charlie played a red card (for example if Alice was able to peek at the card played by Bob):

player(alice).
player(bob).
player(charlie).

color(blue).
color(red).

% The overturned cards -- all players can see these. Order is unimportant.
cards([blue, red, red]).

played(alice, red).
played(bob, blue).

The most similar SO question I was able to find was this one, but I haven't been able to apply it to my problem. The CLPFD library definitely seems relevant.

Upvotes: 3

Views: 328

Answers (2)

CapelliC
CapelliC

Reputation: 60034

my hint needs a 'syntactical adaptation' to fit your question: from my viewpoint, it's essential to separate the facts expressing a particular query from entities identities: so, I propose a game/2 assessing the relation between a set of cards (those overturned, of course) and an association of player and played card, expressed as Player-Card:

player(alice).
player(bob).
player(charlie).

color(blue).
color(red).

game(Cs, [P-C|Ps]) :-
    player(P), color(C),
    select(C, Cs, Other),
    game(Other, Ps),
    \+ memberchk(P-_, Ps).
game([], []).

now, a lot of specific queries can be answered. For example

game([blue, red, red], [alice-blue,bob-B,charlie-C]).
B = C, C = red ;
B = C, C = red ;
false.

or

?- so:game([blue, red, red], [alice-blue,X,Y]).
X = bob-red,
Y = charlie-red ;
...

or

?- game([blue, red, red], [alice-red, bob-blue, Y]).
Y = charlie-red ;
...

To avoid duplicates solutions, setof/3 can be used.

Upvotes: 0

mat
mat

Reputation: 40778

Already for a really well-done background search: +1! The question you linked to and Boris's solution is indeed strongly related to this task.

First, I would like to point out that your task looks easy on the surface and is something that prima facie looks suitable for Prolog beginners to tackle. In my view, such tasks are not easy at all, and the difficulty quickly gets out of hand when additional knowledge (such as: who knows what, throughout different layers) must also be represented. I can well imagine that beginners who get such tasks as assignments will quickly walk away with the feeling "I could have easily solved this in Java, but it is impossible in Prolog". The fact that they could not have solved it in Java either usually does not bother them in the slightest.

In this concrete case, constraints are indeed a great fit. In fact, the global_cardinality/2 constraint which is for example available in SICStus Prolog solves both examples easily.

When using CLP(FD) constraints, the trick is to map your domain of interest to integers. In this case, I will (arbitrarily) use:

  • 1 for blue
  • 2 for red.

Also, I will simply use variables, one for each person, standing for the concrete "card" (i.e., integer) the person played. The idea is to specify what we know, and let the constraint solver figure out the rest.

So we have, in the first case:

?- global_cardinality([Alice,Bob,Charlie], [1-1,2-2]),
   Alice = 1.
Alice = 1,
Bob = Charlie, Charlie = 2.

And in the second case:

?- global_cardinality([Alice,Bob,Charlie], [1-1,2-2]),
   Alice = 2,
   Bob = 1.
Alice = Charlie, Charlie = 2,
Bob = 1.

So in both cases, simply stating the given constraints suffices to deduce the single respective solution, just like you expected.

Upvotes: 1

Related Questions