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

Last change on this file since 204 was 160, checked in by Tim Baarslag, 6 years ago

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