source: src/main/java/parties/in4010/q12015/group2/Group2.java@ 84

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

Initial import : Genius 9.0.0
File size: 12.6 KB
Line 
1package parties.in4010.q12015.group2;
2
3import static parties.in4010.q12015.group2.edu.berkeley.nlp.lm.NgramLanguageModel.StaticMethods.getDistributionOverNextWords;
4import static parties.in4010.q12015.group2.edu.berkeley.nlp.lm.io.ArpaLmReader.END_SYMBOL;
5import static parties.in4010.q12015.group2.edu.berkeley.nlp.lm.io.ArpaLmReader.START_SYMBOL;
6import static parties.in4010.q12015.group2.edu.berkeley.nlp.lm.io.ArpaLmReader.UNK_SYMBOL;
7
8import java.io.File;
9import java.io.PrintWriter;
10import java.util.ArrayList;
11import java.util.Collection;
12import java.util.HashMap;
13import java.util.List;
14import java.util.Map;
15import java.util.Map.Entry;
16
17import agents.bayesianopponentmodel.BayesianOpponentModelScalable;
18import agents.bayesianopponentmodel.OpponentModel;
19import genius.core.AgentID;
20import genius.core.Bid;
21import genius.core.actions.Accept;
22import genius.core.actions.Action;
23import genius.core.actions.DefaultAction;
24import genius.core.actions.Offer;
25import genius.core.parties.AbstractNegotiationParty;
26import genius.core.parties.NegotiationInfo;
27import genius.core.utility.AdditiveUtilitySpace;
28import parties.in4010.q12015.group2.edu.berkeley.nlp.lm.ArrayEncodedProbBackoffLm;
29import parties.in4010.q12015.group2.edu.berkeley.nlp.lm.ConfigOptions;
30import parties.in4010.q12015.group2.edu.berkeley.nlp.lm.StringWordIndexer;
31import parties.in4010.q12015.group2.edu.berkeley.nlp.lm.io.LmReaders;
32
33/**
34 * Group2 is a class representing a software agent for automatic negotiation in
35 * Genius. The key technical insight in this agent is the application of
36 * statistical language models. We address the problem of predicting the next
37 * bid in the negotiation. Given a state of the negotiation, we predict the next
38 * bid that could be offered from some of the parties -- in a more general
39 * setting this could be the next n bids. Our main idea is to reduce the problem
40 * of bid prediction to a natural-language processing problem of predicting
41 * probabilities of sentences. We design a simple and scalable agent that stores
42 * sequences of bids during a negotiation process, and index these into a
43 * statistical language model. We then employ the language model to find the
44 * highest ranked sentences, and use them to predicted bid(s) during bidding and
45 * acceptance.
46 *
47 * @author Group2
48 * @since 1.0
49 *
50 */
51public class Group2 extends AbstractNegotiationParty {
52 private static final int TOP_K = 15;
53 private static final int LM_ORDER = 5;
54 private static final String LM_TXT = "lm.txt";
55 private static final String LM_ARPA = "lm.arpa";
56 private static final String LM_BINARY = "lm.binary";
57
58 private static final double ACCEPTANCE_TIME = 0.9d;
59 private static final double TRAINING_TIME = 0.5d;
60 private static final double ALPHA_COEFICIENT = 0.8d;
61
62 private static final int RANDOM_ITERATIONS = 100000;
63
64 private Bid maxBid;
65 private double alpha;
66 private Bid opponentBid;
67 private Bid upcommingBid;
68 private Map<String, List<String>> trainingBids;
69 private Map<String, OpponentModel> opponentsModels;
70 private Map<String, ArrayEncodedProbBackoffLm<String>> languageModels;
71
72 /**
73 * Initializes maxBid, alpha, opponentModels collections and trainingBids
74 * collection.
75 */
76 @Override
77 public void init(NegotiationInfo info) {
78 super.init(info);
79 try {
80 this.maxBid = utilitySpace.getMaxUtilityBid();
81 } catch (Exception e) {
82 throw new RuntimeException(e);
83 }
84 this.alpha = getUtility(maxBid) * ALPHA_COEFICIENT;
85 this.opponentsModels = new HashMap<String, OpponentModel>();
86 this.trainingBids = new HashMap<String, List<String>>();
87 this.languageModels = new HashMap<String, ArrayEncodedProbBackoffLm<String>>();
88 }
89
90 /**
91 * Informs the agent that the opponent just performed the action. Stores the
92 * opponent's action in order to use it when choosing an action. Further, it
93 * performs an opponent modeling according to the strategy described in the
94 * report.
95 */
96 @Override
97 public void receiveMessage(AgentID sender, Action arguments) {
98 super.receiveMessage(sender, arguments);
99 this.opponentBid = DefaultAction.getBidFromAction(arguments);
100 modelOpponent(sender, arguments);
101 }
102
103 /**
104 * The method asks to specify an action to send to the opponents. The method
105 * works as follows: if we are first to place a bid, we place a trade-off
106 * bid with a sufficient utility, otherwise, we determine whether to accept
107 * or not the bid, depending on the acceptance condition. Finally, it
108 * accepts or pose a new trade-off bid. It is essential that our bidding
109 * strategy takes a predicted opponents models into account.
110 */
111 @Override
112 public Action chooseAction(List<Class<? extends Action>> actions) {
113 this.upcommingBid = getTradeOffBid();
114 return isAcceptable() ? new Accept(getPartyId(), opponentBid) : new Offer(getPartyId(), this.upcommingBid);
115 }
116
117 /**
118 * The method implements the acceptance condition described in the report.
119 * Basically, AC_combi(T, alpha) = AC_next AND AC_time(T) OR AC_const(alpha)
120 *
121 * @return
122 */
123 private boolean isAcceptable() {
124 boolean aConst = getUtility(this.opponentBid) >= this.alpha;
125 boolean aNext = getUtility(this.opponentBid) >= getUtility(this.upcommingBid);
126 boolean aTime = timeline.getTime() >= ACCEPTANCE_TIME;
127 return aConst || aNext && aTime;
128 }
129
130 /**
131 * The method tries to build a statistical language model. Then it generates
132 * an upcoming bid based on the trade-off strategy described in the report.
133 * Here we employ the opponent modeling and bid prediction components. The
134 * isBetterThanOpponents(bid) method assures that the generated bid will
135 * have better utility than the estimated utilities of the opponents
136 * according to the opponent model. The method isSuitableForOpponents(bid)
137 * employs the statistical language model. The idea is that we offer bids
138 * which are suitable for our opponents -- our statistical language model
139 * predicts that the opponent will generate certain bid(s) with some
140 * probability.
141 *
142 * @return
143 */
144 private Bid getTradeOffBid() {
145 buildStatisticalLanguageModel();
146 Bid bestBid = null;
147 double bestUtility = 0.0D;
148 double bestDistance = 0.0D;
149 boolean ignoreSuitabilityCheck = false;
150 for (int j = 0; j < 2; j++) {
151 for (int i = 0; i < RANDOM_ITERATIONS; i++) {
152 Bid bid = utilitySpace.getDomain().getRandomBid(null);
153 double oldUtility = getUtility(this.upcommingBid);
154 double newUtility = getUtility(bid);
155 double distance = getHammingDistance(bid, this.opponentBid);
156 if (newUtility > oldUtility && distance <= bestDistance && newUtility > bestUtility
157 && isBetterThanOpponents(bid) && (ignoreSuitabilityCheck || isSuitableForOpponents(bid))) {
158 bestDistance = distance;
159 bestBid = bid;
160 bestUtility = getUtility(bestBid);
161 }
162 }
163 if (bestBid == null) {
164 ignoreSuitabilityCheck = true;
165 } else {
166 break;
167 }
168 }
169 return bestBid == null ? getRandomBid(this.alpha) : bestBid;
170 }
171
172 /**
173 * The method getRandomBid(this.alpha) generates a random bid with utility
174 * greater or equal than alpha. It is based on the well-known Random Walker
175 * strategy. It randomly jumps through the negotiation space, and it is run
176 * with break-off point, avoiding making offers below a certain utility. If
177 * it could not find a bid above a certain utility, the method returns the
178 * maximum utility bid.
179 *
180 * @param target
181 * @return
182 */
183 private Bid getRandomBid(double target) {
184 for (int i = 0; i < RANDOM_ITERATIONS; i++) {
185 Bid b = utilitySpace.getDomain().getRandomBid(null);
186 if (getUtility(b) >= target && isBetterThanOpponents(b)) {
187 return b;
188 }
189 }
190 return this.maxBid;
191 }
192
193 private double getHammingDistance(Bid myBid, Bid opponentBid) {
194 double dist = 0.0D;
195 for (int i = 1; i <= myBid.getIssues().size(); i++) {
196 try {
197 if (myBid.getValue(i).equals(opponentBid.getValue(i))) {
198 continue;
199 }
200 } catch (Exception e) {
201 ;
202 }
203 dist += 1.0D;
204 }
205 return dist;
206 }
207
208 private void modelOpponent(AgentID sender, Action arguments) {
209 if (sender == null)
210 return; // Wouter added
211 if (!this.opponentsModels.containsKey(sender.toString())) {
212 this.opponentsModels.put(sender.toString(),
213 new BayesianOpponentModelScalable((AdditiveUtilitySpace) utilitySpace));
214 }
215 if ((arguments instanceof Offer)) {
216 try {
217 ((OpponentModel) this.opponentsModels.get(sender.toString())).updateBeliefs(this.opponentBid);
218 } catch (Exception e) {
219 ;
220 }
221 }
222
223 if (!this.trainingBids.containsKey(sender.toString())) {
224 this.trainingBids.put(sender.toString(), new ArrayList<String>());
225 }
226 if ((arguments instanceof Offer)) {
227 this.trainingBids.get(sender.toString()).add(this.opponentBid.toString().replaceAll("\\s", ""));
228 }
229 }
230
231 private boolean isBetterThanOpponents(Bid myBid) {
232 for (OpponentModel model : this.opponentsModels.values()) {
233 try {
234 if (model.getExpectedUtility(myBid) >= getUtility(myBid)) {
235 return false;
236 }
237 } catch (Exception e) {
238 return true;
239 }
240 }
241 return true;
242 }
243
244 /**
245 * Trains the statistical language model. First, we check whether it is time
246 * for training. Then, we generate training sequences and store them in a
247 * predefined $.txt$ file. Finally, we employ the statistical language model
248 * framework. The result is trained probabilistic models for each opponent
249 * stored in binary files.
250 */
251 @SuppressWarnings({ "unchecked", "rawtypes" })
252 private void buildStatisticalLanguageModel() {
253 if (timeline.getTime() > TRAINING_TIME && this.languageModels.isEmpty()) {
254 for (Map.Entry<String, List<String>> entry : trainingBids.entrySet()) {
255 try {
256 String opponentId = entry.getKey();
257 List<String> opponentBids = entry.getValue();
258 PrintWriter writer = new PrintWriter(opponentId + LM_TXT, "UTF-8");
259 for (int i = 0; i < opponentBids.size(); i++) {
260 for (int j = i; j < Math.min(i + LM_ORDER, opponentBids.size()); j++) {
261 writer.print(opponentBids.get(j));
262 writer.print(" ");
263 }
264 writer.println(".");
265 }
266 writer.close();
267 List<String> files = new ArrayList<String>();
268 files.add(opponentId + LM_TXT);
269 StringWordIndexer wi = new StringWordIndexer();
270 wi.setStartSymbol(START_SYMBOL);
271 wi.setEndSymbol(END_SYMBOL);
272 wi.setUnkSymbol(UNK_SYMBOL);
273 LmReaders.createKneserNeyLmFromTextFiles(files, wi, LM_ORDER, new File(opponentId + LM_ARPA),
274 new ConfigOptions());
275 LmReaders.writeLmBinary(LmReaders.readArrayEncodedLmFromArpa(opponentId + LM_ARPA, true),
276 opponentId + LM_BINARY);
277 ArrayEncodedProbBackoffLm lm = (ArrayEncodedProbBackoffLm) LmReaders
278 .readLmBinary(opponentId + LM_BINARY);
279 this.languageModels.put(opponentId, lm);
280 } catch (Exception e) {
281 continue;
282 }
283 }
284 }
285 }
286
287 /**
288 * The prediction phase is encoded in the method predictNextBids(). It is a
289 * standard way of inference in statistical language model setting. For
290 * every opponent language model, we iterate over the distribution of the
291 * next words, sorted by decreasing count, and select the top k. Of course,
292 * we exclude the UNK, START, and END symbols from the prediction. As a
293 * result we return the intersection between the predictions for each
294 * opponent.
295 *
296 * @return
297 */
298 private List<String> predictNextBids() {
299 List<String> result = new ArrayList<String>();
300 if (!this.languageModels.isEmpty()) {
301 for (Map.Entry<String, List<String>> entry : trainingBids.entrySet()) {
302 try {
303 List<String> localResult = new ArrayList<String>();
304 String opponentId = entry.getKey();
305 List<String> opponentBids = entry.getValue();
306 Collection<Entry<String, Double>> dist = getDistributionOverNextWords(
307 this.languageModels.get(opponentId), opponentBids).getEntriesSortedByDecreasingCount();
308 for (Entry<String, Double> e : dist) {
309 if (localResult.size() == TOP_K) {
310 break;
311 } else if (UNK_SYMBOL.equals(e.getKey()) || START_SYMBOL.equals(e.getKey())
312 || END_SYMBOL.equals(e.getKey()) || ".".equals(e.getKey())) {
313 continue;
314 } else {
315 localResult.add(e.getKey());
316 }
317 }
318 if (result.isEmpty()) {
319 result.addAll(localResult);
320 } else {
321 result.retainAll(localResult);
322 }
323 } catch (Exception e) {
324 continue;
325 }
326 }
327 }
328 return result;
329 }
330
331 private boolean isSuitableForOpponents(Bid bid) {
332 List<String> predictedBids = predictNextBids();
333 return predictedBids.isEmpty() || predictedBids.contains(bid.toString().replaceAll("\\s", ""));
334 }
335
336 @Override
337 public String getDescription() {
338 return "in4010.q12015.group2";
339 }
340}
Note: See TracBrowser for help on using the repository browser.