1 | /* *************************************************************************************************************************************
|
---|
2 | TAgent: using the optimal stopping rule (cutoffs) for bidding.
|
---|
3 | Estimates rounds based on own/opponent actions.
|
---|
4 | Uses all the cutoffs (all_osr_cuttofs=true)
|
---|
5 |
|
---|
6 | TODO tournament pb, Java heap space..
|
---|
7 |
|
---|
8 | @author rafik hadfi <rafik@itolab.nitech.ac.jp>
|
---|
9 | * ***********************************************************************************************************************************/
|
---|
10 |
|
---|
11 | package agents;
|
---|
12 |
|
---|
13 | import java.util.ArrayList;
|
---|
14 | import java.util.HashMap;
|
---|
15 | import java.util.Stack;
|
---|
16 |
|
---|
17 | import genius.core.Agent;
|
---|
18 | import genius.core.Bid;
|
---|
19 | import genius.core.actions.Accept;
|
---|
20 | import genius.core.actions.Action;
|
---|
21 | import genius.core.actions.ActionWithBid;
|
---|
22 | import genius.core.actions.Offer;
|
---|
23 | import genius.core.issue.Issue;
|
---|
24 | import genius.core.issue.IssueDiscrete;
|
---|
25 | import genius.core.issue.Value;
|
---|
26 | import genius.core.issue.ValueDiscrete;
|
---|
27 | import genius.core.timeline.Timeline;
|
---|
28 | import genius.core.utility.AdditiveUtilitySpace;
|
---|
29 | import genius.core.utility.Evaluator;
|
---|
30 | import genius.core.utility.EvaluatorDiscrete;
|
---|
31 |
|
---|
32 | public class TAgent extends Agent {
|
---|
33 | private Action actionOfPartner = null;
|
---|
34 | private static int counter, index, idx, m, d, n;
|
---|
35 |
|
---|
36 | private static boolean flag, all_osr_cuttofs, two_osr_subsets, unused;
|
---|
37 |
|
---|
38 | private static double rvB, totalTime, timeLeftBeforeAction,
|
---|
39 | timeLeftAfterAction, OpponentMaxDuration, OwnMaxDuration;
|
---|
40 |
|
---|
41 | private static Stack<HashMap<Value, Double>> stack_h = null,
|
---|
42 | stack_aux = null, stack_hc = null;
|
---|
43 | private static ArrayList<ValueDiscrete> max_values = null;
|
---|
44 |
|
---|
45 | // init is called when a next session starts with the same opponent
|
---|
46 |
|
---|
47 | // #### cutoffs
|
---|
48 | // #################################################################################
|
---|
49 | public double bids(int j) {
|
---|
50 | return (j == 1) ? 0.5 * rvB / n + 0.5 : 0.5 * sq(bids(j - 1)) + 0.5; // adding
|
---|
51 | // scaling.
|
---|
52 | }
|
---|
53 |
|
---|
54 | // ###############################################################################################
|
---|
55 | public double bids_(double Bj) {
|
---|
56 | return Math.sqrt(2 * Bj - 1);
|
---|
57 | }
|
---|
58 |
|
---|
59 | /***************************************************************************************************************************/
|
---|
60 | public void init() {
|
---|
61 | try {
|
---|
62 | totalTime = timeline.getTotalTime();
|
---|
63 | timeLeftAfterAction = timeline.getCurrentTime();
|
---|
64 | timeLeftBeforeAction = OpponentMaxDuration = OwnMaxDuration = 0;
|
---|
65 | counter = index = idx = 0;
|
---|
66 | rvB = 0.0;
|
---|
67 | m = 5;
|
---|
68 | d = -1;
|
---|
69 | n = 1000;
|
---|
70 |
|
---|
71 | flag = true;
|
---|
72 | all_osr_cuttofs = true;
|
---|
73 | two_osr_subsets = false;
|
---|
74 | unused = false;
|
---|
75 |
|
---|
76 | stack_h = new Stack<HashMap<Value, Double>>();
|
---|
77 | stack_aux = new Stack<HashMap<Value, Double>>();
|
---|
78 | stack_hc = new Stack<HashMap<Value, Double>>();
|
---|
79 | max_values = new ArrayList<ValueDiscrete>();
|
---|
80 |
|
---|
81 | int i, number_of_values = -1;
|
---|
82 |
|
---|
83 | Issue pie = utilitySpace.getDomain().getIssues().get(0); // pie is
|
---|
84 | // the
|
---|
85 | // issue
|
---|
86 | System.out.println("###### issue name = " + pie + "\n"
|
---|
87 | + "###### issue type = " + pie.getType());
|
---|
88 | HashMap<Integer, Value> values = new HashMap<Integer, Value>(); // pairs
|
---|
89 | // <issuenumber,
|
---|
90 | // chosen
|
---|
91 | // value
|
---|
92 | // string>
|
---|
93 | switch (pie.getType()) // silly way to get/set rvB...
|
---|
94 | {
|
---|
95 | case DISCRETE: {
|
---|
96 | IssueDiscrete discrete_pie = (IssueDiscrete) pie;
|
---|
97 | number_of_values = discrete_pie.getNumberOfValues();
|
---|
98 | System.out.println("###### number_of_values = "
|
---|
99 | + number_of_values);
|
---|
100 |
|
---|
101 | for (i = 0; i < number_of_values; i++) {
|
---|
102 | ValueDiscrete value = discrete_pie.getValue(i);
|
---|
103 | values.put(pie.getNumber(), discrete_pie.getValue(i));
|
---|
104 | // evaluation
|
---|
105 | Evaluator eval = ((AdditiveUtilitySpace) utilitySpace)
|
---|
106 | .getEvaluator(pie.getNumber());
|
---|
107 | EvaluatorDiscrete evalDiscrete = (EvaluatorDiscrete) eval;
|
---|
108 | Integer evaluation = evalDiscrete
|
---|
109 | .getValue((ValueDiscrete) value);
|
---|
110 |
|
---|
111 | if (true)
|
---|
112 | System.out.println("###### i="
|
---|
113 | + i
|
---|
114 | + "\t u("
|
---|
115 | + value.getValue()
|
---|
116 | + ") = "
|
---|
117 | + getUtility(new Bid(utilitySpace.getDomain(),
|
---|
118 | values)) + "\t" + " eval("
|
---|
119 | + value.getValue() + ") = " + evaluation);
|
---|
120 |
|
---|
121 | if (i > (number_of_values - m))
|
---|
122 | max_values.add(value);
|
---|
123 |
|
---|
124 | if (evaluation != 0 && flag) // reaching rvB
|
---|
125 | {
|
---|
126 | rvB = i;
|
---|
127 | utilitySpace.setReservationValue(rvB);
|
---|
128 | flag = false;
|
---|
129 | }
|
---|
130 | }
|
---|
131 |
|
---|
132 | System.out
|
---|
133 | .println("\n######### generating an example of bids vector ###################################");
|
---|
134 |
|
---|
135 | // generating an example of bids vector
|
---|
136 |
|
---|
137 | for (i = 1; i < ((IssueDiscrete) pie).getNumberOfValues(); i++) {
|
---|
138 | HashMap<Value, Double> h = new HashMap<Value, Double>();
|
---|
139 | h.put(discrete_pie.getValue(i), new Double(n * bids(i))); // using
|
---|
140 | // scaling
|
---|
141 | stack_h.push(h);
|
---|
142 | }
|
---|
143 |
|
---|
144 | // make a copy of stack_h
|
---|
145 | stack_hc.addAll(stack_h);
|
---|
146 |
|
---|
147 | // new stack, without redundancies.
|
---|
148 | stack_aux.push(stack_h.pop());
|
---|
149 |
|
---|
150 | while (!stack_h.isEmpty()) {
|
---|
151 | if (stack_h
|
---|
152 | .get(stack_h.size() - 1)
|
---|
153 | .values()
|
---|
154 | .iterator()
|
---|
155 | .next()
|
---|
156 | .equals(stack_aux.get(stack_aux.size() - 1)
|
---|
157 | .values().iterator().next()))
|
---|
158 | stack_h.pop();
|
---|
159 | else
|
---|
160 | stack_aux.push(stack_h.pop());
|
---|
161 | }
|
---|
162 |
|
---|
163 | for (i = 0; i < stack_aux.size(); i++)
|
---|
164 | System.out.println("###### " + i + " => "
|
---|
165 | + stack_aux.get(i));
|
---|
166 | break;
|
---|
167 | }// case
|
---|
168 | default:
|
---|
169 | throw new Exception("Type " + pie.getType()
|
---|
170 | + " not supported by TAgent.");
|
---|
171 | } // switch
|
---|
172 | } catch (Exception e) {
|
---|
173 | e.printStackTrace();
|
---|
174 | }
|
---|
175 | }
|
---|
176 |
|
---|
177 | /********************************************************************************************************************/
|
---|
178 | private int estimated_rounds_left(boolean opponent) {
|
---|
179 | if (opponent == true) {
|
---|
180 | if (timeLeftBeforeAction - timeLeftAfterAction > OpponentMaxDuration)
|
---|
181 | OpponentMaxDuration = timeLeftBeforeAction
|
---|
182 | - timeLeftAfterAction;
|
---|
183 | } else // own
|
---|
184 | {
|
---|
185 | if (timeLeftAfterAction - timeLeftBeforeAction > OwnMaxDuration)
|
---|
186 | OwnMaxDuration = timeLeftAfterAction - timeLeftBeforeAction;
|
---|
187 | }
|
---|
188 |
|
---|
189 | if (OpponentMaxDuration + OwnMaxDuration == 0)
|
---|
190 | System.out.println("./0 Exception!");
|
---|
191 |
|
---|
192 | double totalDuration = OpponentMaxDuration + OwnMaxDuration, round = (totalTime - timeline
|
---|
193 | .getCurrentTime()) / totalDuration;
|
---|
194 |
|
---|
195 | if ((int) round > d && (int) round < 1000)
|
---|
196 | d = (int) round;
|
---|
197 |
|
---|
198 | return (int) round;
|
---|
199 | }
|
---|
200 |
|
---|
201 | /********************************************************************************************************************/
|
---|
202 | @Override
|
---|
203 | public String getVersion() {
|
---|
204 | return "1.0 (Genius 4.2)";
|
---|
205 | }
|
---|
206 |
|
---|
207 | @Override
|
---|
208 | public String getName() {
|
---|
209 | return "TAgent";
|
---|
210 | }
|
---|
211 |
|
---|
212 | /********************************************************************************************************************/
|
---|
213 |
|
---|
214 | public void ReceiveMessage(Action opponentAction) {
|
---|
215 | actionOfPartner = opponentAction;
|
---|
216 | }
|
---|
217 |
|
---|
218 | /********************************************************************************************************************/
|
---|
219 | public Action chooseAction() {
|
---|
220 | Action action = null;
|
---|
221 | try {
|
---|
222 | timeLeftBeforeAction = timeline.getCurrentTime();
|
---|
223 |
|
---|
224 | if (actionOfPartner == null)
|
---|
225 | action = chooseOSRAction();
|
---|
226 |
|
---|
227 | if (actionOfPartner instanceof Offer) {
|
---|
228 | Bid partnerBid = ((Offer) actionOfPartner).getBid();
|
---|
229 |
|
---|
230 | System.out.println("###### partnerBid === " + partnerBid);
|
---|
231 | System.out.println("###### partnerBid.getValues() === "
|
---|
232 | + partnerBid.getValue(1));
|
---|
233 |
|
---|
234 | double offeredUtilFromOpponent = getUtility(partnerBid);
|
---|
235 | // get current time
|
---|
236 | double time = timeline.getTime();
|
---|
237 |
|
---|
238 | action = chooseOSRAction();
|
---|
239 |
|
---|
240 | Bid myBid = ((Offer) action).getBid();
|
---|
241 | double myOfferedUtil = getUtility(myBid);
|
---|
242 | System.out.println("###### u(myBid = " + myBid.getValue(1)
|
---|
243 | + ") = " + myOfferedUtil);
|
---|
244 | System.out
|
---|
245 | .println("==========================================================================");
|
---|
246 |
|
---|
247 | // accept under certain circumstances
|
---|
248 |
|
---|
249 | /***
|
---|
250 | * # if (isAcceptable(offeredUtilFromOpponent, myOfferedUtil,
|
---|
251 | * time)) { action = new Accept(getAgentID());
|
---|
252 | * System.out.println( "==== Accepting! ===="); } #
|
---|
253 | ***/
|
---|
254 | }
|
---|
255 | if (timeline.getType().equals(Timeline.Type.Time))
|
---|
256 | sleep(0.005); // just for fun
|
---|
257 |
|
---|
258 | timeLeftAfterAction = timeline.getCurrentTime();
|
---|
259 | estimated_rounds_left(false); // receiveMessage the estimation for
|
---|
260 | // own
|
---|
261 | } catch (Exception e) {
|
---|
262 | System.out.println("Exception in ChooseAction:" + e.getMessage());
|
---|
263 | action = new Accept(getAgentID(),
|
---|
264 | ((ActionWithBid) actionOfPartner).getBid()); // best guess
|
---|
265 | // if things
|
---|
266 | // go wrong.
|
---|
267 | }
|
---|
268 | return action;
|
---|
269 | }
|
---|
270 |
|
---|
271 | /********************************************************************************************************************/
|
---|
272 | private boolean isAcceptable(double offeredUtilFromOpponent,
|
---|
273 | double myOfferedUtil, double time) throws Exception {
|
---|
274 | double P = Paccept(offeredUtilFromOpponent, time);
|
---|
275 | if (P > Math.random())
|
---|
276 | return true;
|
---|
277 | return false;
|
---|
278 | }
|
---|
279 |
|
---|
280 | /********************************************************************************************************************/
|
---|
281 |
|
---|
282 | private Action chooseOSRAction() {
|
---|
283 | Bid nextOSRBid = null;
|
---|
284 | try {
|
---|
285 | nextOSRBid = getOSRBid();
|
---|
286 | } catch (Exception e) {
|
---|
287 | System.out.println("Problem with received bid:" + e.getMessage()
|
---|
288 | + ". cancelling bidding");
|
---|
289 | }
|
---|
290 |
|
---|
291 | if (nextOSRBid == null)
|
---|
292 | return (new Accept(getAgentID(),
|
---|
293 | ((ActionWithBid) actionOfPartner).getBid()));
|
---|
294 |
|
---|
295 | return (new Offer(getAgentID(), nextOSRBid));
|
---|
296 | }
|
---|
297 |
|
---|
298 | /********************************************************************************************************************/
|
---|
299 | // @return a random bid with high enough utility value.
|
---|
300 | // @throws Exception if we can't compute the utility (eg no evaluators have
|
---|
301 | // been set)
|
---|
302 | // or when other evaluators than a DiscreteEvaluator are present in the util
|
---|
303 | // space.
|
---|
304 |
|
---|
305 | private Bid getOSRBid() throws Exception {
|
---|
306 | Bid bid = null;
|
---|
307 | HashMap<Integer, Value> val = new HashMap<Integer, Value>(); // pairs
|
---|
308 | // <issuenumber,chosen
|
---|
309 | // value
|
---|
310 | // string>
|
---|
311 |
|
---|
312 | if (all_osr_cuttofs) // using all the cutoffs for bidding
|
---|
313 | // if ( estimated_rounds_left(true) >= stack_aux.size() )
|
---|
314 | {
|
---|
315 | for (Value key : stack_hc.pop().keySet()) // pick only one issue !
|
---|
316 | {
|
---|
317 | val.put(utilitySpace.getDomain().getIssues().get(0).getNumber(),
|
---|
318 | key);
|
---|
319 | counter++;
|
---|
320 | break;
|
---|
321 | }
|
---|
322 |
|
---|
323 | System.out.println("\n\t t = " + timeline.getTime()
|
---|
324 | + "\n\t size = " + stack_hc.size()
|
---|
325 | + "\n\t getCurrentTime = " + timeline.getCurrentTime()
|
---|
326 | * 1000 + "\n\t getTotalTime = "
|
---|
327 | + timeline.getTotalTime() * 1000
|
---|
328 | + "\n\t estimate rounds left = "
|
---|
329 | + estimated_rounds_left(false));
|
---|
330 | } else // estimated_rounds_left(true) < stack_aux.size() => bidding from
|
---|
331 | // the optimal subset
|
---|
332 | {
|
---|
333 | for (Value key : stack_hc.get(800 + idx).keySet())
|
---|
334 | val.put(utilitySpace.getDomain().getIssues().get(0).getNumber(),
|
---|
335 | key);
|
---|
336 |
|
---|
337 | System.out
|
---|
338 | .println("###########################################################################################");
|
---|
339 | System.out.println("###### " + stack_aux.size()
|
---|
340 | + " rounds before deadline ##### erl = " + idx
|
---|
341 | + " ############");
|
---|
342 | System.out.println("###### val = " + val + " ############");
|
---|
343 | System.out
|
---|
344 | .println("###########################################################################################");
|
---|
345 |
|
---|
346 | idx++;
|
---|
347 | }
|
---|
348 | // If the deadline is approaching in next round
|
---|
349 |
|
---|
350 | if (unused) {
|
---|
351 | if (estimated_rounds_left(true) < 10) {
|
---|
352 | System.out
|
---|
353 | .println("###########################################################################################");
|
---|
354 | System.out
|
---|
355 | .println("###### Approaching deadline! ############################################################");
|
---|
356 | System.out
|
---|
357 | .println("###########################################################################################");
|
---|
358 |
|
---|
359 | if (true) {
|
---|
360 | for (Value key : stack_h.get(
|
---|
361 | stack_h.size() - estimated_rounds_left(true))
|
---|
362 | .keySet())
|
---|
363 | // for ( Value key : stack_h.get(0).keySet() )
|
---|
364 | val.put(utilitySpace.getDomain().getIssues().get(0)
|
---|
365 | .getNumber(), key);
|
---|
366 | } else // , jump to the last cutoff (best)
|
---|
367 | {
|
---|
368 | val.put(utilitySpace.getDomain().getIssues().get(0)
|
---|
369 | .getNumber(), (Value) max_values.get(index));
|
---|
370 | System.out.println(" >>>>> max_value[" + index + "] = "
|
---|
371 | + max_values.get(index));
|
---|
372 | index++;
|
---|
373 | }
|
---|
374 |
|
---|
375 | bid = new Bid(utilitySpace.getDomain(), val);
|
---|
376 | System.out.println(" >>>>> val = " + val + " \t utility = "
|
---|
377 | + getUtility(bid));
|
---|
378 |
|
---|
379 | System.out
|
---|
380 | .println("\n##############################################");
|
---|
381 |
|
---|
382 | System.out.println("\n");
|
---|
383 |
|
---|
384 | for (int k = 0; k < stack_h.size(); k++) {
|
---|
385 | System.out.print(" " + k + " => " + stack_h.get(k));
|
---|
386 | }
|
---|
387 |
|
---|
388 | System.out
|
---|
389 | .println("***************************************************************************");
|
---|
390 | System.out.println("\t d = " + d);
|
---|
391 | System.out
|
---|
392 | .println("***************************************************************************");
|
---|
393 |
|
---|
394 | System.out.println("\n");
|
---|
395 | // TODO
|
---|
396 |
|
---|
397 | }
|
---|
398 | }
|
---|
399 |
|
---|
400 | bid = new Bid(utilitySpace.getDomain(), val);
|
---|
401 |
|
---|
402 | System.out.println("###### offering bid = " + bid);
|
---|
403 |
|
---|
404 | return bid;
|
---|
405 | }
|
---|
406 |
|
---|
407 | /********************************************************************************************************************/
|
---|
408 | // This function determines the accept probability for an offer.
|
---|
409 | // At t=0 it will prefer high-utility offers.
|
---|
410 | // As t gets closer to 1, it will accept lower utility offers with
|
---|
411 | // increasing probability.
|
---|
412 | // it will never accept offers with utility 0.
|
---|
413 | // @param u is the utility
|
---|
414 | // @param t is the time as fraction of the total available time
|
---|
415 | // (t=0 at start, and t=1 at end time)
|
---|
416 | // @return the probability of an accept at time t
|
---|
417 | // @throws Exception if you use wrong values for u or t.
|
---|
418 |
|
---|
419 | double Paccept(double u, double t1) throws Exception {
|
---|
420 | double t = t1 * t1 * t1; // steeper increase when deadline approaches.
|
---|
421 | if (u < 0 || u > 1.05)
|
---|
422 | throw new Exception("utility " + u + " outside [0,1]");
|
---|
423 | // normalization may be slightly off, therefore we have a broad boundary
|
---|
424 | // up to 1.05
|
---|
425 | if (t < 0 || t > 1)
|
---|
426 | throw new Exception("time " + t + " outside [0,1]");
|
---|
427 | if (u > 1.)
|
---|
428 | u = 1;
|
---|
429 | if (t == 0.5)
|
---|
430 | return u;
|
---|
431 | return (u - 2. * u * t + 2. * (-1. + t + Math.sqrt(sq(-1. + t) + u
|
---|
432 | * (-1. + 2 * t))))
|
---|
433 | / (-1. + 2 * t);
|
---|
434 | }
|
---|
435 |
|
---|
436 | double sq(double x) {
|
---|
437 | return x * x;
|
---|
438 | }
|
---|
439 | }
|
---|
440 |
|
---|
441 | // End |
---|