source: src/main/java/agents/anac/y2015/pokerface/PokerFace.java@ 345

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

Initial import : Genius 9.0.0
File size: 12.9 KB
Line 
1package agents.anac.y2015.pokerface;
2
3import java.math.BigInteger;
4import java.util.ArrayList;
5import java.util.List;
6import java.util.Map;
7import java.util.Map.Entry;
8import java.util.Random;
9
10import genius.core.AgentID;
11import genius.core.Bid;
12import genius.core.actions.Accept;
13import genius.core.actions.Action;
14import genius.core.actions.DefaultAction;
15import genius.core.actions.Offer;
16import genius.core.bidding.BidDetails;
17import genius.core.boaframework.SortedOutcomeSpace;
18import genius.core.issue.Issue;
19import genius.core.issue.Value;
20import genius.core.misc.Range;
21import genius.core.parties.AbstractNegotiationParty;
22import genius.core.parties.NegotiationInfo;
23import genius.core.timeline.ContinuousTimeline;
24import genius.core.utility.AdditiveUtilitySpace;
25import genius.core.utility.Evaluator;
26
27/**
28 * This is your negotiation party.
29 */
30public class PokerFace extends AbstractNegotiationParty {
31
32 /**
33 * Please keep this constructor. This is called by genius.
34 *
35 * @param utilitySpace
36 * Your utility space.
37 * @param deadlines
38 * The deadlines set for this negotiation.
39 * @param timeline
40 * Value counting from 0 (start) to 1 (end).
41 * @param randomSeed
42 * If you use any randomization, use this seed for it.
43 */
44 private ArrayList<Bid> high_utility_bids = null;
45 private OpponentBidLists opponent_bid_list;
46
47 private final double RANDOM_WALKER_TRESHOLD = 0.6;
48 private final double MINIMAL_WALKER_UTILITY = 0.85;
49
50 private final double CONCEDE_SPEED = (double) 1 / 4;
51 private final double CONCEDE_MINIMUM = 0.5;
52 private final double CONCEDE_TO = 0.5;
53 private Bid last_received_bid = null;
54 private Bid last_concede_bid = null;
55 private Bid final_bid = null;
56 private BigInteger current_step = BigInteger.valueOf(1);
57 private int first_to_offer = -1;
58 private double total_time = 0;
59 private double current_time = 0;
60
61 private int rounds = 0; // rounds seen so far
62 private double[] last_rounds_time; // array to store time of last rounds,
63 // used in moving average
64 private final int MA_SIZE = 10;
65 private double average_time = 0.001; // average time taken for a round (if
66 // time is continuous) to avoid
67 // infinity, initial non 0
68
69 private Random random;
70
71 @Override
72 public void init(NegotiationInfo info) {
73 // Make sure that this constructor calls it's parent.
74 super.init(info);
75
76 random = new Random(info.getRandomSeed());
77 opponent_bid_list = new OpponentBidLists(
78 (AdditiveUtilitySpace) utilitySpace, true);
79 total_time = timeline.getTotalTime();
80 last_rounds_time = new double[MA_SIZE];
81 }
82
83 /**
84 * Each round this method gets called and ask you to accept or offer. The
85 * first party in the first round is a bit different, it can only propose an
86 * offer.
87 *
88 * @param validActions
89 * Either a list containing both accept and offer or only offer.
90 * @return The chosen action.
91 */
92 @SuppressWarnings("rawtypes")
93 @Override
94 public Action chooseAction(List<Class<? extends Action>> validActions) {
95 // with 50% chance, counter offer
96 // if we are the first party, also offer.
97 double time_left, time_after_walker, temp;
98 // ensure time_left is in steps we can still take
99 if (timeline instanceof ContinuousTimeline) {
100 time_left = Math.floor(
101 (total_time - timeline.getCurrentTime()) / average_time);
102 time_after_walker = (total_time / average_time)
103 * (1.0 - RANDOM_WALKER_TRESHOLD);
104 temp = time_left / time_after_walker;
105 } else {
106 time_left = total_time - rounds - 1;
107 time_after_walker = ((total_time - 1)
108 * (1.0 - RANDOM_WALKER_TRESHOLD));
109 temp = (time_left - 1.0) / time_after_walker;
110 }
111 double threshold = CONCEDE_TO + Math.pow(temp, CONCEDE_SPEED) / 2;
112 double last_utility;
113 try {
114 last_utility = utilitySpace.getUtility(last_received_bid);
115 } catch (Exception e) {
116 last_utility = 1.0;
117 }
118 if (first_to_offer == -1) {
119 if (!validActions.contains(Accept.class)) {
120 first_to_offer = 1;
121 } else {
122 first_to_offer = 0;
123 }
124 }
125 if (!validActions.contains(Accept.class) || (last_utility < threshold
126 && (time_left > 1 || first_to_offer == 1))) {
127 if (((timeline instanceof ContinuousTimeline ? current_time
128 : rounds) / total_time) < RANDOM_WALKER_TRESHOLD) {
129 final_bid = randomWalker();
130 } else {
131 if ((int) time_left < 3) {
132 // Opponent is not conceding. Deadline has been reached.
133 // Let them taste a bit of their own medicine. (They have to
134 // accept!)
135 try {
136 final_bid = utilitySpace.getMaxUtilityBid();
137 } catch (Exception e) {
138 // fail safe
139 final_bid = randomWalker();
140 }
141 } else {
142 List<Object> senders = opponent_bid_list.getSenders();
143 List<Entry<Pair<Integer, Value>, Integer>> pair_frequency = opponent_bid_list
144 .getMostFrequentIssueValues(senders.get(0));
145 List<Entry<Pair<Integer, Value>, Double>> weighted_list = opponent_bid_list
146 .weightIssueValues(pair_frequency);
147 final_bid = concederBid(weighted_list);
148 }
149 }
150 updateTime();
151 return new Offer(getPartyId(), final_bid);
152
153 } else {
154 updateTime();
155 return new Accept(getPartyId(), last_received_bid);
156 }
157 }
158
159 /**
160 * All offers proposed by the other parties will be received as a message.
161 * You can use this information to your advantage, for example to predict
162 * their utility.
163 *
164 * @param sender
165 * The party that did the action.
166 * @param action
167 * The action that party did.
168 */
169 @Override
170 public void receiveMessage(AgentID sender, Action action) {
171 super.receiveMessage(sender, action);
172
173 // Here you can listen to other parties' messages
174 Bid bid = DefaultAction.getBidFromAction(action);
175 if (bid != null) {
176 opponent_bid_list.insertBid(sender, bid);
177 last_received_bid = bid;
178 }
179 }
180
181 private Bid concederBid(
182 List<Entry<Pair<Integer, Value>, Double>> ordered_pair) {
183 int actions_left;
184 int actions_after_walker;
185 if (timeline instanceof ContinuousTimeline) {
186 actions_left = (int) Math
187 .round((total_time - current_time) / average_time);
188 actions_after_walker = (int) ((total_time / average_time)
189 * (1.0 - RANDOM_WALKER_TRESHOLD));
190 } else {
191 actions_left = (int) total_time - rounds - 1;
192 actions_after_walker = (int) (total_time
193 * (1.0 - RANDOM_WALKER_TRESHOLD));
194 }
195 Bid average_bid = randomWalker();
196 // calculate how far in the pairset the best bid occurred
197 List<Issue> issues = average_bid.getIssues();
198 Map<Integer, Value> values = average_bid.getValues();
199 List<Pair<Integer, Value>> issue_pairs = new ArrayList<Pair<Integer, Value>>();
200 for (int i = 0; i < values.size(); i++) {
201 Integer issue_id = issues.get(i).getNumber();
202 Value value_id = values.get(i + 1);
203 issue_pairs.add(new Pair<Integer, Value>(issue_id, value_id));
204 }
205 int max_index = 0;
206 for (int i = 0; i < issue_pairs.size(); i++) {
207 int index = -1;
208 for (int j = 0; j < ordered_pair.size(); j++) {
209 Pair<Integer, Value> pair = ordered_pair.get(j).getKey();
210 if (pair.equals(issue_pairs.get(i))) {
211 index = j;
212 break;
213 }
214 }
215 if (index != -1 && index > max_index) {
216 max_index = index;
217 }
218 }
219 BigInteger total_steps = BigInteger.valueOf(2).pow(max_index);
220 BigInteger steps_per_action = total_steps
221 .divide(BigInteger.valueOf(actions_after_walker));
222 BigInteger previous_step = current_step;
223 current_step = steps_per_action.multiply(
224 BigInteger.valueOf(actions_after_walker - actions_left));
225
226 Bid concede_bid;
227
228 try {
229 concede_bid = utilitySpace.getMaxUtilityBid();
230 if (last_concede_bid == null) {
231 last_concede_bid = concede_bid;
232 }
233 } catch (Exception e) {
234 // fail safe
235 concede_bid = average_bid;
236 }
237
238 // binary concede bid
239 concede_bid = generateConcedeBid(current_step, concede_bid,
240 ordered_pair, max_index);
241 for (BigInteger i = previous_step; i.compareTo(
242 current_step) == -1; i = i.add(BigInteger.valueOf(1))) {
243 Bid new_bid = new Bid(concede_bid);
244 new_bid = generateConcedeBid(i, new_bid, ordered_pair, max_index);
245 try {
246 if (utilitySpace.getUtility(new_bid) > utilitySpace
247 .getUtility(concede_bid)) {
248 // System.out.println("===\n new_bid:
249 // "+utilitySpace.getUtility(new_bid)+" concede_bid:
250 // "+utilitySpace.getUtility(concede_bid));
251 concede_bid = new_bid;
252 }
253 } catch (Exception e) {
254 }
255 }
256 final_bid = concede_bid;
257 try {
258
259 if (utilitySpace.getUtility(final_bid) > CONCEDE_MINIMUM) {
260 // System.out.println("Conceded,
261 // Utility:"+utilitySpace.getUtility(concede_bid)+" and
262 // "+actions_left+" steps to go.");
263 return final_bid;
264 } else {
265 // System.out.println("Average Bid,
266 // Utility:"+utilitySpace.getUtility(average_bid)+" and
267 // "+actions_left+" steps to go.");
268 return average_bid;
269 }
270 } catch (Exception e) {
271 return average_bid;
272 }
273 }
274
275 private Bid generateConcedeBid(BigInteger step, Bid bid,
276 List<Entry<Pair<Integer, Value>, Double>> ordered_pair,
277 int issue_count) {
278 for (int i = 0; i < issue_count; i++) {
279 // binary split index to steps to include or not (max_index-bits
280 // number)
281 BigInteger bit = BigInteger.valueOf(2).pow(i);
282 if (step.and(bit).equals(bit)) {
283 Pair<Integer, Value> pair = ordered_pair.get(i).getKey();
284 int issue = pair.getInteger();
285 Value value = pair.getValue();
286 bid = bid.putValue(issue, value);
287 }
288 }
289 return bid;
290 }
291
292 private Bid randomWalker() {
293 List<Bid> bids = getHighUtilityBids(MINIMAL_WALKER_UTILITY);
294 double rnd = random.nextDouble();
295 double[] W = getWeights(bids);
296 int index = 0;
297 double sum = 0;
298 for (int i = 0; i < W.length; i++) { // Sum W until bigger then rnd
299 index = i;
300 sum += W[i];
301 if (sum > rnd) {
302 break;
303 }
304 }
305 // System.out.println("Random bid: "+bids.get(index).toString());
306 return bids.get(index);
307 }
308
309 private List<Bid> getHighUtilityBids(double minimal_utility) {
310 if (high_utility_bids == null) { // singleton
311 high_utility_bids = new ArrayList<Bid>();
312 SortedOutcomeSpace sorted_outcome = new SortedOutcomeSpace(
313 utilitySpace);
314 Range r = new Range(minimal_utility, 1.0);
315 List<BidDetails> bid_list = sorted_outcome.getBidsinRange(r);
316 for (int i = 0; i < bid_list.size(); i++) {
317 high_utility_bids.add(bid_list.get(i).getBid());
318 }
319 }
320 return high_utility_bids;
321 }
322
323 private double[] getWeights(List<Bid> high_bids_list) {
324 int issue_length = high_bids_list.get(0).getIssues().size();
325 int datalength = high_bids_list.size();
326 // get mean values of the issues
327 double[] mean = new double[issue_length];
328 for (int i = 0; i < datalength; i++) {
329 double[] v = getIssueValues(high_bids_list.get(i));
330 for (int j = 0; j < issue_length; j++) {
331 mean[j] += v[j];
332 }
333 }
334 // get variance and distance
335 double[][] dist = new double[datalength][issue_length];
336 double[] sum = new double[issue_length];
337 double[] sum_sq = new double[issue_length];
338 for (int i = 0; i < datalength; i++) {
339 double[] v = getIssueValues(high_bids_list.get(i));
340 for (int j = 0; j < issue_length; j++) {
341 dist[i][j] = Math.abs(v[j] - mean[j]);
342 sum[j] += dist[i][j];
343 sum_sq[j] += sum[j] * sum[j];
344 }
345 }
346 double[] var = new double[issue_length];
347 double sum_var = 0.0;
348 for (int i = 0; i < issue_length; i++) {
349 var[i] = (sum_sq[i] - (sum[i] * sum[i] / datalength))
350 / (datalength - 1);
351 sum_var += var[i];
352 }
353 // normalize variance and distance
354 for (int i = 0; i < datalength; i++) {
355 for (int j = 0; j < issue_length; j++) {
356 dist[i][j] = dist[i][j] / sum[j];
357 }
358 }
359 for (int i = 0; i < issue_length; i++) {
360 var[i] = var[i] / sum_var;
361 }
362
363 // calculate weights for every sample
364 double[] W = new double[datalength];
365 for (int i = 0; i < datalength; i++) {
366 double sample_sum = 0.0;
367 for (int j = 0; j < issue_length; j++) {
368 sample_sum += dist[i][j] * var[j];
369 }
370 W[i] = sample_sum;
371 }
372 return W;
373 }
374
375 private double[] getIssueValues(Bid b) {
376 int size = b.getIssues().size();
377 double[] w = new double[size];
378 for (int j = 0; j < size; j++) {
379 Issue issue = b.getIssues().get(j);
380 double eval;
381 try {
382 Evaluator evaluator = ((AdditiveUtilitySpace) utilitySpace)
383 .getEvaluator(issue.getNumber());
384 eval = evaluator.getWeight() * evaluator.getEvaluation(
385 (AdditiveUtilitySpace) utilitySpace, b,
386 issue.getNumber());
387 } catch (Exception e) {
388 eval = 0.0;
389 }
390 w[j] = eval;
391 }
392 return w;
393 }
394
395 // manage updating time variables
396 private void updateTime() {
397 rounds++;
398 // with continuous time it is more involved;
399 // we store the average time taken per round to estimate time remaining
400 // using an moving average prevents averaging over the full timeline
401 // where
402 // different tactics might be used with different time complexity
403 if (timeline instanceof ContinuousTimeline) {
404 average_time -= last_rounds_time[rounds % MA_SIZE] / MA_SIZE;
405 last_rounds_time[rounds
406 % MA_SIZE] = (timeline.getCurrentTime() - current_time)
407 / rounds;
408 average_time += last_rounds_time[rounds % MA_SIZE] / MA_SIZE;
409 current_time = timeline.getCurrentTime();
410 }
411 }
412
413 @Override
414 public String getDescription() {
415 return "ANAC2015";
416 }
417
418}
Note: See TracBrowser for help on using the repository browser.