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

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

Initial import : Genius 9.0.0
File size: 19.0 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.