[127] | 1 | package agents.anac.y2010.Yushu;
|
---|
| 2 |
|
---|
| 3 | import java.util.Collections;
|
---|
| 4 | import java.util.Date;
|
---|
| 5 | import java.util.LinkedList;
|
---|
| 6 | import java.util.Random;
|
---|
| 7 |
|
---|
| 8 | import genius.core.Agent;
|
---|
| 9 | import genius.core.Bid;
|
---|
| 10 | import genius.core.BidIterator;
|
---|
| 11 | import genius.core.SupportedNegotiationSetting;
|
---|
| 12 | import genius.core.actions.Accept;
|
---|
| 13 | import genius.core.actions.Action;
|
---|
| 14 | import genius.core.actions.ActionWithBid;
|
---|
| 15 | import genius.core.actions.Offer;
|
---|
| 16 | import genius.core.bidding.BidDetails;
|
---|
| 17 | import genius.core.bidding.BidDetailsStrictSorterUtility;
|
---|
| 18 |
|
---|
| 19 | /**
|
---|
| 20 | * ANAC2010 competitor Yushu.
|
---|
| 21 | */
|
---|
| 22 | public class Yushu extends Agent {
|
---|
| 23 | private double eagerness = 1.2;
|
---|
| 24 | private Action actionOfOpponent = null;
|
---|
| 25 | private Bid myLastBid = null;
|
---|
| 26 | private LinkedList<Bid> opponentHistory; // LinkedHashMap<Date,Bid>
|
---|
| 27 | private LinkedList<Double> opponentUtis;
|
---|
| 28 | private LinkedList<Integer> bestTenBids; // decreasing
|
---|
| 29 | private LinkedList<Bid> myHistory;
|
---|
| 30 | private LinkedList<Double> resptimes;
|
---|
| 31 | Bid suggestBid = null; // the bid suggested based on op's bids
|
---|
| 32 | Bid BESTBID = null;
|
---|
| 33 | double topponentBidU = 0;
|
---|
| 34 | double roundleft;
|
---|
| 35 | Date rstime = null; // the time when I send out a
|
---|
| 36 | double HPOSSIBLEU = 0;// the highest utility that can be achieved
|
---|
| 37 | double ACCEPTABLEU = 1; // if oppennent's utility is higher than this,
|
---|
| 38 | // accept it
|
---|
| 39 | double previousTime = 0;
|
---|
| 40 | Random random100;
|
---|
| 41 | Random random200;
|
---|
| 42 | private final boolean TEST_EQUIVALENCE = false;
|
---|
| 43 |
|
---|
| 44 | @Override
|
---|
| 45 | public void init() {
|
---|
| 46 | // if(utilitySpace.getReservationValue()!=null)
|
---|
| 47 | // Utility.MINIMUM_BID_UTILITY = utilitySpace.getReservationValue();
|
---|
| 48 | actionOfOpponent = null;
|
---|
| 49 | myLastBid = null;
|
---|
| 50 | opponentHistory = new LinkedList<Bid>();
|
---|
| 51 | opponentUtis = new LinkedList<Double>();
|
---|
| 52 | myHistory = new LinkedList<Bid>();
|
---|
| 53 | resptimes = new LinkedList<Double>();
|
---|
| 54 | suggestBid = null;
|
---|
| 55 | bestTenBids = new LinkedList<Integer>();
|
---|
| 56 | topponentBidU = 0;
|
---|
| 57 | rstime = null;
|
---|
| 58 | ACCEPTABLEU = 1;
|
---|
| 59 | if (TEST_EQUIVALENCE) {
|
---|
| 60 | random100 = new Random(100);
|
---|
| 61 | random200 = new Random(200);
|
---|
| 62 | } else {
|
---|
| 63 | random100 = new Random();
|
---|
| 64 | random200 = new Random();
|
---|
| 65 | }
|
---|
| 66 | try {
|
---|
| 67 | BESTBID = utilitySpace.getMaxUtilityBid();
|
---|
| 68 | HPOSSIBLEU = utilitySpace.getUtility(BESTBID);
|
---|
| 69 | } catch (Exception e) {
|
---|
| 70 | HPOSSIBLEU = 1;
|
---|
| 71 | }
|
---|
| 72 | }
|
---|
| 73 |
|
---|
| 74 | @Override
|
---|
| 75 | public String getVersion() {
|
---|
| 76 | return "2";
|
---|
| 77 | }
|
---|
| 78 |
|
---|
| 79 | @Override
|
---|
| 80 | public String getName() {
|
---|
| 81 | return "Yushu";
|
---|
| 82 | }
|
---|
| 83 |
|
---|
| 84 | @Override
|
---|
| 85 | public void ReceiveMessage(Action opponentAction) {
|
---|
| 86 | actionOfOpponent = opponentAction;
|
---|
| 87 | }
|
---|
| 88 |
|
---|
| 89 | @Override
|
---|
| 90 | public Action chooseAction() {
|
---|
| 91 | double targetuti = -1;
|
---|
| 92 | resptimes.add(timeline.getTime() - previousTime);
|
---|
| 93 | previousTime = timeline.getTime();
|
---|
| 94 | Action action = null;
|
---|
| 95 | try {
|
---|
| 96 | if (actionOfOpponent == null) {
|
---|
| 97 | Bid initialbid = BESTBID;
|
---|
| 98 | action = new Offer(getAgentID(), initialbid);
|
---|
| 99 | } else if (actionOfOpponent instanceof Offer) {
|
---|
| 100 | Bid opponentBid = ((Offer) actionOfOpponent).getBid();
|
---|
| 101 | double utiop = utilitySpace.getUtility(opponentBid);
|
---|
| 102 | this.opponentHistory.add(opponentBid);
|
---|
| 103 | this.opponentUtis.add(utiop);
|
---|
| 104 | topponentBidU = topponentBidU + utiop;
|
---|
| 105 | updateBelief(opponentBid, utiop);
|
---|
| 106 |
|
---|
| 107 | if (this.myLastBid == null)
|
---|
| 108 | targetuti = 1;
|
---|
| 109 | else
|
---|
| 110 | targetuti = getTargetUtility();
|
---|
| 111 |
|
---|
| 112 | boolean accept = false;
|
---|
| 113 | if ((utiop >= targetuti) | (utiop >= ACCEPTABLEU)) {
|
---|
| 114 |
|
---|
| 115 | if (this.suggestBid == null)
|
---|
| 116 | accept = true;
|
---|
| 117 | if (roundleft < 8)
|
---|
| 118 | accept = true;
|
---|
| 119 | if ((this.suggestBid != null) & (roundleft > 8)) {
|
---|
| 120 | double utit = utilitySpace.getUtility(this.suggestBid);
|
---|
| 121 | if (utit <= utiop)
|
---|
| 122 | accept = true;
|
---|
| 123 | }
|
---|
| 124 | }
|
---|
| 125 | if (accept) {
|
---|
| 126 | action = new Accept(getAgentID(), opponentBid);
|
---|
| 127 |
|
---|
| 128 | } else {
|
---|
| 129 | Bid mynextBid;
|
---|
| 130 | if (this.suggestBid != null) {
|
---|
| 131 | mynextBid = this.suggestBid;
|
---|
| 132 | } else {
|
---|
| 133 | if (targetuti >= HPOSSIBLEU)
|
---|
| 134 | mynextBid = utilitySpace.getMaxUtilityBid();
|
---|
| 135 | else {
|
---|
| 136 | mynextBid = getNextBid(targetuti);
|
---|
| 137 | }
|
---|
| 138 | }
|
---|
| 139 | action = new Offer(getAgentID(), mynextBid);
|
---|
| 140 | }
|
---|
| 141 | }
|
---|
| 142 | // Thread.sleep(1000); //
|
---|
| 143 | } catch (Exception e) {
|
---|
| 144 | e.printStackTrace();
|
---|
| 145 | targetuti = getTargetUtility();
|
---|
| 146 | try {
|
---|
| 147 | Bid mynextBid = getNextBid(targetuti);
|
---|
| 148 | action = new Offer(getAgentID(), mynextBid);
|
---|
| 149 | } catch (Exception es) {
|
---|
| 150 | e.printStackTrace();
|
---|
| 151 | // best guess if things go wrong.
|
---|
| 152 | action = new Accept(getAgentID(),
|
---|
| 153 | ((ActionWithBid) actionOfOpponent).getBid());
|
---|
| 154 | }
|
---|
| 155 | // action=new Accept(getAgentID()); // best guess if things go
|
---|
| 156 | // wrong.
|
---|
| 157 | }
|
---|
| 158 |
|
---|
| 159 | if (action instanceof Offer) {
|
---|
| 160 | this.myLastBid = ((Offer) action).getBid();
|
---|
| 161 | myHistory.add(this.myLastBid);
|
---|
| 162 | }
|
---|
| 163 | return action;
|
---|
| 164 | }
|
---|
| 165 |
|
---|
| 166 | // generate the objective utitility of my next offer
|
---|
| 167 | public double getTargetUtility() {
|
---|
| 168 | double tround = Math.max(averResT(), averLastTResT(3));
|
---|
| 169 |
|
---|
| 170 | double lefttime = 1 - timeline.getTime();
|
---|
| 171 |
|
---|
| 172 | roundleft = lefttime / tround;
|
---|
| 173 |
|
---|
| 174 | if (roundleft > 6.7)
|
---|
| 175 | Utility.MINIMUM_BID_UTILITY = 0.93 * HPOSSIBLEU;
|
---|
| 176 | else if (roundleft > 5)
|
---|
| 177 | Utility.MINIMUM_BID_UTILITY = 0.90 * HPOSSIBLEU;
|
---|
| 178 | else if (lefttime > 3 * tround)
|
---|
| 179 | Utility.MINIMUM_BID_UTILITY = 0.86 * HPOSSIBLEU;
|
---|
| 180 | else if (lefttime > 2.3 * tround)
|
---|
| 181 | Utility.MINIMUM_BID_UTILITY = 0.8 * HPOSSIBLEU;
|
---|
| 182 | else
|
---|
| 183 | Utility.MINIMUM_BID_UTILITY = 0.6 * HPOSSIBLEU;
|
---|
| 184 | if (lefttime < 15 * tround)
|
---|
| 185 | ACCEPTABLEU = 0.92 * HPOSSIBLEU;
|
---|
| 186 | else
|
---|
| 187 | ACCEPTABLEU = 0.96 * HPOSSIBLEU;
|
---|
| 188 |
|
---|
| 189 | // consider the domain competition
|
---|
| 190 | double averopu = 0, averopui = 0;
|
---|
| 191 | if (this.opponentHistory.size() > 0)
|
---|
| 192 | averopui = this.topponentBidU / this.opponentHistory.size();
|
---|
| 193 | averopu = Math.max(0.30, averopui);
|
---|
| 194 |
|
---|
| 195 | double rte = 20 + (1 - averopu) / 0.10 * 20;
|
---|
| 196 | if ((lefttime < rte * tround) & (this.opponentHistory.size() > 3)
|
---|
| 197 | & (averopu < 0.75)) {
|
---|
| 198 | Utility.MINIMUM_BID_UTILITY = Utility.MINIMUM_BID_UTILITY
|
---|
| 199 | - (0.75 - averopu) / 2.5;
|
---|
| 200 | }
|
---|
| 201 | Utility.MINIMUM_BID_UTILITY = Math.max(0.50,
|
---|
| 202 | Utility.MINIMUM_BID_UTILITY); // no
|
---|
| 203 | // less
|
---|
| 204 | // than
|
---|
| 205 | // 0.5
|
---|
| 206 | double time = timeline.getTime();
|
---|
| 207 | // if(time>0.5)
|
---|
| 208 | Utility.MINIMUM_BID_UTILITY = Utility.MINIMUM_BID_UTILITY
|
---|
| 209 | * (Math.min(0.75, averopu) / 3 + 0.75);
|
---|
| 210 | Utility.MINIMUM_BID_UTILITY = Math.max(Utility.MINIMUM_BID_UTILITY,
|
---|
| 211 | averopu);
|
---|
| 212 | double targetuti = HPOSSIBLEU
|
---|
| 213 | - (HPOSSIBLEU - Utility.MINIMUM_BID_UTILITY)
|
---|
| 214 | * Math.pow(time, eagerness);
|
---|
| 215 | // Debug.LOG("CASE 4-"+this.opponentUtis.size()+" "+rte+"
|
---|
| 216 | // roundleft-"+roundleft);
|
---|
| 217 |
|
---|
| 218 | if (lefttime < 1.6 * tround) {
|
---|
| 219 | suggestBid = this.opponentHistory.get(this.bestTenBids.getFirst());
|
---|
| 220 | return targetuti;
|
---|
| 221 | }
|
---|
| 222 |
|
---|
| 223 | // consider op's best past offer
|
---|
| 224 | if (lefttime > 50 * tround)
|
---|
| 225 | targetuti = Math.max(targetuti,
|
---|
| 226 | opponentUtis.get(this.bestTenBids.getFirst()) * 1.001);
|
---|
| 227 | if (((lefttime < 10 * tround) & (opponentUtis
|
---|
| 228 | .get(this.bestTenBids.getFirst()) > targetuti * 0.95))
|
---|
| 229 | | opponentUtis.get(this.bestTenBids.getFirst()) >= targetuti) {
|
---|
| 230 | double newtargetuti = targetuti;
|
---|
| 231 | if ((lefttime < 10 * tround) & (opponentUtis
|
---|
| 232 | .get(this.bestTenBids.getFirst()) > targetuti * 0.95))
|
---|
| 233 | newtargetuti = targetuti * 0.95;
|
---|
| 234 |
|
---|
| 235 | // check whether the best op bid was offered in the last 4 rouds
|
---|
| 236 | boolean offered = false;
|
---|
| 237 | int length = Math.min(this.myHistory.size(), 4);
|
---|
| 238 |
|
---|
| 239 | for (int i = this.myHistory.size() - 1; i >= this.myHistory.size()
|
---|
| 240 | - length; i--) {
|
---|
| 241 | if (this.myHistory.get(i).equals(this.opponentHistory
|
---|
| 242 | .get(this.bestTenBids.getFirst()))) {
|
---|
| 243 | offered = true;
|
---|
| 244 | }
|
---|
| 245 | }
|
---|
| 246 | if (offered) {
|
---|
| 247 | LinkedList<Integer> candidates = new LinkedList<Integer>();
|
---|
| 248 | for (int i = 0; i < bestTenBids.size(); i++)
|
---|
| 249 | if (this.opponentUtis
|
---|
| 250 | .get(bestTenBids.get(i)) >= newtargetuti)
|
---|
| 251 | candidates.add(bestTenBids.get(i));
|
---|
| 252 | int indexc = (int) (random100.nextDouble() * candidates.size());
|
---|
| 253 | suggestBid = this.opponentHistory.get(candidates.get(indexc));
|
---|
| 254 |
|
---|
| 255 | } else {
|
---|
| 256 | suggestBid = this.opponentHistory
|
---|
| 257 | .get(this.bestTenBids.getFirst());
|
---|
| 258 | }
|
---|
| 259 | targetuti = newtargetuti;
|
---|
| 260 | }
|
---|
| 261 | return targetuti;
|
---|
| 262 | }
|
---|
| 263 |
|
---|
| 264 | // generate the next bid satisfing the
|
---|
| 265 | private Bid getNextBid(double targetuti) throws Exception {
|
---|
| 266 | Bid nextBid = null;
|
---|
| 267 | double maxdiff = Double.MAX_VALUE;
|
---|
| 268 | double tempmaxdiff = Double.MAX_VALUE;
|
---|
| 269 |
|
---|
| 270 | LinkedList<BidDetails> candidates = new LinkedList<BidDetails>();
|
---|
| 271 | BidIterator bidsIter = new BidIterator(utilitySpace.getDomain());
|
---|
| 272 | while (bidsIter.hasNext()) {
|
---|
| 273 | Bid tmpBid = bidsIter.next();
|
---|
| 274 | double utitemp = utilitySpace.getUtility(tmpBid);
|
---|
| 275 | double vlowbound;
|
---|
| 276 | if (roundleft > 30)
|
---|
| 277 | vlowbound = Math.max(this.opponentUtis.get(bestTenBids.get(0)),
|
---|
| 278 | targetuti);
|
---|
| 279 | else
|
---|
| 280 | vlowbound = 0.96 * targetuti;
|
---|
| 281 | if ((utitemp > vlowbound) & (utitemp < 1.08 * targetuti))
|
---|
| 282 | candidates.add(new BidDetails(tmpBid,
|
---|
| 283 | utilitySpace.getUtility(tmpBid), timeline.getTime()));
|
---|
| 284 | double currentdiff = Math.abs(utitemp - targetuti);
|
---|
| 285 | if (currentdiff < tempmaxdiff) {
|
---|
| 286 | tempmaxdiff = currentdiff;
|
---|
| 287 | }
|
---|
| 288 |
|
---|
| 289 | if ((currentdiff < maxdiff) & (utitemp > targetuti)) {
|
---|
| 290 | maxdiff = currentdiff;
|
---|
| 291 | nextBid = tmpBid;
|
---|
| 292 | }
|
---|
| 293 | }
|
---|
| 294 | if (this.myHistory.size() > 10) {
|
---|
| 295 | candidates.add(new BidDetails(nextBid,
|
---|
| 296 | utilitySpace.getUtility(nextBid), timeline.getTime()));
|
---|
| 297 | if (TEST_EQUIVALENCE) {
|
---|
| 298 | Collections.sort(candidates,
|
---|
| 299 | new BidDetailsStrictSorterUtility());
|
---|
| 300 | }
|
---|
| 301 | int indexc = (int) (random200.nextDouble() * candidates.size());
|
---|
| 302 | nextBid = candidates.get(indexc).getBid();
|
---|
| 303 | }
|
---|
| 304 |
|
---|
| 305 | return nextBid;
|
---|
| 306 | }
|
---|
| 307 |
|
---|
| 308 | // learning --to complete
|
---|
| 309 | public void updateBelief(Bid opponentBid, double uti) {
|
---|
| 310 | int index = this.opponentHistory.size() - 1;
|
---|
| 311 | if (bestTenBids.size() == 0)
|
---|
| 312 | bestTenBids.add(index);
|
---|
| 313 | else {
|
---|
| 314 | LinkedList<Integer> newlist = new LinkedList<Integer>();
|
---|
| 315 | if (uti > this.opponentUtis.get(bestTenBids.getFirst())) {
|
---|
| 316 | newlist.add(index);
|
---|
| 317 | for (int j = 0; j < bestTenBids.size(); j++)
|
---|
| 318 | newlist.add(bestTenBids.get(j));
|
---|
| 319 | bestTenBids = newlist;
|
---|
| 320 | } else if (uti <= this.opponentUtis.get(bestTenBids.getLast()))
|
---|
| 321 | bestTenBids.add(index);
|
---|
| 322 | else {
|
---|
| 323 | for (int i = 1; i < bestTenBids.size(); i++) {
|
---|
| 324 | if ((uti <= this.opponentUtis.get(bestTenBids.get(i - 1)))
|
---|
| 325 | & (uti > this.opponentUtis
|
---|
| 326 | .get(bestTenBids.get(i)))) {
|
---|
| 327 | for (int j = 0; j < i; j++)
|
---|
| 328 | newlist.add(bestTenBids.get(j));
|
---|
| 329 | newlist.add(index);
|
---|
| 330 | for (int j = i; j < bestTenBids.size(); j++)
|
---|
| 331 | newlist.add(bestTenBids.get(j));
|
---|
| 332 | break;
|
---|
| 333 | }
|
---|
| 334 | }
|
---|
| 335 | // Debug.LOG("CASE 3-"+this.opponentUtis.size());
|
---|
| 336 | bestTenBids = newlist;
|
---|
| 337 | }
|
---|
| 338 | }
|
---|
| 339 | if (bestTenBids.size() > 10)
|
---|
| 340 | bestTenBids.removeLast();
|
---|
| 341 | }
|
---|
| 342 |
|
---|
| 343 | public double averResT() {
|
---|
| 344 | if (resptimes.size() == 0)
|
---|
| 345 | return 0;
|
---|
| 346 | double total = 0;
|
---|
| 347 | for (int i = 0; i < resptimes.size(); i++)
|
---|
| 348 | total = total + resptimes.get(i);
|
---|
| 349 | return total / resptimes.size();
|
---|
| 350 | }
|
---|
| 351 |
|
---|
| 352 | public double averLastTResT(int length) {
|
---|
| 353 | if (resptimes.size() < length)
|
---|
| 354 | return 0;
|
---|
| 355 | double total = 0;
|
---|
| 356 | for (int i = resptimes.size() - 1; i > resptimes.size() - length
|
---|
| 357 | - 1; i--)
|
---|
| 358 | total = total + resptimes.get(i);
|
---|
| 359 | return total / length;
|
---|
| 360 | }
|
---|
| 361 |
|
---|
| 362 | @Override
|
---|
| 363 | public SupportedNegotiationSetting getSupportedNegotiationSetting() {
|
---|
| 364 | return SupportedNegotiationSetting.getLinearUtilitySpaceInstance();
|
---|
| 365 | }
|
---|
| 366 |
|
---|
| 367 | @Override
|
---|
| 368 | public String getDescription() {
|
---|
| 369 | return "ANAC2010";
|
---|
| 370 | }
|
---|
[1] | 371 | } |
---|