-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathsolver.pl
145 lines (116 loc) · 4.26 KB
/
solver.pl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
/*
Game description framework
author: Kostas Stathis
contributor: Agnieszka Mensfelt
SWI-Prolog version
Last update: 06/08/2024
*/
/* Game independent description */
% All legal evolutions of a game: can be used both as a generator and test.
game(F,F):- final(F).
game(S,F):- \+ final(S), legal(M,S), game(do(M,S),F).
% Situation Calculus - our formulation for games.
holds(F, S):- initially(F, S).
holds(F, do(M, S)):- effect(F, M, S).
holds(F, do(A, S)):- holds(F, S), \+ abnormal(F, A, S).
/* Game specific predicates for PD-like games */
% Initial state
initial(s0).
% What holds initially: who is a player, their role, and whether they can play.
initially(player(you), s0).
initially(player(them), s0).
initially(role(you,row), s0).
initially(role(them,col), s0).
initially(control(you), s0).
initially(control(them), s0).
% When a state is final: no need to check content as it generated by game/2,
% implying it is a legal state.
final(do(choice(_P2, _M2), do(choice(_P1, _M1), S))):-initial(S).
% A legal move is a possible move where the player has control (is its turn).
legal(choice(P, M), S):- possible(choice(P, M), S), holds(control(P), S).
% What is possible for a player to choose
possible(choice(P,'B'), S):- holds(player(P), S).
possible(choice(P,'R'), S):- holds(player(P), S).
% The effects of a move: if P has chosen M, then in the next state this
% is what they did.
effect(did(P, M), choice(P, M), _S).
% The effects of a move: once a choice is made, the player looses control, i.e.
% cannot move anymore.
abnormal(control(P), choice(P, _M), _S).
% What holds finally: the outcome with players, Moves, and Utilities.
finally(outcome(P1,M1,U1,P2,M2,U2), S):-
final(S),
holds(role(P1, row), S),
holds(did(P1, M1), S),
holds(role(P2, col), S),
holds(did(P2, M2), S),
payoff(M1, M2, U1, U2).
% Goals achieved by the players.
finally(goal(P1, U1), S):-
finally(outcome(P1,_,U1,_,_,_), S).
finally(goal(P2, U2), S):-
finally(outcome(_,_,_,P2,_,U2), S).
/* Auxiliary predicates */
minU(M, U):-
findall(X, payoff(M, _, X, _), Xs),
sort(Xs, [U|_]).
higher_guaranteed_payoff(M1, M2):-
minU(M1, U1),
minU(M2, U2),
U1 > U2.
lower_guaranteed_payoff(M1, M2):-
minU(M1, U1),
minU(M2, U2),
U1 < U2.
higher(X, Y) :-
X > Y.
lower(X, Y) :-
X < Y.
lowest_payoff(Payoff) :-
findall(P, (payoff(_, _, P, _); payoff(_, _, _, P)), Payoffs),
min_list(Payoffs, MinPayoff),
Payoff = MinPayoff.
highest_payoff(Payoff) :-
findall(P, (payoff(_, _, P, _); payoff(_, _, _, P)), Payoffs),
max_list(Payoffs, MaxPayoff),
Payoff = MaxPayoff.
lowest_individual_payoff_for_choice(Payoff, Choice) :-
payoff(Choice, _, Payoff, _),
\+ (payoff(Choice, _, P1, _), P1 < Payoff).
highest_individual_payoff_for_choice(Payoff, Choice) :-
payoff(Choice, _, Payoff, _),
\+ (payoff(Choice, _, P1, _), P1 > Payoff).
highest_guaranteed_payoff_choice(Choice) :-
findall(Payoff, lowest_individual_payoff_for_choice(Payoff, _), Payoffs),
max_list(Payoffs, LowestPayoff),
lowest_individual_payoff_for_choice(LowestPayoff, Choice).
lowest_guaranteed_payoff_choice(Choice) :-
findall(LowestPayoff, lowest_individual_payoff_for_choice(LowestPayoff, _), LowestPayoffs),
min_list(LowestPayoffs, MaxLowestPayoff),
lowest_individual_payoff_for_choice(MaxLowestPayoff, Choice).
highest_possible_individual_payoff(Payoff) :-
findall(P, (payoff(_, _, P, _); payoff(_, _, _, P)), Payoffs),
max_list(Payoffs, MaxPayoff),
Payoff = MaxPayoff.
lowest_possible_individual_payoff(Payoff) :-
findall(P, (payoff(_, _, P, _); payoff(_, _, _, P)), Payoffs),
min_list(Payoffs, MaxPayoff),
Payoff = MaxPayoff.
highest_mutual_payoff(Choice1, Choice2) :-
findall(Total, (
payoff(_, _, Payoff1, Payoff2),
Total is Payoff1 + Payoff2,
Payoff1 =:= Payoff2
), Totals),
max_list(Totals, MaxTotal),
payoff(Choice1, Choice2, Payoff1, Payoff2),
Payoff1 + Payoff2 =:= MaxTotal.
lowest_mutual_payoff(Choice1, Choice2) :-
findall(Total, (
payoff(_, _, Payoff1, Payoff2),
Total is Payoff1 + Payoff2,
Payoff1 =:= Payoff2
), Totals),
min_list(Totals, MaxTotal),
payoff(Choice1, Choice2, Payoff1, Payoff2),
Payoff1 + Payoff2 =:= MaxTotal.