Prolog Project - Haggle

Versions Compared


  • This line was added.
  • This line was removed.
  • Formatting was changed.
Wiki Markup
cite{font-family:Courier New; font-style:normal}

This page implements an interesting project in order to demonstrate how the details presented earlier all come together to make more powerful programs.

h3. Problem Description

In a party game called Haggle, a group of players (at least eight) are alleach given an envelope which partially explains the game rules.  Inside the envelope are a dozen colored cards and two scoring rules.  UnbeknowestUnbeknownst to the participants, a total of 15 rules combine and intertwine to form a complex system.  The goal is to trade and talk with competitors in an attempt to form the highest-scoring collection of cards.

Some rules have the form: "The hand with the most XXXX cards receives a bonus of YYYY," or even, "Every hand containing XXXX causes all other hands to lose YYYY points," which may be countered by "A set XXXX protects you from one set of YYYY."  These make your score depend upon the hands that other players submit.

We created a program that has enough artificial intelligence to determine what hand will score the best, based on the known subset of rules.  From this, it can judge whether or not a trade will be beneficial.

h3. Current Progress

So far, I have implemented a program which will score a hand ignoring those rules which depend on other submissions.  In particular, this permits the execution of queries such as the following:

??getScore(????[R,O,Y,G,W]????,Score),R>=7, O>0,Y>0,G>0,W>0, R+O+Y+G+W>12.??                  -- see how you'd score with certain constraints on your hand
??getScore(Hand,Score),forall(getScore(OtherHand,OtherScore),Score>=OtherScore).??    -- find the absolute best hand (not considering other players) -- takes just a couple minutes
??getScore(Hand,Score),Score>=54,nth0(0,Hand,R),R>=7.??                               -- find the best hand if you get the "most red" bonus

The middle one is the most exciting\!

This has required the use of randomness, forall (in the query), multiple (disjoint) cases for terms (perhaps I should use cuts?), recursion, and generate-and-test.

It can score a hand based on a rule subset.  This includes the ability to generate a goal based on limited information.  We lumped together the rules 1,2, and 3.  In order to do this, we added a LAYER OF ABSTRACTION in order to call score for an arbitrary rule.

It can choose from among the highest scoring hands to choose a goal which requires the least number of trades (sort of)

It can accept or reject a trade offer.  Whether or not it makes the right decision may be questionable, but it's pretty good.

h3. Extension Ideas

An awesome program would simulate a group of people playing Haggle.  This may be beyond our reach.  But perhaps not :-)

At least I can make something like:

This would enable me to write:
possibleTrade(CurrentHand, Goal, Rejects, Wishlist)
I'm not sure if this incorporates wanting/willing to give up rule cards or not.  Perhaps that is separate

If I do have several players, each must keep track of its

Known Rules (it knows all rules it has seen, and is currently holding some.  Should I make it forget rules?  Naw, it's not too hard to remember them)
Goal (this could be computed, but since it takes a few minutes, should only be recomputed when it learns a new rule)

I'm not sure if I should keep a list of players, each of which is a structure containing these fields, or if I need to read and write from files.

Speaking of files, the interesting thing about this simulation would be how the _actual_ score of a player's goal changes as it learns more rules.  Of course, scoring the GOAL changes could be done without an entire, multi-player simulation.  But it would still be more interesting to see the changes of many players over time.

One thing that would be really hard is for the players to modify their strategy based on others' actions.  If you are trying to get all of the reds and someone else is, too, then you _might_ want to stop.  And if player X has been asking _everyone_ for green, you may not want to give him any, though you are likely willing to give them to others.

I think I would have "turns," and each turn 2 randomly selected players would try to trade with each other.  I'm not sure when this would stop.  Perhaps after X turns with no trades.  Perhaps when everyone reaches its goal.  At any rate, this would require that failing to make trades towards one's goal would make the player reevaluate to find a new goal.  Especially at the beginning, you may think you want one color, but if someone offers a trade for something else, you may be willing to do so.

Maybe rule trades occur until a player has seen enough repeats to feel as though it has seen them all.  When I played it, the cards WERE numbered, but it's hard to remember _exactly_ how many you have seen.