This page implements an interesting project in order to demonstrate how the details presented earlier all come together to make more powerful programs.
In a party game called Haggle, a group of players (at least eight) are each given an envelope which partially explains the game rules. Inside the envelope are a dozen colored cards and two scoring rules. Unbeknownst 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.
The computer player is a collection of three pieces of information: which rules it has seen, the current cards in its hand, and its goal.
The current hand is a list of 5 numbers corresponding to the quantity of each type of card (red, orange, yellow, blue, and white). The goal uses the same representation.
The rules in the game are numbered, so the known rules are stored as a list of those numbers.
For example, if the player has seen rules 1, 5, and 9, has 4 red cards and 7 blue cards, and wants to get 3 reds and 9 blues, then it is represented as player([1,5,9], [4,0,0,7,0], [3,0,0,9,0])
Technically it could recompute the goal ([3,0,0,9,0] in the example) at any time, but it takes over a minute to calculate, so it is far more efficient to store it in the player.
We separate the logic of calculating scores from the logic of deciding trades into two files.
The first three rules in the game contain hints about the basic value of each color of card. Together they specify the values without ambiguity. To simplify matters, we combine these into a single rule (which we denote as rule 1).
Omitting those rules which are dependent upon the cards that other players turn in, the remaining rules may all be interpreted as transformations of the score. For example, a rule which states that "Every two yellow cards doubles the score of one white card" means "for each set of (2 yellows and a white) add the score of a white card". This interpretation allows each rule to be processed independently (as opposed to trying to find how many points each individual card adds based on all rules).
Every game rule that we implemented has a corresponding score function. The score functions for rules 1 and 13 are provided below.
score1 simply multiplies the quantities by the values for each color and assigns the result to Score. We use this to calculate the base score of a given hand.
score13 is recursive. It only cares about the quantities of yellow and white cards, so the others are omitted with underscores. If there are fewer than 2 yellows or no whites, then one of the last two rules applies, so the new score will be unchanged from the BaseScore. Otherwise the first rule is used. This recursively calls score13 so that multiple sets of two yellow and one white are all counted. Since a player may know rule 13 but not rule 1, score13 does not assume that the value of a white card is 5. Instead, we provide the guessed value of a white card as WhiteVal.
Calling the Score Functions
Since a computer player may know any subset of rules, we include the following methods for calculating a score.
callGetScore is the interface for calling getScore. It initializes the BaseScore to 0 and the GuessedWorth of all cards to 1. getScore recursively applies each rule one at a time. Each time it is called, it finds new values for the score and worth based on the first rule in the list of known rules. Once the list is empty, the first option for getScore acts as the base case and terminates the recursion.
In order to call an arbitrary scoring function, we have the dispatcher score which takes a rule number and calls the appropriate scoring function. Some rules require modification of the GuessedWorth or Hand. Those which do not can simply ignore these with underscores.
In order to access the value of the white cards without writing out the list, we use the built-in predicate nth0. nth0(Index, List, Value) is true when, in Java syntax, List[Index] == Value.
Finding A Goal
In order to know whether or not a trade will be beneficial, you must know what hand you want to obtain. Just given a subset of rules, the best hand may be calculated by finding a hand which has the best score. We do this using a forall, which is not particularly efficient. This predicate will find all possible values to satisfy its first term (in this case, all values for OtherScore), and if the second term is true for all of them, then the forall is true.
Thus the entire statement may require the program to execute callGetScore n times, and for each of those the forall requires n more calls to callGetScore. Together this is O(n), where n is the number of possible hands. The problem is really just the problem of finding the maximum element in a list, so we ought to be able to implement this in O(n) time, but this approach allows us to demonstrate the use of forall.
Oftentimes there is more than one hand that tie for the best score. In that case, the goal hand should be the hand which, among all possible "best" hands, is most easily obtained from the current hand. One way to find the goal is as follows (you also must define closerToCurrent).
Unfortunately this squares the time complexity again, so we are up to O(n^4). Alternatively you can combine these expressions into the single rule as follows.
This is much faster; it takes just over a minute to choose the goal for a hand with four rules (at least for a certain hand-rules combination; the process likely takes a fairly variable length of time to compute).
The key action in Haggle is making trades, so the computer must be able to determine if a proposed trade is beneficial.
There are a couple of different reasons why you might want to make a trade. The ability to give a predicate multiple rules makes this very easy to implement with Prolog.
Offer and Request are represented, like a hand, as a list of 5 numbers.
The first reason we provide for making a trade is if both the Offer is desired and the Request cards are "junk." The second definition means that the computer will make a trade if the requested cards are junk and it will end up with more cards than it started with, so that it will have more cards to trade.
We define cards to be junk or desired based on how the goal compares with the current hand. The term findExtra(Hand1, Hand2, Extra) assigns Extra to be the "difference" between the two hands. If a quantity in Hand1 is greater than in Hand2, then Extra contains the difference. Otherwise it contains zero. This term is used both to determine how many cards of each color the player is missing (what it desires), and how many undesired cards are in its hand (what is junk).
Then we use isLess to check that the offer is less than the Lack, which means that all of the offered cards are needed. It also checks that the request is less than Excess, meaning that none of the requested cards are used toward the goal.
The first terms in the body of the trade rules verifies that the Offer and Request are valid hands. If these variables were not initialized, then these terms generate all possibilities, so that we can use these rules to find possible trades, not just evaluate them.
At the start of the game, the rule cards are distributed among all of the players equally. With a large group, multiple copies may be distributed, but to keep it simple, our initialization just uses a single copy.
It is easy to modify this initialization process to start with more rules, or even duplicates of rules. The process of initialization can be time consuming because each player must choose its goal, but it only takes a few minutes, and having more players (and hence fewer rules per player) is actually faster than just having two.
As mentioned previously, the logic is separated into a couple of files. A runner file named "PrologRunner" contains the following fact, which serves as an import statement when called.
An example of execution:
The last command took the better part of 20 minutes to find all possibilities. As such, I cannot imagine using a forall to find a 'best' trade. Simply eliminating the possibility of the no-trade trade (listed first) and then taking the first viable trade would be reasonable. Perhaps a better alternative is to modify the trade predicate so that if Offer and Request are not initialized (as in the first term of the query), then they are generated by taking subsets of Excess and Lack rather than trying all possible hands.
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 gt=OtherScore). – find the absolute best hand (not considering other players) – takes just a couple minutes
getScore(Hand,Score),Score gt=54,nth0(0,Hand,R),R gt=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.
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.