# Pages … Home Prolog Prolog Project - Haggle Page History

## Key

• This line was removed.
• Formatting was changed.
Comment: Migrated to Confluence 4.0
Wiki Markup
```{style}
cite{font-family:Courier New; font-style:normal}
{style}

```

This

...

page

...

implements

...

an

...

interesting

...

project

...

in

...

order

...

to

...

demonstrate

...

how

...

the

...

details

...

presented

...

earlier

...

all

...

come

...

together

...

to

...

make

...

more

...

powerful

...

programs.

...

...

...

...

...

...

...

### 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....} Code Block```%calculate the basic score score1([R,O,Y,B,W],Score):-Score is Y+2*B+3*R+4*O+5*W. %Rule13: every set of two yellow and a white doubles the value of the white score13([_,_,Y,_,W], BaseScore, NewScore, WhiteVal):- Y>=2, W>=1, Partial is BaseScore+WhiteVal, score13([_,_,Y-2,_,W-1], Partial, NewScore, WhiteVal). score13([_,_,Y,_,_], BaseScore, BaseScore, _) :- Y<2. score13([_,_,Y,_,W], BaseScore, BaseScore, _) :- Y>=2,W<1. {code} ??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??. h4. Calling the Score Functions Since a computer player may know any subset of rules, we include the following methods for calculating a score. {code}```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.

Code Block
```callGetScore(Hand, Rules, FinalScore):-hand(Hand),getScore(Hand,Rules,0,FinalScore,[1,1,1,1,1]).
getScore(_, [], BaseScore, BaseScore, _).
getScore(Hand, [Rule|Rules], BaseScore,FinalScore,GuessedWorth):-
score(Rule,Hand,NewHand,BaseScore,NewScore,GuessedWorth,NewGuessedWorth),
getScore(NewHand,Rules,NewScore,FinalScore,NewGuessedWorth).

%dispatchers
score(1,Hand,Hand, _,NewScore,_,NewGuessedWorth):-
NewGuessedWorth = [3,4,1,2,5], score1(Hand,NewScore).
score(13,Hand,Hand, BaseScore,NewScore,GuessedWorth,GuessedWorth):-
nth0(4,GuessedWorth, WhiteVal),score13(Hand,BaseScore,NewScore,WhiteVal).
{code}

??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??.

h3. Finding A Goal

{code}```

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

Code Block
```findGoal(Rules, BestHand):-
callGetScore(BestHand,Rules,Score),forall(callGetScore(_,Rules,OtherScore),Score>=OtherScore).
{code}

```

In

...

order

...

to

...

know

...

whether

...

or

...

not

...

a

...

...

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

...

).

...

}
Code Block
```chooseGoal(player(Rules, CurrentHand, GoalHand)):-findGoal(Rules,GoalHand),
forall(findGoal(Rules,AltGoal), closerToCurrent(CurrentHand,GoalHand,AltGoal)).
{code}

```

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.

...

}
Code Block
```chooseGoal(player(Rules,CurrentHand,GoalHand)):-callGetScore(GoalHand,Rules,Score),
forall(callGetScore(OtherHand,Rules,OtherScore), isBetter(GoalHand,OtherHand,Score,OtherScore,CurrentHand)).

{code}

```

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).

...

...

...

### Initialization

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.

Code Block
```allRules([1,4,5,10,11,13,14,15]). %we only implemented scoring functions for about half of the rules

%Creates a list of N players
initializePlayers(NPlayers, PlayerList) :- allRules(Rules), length(Rules, NRules),
floor(NRules/NPlayers, NRulesPer),
initializePlayers(NPlayers, PlayerList, NRulesPer, Rules),!.
%recursive definition to create the list of players
initializePlayers(0, [], _, _).
initializePlayers(NPlayers, [player(Rules, Hand, Goal)|PlayerList],
NRulesPer, RulesLeft):-
H1 = [3, 3, 3, 3, 3],
decrement(H1, H2), decrement(H2, H3), decrement(H3, Hand), %decrement randomly removes one card
pickRules(Rules, NewRulesLeft, RulesLeft, NRulesPer),      %chooses some rules and removes them RulesLeft
chooseGoal(player(Rules, Hand, Goal)), NPlayersLess is NPlayers-1,
initializePlayers(NPlayersLess, PlayerList, NRulesPer, NewRulesLeft).

{code}

```

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.

...

### Results

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.

...

}
Code Block
```loadGame :-consult('HaggleRules.pl'), consult('HagglePlayer.pl').
{code}

```

An

...

example

...

of

...

execution:

...

Code Block
title Queries
```?- ['PrologRunner.pl'].
% HaggleRules.pl compiled 0.00 sec, 124 bytes
% HagglePlayer.pl compiled 0.00 sec, 76 bytes
true.

% HaggleRules.pl compiled 0.00 sec, 124 bytes
% HagglePlayer.pl compiled 0.00 sec, 76 bytes
true.

?- initializePlayers(2, Players).
Players = [player([1, 5, 11, 15], [3, 1, 3, 3, 2], [3, 1, 0, 2, 4]),
player([4, 10, 13, 14], [3, 3, 2, 2, 2], [2, 2, 4, 3, 2])].

trade(Request,Offer,player([4, 10, 13, 14], [3, 3, 2, 2, 2], [2, 2, 4, 3, 2])).
Offer = Request, Request = [0, 0, 0, 0, 0] ;
Offer = [0, 1, 0, 0, 0],
Request = [0, 0, 1, 0, 0] ;%the program finds each Offer/Request pair twice, which
Offer = [0, 1, 0, 0, 0],   %we removed to save space
Request = [0, 0, 0, 1, 0] ;
Offer = [1, 0, 0, 0, 0],
Request = [0, 0, 1, 0, 0] ;
Offer = [1, 0, 0, 0, 0],
Request = [0, 0, 0, 1, 0] ;
Offer = [1, 1, 0, 0, 0],
Request = [0, 0, 2, 0, 0] ;
Offer = [1, 1, 0, 0, 0],
Request = [0, 0, 0, 1, 0] ;
Offer = [1, 1, 0, 0, 0],
Request = [0, 0, 1, 1, 0] ;
false.

{code}

```

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'

...

...

Simply

...

eliminating

...

the

...

possibility

...

of

...

the

...

...

...

(listed

...

first)

...

and

...

then

...

taking

...

the

...

first

...

viable

...

...

would

...

be

...

reasonable.

...

Perhaps

...

a

...

better

...

alternative

...

is

...

to

...

modify

...

the

...

...

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.

...

Wiki Markup
```{htmlcomment}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 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.

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:
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
Hand
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. {```

...

 `htmlcomment}`