source: src/main/java/agents/anac/y2011/Gahboninho/OpponnentModel.java@ 126

Last change on this file since 126 was 126, checked in by Aron Hammond, 6 years ago

Added function to calculate opposition to MultiLateralAnalysis.java

Moved code to add RLBOA listeners to RLBOAUtils is misc package

Added input for strategyParameters to SessionPanel (gui)

!! close SessionInfo after tournament; this caused /tmp/ to fill up with GeniusData files

Our own package:

  • Added opponents and strategies that are mentioned in the report
  • Change class hierarchy, agents can now extend from RLBOAagentBilateral to inherit RL functionality.
  • States extend from AbstractState
File size: 18.5 KB
Line 
1package agents.anac.y2011.Gahboninho;
2
3import java.util.Comparator;
4import java.util.List;
5import java.util.Map.Entry;
6
7import genius.core.Bid;
8import genius.core.issue.ISSUETYPE;
9import genius.core.issue.Issue;
10import genius.core.issue.IssueDiscrete;
11import genius.core.issue.IssueInteger;
12import genius.core.issue.IssueReal;
13import genius.core.issue.Value;
14import genius.core.issue.ValueDiscrete;
15import genius.core.issue.ValueInteger;
16import genius.core.issue.ValueReal;
17import genius.core.timeline.TimeLineInfo;
18import genius.core.utility.AdditiveUtilitySpace;
19
20import java.util.Random;
21import java.util.TreeMap;
22
23public class OpponnentModel {
24 AdditiveUtilitySpace US;
25 private final boolean TEST_EQUIVALENCE = false;
26 private Random random500;
27 private Random random600;
28
29 /**
30 * provides prediction of how important each dispute element is, considering
31 * opponent's Behavior and "obsessions"
32 */
33
34 // alternative ideas for calculating utility:
35 // using k-nearest neigough, since opponent may use the same bid many times
36 public class IssuePrediction // represents one Issue of the bid (e.g.
37 // Screen-Size/Brand)
38 {
39 // the following tells how preferable each option is
40
41 class NumericValues implements GahbonValueType {
42 private final int DiscretizationResolution = 21;
43
44 private double TranslateValue(Value V) {
45 if (V instanceof ValueInteger)
46 return ((ValueInteger) V).getValue();
47
48 return ((ValueReal) V).getValue();
49 }
50
51 int[] ValueFrequencies;
52
53 private int GetFrequencyIndex(double V) {
54 return (int) ((V - MinValue) / (MaxValue / (DiscretizationResolution - 1)));
55 }
56
57 double MinValue;
58 double MaxValue;
59
60 boolean isFirstValue = true;
61 double FirstValue; // we assume that if FirstValue == MaxValue, then
62 // MaxValue has max utility
63
64 double BidFrequencyIndexSum = 0;
65 double NormalizedVariance; // 0 to 1
66 int OpponentBidCountToConsider = 0;
67
68 // this method learns from opponent's choices
69 public void UpdateImportance(
70 Value OpponentBid /*
71 * value of this Issue as received from
72 * opponent
73 */) {
74 ++OpponentBidCountToConsider;
75 double BidValue = TranslateValue(OpponentBid);
76 if (isFirstValue) {
77 isFirstValue = false;
78
79 // choose if the highest utility for the opponent is
80 // max-value or min-value
81 if ((MaxValue - BidValue) >= (BidValue - MinValue))
82 FirstValue = MaxValue;
83 else
84 FirstValue = MinValue;
85 }
86
87 ++ValueFrequencies[GetFrequencyIndex(BidValue)];
88 BidFrequencyIndexSum += GetFrequencyIndex(BidValue);
89
90 double AverageFrequencyIndex = BidFrequencyIndexSum / OpponentBidCountToConsider;
91
92 NormalizedVariance = 0;
93 for (int i = 0; i < DiscretizationResolution; ++i) {
94 double Distance = (AverageFrequencyIndex - i) / (DiscretizationResolution - 1);
95 NormalizedVariance += (double) (this.ValueFrequencies[i]) * Distance * Distance;
96 }
97
98 // NormalizedVariance /= BidFrequencyIndexSum;
99 }
100
101 public double GetNormalizedVariance() {
102 return NormalizedVariance;
103 }
104
105 public int GetUtilitiesCount() {
106 return this.DiscretizationResolution;
107 }
108
109 public double GetExpectedUtilityByValue(Value V) {
110 return Math.min(1, Math.max(0, 1 - Math.abs(TranslateValue(V) - FirstValue)));
111 }
112
113 public void INIT(genius.core.issue.Issue I) {
114 ValueFrequencies = new int[this.DiscretizationResolution];
115 if (I.getType() == ISSUETYPE.INTEGER) {
116 IssueInteger II = (IssueInteger) I;
117 MaxValue = II.getUpperBound();
118 MinValue = II.getLowerBound();
119 } else {
120 IssueReal RI = (IssueReal) I;
121 MaxValue = RI.getUpperBound();
122 MinValue = RI.getLowerBound();
123 }
124
125 }
126
127 }
128
129 class DiscreteValues implements GahbonValueType {
130 TreeMap<ValueDiscrete, Integer> OptionIndexByValue = null;
131 TreeMap<Integer, ValueDiscrete> ValueByOptionIndex = null;
132
133 int MostImportantValueOccurrencesAndBonuses = 1;
134
135 // TODO: make this funtion better!
136 // OptionOccurrencesCountWithoutSundayPreference's bonus
137 // should not be constant
138 int TotalImportanceSum = 0; // sum of all importances
139
140 private double GetOptionImportance(int OptionIndex) {
141 int FirstOptionBonus = UpdatesCount / (OptionOccurrencesCountByIndex.length); // the
142 // first
143 // choice
144 // always
145 // gets
146 // a
147 // large
148 // bonus,
149 // so
150 // this
151 // may
152 // minimize
153 // "noises
154
155 if (FirstIterationOptionIndex == OptionIndex) {
156 return OptionOccurrencesCountByIndex[OptionIndex] + FirstOptionBonus;
157 }
158
159 return OptionOccurrencesCountByIndex[OptionIndex];
160
161 }
162
163 int UpdatesCount = 0;
164 int FirstIterationOptionIndex = -1; // First Iteration has much more
165 // weight than other iterations,
166 // since it is reasonable to
167 // assume it indicates
168 // opponent's optimal option
169 int[] OptionOccurrencesCountByIndex = null; // Tells how many times
170 // each option was
171 // chosen by opponent
172 TreeMap<Integer, Integer> OptionIndexByImportance = new TreeMap<Integer, Integer>();
173 double IssueImportanceRankVariance = 0; // normalized ( 0 to 1,
174 // where 1 is maximum
175 // variance)
176
177 // this method learns from opponent's choices
178 public void UpdateImportance(
179 Value OpponentBid /*
180 * value of this Issue as received from
181 * opponent
182 */) {
183 ++UpdatesCount;
184
185 Integer incommingOptionIndex = OptionIndexByValue.get(OpponentBid);
186 if (-1 == FirstIterationOptionIndex)
187 FirstIterationOptionIndex = incommingOptionIndex;
188 ++OptionOccurrencesCountByIndex[incommingOptionIndex];
189
190 // let OptionIndexByOccurrencesCount sort the options by their
191 // importance rank:
192 OptionIndexByImportance.clear();
193
194 MostImportantValueOccurrencesAndBonuses = 0;
195 TotalImportanceSum = 0;
196 for (int OptionIndex = 0; OptionIndex < OptionOccurrencesCountByIndex.length; ++OptionIndex) {
197 int OptionImportance = (int) GetOptionImportance(OptionIndex);
198 MostImportantValueOccurrencesAndBonuses = Math.max(MostImportantValueOccurrencesAndBonuses,
199 OptionImportance);
200
201 OptionIndexByImportance.put(OptionImportance, OptionIndex);
202 TotalImportanceSum += OptionImportance;
203
204 }
205
206 // now calculate how easily the opponent gives up his better
207 // options in this issue:
208 double AverageImportanceRank = 0;
209 int currentOptionRank = 0; // highest rank is 0
210 for (Integer currentOptionIndex : OptionIndexByImportance.values()) {
211 AverageImportanceRank += currentOptionRank * GetOptionImportance(currentOptionIndex);
212 ++currentOptionRank;
213 }
214 AverageImportanceRank /= TotalImportanceSum;
215
216 IssueImportanceRankVariance = 0;
217 currentOptionRank = 0; // highest rank is 0
218 for (Integer currentOptionIndex : OptionIndexByImportance.values()) {
219 double CurrentOptionDistance = (AverageImportanceRank - currentOptionRank)
220 / OptionOccurrencesCountByIndex.length; // divide by
221 // option
222 // count to
223 // normalized
224 // distances
225
226 IssueImportanceRankVariance += OptionOccurrencesCountByIndex[currentOptionIndex] * // Occurrence
227 // count
228 // of
229 // current
230 // option
231 (CurrentOptionDistance * CurrentOptionDistance); // variance
232 // of
233 // current
234 // option
235
236 ++currentOptionRank;
237 }
238
239 IssueImportanceRankVariance /= TotalImportanceSum;
240 }
241
242 public double GetNormalizedVariance() {
243 return IssueImportanceRankVariance;
244 }
245
246 public int GetUtilitiesCount() {
247 return ValueByOptionIndex.size();
248 }
249
250 public double GetExpectedUtilityByValue(Value V) {
251 int ValueIndex = (Integer) (OptionIndexByValue.get(V));
252 return GetOptionImportance(ValueIndex) / MostImportantValueOccurrencesAndBonuses;
253 }
254
255 public void INIT(genius.core.issue.Issue I) {
256 IssueDiscrete DI = (IssueDiscrete) I;
257 OptionOccurrencesCountByIndex = new int[DI.getNumberOfValues()];
258
259 Comparator<ValueDiscrete> DIComparer = new Comparator<ValueDiscrete>() {
260 public int compare(ValueDiscrete o1, ValueDiscrete o2) {
261 return o1.getValue().compareTo(o2.getValue());
262 }
263 };
264 OptionIndexByValue = new TreeMap<ValueDiscrete, Integer>(DIComparer);
265 ValueByOptionIndex = new TreeMap<Integer, ValueDiscrete>();
266
267 for (int ValueIndex = 0; ValueIndex < DI.getNumberOfValues(); ++ValueIndex) {
268 OptionOccurrencesCountByIndex[ValueIndex] = 0;
269
270 ValueDiscrete V = DI.getValues().get(ValueIndex);
271 OptionIndexByValue.put(V, ValueIndex);
272 }
273
274 }
275
276 }
277
278 public double ExpectedWeight; // depends on comparison of this issue's
279 // variance and other issues'
280 public GahbonValueType Issue;
281 public genius.core.issue.Issue IssueBase;
282
283 public void INIT(Issue I) {
284 // check what type of issue we are talking about
285 if (I instanceof IssueDiscrete) {
286 IssueDiscrete DI = (IssueDiscrete) I;
287 String[] values = new String[DI.getValues().size()];
288 int ValueIndex = 0;
289 for (ValueDiscrete v : DI.getValues())
290 values[ValueIndex++] = new String(v.getValue());
291 IssueBase = new IssueDiscrete(DI.getName(), DI.getNumber(), values);
292 Issue = new DiscreteValues();
293 Issue.INIT(I);
294 } else if (I instanceof IssueReal) {
295 IssueReal RI = (IssueReal) I;
296 IssueBase = new IssueReal(RI.getName(), RI.getNumber(), RI.getLowerBound(), RI.getUpperBound());
297 Issue = new NumericValues();
298 Issue.INIT(I);
299 } else if (I instanceof IssueInteger) {
300 IssueInteger II = (IssueInteger) I;
301 IssueBase = new IssueReal(II.getName(), II.getNumber(), II.getLowerBound(), II.getUpperBound());
302 Issue = new NumericValues();
303 Issue.INIT(I);
304 }
305
306 }
307
308 }
309
310 public IssuePrediction[] IssuesByIndex = null; // holds all Issues, by index
311 // corresponding to Domain's
312 public TreeMap<Integer, Integer> IPIndexByIssueNumber = new TreeMap<Integer, Integer>();
313 public double TotalIssueOptionsVariance;
314 private TimeLineInfo timeline;
315
316 public OpponnentModel(AdditiveUtilitySpace utilitySpace, TimeLineInfo timeline) {
317 // utilitySpace is derived (and initialized) from Agent
318 if (TEST_EQUIVALENCE) {
319 random500 = new Random(500);
320 random600 = new Random(600);
321 } else {
322 random500 = new Random();
323 random600 = new Random();
324 }
325
326 this.US = utilitySpace;
327 this.timeline = timeline;
328 IssuesByIndex = new IssuePrediction[US.getDomain().getIssues().size()];
329 List<Issue> IA = US.getDomain().getIssues();
330
331 for (int IssueIndex = 0; IssueIndex < IA.size(); ++IssueIndex) {
332 IssuesByIndex[IssueIndex] = new IssuePrediction();
333 IssuesByIndex[IssueIndex].INIT(IA.get(IssueIndex));
334 IPIndexByIssueNumber.put(IA.get(IssueIndex).getNumber(), IssueIndex);
335 }
336 }
337
338 TreeMap<String, Bid> OpponentBids = new TreeMap<String, Bid>();
339
340 public void UpdateImportance(
341 Bid OpponentBid /*
342 * Incomming Bid as received from opponent
343 */) throws Exception {
344 String bidStr = OpponentBid.toString();
345 if (OpponentBids.containsKey(bidStr))
346 return;
347 OpponentBids.put(bidStr, OpponentBid);
348
349 final double ZeroVarianceToMinimalVarianceWeight = 3;
350 // a heuristic value that tells us that an issue with no variance
351 // is 3 times as important as the issue with minimal variance
352
353 TotalIssueOptionsVariance = 0;
354
355 double MinimalNonZeroVariance = Double.MAX_VALUE;
356 int ZeroVarianceIssueCount = 0; //
357 for (int IssueIndex = 0; IssueIndex < IssuesByIndex.length; ++IssueIndex) {
358 int IssueID = IssuesByIndex[IssueIndex].IssueBase.getNumber();
359 IssuesByIndex[IssueIndex].Issue.UpdateImportance(OpponentBid.getValue(IssueID));
360
361 double IssueVariance = IssuesByIndex[IssueIndex].Issue.GetNormalizedVariance();
362
363 TotalIssueOptionsVariance += IssueVariance;
364
365 if (0 == IssueVariance)
366 ++ZeroVarianceIssueCount;
367 else
368 MinimalNonZeroVariance = Math.min(IssueVariance, MinimalNonZeroVariance);
369 }
370
371 // we decide how important each issue is, by comparing it's variance
372 // to the most important issue (with minimal variance)
373
374 TotalIssueOptionsVariance /= MinimalNonZeroVariance * (1.0 / ZeroVarianceToMinimalVarianceWeight); // we
375 // now
376 // count
377 // importance
378 // of
379 // issue
380 // with
381 // units
382 // of size (1.0 / ZeroVarianceToMinimalVarianceWeight) *
383 // MinimalNonZeroVariance
384
385 // we add one unit per Zero-Variance Issue
386 TotalIssueOptionsVariance += ZeroVarianceIssueCount;
387
388 double WeightCount = 0;
389
390 if (TotalIssueOptionsVariance != ZeroVarianceIssueCount) // check if all
391 // weights
392 // are not
393 // the same
394 // ( all
395 // variances
396 // zero)
397 {
398 // zero variance issue have exactly 1 VarianceUnits,
399 // next minimal variance had ZeroVarianceToMinimalVarianceWeight
400 // VarianceUnits
401 // other issues are weighted with same relation
402 double VarianceUnit = MinimalNonZeroVariance / ZeroVarianceToMinimalVarianceWeight;
403
404 // calculate each issue weight (each weight is 0 to 1)
405 for (int IssueIndex = IssuesByIndex.length - 1; IssueIndex >= 0; --IssueIndex) {
406 if (0 == IssuesByIndex[IssueIndex].Issue.GetNormalizedVariance()) {
407 // if the issue has 0 variance, we give it maximum weight
408 // more weight than the next (non-zero variance) important
409 // issue
410 IssuesByIndex[IssueIndex].ExpectedWeight = 1;
411 } else
412 IssuesByIndex[IssueIndex].ExpectedWeight = VarianceUnit
413 / IssuesByIndex[IssueIndex].Issue.GetNormalizedVariance();
414
415 WeightCount += IssuesByIndex[IssueIndex].ExpectedWeight;
416 }
417 }
418
419 for (int IssueIndex = IssuesByIndex.length - 1; IssueIndex >= 0; --IssueIndex) {
420 // if up until now we were always given the same bid, then all
421 // issues has the same importance and same variance(0)
422 if (TotalIssueOptionsVariance == ZeroVarianceIssueCount)
423 IssuesByIndex[IssueIndex].ExpectedWeight = 1.0 / IssuesByIndex.length;
424 else
425 IssuesByIndex[IssueIndex].ExpectedWeight /= WeightCount; // normalize
426 // weights
427 }
428 }
429
430 public double EvaluateOpponentUtility(Bid B) throws Exception {
431 double UtilitySum = 0;
432
433 try {
434 for (int IssueIndex = 0; IssueIndex < IssuesByIndex.length; ++IssueIndex) {
435 int IssueID = IssuesByIndex[IssueIndex].IssueBase.getNumber();
436 UtilitySum += IssuesByIndex[IssueIndex].ExpectedWeight
437 * IssuesByIndex[IssueIndex].Issue.GetExpectedUtilityByValue(B.getValue(IssueID));
438 }
439 } catch (Exception e) {
440 e.printStackTrace();
441 }
442 return UtilitySum;
443 }
444
445 TreeMap<Integer, TreeMap<String, ValueDiscrete>> ValueTranslation = new TreeMap<Integer, TreeMap<String, ValueDiscrete>>();
446
447 public Value ImproveValue(int IssueNumber, ValueDiscrete ValToImprove) throws Exception {
448 TreeMap<String, ValueDiscrete> ValueTranslator = ValueTranslation.get(IssueNumber);
449 ValueDiscrete resultValue = new ValueDiscrete(ValToImprove.toString());
450
451 if (ValueTranslator != null) {
452 resultValue = ValueTranslator.get(ValToImprove.toString());
453 if (resultValue != null)
454 return resultValue;
455 } else {
456 ValueTranslator = new TreeMap<String, ValueDiscrete>();
457 ValueTranslation.put(IssueNumber, ValueTranslator);
458 }
459
460 IssuePrediction IS = IssuesByIndex[IPIndexByIssueNumber.get(IssueNumber)];
461 Issue I = IS.IssueBase;
462 Bid tmpBid = US.getDomain().getRandomBid(random500);
463 tmpBid = tmpBid.putValue(IssueNumber, ValToImprove);
464
465 double oppUtilityWithVal = IS.Issue.GetExpectedUtilityByValue(ValToImprove);
466 double utilityWithVal = US.getEvaluation(IssueNumber, tmpBid);
467
468 if (!(I instanceof IssueDiscrete))
469 return ValToImprove;
470
471 IssueDiscrete DI = (IssueDiscrete) I;
472
473 int size = DI.getNumberOfValues();
474 for (int i = 0; i < size; i++) {
475 ValueDiscrete curr = DI.getValue(i);
476 tmpBid = tmpBid.putValue(IssueNumber, curr);
477 double myUtilityWithCurrent = US.getEvaluation(IssueNumber, tmpBid);
478 double oppUtilityWithCurrent = IS.Issue.GetExpectedUtilityByValue(curr);
479 // // find a value which is not worse than valTo improve but better
480 // for opponent
481 if (myUtilityWithCurrent >= utilityWithVal && oppUtilityWithCurrent > oppUtilityWithVal * 1.3) {
482 oppUtilityWithVal = oppUtilityWithCurrent;
483 resultValue = curr;
484 }
485 }
486 ValueTranslator.put(ValToImprove.toString(), resultValue);
487
488 return resultValue;
489 }
490
491 public Bid ImproveBid(Bid BidToImprove) throws Exception {
492
493 Bid resultBid = US.getDomain().getRandomBid(random600);
494 for (Issue issue : US.getDomain().getIssues()) {
495 try {
496 if (issue.getType() == ISSUETYPE.DISCRETE)
497 resultBid = resultBid.putValue(issue.getNumber(),
498 ImproveValue(issue.getNumber(), (ValueDiscrete) BidToImprove.getValue(issue.getNumber())));
499 else
500 resultBid = resultBid.putValue(issue.getNumber(), BidToImprove.getValue(issue.getNumber()));
501
502 } catch (Exception e) {
503 try {
504 resultBid = resultBid.putValue(issue.getNumber(),
505 (ValueDiscrete) BidToImprove.getValue(issue.getNumber()));
506 } catch (Exception E) {
507 return BidToImprove;
508 }
509 }
510
511 }
512
513 return resultBid;
514 }
515
516 public TreeMap<Double, Bid> FilterBids(TreeMap<Double, Bid> Bids, int DesiredResultEntries) throws Exception {
517 TreeMap<Double, Bid> resultBids = new TreeMap<Double, Bid>();
518 Entry<Double, Bid> bidIter = Bids.lastEntry();
519
520 double BestKey = bidIter.getKey();
521 Bid bestBid = bidIter.getValue();
522 double bestOppUtil = EvaluateOpponentUtility(bestBid);
523 resultBids.put(BestKey, bestBid);
524
525 bidIter = Bids.lowerEntry(bidIter.getKey());
526
527 // int EntryContraction = Bids.size() /
528 // Math.max(1,DesiredResultEntries);
529 // int RemainingEntriesToContraction = EntryContraction;
530
531 while (bidIter != null && timeline.getTime() < 0.94) {
532
533 Bid checkedBid = bidIter.getValue();
534 double checkedKey = US.getUtility(checkedBid);
535 double checkedOppUtil = EvaluateOpponentUtility(checkedBid);
536
537 if (checkedOppUtil >= bestOppUtil * 0.84) {
538 resultBids.put(checkedKey, checkedBid);
539 if (checkedOppUtil > bestOppUtil) {
540 bestBid = checkedBid;
541 BestKey = checkedKey;
542 bestOppUtil = checkedOppUtil;
543 }
544 }
545
546 bidIter = Bids.lowerEntry(bidIter.getKey());
547 }
548
549 // if (bestBid != null)
550 // resultBids.put(BestKey, bestBid);
551
552 if (resultBids.size() < DesiredResultEntries / 10 || resultBids.size() < 20)
553 return Bids;
554 return resultBids;
555 }
556}
Note: See TracBrowser for help on using the repository browser.