source: anac2020/Anaconda/src/main/java/geniusweb/exampleparties/anaconda/Anaconda.java@ 43

Last change on this file since 43 was 28, checked in by wouter, 3 years ago

#3
File size: 12.4 KB
Line 
1package geniusweb.exampleparties.anaconda;
2
3import java.io.IOException;
4import java.util.ArrayList;
5import java.util.Arrays;
6import java.util.Collections;
7import java.util.HashSet;
8import java.util.List;
9import java.util.Random;
10import java.util.logging.Level;
11
12import javax.websocket.DeploymentException;
13
14import geniusweb.actions.Accept;
15import geniusweb.actions.Action;
16import geniusweb.actions.Comparison;
17import geniusweb.actions.ElicitComparison;
18import geniusweb.actions.Offer;
19import geniusweb.actions.PartyId;
20import geniusweb.bidspace.AllBidsList;
21import geniusweb.inform.ActionDone;
22import geniusweb.inform.Finished;
23import geniusweb.inform.Inform;
24import geniusweb.inform.Settings;
25import geniusweb.inform.YourTurn;
26import geniusweb.issuevalue.Bid;
27import geniusweb.party.Capabilities;
28import geniusweb.party.DefaultParty;
29import geniusweb.profile.PartialOrdering;
30import geniusweb.profile.Profile;
31import geniusweb.profileconnection.ProfileConnectionFactory;
32import geniusweb.profileconnection.ProfileInterface;
33import geniusweb.progress.Progress;
34import geniusweb.progress.ProgressRounds;
35import tudelft.utilities.logging.Reporter;
36
37public class Anaconda extends DefaultParty {
38
39 // constants
40 public static final double DEFAULT_ELICITATATION_COST = 0.01d;
41 private final Random rand = new Random();
42 private selfMap impMap;
43 private oponnentMap opponentImpMap;
44
45 private Bid receivedBid;
46
47 // variables
48 private int partial_order_bids_count = 0;
49 private ArrayList<Bid> selfBidsHistory = new ArrayList<Bid>();
50 private ArrayList<Bid> oppBidsHistory = new ArrayList<Bid>();
51
52 // parameters
53 private int bid_space_size;
54
55 // new for GeniusWeb
56 private ProfileInterface profileint;
57 private PartyId me;
58 private Progress progress;
59 private Action lastReceivedAction = null;
60 private AllBidsList allbids; // all bids in domain.
61
62 private int topN = 106;
63 private Bid reservation_bid = null;
64 private double elicitation_cost;
65 private int lower_bound_rank;
66 private int minimal_lower_bound_rank;
67 private int dynamic_lower_bound_rank;
68
69 public Anaconda() {
70 super();
71 }
72
73 public Anaconda(Reporter reporter) {
74 super(reporter);
75 }
76
77 @Override
78 public void notifyChange(Inform info) {
79 try {
80 if (info instanceof Settings) {
81 init((Settings) info);
82 } else if (info instanceof ActionDone) {
83 lastReceivedAction = ((ActionDone) info).getAction();
84 if (lastReceivedAction instanceof Offer) {
85 this.receivedBid = ((Offer) lastReceivedAction).getBid();
86 this.oppBidsHistory.add(this.receivedBid);
87 } else if (lastReceivedAction instanceof Comparison) {
88 // TODO: update MLB
89 Bid currentBid = ((Comparison) lastReceivedAction).getBid();
90 List<Bid> worseBids = ((Comparison) lastReceivedAction).getWorse();
91 List<Bid> betterBids = ((Comparison) lastReceivedAction).getBetter();
92 for (Bid worseBid : worseBids) {
93 this.impMap.comparison_update(currentBid, worseBid);
94 }
95 for (Bid betterBid : betterBids) {
96 this.impMap.comparison_update(betterBid, currentBid);
97 }
98 for (Bid betterBid : betterBids) {
99 for (Bid worseBid : worseBids) {
100 this.impMap.comparison_update(betterBid, worseBid);
101 }
102 }
103
104 this.partial_order_bids_count++;
105 this.impMap.updateBidsRank(allbids);
106 }
107 } else if (info instanceof YourTurn) {
108 double time = progress.get(System.currentTimeMillis());
109
110 // elicit - assume async
111 double lower_imp = this.impMap.rank_to_importance(this.lower_bound_rank);
112 double upper_imp = this.impMap.getMaxBidImp();
113 Bid b_star = this.getBidStar(lower_imp, upper_imp);
114 // TODO: add flag for single elicit
115 if (this.should_elicit(b_star)) {
116 Bid elicit_bid = this.impMap.getBidForElicit(lower_imp, upper_imp, allbids);
117 ElicitComparison elicit_action = new ElicitComparison(me, elicit_bid, (List<Bid>) this.allbids);
118 getConnection().send(elicit_action);
119 }
120
121 // update
122 this.update_params(time);
123 // action
124 Action action = chooseAction();
125 getConnection().send(action);
126
127 if (action instanceof Offer) {
128 Bid sent_bid = ((Offer) action).getBid();
129 this.selfBidsHistory.add(sent_bid);
130 }
131
132 if (progress instanceof ProgressRounds) {
133 progress = ((ProgressRounds) progress).advance();
134 }
135 } else if (info instanceof Finished) {
136 getReporter().log(Level.INFO, "Final ourcome:" + info);
137 }
138 } catch (Exception e) {
139 throw new RuntimeException("Failed to handle info", e);
140 }
141 }
142
143 private void update_params(double time) {
144 // linear decay
145 this.lower_bound_rank = (int) Math
146 .round((this.bid_space_size - 1) - time * ((this.bid_space_size - 1) - this.minimal_lower_bound_rank));
147 }
148
149 @Override
150 public Capabilities getCapabilities() {
151 return new Capabilities(new HashSet<>(Arrays.asList("SHAOP")), Collections.singleton(Profile.class));
152 }
153
154 @Override
155 public String getDescription() {
156 return "ANAC 2020 Anaconda SHAOP.";
157 }
158
159 private void init(Settings info) throws IOException, DeploymentException {
160 this.me = info.getID();
161 this.progress = info.getProgress();
162
163 this.profileint = ProfileConnectionFactory.create(info.getProfile().getURI(), getReporter());
164 PartialOrdering partialprofile = (PartialOrdering) profileint.getProfile();
165
166 this.reservation_bid = this.profileint.getProfile().getReservationBid();
167 this.elicitation_cost = DEFAULT_ELICITATATION_COST; // TODO: complete
168 allbids = new AllBidsList(partialprofile.getDomain());
169 this.bid_space_size = allbids.size().intValue();
170
171 this.impMap = new selfMap(partialprofile);
172 this.opponentImpMap = new oponnentMap(partialprofile);
173
174 // bids from our profile.
175 List<Bid> orderedbids = new SimpleLinearOrdering(profileint.getProfile()).getBids();
176
177 // Update my importance map
178 this.impMap.initial_update(orderedbids, allbids);
179 this.partial_order_bids_count = orderedbids.size();
180
181 // LB and MLB
182 this.lower_bound_rank = this.bid_space_size - 1;
183 double RB_sigma = Math.sqrt(bid_variance(this.reservation_bid));
184 double U_RB = this.impMap.getImportance(this.reservation_bid);
185 int RB_rank_abs = this.impMap.importanceToRankAbs(U_RB);
186 int rise = this.impMap.importanceToRankAbs(U_RB + RB_sigma) - RB_rank_abs;
187 int fall = RB_rank_abs - this.impMap.importanceToRankAbs(U_RB - RB_sigma);
188 int RB_sigma_rank_abs = (int) Math.round((rise + fall) / 2.0);
189 this.minimal_lower_bound_rank = RB_rank_abs + RB_sigma_rank_abs;
190 }
191
192 private Action chooseAction() {
193 // start competition - offer our max importance bid
194 if (!(this.lastReceivedAction instanceof Offer)) {
195 return new Offer(me, this.impMap.getBidInRank(this.bid_space_size - 1));
196 }
197
198 // accept
199 double received_bid_imp = this.impMap.getImportance(this.receivedBid);
200 int received_bid_rank = this.impMap.importanceToRankAbs(received_bid_imp);
201
202 if (received_bid_rank >= this.lower_bound_rank) {
203 return new Accept(me, this.receivedBid);
204 }
205
206 // offer
207 double lower_imp = this.impMap.rank_to_importance(this.lower_bound_rank);
208 double upper_imp = this.impMap.getMaxBidImp();
209 List<Bid> bids_intersection = this.getIntersectingBids(lower_imp, upper_imp);
210
211 // no intersection
212 Bid bid_offer = null;
213
214 if (bids_intersection.isEmpty()) {
215 List<Bid> optionalBids = this.opponentImpMap.getTopBids(bids_intersection, this.topN);
216 bid_offer = optionalBids.get(rand.nextInt(optionalBids.size()));
217 }
218 //
219 else {
220 Bid best_bid = this.impMap.getBestBid(bids_intersection);
221 this.dynamic_lower_bound_rank = this.impMap.importanceToRankAbs(this.impMap.getImportance(best_bid));
222 bid_offer = best_bid;
223 }
224
225 return new Offer(me, bid_offer);
226 }
227
228 private List<Bid> getIntersectingBids(double lower_imp, double upper_imp) {
229 List<Bid> self_bids = this.impMap.getBidsInRange(lower_imp, upper_imp, this.allbids);
230 List<Bid> opp_bids = this.getOppOptionalBids();
231 HashSet<Bid> self_bids_hash = new HashSet<Bid>(self_bids);
232
233 List<Bid> intersection = new ArrayList<Bid>();
234
235 for (Bid bid : opp_bids) {
236 if (self_bids_hash.contains(bid)) {
237 intersection.add(bid);
238 }
239 }
240
241 return intersection;
242 }
243
244 private List<Bid> getOppOptionalBids() {
245 double opp_lower_bound = this.find_OLB();
246 List<Bid> optionalBids = this.opponentImpMap.getBidsInRange(opp_lower_bound, Double.MAX_VALUE, this.allbids);
247
248 return optionalBids;
249 }
250
251 // elicit comparison
252 private Double bid_variance(Bid bid) {
253 return bid_variance(bid, 0);
254 }
255
256 private Double bid_variance(Bid bid, int n_diff) {
257 Double variance = 0.0;
258
259 for (String issue : bid.getIssues()) {
260 List<impUnit> currentIssueList = this.impMap.get(issue);
261 for (impUnit currentUnit : currentIssueList) {
262 int n = currentUnit.total_count + n_diff;
263 Double p = currentUnit.probability;
264
265 variance += issue_variance(n, p);
266 }
267 }
268
269 return variance;
270 }
271
272 private Double issue_variance(int n, Double p) {
273 if (n < 2) {
274 return 0.0;
275 }
276
277 Double variance = 0.0;
278 // E(x)
279 Double E1 = 0.0;
280 // E(x^2)
281 Double E2 = 0.0;
282
283 // init for k = 2
284 int n_choose_k = n * (n - 1) / 2;
285 Double pow_p_k = p * p;
286 Double pow_1_p_n_k = Math.pow(1 - p, n - 2);
287
288 for (int k = 2; k <= n; k++) {
289 Double log_k = Math.log(k);
290 Double val = n_choose_k * pow_p_k * pow_1_p_n_k * log_k;
291 E1 += val;
292 E2 += val * log_k;
293
294 // update
295 pow_p_k *= p;
296 pow_1_p_n_k /= 1 - p;
297 n_choose_k *= (n - k);
298 n_choose_k /= (k + 1);
299 }
300
301 // Var(x) = E(x^2) - (E(x)^2)
302 variance = E2 - E1 * E1;
303 return variance;
304 }
305
306 private boolean should_elicit(Bid b_star) {
307 double time = progress.get(System.currentTimeMillis());
308
309 double U_b_star = this.impMap.getImportance(b_star);
310
311 double U_RB = this.impMap.getImportance(this.reservation_bid);
312
313 double RB_sigma = Math.sqrt(bid_variance(this.reservation_bid));
314 // n -> n + N -2
315 int N = this.partial_order_bids_count;
316 double RB_sigma_new = Math.sqrt(bid_variance(this.reservation_bid, N - 2));
317
318 int RB_rank_abs = this.impMap.importanceToRankAbs(U_RB);
319 int rise = this.impMap.importanceToRankAbs(U_RB + RB_sigma) - RB_rank_abs;
320 int fall = RB_rank_abs - this.impMap.importanceToRankAbs(U_RB - RB_sigma);
321 int RB_sigma_rank_abs = (int) Math.round((rise + fall) / 2.0);
322
323 rise = this.impMap.importanceToRankAbs(U_RB + RB_sigma_new) - RB_rank_abs;
324 fall = RB_rank_abs - this.impMap.importanceToRankAbs(U_RB - RB_sigma_new);
325 int RB_sigma_new_rank_abs = (int) Math.round((rise + fall) / 2.0);
326
327 double U_OLB = this.find_OLB(); // minimum opp. imp map value(opp. bids history)
328 double OLB = this.impMap.importanceToRankAbs(U_OLB) / this.bid_space_size;
329 double ORB = 0.5; // prior
330
331 double OMLB_prior = ORB + (1.0 * RB_sigma_rank_abs / this.bid_space_size);
332 if (OLB < OMLB_prior) {
333 Bid bid_almost_worst = this.impMap.getBidInRank(1);
334 double bid_sigma = Math.sqrt(bid_variance(bid_almost_worst));
335 double U_bid = this.impMap.getImportance(bid_almost_worst);
336 int bid_sigma_rank_abs = this.impMap.importanceToRankAbs(U_bid + bid_sigma)
337 - this.impMap.importanceToRankAbs(U_bid);
338 double bid_sigma_rank = bid_sigma_rank_abs / this.bid_space_size;
339
340 double projection = (1 - OLB) * time;
341
342 OMLB_prior = Math.max(bid_sigma_rank, projection);
343 }
344
345 double alpha = time;
346 double OMLB = alpha * OLB + (1 - alpha) * OMLB_prior;
347 double seg_OMLB = 1 - OMLB;
348
349 double p_diff = 1.0 * (RB_sigma_new_rank_abs - RB_sigma_rank_abs) * seg_OMLB / this.bid_space_size;
350
351 return (this.elicitation_cost / (U_b_star - U_RB)) < p_diff;
352 }
353
354 private double find_OLB() {
355 double min_bid_imp = Double.POSITIVE_INFINITY;
356
357 for (Bid bid : this.oppBidsHistory) {
358 double bid_imp = this.opponentImpMap.getImportance(bid);
359
360 if (bid_imp < min_bid_imp) {
361 min_bid_imp = bid_imp;
362 }
363 }
364
365 return min_bid_imp;
366 }
367
368 private Bid getBidStar(double lower_imp, double upper_imp) {
369 List<Bid> optionalBids = this.getIntersectingBids(lower_imp, upper_imp);
370
371 if (optionalBids.isEmpty()) {
372 double RB_imp = this.impMap.getImportance(this.reservation_bid);
373 int RB_rank = this.impMap.importanceToRankAbs(RB_imp);
374 int best_rank = this.bid_space_size - 1;
375 int mid_bid_imp = Math.round((RB_rank + best_rank) / 2);
376 Bid bid = this.impMap.getBidInRank(mid_bid_imp);
377 return bid;
378 }
379
380 // return best bid from optional bids
381 Bid bid = this.impMap.getBestBid(optionalBids);
382 return bid;
383 }
384}
Note: See TracBrowser for help on using the repository browser.