source: src/main/java/agents/anac/y2015/RandomDance/RandomDance.java@ 346

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

Initial import : Genius 9.0.0
File size: 16.4 KB
Line 
1package agents.anac.y2015.RandomDance;
2
3import java.util.ArrayList;
4import java.util.HashMap;
5import java.util.HashSet;
6import java.util.LinkedList;
7import java.util.List;
8import java.util.Map;
9import java.util.Set;
10
11import genius.core.AgentID;
12import genius.core.Bid;
13import genius.core.actions.Accept;
14import genius.core.actions.Action;
15import genius.core.actions.EndNegotiation;
16import genius.core.actions.Offer;
17import genius.core.issue.Issue;
18import genius.core.issue.IssueDiscrete;
19import genius.core.issue.IssueInteger;
20import genius.core.issue.Value;
21import genius.core.issue.ValueDiscrete;
22import genius.core.issue.ValueInteger;
23import genius.core.parties.AbstractNegotiationParty;
24import genius.core.parties.NegotiationInfo;
25import genius.core.utility.AdditiveUtilitySpace;
26
27/**
28 * This is your negotiation party.
29 */
30public class RandomDance extends AbstractNegotiationParty {
31
32 /*
33 * パレート最適最速アタックを目指す(ひとまず)
34 */
35
36 @Override
37 public void init(NegotiationInfo info) {
38 super.init(info);
39 }
40
41 final int NashCountMax = 200;
42 final int NumberOfAcceptSafety = 5;
43 final int NumberOfRandomTargetCheck = 3;
44
45 private boolean init = false;
46 /**
47 * Map with {@link AgentID} as key
48 */
49 private Map<String, PlayerDataLib> utilityDatas = new HashMap<String, PlayerDataLib>();
50 private PlayerData myData = null;
51
52 private List<String> nash = new LinkedList<String>();
53 private Map<String, Bid> olderBidMap = new HashMap<String, Bid>();
54
55 private double discountFactor = 1.0;
56 private double reservationValue = 0;
57
58 private double olderTime = 0;
59
60 @Override
61 public Action chooseAction(List<Class<? extends Action>> validActions) {
62
63 if (!init) {
64 init = true;
65 myInit();
66 }
67
68 Map<String, PlayerData> utilityMap = new HashMap<String, PlayerData>();
69 for (String str : utilityDatas.keySet()) {
70 utilityMap.put(str, utilityDatas.get(str).getRandomPlayerData());
71 }
72 utilityMap.put("my", myData);
73
74 /*
75 * 前回の相手のBidのうち、より他の相手に歩み寄って
76 * いるプレイヤーを探す : Find player that walked maximum
77 * value?
78 */
79 double maxval = -999;
80 String maxPlayer = null;
81 for (String string : olderBidMap.keySet()) {
82 double utility = 1.0;
83 for (String player : utilityMap.keySet()) {
84 if (string.equals(player)) {
85 continue;
86 }
87 utility *= utilityMap.get(player)
88 .GetUtility(olderBidMap.get(string));
89 }
90 if (utility > maxval) {
91 maxval = utility;
92 maxPlayer = string;
93 }
94 }
95 if (maxPlayer != null) {
96 nash.add(maxPlayer);
97 }
98 while (nash.size() > NashCountMax) {
99 nash.remove(0);
100 }
101
102 Map<String, Double> playerWeight = getWeights();
103
104 Action action = null;
105 Offer offer = null;
106
107 double target = GetTarget(utilityMap);
108 double utility = 0;
109
110 if (olderBid != null) {
111
112 try {
113 utility = utilitySpace.getUtility(olderBid);
114 } catch (Exception e) {
115 // TODO 自動生成された catch ブロック
116 e.printStackTrace();
117 }
118 }
119
120 try {
121 offer = new Offer(getPartyId(),
122 SearchBid(target, utilityMap, playerWeight));
123 action = offer;
124 } catch (Exception e) {
125 // TODO 自動生成された catch ブロック
126 e.printStackTrace();
127 }
128
129 if (action == null || IsAccept(target, utility)) {
130 action = new Accept(getPartyId(), olderBid);
131 }
132 if (IsEndNegotiation(target)) {
133 action = new EndNegotiation(getPartyId());
134 }
135
136 return action;
137 }
138
139 public Map<String, Double> getWeights() {
140 /*
141 * プレイヤーウェイトの計算 : Calculation of player weight
142 */
143 Map<String, Double> playerWeight = new HashMap<String, Double>();
144 int rand = (int) (Math.random() * 3);
145
146 switch (rand) {
147 case 0:
148 for (String string : utilityDatas.keySet()) {
149 playerWeight.put(string, 0.0001);
150 }
151 for (String string : nash) {
152 playerWeight.put(string, playerWeight.get(string) + 1.0);
153 }
154 break;
155
156 case 1:
157 for (String string : utilityDatas.keySet()) {
158 playerWeight.put(string, 1.0);
159 }
160 break;
161 case 2:
162 boolean flag = Math.random() < 0.5;
163 for (String string : utilityDatas.keySet()) {
164
165 if (string.equals("my")) {
166 continue;
167 }
168
169 if (flag) {
170 playerWeight.put(string, 1.0);
171 } else {
172 playerWeight.put(string, 0.01);
173 }
174 flag = !flag;
175 }
176 break;
177 default:
178 for (String string : utilityDatas.keySet()) {
179 playerWeight.put(string, 1.0);
180 }
181 break;
182 }
183
184 // System.err.println("PlayerWeight : " + playerWeight.toString());
185
186 return playerWeight;
187 }
188
189 Bid olderBid = null; // the last received bid
190
191 @Override
192 public void receiveMessage(AgentID sender, Action action) {
193 super.receiveMessage(sender, action);
194
195 if (sender == null) {
196 return;
197 }
198 if (utilityDatas.containsKey(sender.toString()) == false) {
199 utilityDatas.put(sender.toString(),
200 new PlayerDataLib(utilitySpace.getDomain().getIssues()));
201 }
202
203 if (action.getClass() == Offer.class) {
204 Offer offer = (Offer) action;
205 Bid bid = offer.getBid();
206 olderBid = bid;
207 }
208
209 olderBidMap.put(sender.toString(), olderBid);
210
211 try {
212 utilityDatas.get(sender.toString()).AddBid(olderBid);
213 } catch (Exception e) {
214 e.printStackTrace();
215 }
216
217 }
218
219 private boolean IsAccept(double target, double utility) {
220 double time = timeline.getTime();
221 double d = time - olderTime;
222 olderTime = time;
223 // 時間ギリギリならAccept
224 if (time + d * NumberOfAcceptSafety > 1.0) {
225 // System.err.println("Accept Time");
226 return true;
227 }
228
229 if (olderBid == null) {
230 return false;
231 }
232 // targetより大きければAccept : If greater than the target Accept
233 if (utility > target) {
234 // System.err.println("Accept utility over target! " + target + " "
235 // + utility);
236 return true;
237 }
238 return false;
239 }
240
241 private boolean IsEndNegotiation(double target) {
242
243 if (target < reservationValue) {
244 return true;
245 }
246
247 return false;
248 }
249
250 private double GetTarget(Map<String, PlayerData> datas) {
251
252 double max = 0;
253
254 Map<String, Double> weights = new HashMap<String, Double>();
255
256 /*
257 * for(String str:datas.keySet()){ weights.put(str, 1.0); } Bid bid =
258 * SearchBidWithWeights(datas, weights); try { max = Math.max(max,
259 * utilitySpace.getUtility(bid)); } catch (Exception e) { // TODO
260 * 自動生成された catch ブロック e.printStackTrace(); }
261 */
262
263 for (int i = 0; i < NumberOfRandomTargetCheck; i++) {
264
265 Map<String, PlayerData> utilityMap = new HashMap<String, PlayerData>();
266 for (String str : utilityDatas.keySet()) {
267 utilityMap.put(str,
268 utilityDatas.get(str).getRandomPlayerData());
269 weights.put(str, 1.0);
270 }
271 utilityMap.put("my", myData);
272 weights.put("my", 1.0);
273
274 Bid bid = SearchBidWithWeights(utilityMap, weights);
275 try {
276 max = Math.max(max, utilitySpace.getUtility(bid));
277 } catch (Exception e) {
278 // TODO 自動生成された catch ブロック
279 e.printStackTrace();
280 }
281
282 }
283
284 double target = 1.0
285 - (1.0 - max) * (Math.pow(timeline.getTime(), discountFactor));
286
287 if (discountFactor > 0.99) {
288 target = 1.0 - (1.0 - max) * (Math.pow(timeline.getTime(), 3));
289 }
290
291 // System.err.println("time = " + timeline.getTime()+ "target = " +
292 // target +" max = " + max);
293 return target;
294 }
295
296 private void myInit() {
297 PlayerData playerData = new PlayerData(
298 utilitySpace.getDomain().getIssues(), 1.0);
299
300 try {
301 playerData.SetMyUtility((AdditiveUtilitySpace) utilitySpace);
302 } catch (Exception e) {
303 // TODO 自動生成された catch ブロック
304 e.printStackTrace();
305 }
306 myData = playerData;
307
308 reservationValue = utilitySpace.getReservationValue();
309 discountFactor = utilitySpace.getDiscountFactor();
310
311 }
312
313 /**
314 *
315 * @param datas
316 * @param weights
317 * Map with {@link AgentID} as key, and weight as value.
318 * @return bid that has maximum utility, using the given weights.
319 */
320 private Bid SearchBidWithWeights(Map<String, PlayerData> datas,
321 Map<String, Double> weights) {
322 Bid ret = generateRandomBid();
323 // there must be some player, we use it to get the issue values.
324 PlayerData player0data = datas.get(datas.keySet().iterator().next());
325 for (Issue issue : utilitySpace.getDomain().getIssues()) {
326
327 List<Value> values = player0data.getIssueData(issue).getValues();
328
329 double max = -1;
330 Value maxValue = null;
331
332 for (Value value : values) {
333
334 double v = 0;
335
336 for (String string : datas.keySet()) {
337 PlayerData data = datas.get(string);
338 double weight = weights.get(string);
339 v += data.GetValue(issue, value) * weight;
340 }
341 if (v > max) {
342 max = v;
343 maxValue = value;
344 }
345 }
346 ret = ret.putValue(issue.getNumber(), maxValue);
347 }
348 return ret;
349 }
350
351 /*
352 * target以上で良い感じに
353 */
354 private Bid SearchBid(double target, Map<String, PlayerData> datas,
355 Map<String, Double> weights) throws Exception {
356
357 /*
358 * 引数に渡すようのMapを作る
359 */
360 Map<String, PlayerData> map = new HashMap<String, PlayerData>();
361 map.putAll(datas);
362 map.put("my", myData);
363
364 Map<String, Double> weightbuf = new HashMap<String, Double>();
365 /*
366 * 敵ウェイトを合計1になるようにする: set weights to sum
367 * to 1
368 */
369 double sum = 0;
370 for (Double d : weights.values()) {
371 sum += d;
372 }
373 for (String key : weights.keySet()) {
374 weightbuf.put(key, weights.get(key) / sum);
375 }
376
377 for (double w = 0; w < 9.999; w += 0.01) {
378
379 double myweight = w / (1.0 - w);
380 weightbuf.put("my", myweight);
381
382 Bid bid = SearchBidWithWeights(map, weightbuf);
383
384 if (utilitySpace.getUtility(bid) > target) {
385 return bid;
386 }
387 }
388
389 return utilitySpace.getMaxUtilityBid();
390 }
391
392 @Override
393 public String getDescription() {
394 return "ANAC2015";
395 }
396
397}
398
399/**
400 * 3 player datas for each player, one with constant derta, one with decreasing
401 * and one with increasing.
402 */
403class PlayerDataLib {
404
405 ArrayList<PlayerData> playerDatas = new ArrayList<PlayerData>();
406
407 public PlayerDataLib(List<Issue> issues) {
408 playerDatas.add(new PlayerData(issues, 1.0));
409 playerDatas.add(new PlayerData(issues, 1.05));
410 playerDatas.add(new PlayerData(issues, 0.95));
411 }
412
413 public PlayerData getRandomPlayerData() {
414 int rand = (int) (Math.random() * playerDatas.size());
415 return playerDatas.get(rand);
416 }
417
418 public void AddBid(Bid bid) {
419 for (PlayerData d : playerDatas) {
420 try {
421 d.AddBid(bid);
422 } catch (Exception e) {
423 // TODO 自動生成された catch ブロック
424 e.printStackTrace();
425 }
426 }
427 }
428
429 public ArrayList<PlayerData> getPlayerDataList() {
430 return playerDatas;
431 }
432
433}
434
435class PlayerData {
436 // IssueData is raw type.
437 Map<Issue, IssueData> map = new HashMap<Issue, IssueData>();
438 Set<Bid> history = new HashSet<Bid>();
439 double derta = 1.00;
440
441 public IssueData<Issue, Value> getIssueData(Issue issue) {
442 return map.get(issue);
443 }
444
445 /**
446 * Mape a map of IssueData for all issues.
447 *
448 * @param issues
449 * @param derta
450 * the relevance change for each next bid. So if eg 0.8, each
451 * next update has a relevance 0.8 times the previous update
452 */
453 public PlayerData(List<Issue> issues, double derta) {
454 for (Issue issue : issues) {
455 if (issue instanceof IssueDiscrete) {
456 map.put(issue,
457 new IssueDataDiscrete((IssueDiscrete) issue, derta));
458 } else {
459 map.put(issue,
460 new IssueDataInteger((IssueInteger) issue, derta));
461 }
462 }
463 this.derta = derta;
464 }
465
466 public double GetUtility(Bid bid) {
467 double ret = 0;
468 for (Issue issue : bid.getIssues()) {
469 try {
470 ret += GetValue(issue, bid.getValue(issue.getNumber()));
471 } catch (Exception e) {
472 // TODO 自動生成された catch ブロック
473 e.printStackTrace();
474 }
475 }
476 return ret;
477 }
478
479 public double GetValue(Issue issue, Value value) {
480 ValuePut(issue);
481 return map.get(issue).GetValueWithWeight(value);
482 }
483
484 public void SetMyUtility(AdditiveUtilitySpace utilitySpace)
485 throws Exception {
486
487 Bid bid = utilitySpace.getMinUtilityBid();
488 List<Issue> issues = utilitySpace.getDomain().getIssues();
489 double min = utilitySpace.getUtility(bid);
490
491 for (Issue issue : issues) {
492 IssueData issueData = map.get(issue);
493 bid = utilitySpace.getMinUtilityBid();
494 List<Value> values = issueData.getValues();
495
496 for (Value value : values) {
497 bid = bid.putValue(issue.getNumber(), value);
498 double v = utilitySpace.getUtility(bid) - min;
499 issueData.setValue(value, v);
500 }
501 issueData.setWeight(1.0 / (1.0 - min));
502 issueData.Locked();
503 }
504
505 // System.err.println(this.toString());
506
507 }
508
509 /**
510 * Accumulates occurences of issues
511 *
512 * @param bid
513 * @throws Exception
514 */
515 public void AddBid(Bid bid) throws Exception {
516
517 if (history.contains(bid)) {
518 return;
519 }
520 history.add(bid);
521
522 double countsum = 0;
523 for (Issue issue : bid.getIssues()) {
524 ValuePut(issue);
525 map.get(issue).Update(bid.getValue(issue.getNumber()));
526 countsum += map.get(issue).getMax();
527 }
528
529 for (Issue issue : bid.getIssues()) {
530 map.get(issue).setWeight(map.get(issue).getMax() / countsum);
531 }
532 }
533
534 /*
535 * Mapにキーがない時に追加する関数: put in map if not there
536 * yet
537 */
538 private void ValuePut(Issue issue) {
539 if (!map.containsKey(issue)) {
540 if (issue instanceof IssueDiscrete) {
541 map.put(issue,
542 new IssueDataDiscrete((IssueDiscrete) issue, derta));
543 } else {
544 map.put(issue,
545 new IssueDataInteger((IssueInteger) issue, derta));
546 }
547 }
548 }
549
550 @Override
551 public String toString() {
552
553 String ret = "";
554 for (Issue issue : map.keySet()) {
555 ret += issue.toString() + ":" + map.get(issue).toString() + "\n";
556 }
557 return ret;
558 }
559
560 /*
561 * 各Issueごとの数え上げデータ: count data for each issue
562 * Refactored W.Pasman to handle other issue types
563 */
564 abstract class IssueData<IssueType extends Issue, ValueType extends Value> {
565 private boolean locked = false;
566 private double weight = 1;
567 private double derta = 1.0;
568 private double max = 1;
569 private Map<Value, Double> map = new HashMap<Value, Double>();
570 private double adder = 1.0;
571 private IssueType issue;
572
573 /**
574 *
575 * @param issue
576 * the issue that this data contains
577 * @param derta
578 * the relevance change for each next bid. So if eg 0.8, each
579 * next update has a relevance 0.8 times the previous update.
580 */
581 public IssueData(IssueType issue, double derta) {
582 this.issue = issue;
583 this.derta = derta;
584
585 for (ValueType value : getValues()) {
586 setValue(value, 0);
587 }
588 }
589
590 public Issue getIssue() {
591 return issue;
592 }
593
594 /**
595 * Returns the possible values for this issue. Similar to
596 * {@link IssueDiscrete#getValues()}
597 */
598 public abstract List<ValueType> getValues();
599
600 /**
601 * /* 更新禁止のロックをかける ロックは外せない :
602 * lock the update
603 */
604 public void Locked() {
605 locked = true;
606 }
607
608 public double getWeight() {
609 return weight;
610 }
611
612 public void setWeight(double weight) {
613 this.weight = weight;
614 }
615
616 public boolean isLocked() {
617 return locked;
618 }
619
620 private double getMax() {
621 return max;
622 }
623
624 double GetValue(ValueType value) {
625 ValuePut(value);
626 return map.get(value) / max;
627 }
628
629 double GetValueWithWeight(ValueType value) {
630 return GetValue(value) * getWeight();
631 }
632
633 /*
634 * 相手のBidがきた時の更新関数 とりあえず1を足す put
635 * value in the map. Each next update will have relevance changed by
636 * factor derta.
637 */
638 public void Update(ValueType value) {
639 if (isLocked()) {
640 System.err.println("LockedAccess!!");
641 return;
642 }
643 ValuePut(value);
644 map.put(value, map.get(value) + adder);
645 max = Math.max(max, map.get(value));
646 adder *= derta;
647 }
648
649 @Override
650 public String toString() {
651 return "weight:" + getWeight() + ":" + map.toString();
652 }
653
654 protected void setValue(ValueType value, double util) {
655 if (isLocked()) {
656 System.err.println("LockedAccess!!");
657 } else {
658 map.put(value, util);
659 }
660 }
661
662 /*
663 * Mapにキーがない時に追加する関数 : put key in map if not
664 * yet there
665 */
666 protected void ValuePut(ValueType value) {
667 if (!map.containsKey(value)) {
668 map.put(value, 0.0);
669 }
670 }
671
672 }
673
674 class IssueDataDiscrete extends IssueData<IssueDiscrete, ValueDiscrete> {
675
676 public IssueDataDiscrete(IssueDiscrete issue, double derta) {
677 super(issue, derta);
678 }
679
680 @Override
681 public List<ValueDiscrete> getValues() {
682 return ((IssueDiscrete) getIssue()).getValues();
683 }
684 }
685
686 class IssueDataInteger extends IssueData<IssueInteger, ValueInteger> {
687
688 public IssueDataInteger(IssueInteger issue, double derta) {
689 super(issue, derta);
690 }
691
692 @Override
693 public List<ValueInteger> getValues() {
694 IssueInteger iss = (IssueInteger) getIssue();
695 List<ValueInteger> values = new ArrayList<ValueInteger>();
696
697 for (int v = iss.getLowerBound(); v <= iss.getUpperBound(); v++) {
698 values.add(new ValueInteger(v));
699 }
700 return values;
701 }
702
703 }
704
705}
Note: See TracBrowser for help on using the repository browser.