source: src/main/java/agents/anac/y2014/Gangster/BidStorage.java

Last change on this file was 1, checked in by Wouter Pasman, 6 years ago

Initial import : Genius 9.0.0
File size: 11.5 KB
Line 
1package agents.anac.y2014.Gangster;
2
3import java.util.ArrayList;
4import java.util.List;
5import java.util.PriorityQueue;
6import java.util.TreeSet;
7
8import genius.core.Bid;
9import genius.core.bidding.BidDetails;
10
11class BidStorage {
12
13 int MAX_CAPACITY; //maximum size to avoid decrease in performance.
14 int MAX_SIZE_AFTER_CLEANING; // 2 times the minimum size we need to maintain good results.
15 int expectedAmountOfProposals;
16
17 int MAX_SIZE_NOT_SELFISH_ENOUGH = 5000;
18 int MAX_SIZE_NOT_SELFISH_ENOUGH_AFTER_CLEANING = 1000;
19
20 int NUM_BINS_FOR_PROPOSED_TO_US = 100;
21
22 //these two sets store the samples found by the searches and which are selfish enough. These two lists should always contain exactly the same elements.
23 private TreeSet<ExtendedBidDetails> sortedByDiversity = new TreeSet(ExtendedBidDetails.DiversityComparator);
24 private TreeSet<ExtendedBidDetails> sortedByDistance = new TreeSet(ExtendedBidDetails.DistanceComparator);
25
26 private TreeSet<ExtendedBidDetails> notSelfishEnough = new TreeSet(ExtendedBidDetails.UtilityComparator); //although priority queue is faster, it allows multiple copies of the same element, which we don't want.
27
28 //these lists store the proposals made
29 private ArrayList<Bid> proposedByOpponent;
30 private ArrayList<Bid> proposedByUs;
31
32 PriorityQueue<BidDetails>[] reproposableBids;
33 TreeSet<BidDetails> reproposableBidsMain;
34
35 private double targetUtility;
36
37 public BidStorage(int maxCapacity, int maxSizeAfterCleaning, int expectedAmountOfProposals) {
38 this.MAX_CAPACITY = maxCapacity;
39 this.MAX_SIZE_AFTER_CLEANING = maxSizeAfterCleaning;
40
41 proposedByOpponent = new ArrayList(expectedAmountOfProposals);
42 proposedByUs = new ArrayList(expectedAmountOfProposals);
43 reproposableBids = new PriorityQueue[NUM_BINS_FOR_PROPOSED_TO_US];
44 reproposableBidsMain = new TreeSet<BidDetails>();
45 }
46
47
48
49
50 /**
51 * Add incoming bid from the opponent.
52 *
53 * @param opponentBid
54 * @throws Exception
55 */
56 void addOpponentBid(BidDetails bd) throws Exception{
57
58 proposedByOpponent.add(bd.getBid());
59
60 //if the list gets too large, clean up.
61 if(proposedByOpponent.size() > 3000){
62 ArrayList<Bid> newList = new ArrayList(3500);
63 for(int i=proposedByOpponent.size()/2; i<proposedByOpponent.size(); i++){
64 newList.add(proposedByOpponent.get(i));
65 proposedByOpponent = newList;
66 }
67
68 }
69
70
71
72 //now we should recalculate the distances of samples stored in the list sortedByOpponentDistance to keep the sorting correct.
73 for(ExtendedBidDetails ebd : sortedByDiversity){ //we loop over sortedByDiversity because it contains exactly the same elements as sortedByOpponentDistance
74
75 //check if the new opponent bid is closer to the current sample than the closest opponent bid currently set in the sample.
76 int dist = Utils.calculateManhattanDistance(ebd.bidDetails.getBid(), bd.getBid());
77 if(dist < ebd.distanceToOpponent){
78
79 //remove the ebd from the treeset
80 sortedByDistance.remove(ebd);
81
82 //change the opponent distance
83 ebd.setClosestOpponentBid(bd.getBid(), dist);
84
85 //re-insert ebd into the treeSet
86 sortedByDistance.add(ebd);
87 }
88
89
90 }
91
92 int i = (int)Math.floor(bd.getTime() * ((double)reproposableBids.length));
93 if(i == reproposableBids.length){
94 i--; //security measure.
95 }
96
97 if(reproposableBids[i] == null){
98 reproposableBids[i] = new PriorityQueue<BidDetails>();
99 }
100
101 if(reproposableBids[i].size() > 0){
102 BidDetails old_first = (BidDetails)reproposableBids[i].peek();
103 if(bd.getMyUndiscountedUtil() > old_first.getMyUndiscountedUtil()){
104 reproposableBidsMain.remove(old_first);
105 reproposableBidsMain.add(bd);
106 }
107 }else{
108 reproposableBidsMain.add(bd);
109 }
110 reproposableBids[i].add(bd);
111
112
113 }
114
115
116 void addBidProposedByUs(Bid ourBid) throws Exception{
117
118 proposedByUs.add(ourBid);
119
120 //if the list gets too large, clean up.
121 if(proposedByUs.size() > 3000){
122 ArrayList<Bid> newList = new ArrayList(3500);
123 for(int i=proposedByUs.size()/2; i<proposedByUs.size(); i++){
124 newList.add(proposedByUs.get(i));
125 proposedByUs = newList;
126 }
127 }
128
129 //now we should recalculate the diversity of all stored samples.
130 for(ExtendedBidDetails ebd : sortedByDistance){ //we loop over sortedByOpponentDistance because it contains exactly the same elements as sortedByOpponentDistance
131
132 int diversity = Utils.calculateManhattanDistance(ebd.bidDetails.getBid(), ourBid);
133 if(diversity < ebd.diversity){
134
135 //remove the ebd from the treeset
136 sortedByDiversity.remove(ebd);
137
138 //change the opponent distance
139 ebd.setOurClosestBid(ourBid, diversity);
140
141 //re-insert ebd into the treeSet
142 sortedByDiversity.add(ebd);
143 }
144 }
145
146
147 }
148
149
150
151 void setTargetUtility(double targetUtility) throws Exception{
152
153 this.targetUtility = targetUtility;
154
155 if(notSelfishEnough.size() == 0){
156 return;
157 }
158
159 ExtendedBidDetails ebd = notSelfishEnough.last();
160 double util = ebd.getMyUndiscountedUtil();
161 while(util > targetUtility){
162
163 notSelfishEnough.remove(ebd);
164
165 //recalculate distance and diversity of ebd.
166 for(Bid opponentBid : proposedByOpponent){
167 ebd.setClosestOpponentBidMaybe(opponentBid);
168 }
169 for(Bid ourBid : proposedByUs){
170 ebd.setOurClosestBidMaybe(ourBid);
171 }
172
173 sortedByDistance.add(ebd);
174 sortedByDiversity.add(ebd);
175
176 if(notSelfishEnough.size() == 0){
177 break;
178 }
179
180 ebd = notSelfishEnough.last();
181 util = ebd.getMyUndiscountedUtil();
182 }
183
184
185
186 }
187
188
189
190 //add all bids found by genetic algorithm
191 void addAll(List<BidDetails> bids, boolean foundByLocalSearch) throws Exception{
192 for(BidDetails bd : bids){
193 add(bd, foundByLocalSearch);
194 }
195
196 }
197
198 //add a bid found by genetic algorithm
199 void add(BidDetails sample, boolean foundByLocalSearch) throws Exception{
200
201 //wrap the sample in an extended data structure
202 ExtendedBidDetails ebd = new ExtendedBidDetails(sample);
203
204 //store the sample, but only if we haven't already proposed it before.
205 if(ebd.diversity > 0){
206
207 if(ebd.getMyUndiscountedUtil() > targetUtility){
208
209
210 //find the opponent bid that was closest to this sample.
211 for(Bid opponentBid : proposedByOpponent){
212 ebd.setClosestOpponentBidMaybe(opponentBid);
213 }
214 sortedByDistance.add(ebd);
215
216
217
218 //find our bid that was closest to this sample.
219 for(Bid ourBid : proposedByUs){
220 ebd.setOurClosestBidMaybe(ourBid);
221 }
222 sortedByDiversity.add(ebd);
223
224
225
226 }else{
227 notSelfishEnough.add(ebd);
228 }
229
230
231 if(notSelfishEnough.size() > MAX_SIZE_NOT_SELFISH_ENOUGH){
232 cleanUpNotSelfishEnough();
233 }
234
235
236 //if we have stored too many elements we should throw away some.
237 if(sortedByDiversity.size() > MAX_CAPACITY){
238 cleanUp();
239 }
240
241
242 }
243
244
245 }
246
247
248
249
250 //This method is called when we have to many bids stored.
251 //throws away a predefined part of the stored samples.
252 void cleanUp(){
253
254 int n = MAX_SIZE_AFTER_CLEANING / 2;
255 TreeSet<ExtendedBidDetails> savedBids = new TreeSet(ExtendedBidDetails.IDComparator);
256
257 //save the n best elements of both lists..
258 ExtendedBidDetails nextElement;
259 nextElement = sortedByDiversity.last();
260 for(int i=0; i<n; i++){
261 savedBids.add(nextElement);
262 nextElement = sortedByDiversity.lower(nextElement);
263 }
264
265
266 nextElement = sortedByDistance.last();
267 for(int i=0; i<n; i++){
268 savedBids.add(nextElement);
269 nextElement = sortedByDistance.lower(nextElement);
270 }
271
272 sortedByDiversity.clear();
273 sortedByDiversity.addAll(savedBids);
274
275
276 sortedByDistance.clear();
277 sortedByDistance.addAll(savedBids);
278
279 }
280
281
282 void cleanUpNotSelfishEnough(){
283
284 ArrayList<ExtendedBidDetails> savedBids = new ArrayList();
285
286 //save the n best elements of both lists..
287 ExtendedBidDetails nextElement;
288 nextElement = notSelfishEnough.last();
289 for(int i=0; i<MAX_SIZE_NOT_SELFISH_ENOUGH_AFTER_CLEANING; i++){
290 savedBids.add(nextElement);
291 nextElement = notSelfishEnough.lower(nextElement);
292 }
293
294 notSelfishEnough.clear();
295 notSelfishEnough.addAll(savedBids);
296
297 }
298
299
300 boolean weHaveSelfishEnoughBids(){
301 return sortedByDiversity.size() > 0;
302 }
303
304
305 /**
306 * Returns the next bid to propose.
307 * Returns null if we don't have any bid that is selfish enough.
308 *
309 * @param ourTargetUtility
310 * @param maxDistance
311 * @return
312 */
313 ExtendedBidDetails getNext(double ourTargetUtility, int maxDistance){
314
315 //do we have any bids that are selfish enough?
316 // if no: return null
317 // if yes: do we have any bids that are altruistic enough and selfish enough?
318 // if yes: get the set of bids that are altreuistic enough and selfish enough, and return the most altruistic bid
319 // if no: get the set of bids that are selfish enough, and return the bid with highest diversity among those
320
321
322 if(sortedByDistance.size() == 0){
323 return null;
324 }
325
326
327 ExtendedBidDetails next = sortedByDistance.last();
328 if(next.distanceToOpponent < maxDistance){
329 return next;
330 }
331
332 next = sortedByDiversity.last();
333 return next;
334
335 }
336
337 void removeBid(ExtendedBidDetails ebd){
338 sortedByDiversity.remove(ebd);
339 sortedByDistance.remove(ebd);
340 }
341
342
343
344 int firstNonNullBucket = 0;
345
346
347 /**
348 * Returns the best bid in the past time window proposed to us.
349 *
350 * @param time
351 * @param ourTargetUtility
352 * @return
353 */
354 BidDetails getReproposableBid(double time, double ourTargetUtility, double timeWindow){
355
356
357 double minTime = time - timeWindow;
358
359
360 int j = (int) Math.floor(minTime * (double)reproposableBids.length);
361 for(int k=firstNonNullBucket; k<j; k++){
362 reproposableBids[k] = null;
363 }
364 if(j>0){
365 firstNonNullBucket = j;
366 }
367
368 BidDetails possibleProposal = null;
369 while(reproposableBidsMain.size() > 0){
370
371 possibleProposal = reproposableBidsMain.first();
372
373 //first test if utility is high enough
374 if(possibleProposal.getMyUndiscountedUtil() < ourTargetUtility){
375 return null; //even the best opponent bid doesn't have enough utility
376 }
377
378 //then test if it is inside our time window.
379 if(possibleProposal.getTime() > minTime){
380
381 //if yes, we should return it. but fist
382 //remove it from the main list, as well as from its bucket
383 //get the new best element from the bucket and add it to the main list.
384
385 reproposableBidsMain.remove(possibleProposal);
386
387 int i = (int) Math.floor(possibleProposal.getTime() * (double)reproposableBids.length);
388 if(reproposableBids[i] != null){
389
390 reproposableBids[i].remove(possibleProposal);
391
392 if(reproposableBids[i].size() > 0){
393 reproposableBidsMain.add((BidDetails)reproposableBids[i].peek());
394 }
395 }
396 return possibleProposal;
397
398 }else{
399
400 //if the bid is not inside the time window, then just remove it.
401 reproposableBidsMain.remove(possibleProposal);
402 }
403 }
404
405 return null;
406 }
407
408 /**
409 *This method should be called when we do not expect the discounted utilities offered by the opponent to increase.
410 * Sets the target to the next expected utility u_i.
411 *
412 */
413 double getBestOfferedUtility(double time, double timeWindow){
414
415 if(reproposableBidsMain.size() == 0){
416 return 0;
417 }
418
419 BidDetails best = reproposableBidsMain.first();
420 while(best != null && best.getTime() < (time-timeWindow)){
421 best = reproposableBidsMain.higher(best);
422 }
423
424 if(best == null){
425 return 0;
426 }
427
428 return best.getMyUndiscountedUtil();
429
430 }
431
432
433 int size(){
434 return sortedByDiversity.size() + notSelfishEnough.size();
435 }
436
437 //Returns the number of bids stored that are selfish enough.
438 int getNumSelfishBids(){
439 return sortedByDiversity.size();
440 }
441
442 boolean testConsistency(){
443 return sortedByDiversity.size() == sortedByDistance.size();
444 }
445}
Note: See TracBrowser for help on using the repository browser.