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

Last change on this file since 126 was 126, checked in by Aron Hammond, 6 years ago

Added function to calculate opposition to MultiLateralAnalysis.java

Moved code to add RLBOA listeners to RLBOAUtils is misc package

Added input for strategyParameters to SessionPanel (gui)

!! close SessionInfo after tournament; this caused /tmp/ to fill up with GeniusData files

Our own package:

  • Added opponents and strategies that are mentioned in the report
  • Change class hierarchy, agents can now extend from RLBOAagentBilateral to inherit RL functionality.
  • States extend from AbstractState
File size: 12.3 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.