[1] | 1 | package agents.anac.y2015.pnegotiator;
|
---|
| 2 |
|
---|
| 3 | import java.util.ArrayList;
|
---|
| 4 | import java.util.Arrays;
|
---|
| 5 | import java.util.Iterator;
|
---|
| 6 | import java.util.List;
|
---|
| 7 | import java.util.Random;
|
---|
| 8 | import java.util.TreeSet;
|
---|
| 9 |
|
---|
| 10 | import genius.core.Bid;
|
---|
| 11 | import genius.core.Domain;
|
---|
| 12 | import genius.core.issue.Issue;
|
---|
| 13 | import genius.core.issue.IssueDiscrete;
|
---|
| 14 | import genius.core.issue.ValueDiscrete;
|
---|
| 15 | import genius.core.utility.AdditiveUtilitySpace;
|
---|
| 16 | import genius.core.utility.EvaluatorDiscrete;
|
---|
| 17 |
|
---|
| 18 | /**
|
---|
| 19 | * Created by chad on 2/28/15.
|
---|
| 20 | */
|
---|
| 21 | public class BayesLogic {
|
---|
| 22 | private AdditiveUtilitySpace utilitySpace;
|
---|
| 23 | private ArrayList<TreeSet<ValueFrequency>> valueFrequencies;
|
---|
| 24 | private ArrayList<ValueFrequency>[] vFreqs;
|
---|
| 25 | public int T = 1;
|
---|
| 26 | int totalBids = 0;
|
---|
| 27 | int P;
|
---|
| 28 | public int V = 1;
|
---|
| 29 |
|
---|
| 30 | public BayesLogic(AdditiveUtilitySpace utilitySpace, int P)
|
---|
| 31 | throws Exception {
|
---|
| 32 | Domain domain = utilitySpace.getDomain();
|
---|
| 33 | List<Issue> issues = domain.getIssues();
|
---|
| 34 | this.P = P;
|
---|
| 35 |
|
---|
| 36 | this.utilitySpace = utilitySpace;
|
---|
| 37 | valueFrequencies = new ArrayList<TreeSet<ValueFrequency>>(
|
---|
| 38 | issues.size() - 1);
|
---|
| 39 | vFreqs = new ArrayList[issues.size() - 1];
|
---|
| 40 | for (int i = 0; i < issues.size() - 1; ++i) {
|
---|
| 41 | // System.out.println("Adding TreeSet<ValueFrequency> vfs[" + (i) +
|
---|
| 42 | // "]");
|
---|
| 43 | valueFrequencies.add(i, new TreeSet<ValueFrequency>(new VFComp()));
|
---|
| 44 | vFreqs[i] = new ArrayList<ValueFrequency>();
|
---|
| 45 | IssueDiscrete di = (IssueDiscrete) domain.getIssues().get(i);
|
---|
| 46 | EvaluatorDiscrete ed = (EvaluatorDiscrete) utilitySpace
|
---|
| 47 | .getEvaluator(i + 1);
|
---|
| 48 | for (ValueDiscrete v : di.getValues()) {
|
---|
| 49 | // System.out.println("\tAdding ValueFrequency element[" +
|
---|
| 50 | // v.value + ", " + (ed.getEvaluation(v) * ed.getWeight()) +
|
---|
| 51 | // "]");
|
---|
| 52 | ValueFrequency v1 = new ValueFrequency(v, ed.getEvaluation(v),
|
---|
| 53 | P);
|
---|
| 54 | valueFrequencies.get(i).add(v1);
|
---|
| 55 | vFreqs[i].add(v1);
|
---|
| 56 | }
|
---|
| 57 | }
|
---|
| 58 |
|
---|
| 59 | }
|
---|
| 60 |
|
---|
| 61 | public Bid bayesBid(Bid bestBid) {
|
---|
| 62 | Bid b = new Bid(bestBid);
|
---|
| 63 | for (int i = 0; i < valueFrequencies.size(); ++i) {
|
---|
| 64 | Iterator<ValueFrequency> itr = valueFrequencies.get(i)
|
---|
| 65 | .descendingIterator();
|
---|
| 66 | ValueDiscrete highestExpectedUtilVal = null;
|
---|
| 67 | double highestExpectedUtil = -1.0;
|
---|
| 68 | // System.out.format("Issue: %d\n", i);
|
---|
| 69 | while (itr.hasNext()) {
|
---|
| 70 | ValueFrequency vfr = itr.next();
|
---|
| 71 | double FP = 1;
|
---|
| 72 | for (int p = 0; p < P; p++)
|
---|
| 73 | FP *= vfr.opponentFrequency[p];
|
---|
| 74 | // Math.pow(totalBids,P)
|
---|
| 75 | double EU = FP * Math.pow(vfr.utility, V);
|
---|
| 76 | // System.out.format(" Choice: %10s, U = %6.4f, E[U]: %10.2f, Frequencies: %s\n",
|
---|
| 77 | // vfr.value, vfr.utility, EU,
|
---|
| 78 | // Arrays.toString(vfr.opponentFrequency));
|
---|
| 79 | if (EU > highestExpectedUtil) {
|
---|
| 80 | highestExpectedUtilVal = vfr.value;
|
---|
| 81 | highestExpectedUtil = EU;
|
---|
| 82 | }
|
---|
| 83 | }
|
---|
| 84 | // ValueDiscrete highestExpectedUtilVal =
|
---|
| 85 | // (ValueDiscrete)(lastBid.getValue(i + 1));
|
---|
| 86 | // while(itr.hasNext()) {
|
---|
| 87 | // ValueFrequency vfr = itr.next();
|
---|
| 88 | // if((((double)vfr.opponentFrequency)/(double)totalBids) *
|
---|
| 89 | // vfr.utility >= highestExpectedUtil) {
|
---|
| 90 | // highestExpectedUtil =
|
---|
| 91 | // ((double)vfr.opponentFrequency/(double)totalBids * vfr.utility);
|
---|
| 92 | // highestExpectedUtilVal = vfr.value;
|
---|
| 93 | // }
|
---|
| 94 | // }
|
---|
| 95 | b = b.putValue(i + 1, highestExpectedUtilVal);
|
---|
| 96 | }
|
---|
| 97 | return b;
|
---|
| 98 | }
|
---|
| 99 |
|
---|
| 100 | private Bid asBid(ValueFrequency[] b) throws Exception {
|
---|
| 101 | Bid b1 = utilitySpace.getMaxUtilityBid();
|
---|
| 102 | for (int i = 0; i < b.length; i++) {
|
---|
| 103 | b1 = b1.putValue(i + 1, b[i].value);
|
---|
| 104 | }
|
---|
| 105 | return b1;
|
---|
| 106 | }
|
---|
| 107 |
|
---|
| 108 | private double EU2(ValueFrequency[] b) throws Exception {
|
---|
| 109 | double EU = utilitySpace.getUtility(asBid(b));
|
---|
| 110 | for (int p = 1; p < P; p++) {
|
---|
| 111 | for (int v = 0; v < b.length; v++)
|
---|
| 112 | EU *= b[v].opponentFrequency[p];
|
---|
| 113 | }
|
---|
| 114 | return EU;
|
---|
| 115 | }
|
---|
| 116 |
|
---|
| 117 | /**
|
---|
| 118 | * Approximates bid value
|
---|
| 119 | *
|
---|
| 120 | * @return
|
---|
| 121 | */
|
---|
| 122 | public Bid bayesBid2(Random rand) throws Exception {
|
---|
| 123 | ValueFrequency[] b = new ValueFrequency[valueFrequencies.size()];
|
---|
| 124 | for (int i = 0; i < valueFrequencies.size(); i++)
|
---|
| 125 | b[i] = valueFrequencies.get(i).last();
|
---|
| 126 | double T = 1, Tmin = 0.2, alpha = 0.9;
|
---|
| 127 | int K = 10;
|
---|
| 128 | double EU = EU2(b);
|
---|
| 129 | do {
|
---|
| 130 | System.out.println(T);
|
---|
| 131 | for (int k = 0; k < K; k++) {
|
---|
| 132 | ValueFrequency[] nb = Arrays.copyOf(b, b.length);
|
---|
| 133 |
|
---|
| 134 | int ri = rand.nextInt(nb.length);
|
---|
| 135 | nb[ri] = vFreqs[ri].get(rand.nextInt(vFreqs[ri].size()));
|
---|
| 136 |
|
---|
| 137 | double nEU = EU2(nb);
|
---|
| 138 | double p = Math.exp((EU - nEU) / T);
|
---|
| 139 | if (p > rand.nextDouble()) {
|
---|
| 140 | b = nb;
|
---|
| 141 | EU = nEU;
|
---|
| 142 | }
|
---|
| 143 | }
|
---|
| 144 | T *= alpha;
|
---|
| 145 | } while (T > Tmin);
|
---|
| 146 | return asBid(b);
|
---|
| 147 | }
|
---|
| 148 |
|
---|
| 149 | // Update the frequency of our proposed values based on a bid we're about to
|
---|
| 150 | // make
|
---|
| 151 | public void updateOurFrequency(Bid bid) throws Exception {
|
---|
| 152 | for (int i = 0; i < valueFrequencies.size(); ++i) {
|
---|
| 153 | Iterator<ValueFrequency> itr = valueFrequencies.get(i)
|
---|
| 154 | .descendingIterator();
|
---|
| 155 | while (itr.hasNext()) {
|
---|
| 156 | ValueFrequency vfr = itr.next();
|
---|
| 157 | if (vfr.value.toString().compareTo(
|
---|
| 158 | ((ValueDiscrete) bid.getValue(i + 1)).toString()) == 0) {
|
---|
| 159 | vfr.ourFrequency++;
|
---|
| 160 | }
|
---|
| 161 | break;
|
---|
| 162 | }
|
---|
| 163 | }
|
---|
| 164 | }
|
---|
| 165 |
|
---|
| 166 | // Update the frequency of opponents' proposed values based on a bid an
|
---|
| 167 | // opponent just made
|
---|
| 168 | public void updateOpponentFrequency(Bid bid, int P) throws Exception {
|
---|
| 169 | ++totalBids;
|
---|
| 170 | for (int i = 0; i < valueFrequencies.size(); ++i) {
|
---|
| 171 | Iterator<ValueFrequency> itr = valueFrequencies.get(i)
|
---|
| 172 | .descendingIterator();
|
---|
| 173 | while (itr.hasNext()) {
|
---|
| 174 | ValueFrequency vfr = itr.next();
|
---|
| 175 | // if(vfr.value.toString().compareTo(((ValueDiscrete)bid.getValue(i+1)).toString())
|
---|
| 176 | // == 0) {
|
---|
| 177 | // System.out.println(vfr + " " + bid);
|
---|
| 178 | if (vfr.value.toString().equals(bid.getValue(i + 1).toString())) {
|
---|
| 179 | vfr.opponentFrequency[P] += T;
|
---|
| 180 | break;
|
---|
| 181 | }
|
---|
| 182 | }
|
---|
| 183 | }
|
---|
| 184 | }
|
---|
| 185 | }
|
---|