source: src/main/java/agents/anac/y2014/SimpaticoAgent/Simpatico.java@ 84

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

Initial import : Genius 9.0.0
File size: 18.4 KB
Line 
1package agents.anac.y2014.SimpaticoAgent;
2
3import java.util.ArrayList;
4import java.util.HashMap;
5import java.util.List;
6import java.util.Random;
7
8import genius.core.Agent;
9import genius.core.Bid;
10import genius.core.actions.Accept;
11import genius.core.actions.Action;
12import genius.core.actions.Offer;
13import genius.core.issue.Issue;
14import genius.core.issue.IssueDiscrete;
15import genius.core.issue.IssueInteger;
16import genius.core.issue.IssueReal;
17import genius.core.issue.Value;
18import genius.core.issue.ValueDiscrete;
19import genius.core.issue.ValueInteger;
20import genius.core.issue.ValueReal;
21
22/**
23 * @author Bedour Alrayes, Paulo Ricca, Ozgur Kafali, Kostas Stathis
24 * @institution Royal Holloway University of London
25 *
26 *
27 */
28public class Simpatico extends Agent {
29 private Action actionOfPartner = null;
30 private double initialMinimumBidUtility = 0.9;
31 private double minimumBidUtility = initialMinimumBidUtility;
32 private double acceptanceBidUtility = 0.85;
33 private BidTuple bestOpponentOffer = null;
34 private ArrayList<BidTuple> bestOpponentOffers = new ArrayList<Simpatico.BidTuple>();
35 private int bidToSubmitBack = 0; // used in the last moments, we propose
36 // back the best of the opponents bids
37
38 // Search Parameters
39 private int initialSearchDepth = 3;
40 private int maximumSearchDepth = initialSearchDepth;
41 private int maximumSearchDepthForOurBids = 2;
42 private float percentageOfIssuesToChange = 0.5f;
43 private float randomSearchRatio = 0.3f;
44
45 // Decision making parameters
46 double maximumRoundTime = 0;
47 double lastRoundTime = 0;
48 boolean opponentIsCooperative = true;
49
50 int countOpponentOffers = 0;
51 double cooperationthreshold = 0.5;
52 double minimumCooperativeUtility = 0.5;
53 double numberOfCooperativeUtilities;
54
55 @Override
56 public void init() {
57 actionOfPartner = null;
58 initialMinimumBidUtility = 0.9;
59 minimumBidUtility = initialMinimumBidUtility;
60 acceptanceBidUtility = 0.85;
61 bestOpponentOffer = null;
62 bestOpponentOffers = new ArrayList<Simpatico.BidTuple>();
63 bidToSubmitBack = 0; // used in the last moments, we propose back the
64 // best of the opponents bids
65
66 // Search Parameters
67 initialSearchDepth = 3;
68 maximumSearchDepth = initialSearchDepth;
69 maximumSearchDepthForOurBids = 2;
70 percentageOfIssuesToChange = 0.5f;
71 randomSearchRatio = 0.3f;
72
73 // Decision making parameters
74 maximumRoundTime = 0;
75 lastRoundTime = 0;
76 opponentIsCooperative = true;
77
78 countOpponentOffers = 0;
79 cooperationthreshold = 0.5;
80 minimumCooperativeUtility = 0.5;
81 }
82
83 private BidTuple SearchNeighbourhood(BidTuple initialBid) {
84 return SearchNeighbourhood(initialBid, maximumSearchDepth);
85 }
86
87 @Override
88 public String getVersion() {
89 return "1.0";
90 }
91
92 @Override
93 public String getName() {
94 return "Simp�tico";
95 }
96
97 @Override
98 public void ReceiveMessage(Action opponentAction) {
99 actionOfPartner = opponentAction;
100 }
101
102 private BidTuple SearchNeighbourhood(BidTuple initialBid, int depth) {
103 if (depth == 0) {
104 return initialBid;
105 }
106 BidTuple bestBid = initialBid;
107 int nIssues = initialBid.bid.getIssues().size();
108
109 int numberOfIssuesToChange = (int) (nIssues
110 * percentageOfIssuesToChange);
111 if (numberOfIssuesToChange > 5)
112 numberOfIssuesToChange = 5;
113 debug("NUMBER OF ISSUES: " + numberOfIssuesToChange, 3);
114
115 int[] issuesToChange = new int[numberOfIssuesToChange];
116 Random rand = new Random();
117 for (int i = 0; i < issuesToChange.length; i++) {
118 boolean alreadyChosen;
119 boolean assigned = false;
120 do {
121 alreadyChosen = false;
122 int issueIndexChosen = 1 + rand.nextInt(nIssues - 1);
123 for (int j = 0; j <= i - 1; j++) {
124 if (issuesToChange[j] == issueIndexChosen) {
125 alreadyChosen = true;
126 }
127 }
128 if (!alreadyChosen) {
129 issuesToChange[i] = issueIndexChosen;
130 assigned = true;
131 }
132
133 } while (!assigned && alreadyChosen);
134 }
135 try {
136 for (int i = 0; i < issuesToChange.length; i++) {
137 BidTuple bidTupleTmp;
138 switch (initialBid.bid.getIssues().get(issuesToChange[i])
139 .getType()) {
140 case DISCRETE:
141 bidTupleTmp = getDiscreteIssueVariation(initialBid,
142 issuesToChange[i], 1);
143 if (bidTupleTmp != null) {
144 if (bidTupleTmp.utility > bestBid.utility)
145 bestBid = bidTupleTmp;
146 BidTuple returnedBid = SearchNeighbourhood(bidTupleTmp,
147 depth - 1);
148 if (returnedBid.utility > bestBid.utility)
149 bestBid = returnedBid;
150 }
151
152 bidTupleTmp = getDiscreteIssueVariation(initialBid,
153 issuesToChange[i], -1);
154 if (bidTupleTmp != null) {
155 if (bidTupleTmp.utility > bestBid.utility)
156 bestBid = bidTupleTmp;
157 BidTuple returnedBid = SearchNeighbourhood(bidTupleTmp,
158 depth - 1);
159 if (returnedBid.utility > bestBid.utility)
160 bestBid = returnedBid;
161 }
162 break;
163 case REAL:
164 IssueReal issueReal = (IssueReal) initialBid.bid.getIssues()
165 .get(issuesToChange[i]);
166 double range = issueReal.getUpperBound()
167 - issueReal.getLowerBound();
168 double variation = range * 0.05;
169
170 bidTupleTmp = getRealIssueVariation(initialBid,
171 issuesToChange[i], rand.nextFloat() * variation);
172 if (bidTupleTmp != null) {
173 if (bidTupleTmp.utility > bestBid.utility)
174 bestBid = bidTupleTmp;
175 BidTuple returnedBid = SearchNeighbourhood(bidTupleTmp,
176 depth - 1);
177 if (returnedBid.utility > bestBid.utility)
178 bestBid = returnedBid;
179 }
180
181 bidTupleTmp = getRealIssueVariation(initialBid,
182 issuesToChange[i], -rand.nextFloat() * variation);
183 if (bidTupleTmp != null) {
184 if (bidTupleTmp.utility > bestBid.utility)
185 bestBid = bidTupleTmp;
186 BidTuple returnedBid = SearchNeighbourhood(bidTupleTmp,
187 depth - 1);
188 if (returnedBid.utility > bestBid.utility)
189 bestBid = returnedBid;
190 }
191 break;
192 case INTEGER:
193 bidTupleTmp = getIntegerIssueVariation(initialBid,
194 issuesToChange[i], 1);
195 if (bidTupleTmp != null) {
196 if (bidTupleTmp.utility > bestBid.utility)
197 bestBid = bidTupleTmp;
198 BidTuple returnedBid = SearchNeighbourhood(bidTupleTmp,
199 depth - 1);
200 if (returnedBid.utility > bestBid.utility)
201 bestBid = returnedBid;
202 }
203
204 bidTupleTmp = getIntegerIssueVariation(initialBid,
205 issuesToChange[i], -1);
206 if (bidTupleTmp != null) {
207 if (bidTupleTmp.utility > bestBid.utility)
208 bestBid = bidTupleTmp;
209 BidTuple returnedBid = SearchNeighbourhood(bidTupleTmp,
210 depth - 1);
211 if (returnedBid.utility > bestBid.utility)
212 bestBid = returnedBid;
213 }
214 break;
215 default:
216 throw new Exception(
217 "issue type not supported by " + getName());
218 }
219 }
220 } catch (Exception e) {
221 debug(e.getMessage());
222 e.printStackTrace();
223 }
224 return bestBid;
225 }
226
227 private void saveBestOpponentBids(BidTuple bid) {
228 int insertPosition = 0;
229 for (int i = 0; i < bestOpponentOffers.size(); i++) {
230 if (bestOpponentOffers.get(i).utility > bid.utility)
231 insertPosition++;
232 }
233 bestOpponentOffers.add(insertPosition, bid);
234 if (bestOpponentOffers.size() > 10)
235 bestOpponentOffers.remove(10);
236 }
237
238 private BidTuple getDiscreteIssueVariation(BidTuple bid, int issueId,
239 int variation) throws Exception {
240 Bid tmpBid = new Bid(bid.bid);
241 BidTuple bidTupleTmp = null;
242 IssueDiscrete issueDiscrete = (IssueDiscrete) tmpBid.getIssues()
243 .get(issueId);
244 int temIssueIndex = issueDiscrete.getIndex(issueDiscrete);
245 if (issueDiscrete.getNumberOfValues() >= temIssueIndex + variation
246 && temIssueIndex + variation >= 0) {
247 ValueDiscrete value = issueDiscrete
248 .getValue(temIssueIndex + variation);
249 tmpBid = tmpBid.putValue(issueId, value);
250 double util = getUtility(tmpBid);
251 bidTupleTmp = new BidTuple(tmpBid, util);
252 }
253 return bidTupleTmp;
254 }
255
256 private BidTuple getRealIssueVariation(BidTuple bid, int issueId,
257 double variation) throws Exception {
258 Bid tmpBid = new Bid(bid.bid);
259 BidTuple bidTupleTmp = null;
260 IssueReal issueReal = (IssueReal) tmpBid.getIssues().get(issueId);
261 int temIssueValue = ((ValueInteger) tmpBid.getValue(issueId))
262 .getValue();
263 if (issueReal.getUpperBound() >= temIssueValue + variation
264 && issueReal.getLowerBound() <= temIssueValue + variation) {
265 ValueReal value = new ValueReal(temIssueValue + variation);
266 tmpBid = tmpBid.putValue(issueId, value);
267 double util = getUtility(tmpBid);
268 bidTupleTmp = new BidTuple(tmpBid, util);
269 }
270 return bidTupleTmp;
271 }
272
273 private BidTuple getIntegerIssueVariation(BidTuple bid, int issueId,
274 int variation) throws Exception {
275 Bid tmpBid = new Bid(bid.bid);
276 BidTuple bidTupleTmp = null;
277 IssueInteger issueInteger = (IssueInteger) tmpBid.getIssues()
278 .get(issueId);
279 int temIssueValue = ((ValueInteger) tmpBid.getValue(issueId))
280 .getValue();
281 if (issueInteger.getUpperBound() >= temIssueValue + variation
282 && issueInteger.getLowerBound() <= temIssueValue + variation) {
283 ValueInteger value = new ValueInteger(temIssueValue + variation);
284 tmpBid = tmpBid.putValue(issueId, value);
285 double util = getUtility(tmpBid);
286 bidTupleTmp = new BidTuple(tmpBid, util);
287 }
288 return bidTupleTmp;
289 }
290
291 @Override
292 public Action chooseAction() {
293 boolean NeverFoundHighUtilityInNeighbourhood = true;
294 debug("1. choosing action");
295 // get current time
296 double time = timeline.getTime();
297 // calculate maximum round time
298 if (actionOfPartner != null) {
299 if (maximumRoundTime < time - lastRoundTime)
300 maximumRoundTime = time - lastRoundTime;
301 debug("maximumRoundTime: " + maximumRoundTime);
302 lastRoundTime = time;
303 }
304 Action action = null;
305 try {
306 if (actionOfPartner == null) {
307 lastRoundTime = time;
308 debug("OFFER: FIRST RANDOM OFFER", 3);
309 return action = chooseRandomBidAction();
310 }
311 if (actionOfPartner instanceof Offer) {
312 Bid partnerBid = ((Offer) actionOfPartner).getBid();
313 double offeredUtilFromOpponent = getUtility(partnerBid);
314
315 if (time >= 0.99 && offeredUtilFromOpponent >= 0.75) {
316 debug("ime >= 0.99 && offeredUtilFromOpponent>= 0.75");
317 debug("OFFER: STRAIGHT ACCEPT, TIME IS RUNNING OUT, GOOD OFFER",
318 3);
319 return action = new Accept(getAgentID(), partnerBid);
320 }
321
322 BidTuple opponentBid = new BidTuple(partnerBid,
323 offeredUtilFromOpponent);
324 saveBestOpponentBids(opponentBid);
325
326 if (bestOpponentOffer == null
327 || bestOpponentOffer.utility < offeredUtilFromOpponent)
328 bestOpponentOffer = opponentBid;
329
330 // Last moments, submit back the opponents best bids
331 if ((time >= 1 - (maximumRoundTime * 1.09))) {
332 debug("final round:" + maximumRoundTime);
333 debug("(time>=1-(maximumRoundTime*1.05)) && bestOpponentOffer.utility >= 0.5");
334 if (bidToSubmitBack >= bestOpponentOffers.size())
335 bidToSubmitBack = 0;
336 debug("OFFER: BEST OF THE OPPONENTS NR " + bidToSubmitBack,
337 3);
338 return action = new Offer(getAgentID(),
339 bestOpponentOffers.get(bidToSubmitBack++).bid);
340 }
341
342 updateOpponentProfile(partnerBid, offeredUtilFromOpponent);
343 updateMinimumBidUtility(partnerBid, offeredUtilFromOpponent);
344
345 debug("3. searching the vicinity of the opp bid");
346 debug("MINIMUM UTILITY: " + minimumBidUtility, 3);
347 BidTuple bestBidInTheVicinity = SearchNeighbourhood(
348 opponentBid);
349 debug("bestBidInTheVicinity.utility"
350 + bestBidInTheVicinity.utility);
351 if (bestBidInTheVicinity.utility < minimumBidUtility) {
352 debug("4. bad search, going to pick a random");
353 action = chooseRandomBidAction();
354
355 // if the random returned a null, which means we couldnt
356 // find a bid before time ran out,
357 // we offer back the best opponent bid
358 if (((Offer) action).getBid() == null
359 && bestOpponentOffer.utility >= 0.5) {
360 debug("action == null && bestOpponentOffer.utility >= 0.5");
361 return action = new Offer(getAgentID(),
362 bestOpponentOffer.bid);
363 }
364
365 debug("bid Random");
366 debug("OFFER: RANDOM BID", 3);
367
368 } else {
369 debug("5. found a good bid in the vicinity");
370 NeverFoundHighUtilityInNeighbourhood = false;
371 action = new Offer(getAgentID(), bestBidInTheVicinity.bid);
372 debug("Bid in bestBidInTheVicinity");
373 debug("OFFER: OPPONENT VICINITY", 3);
374 }
375
376 if (NeverFoundHighUtilityInNeighbourhood) {
377 if (time > 0.8) {
378 debug("6. time > 0.8, maximumsearchdepth = "
379 + (int) (initialSearchDepth * 1.5));
380 maximumSearchDepth = (int) (initialSearchDepth * 1.5);
381 } else if (time > 0.5) {
382 debug("7. time > 0.5, maximumsearchdepth = "
383 + (int) (initialSearchDepth * 1.2));
384 maximumSearchDepth = (int) (initialSearchDepth * 1.2);
385 }
386 }
387
388 Bid myBid = ((Offer) action).getBid();
389 double myOfferedUtil = getUtility(myBid);
390
391 // accept under certain circumstances
392 if (isAcceptable(offeredUtilFromOpponent, myOfferedUtil,
393 time)) {
394 debug("8. opponents bid is acceptable");
395 debug("Accept");
396 debug("OFFER: STRAIGHT ACCEPT", 3);
397 action = new Accept(getAgentID(), partnerBid);
398 }
399
400 }
401
402 } catch (Exception e) {
403 debug("Exception in ChooseAction:" + e.getMessage());
404 return action = new Offer(getAgentID(), bestOpponentOffer.bid); // best
405 // guess
406 // if
407 // things
408 // go
409 // wrong.
410 }
411 debug("9. end of choose action");
412 return action;
413 }
414
415 private void updateOpponentProfile(Bid partnerBid,
416 double offeredUtilFromOpponent) {
417 countOpponentOffers++;
418 if (offeredUtilFromOpponent > minimumCooperativeUtility) {
419 numberOfCooperativeUtilities++;
420 }
421 if ((numberOfCooperativeUtilities
422 / countOpponentOffers) > cooperationthreshold) {
423 opponentIsCooperative = true;
424 debug("-- OPPONENT IS COOPERATIVE", 1);
425 } else {
426 opponentIsCooperative = false;
427 debug("-- OPPONENT IS HARD HEADED", 1);
428 }
429 }
430
431 private boolean isAcceptable(double offeredUtilFromOpponent,
432 double myOfferedUtil, double time) throws Exception {
433 double discount_utility_factor = utilitySpace.getDiscountFactor();
434 acceptanceBidUtility = initialMinimumBidUtility
435 * Math.pow(discount_utility_factor, time);
436
437 if (time >= 0.9) {
438 initialMinimumBidUtility = 0.85;
439 }
440
441 if (offeredUtilFromOpponent >= acceptanceBidUtility) {
442 debug("offeredUtilFromOpponent >= " + acceptanceBidUtility);
443 return true;
444 }
445
446 if (offeredUtilFromOpponent >= myOfferedUtil) {
447 debug("offeredUtilFromOpponent >= myOfferedUtil");
448 return true;
449 }
450
451 return false;
452 }
453
454 private Action chooseRandomBidAction() {
455 Bid nextBid = null;
456 try {
457 nextBid = getRandomBid();
458 } catch (Exception e) {
459 debug("Problem with received bid:" + e.getMessage()
460 + ". cancelling bidding");
461 }
462 return (new Offer(getAgentID(), nextBid));
463 }
464
465 private Bid getRandomBid() throws Exception {
466 HashMap<Integer, Value> values = new HashMap<Integer, Value>(); // pairs
467 // <issuenumber,chosen
468 // value
469 // string>
470 List<Issue> issues = utilitySpace.getDomain().getIssues();
471 Random randomnr = new Random();
472
473 debug("R 1.beginning Random pick");
474
475 Bid bid = null;
476
477 int tries = 0;
478 int absoluteTries = 0;
479 float minimumUtilTolerance = 0;
480 do {
481 tries++;
482 absoluteTries++;
483 if (tries > 2000)// && minimumUtilTolerance<0.09)
484 {
485 debug("R 1.increasing tolerance");
486 minimumUtilTolerance += 0.001;
487 tries = 0;
488 }
489
490 for (Issue lIssue : issues) {
491 switch (lIssue.getType()) {
492 case DISCRETE:
493 IssueDiscrete lIssueDiscrete = (IssueDiscrete) lIssue;
494 int optionIndex = randomnr
495 .nextInt(lIssueDiscrete.getNumberOfValues());
496 values.put(lIssue.getNumber(),
497 lIssueDiscrete.getValue(optionIndex));
498 break;
499 case REAL:
500 IssueReal lIssueReal = (IssueReal) lIssue;
501 int optionInd = randomnr.nextInt(
502 lIssueReal.getNumberOfDiscretizationSteps() - 1);
503 values.put(lIssueReal.getNumber(), new ValueReal(lIssueReal
504 .getLowerBound()
505 + (lIssueReal.getUpperBound()
506 - lIssueReal.getLowerBound()) * (optionInd)
507 / (lIssueReal
508 .getNumberOfDiscretizationSteps())));
509 break;
510 case INTEGER:
511 IssueInteger lIssueInteger = (IssueInteger) lIssue;
512 int optionIndex2 = lIssueInteger.getLowerBound()
513 + randomnr.nextInt(lIssueInteger.getUpperBound()
514 - lIssueInteger.getLowerBound());
515 values.put(lIssueInteger.getNumber(),
516 new ValueInteger(optionIndex2));
517 break;
518 default:
519 throw new Exception("issue type " + lIssue.getType()
520 + " not supported by SimpleAgent2");
521 }
522 }
523 bid = new Bid(utilitySpace.getDomain(), values);
524
525 } while (getUtility(bid) < minimumBidUtility - minimumUtilTolerance);
526 debug("R 2.Generated a random bid. current utility: " + getUtility(bid)
527 + ", tolerance: " + minimumUtilTolerance + "; tries: "
528 + absoluteTries);
529
530 Bid randomBid = bid;
531
532 // // search the vicinity of the random offer
533 if (randomnr.nextFloat() < randomSearchRatio) {
534 debug("R 3.Going to search the vicinity of the random pick");
535 bid = SearchNeighbourhood(new BidTuple(bid, getUtility(bid)),
536 maximumSearchDepthForOurBids).bid;
537 }
538
539 if (bid != randomBid) {
540 debug("OFFER: RANDOM VICINITY BID", 3);
541 } else {
542 debug("OFFER: RANDOM BID", 3);
543 }
544
545 debug("R 4.Random pick finished");
546 return bid;
547 }
548
549 private void updateMinimumBidUtility(Bid partnerBid,
550 double offeredUtilFromOpponent) {
551
552 double time = timeline.getTime();
553 double discount_utility_factor = utilitySpace.getDiscountFactor();
554 if (time >= 0.5 && opponentIsCooperative) {
555 minimumBidUtility = 0.88 * Math.pow(discount_utility_factor, time);
556 debug("2. ADJUSTING MINIMUM UTILITY: " + minimumBidUtility);
557 }
558 debug("2. MINIMUM UTILITY: " + minimumBidUtility);
559 debug("2. discount factor: " + discount_utility_factor);
560 }
561
562 private void debug(String line) {
563 debug(line, 0);
564 }
565
566 private void debug(String line, int priority) {
567 if (priority >= 4)
568 System.out.println(line);
569 }
570
571 private class BidTuple {
572 public Bid bid;
573 public double utility;
574
575 public BidTuple(Bid bid, double utility) {
576 this.bid = bid;
577 this.utility = utility;
578 }
579 }
580
581 @Override
582 public String getDescription() {
583 return "ANAC2014 compatible with non-linear utility spaces";
584 }
585
586}
Note: See TracBrowser for help on using the repository browser.