001 /*
002 * JMiniMax.java
003 *
004 * Created on 14. März 2004, 14:47
005 */
006
007 package MiniMax;
008
009 /**
010 * Iteratives, näherungsweises Verfahren zur Bestimmung des Werts eines
011 * Zweipersonen-Spiels nach dem MiniMax-Prinzip,
012 * aus:
013 * Paragraph 6, in: Wentzel, J.S. (1976); Elemente der Spieltheorie,
014 * Verlag Harri Deutsch, Frankfurt.
015 *
016 * @author Florian Hiemeyer
017 * @version 1.00
018 */
019 public class JMiniMax {
020
021 /** SpielMatrix, in Integerform transformiert. */
022 private int[][] game;
023
024 /** Zeilenzahl in game */
025 private int rows;
026
027 /** Spaltenzahl in game */
028 private int cols;
029
030 /** Kleinster Wert des Spiels */
031 private int alpha;
032
033 /** Größter Wert des Spiels */
034 private int beta;
035
036 /** optimale gemischte Strategie von Spieler A */
037 private double[] mixStratA;
038
039 /** optimale gemischte Strategie von Spieler B */
040 private double[] mixStratB;
041
042 /** Schätzer für den Wert des Spiels */
043 private double nuEst;
044
045 /** ist ein Exakter Wert des Spiels direkt ermittelbar? */
046 private boolean exactNu = false;
047
048 /** Maximale Iterationszahl */
049 private int maxIter = 18;
050
051 /** Abbruchgenauigkeit der Schätzung für den Wert des Spiels */
052 private double nuEps = 0.0000001;
053
054 /** Konstruktor, benutzerdefinierte Genauigkeit */
055 public JMiniMax( int[][] _game, double eps, int maxIt ) {
056 nuEps = eps;
057 maxIter = maxIt;
058 if ( _game == null )
059 System.out.println("Error! Invalid Game!");
060
061 game = cleanGame(_game);
062
063 values();
064
065 }
066
067 /** Konstruktor, nutze Voreinstellungen zur Genauigkeit */
068 public JMiniMax( int[][] _game ) {
069 if ( _game == null )
070 System.out.println("Error! Invalid Game!");
071
072 game = cleanGame(_game);
073
074 values();
075 }
076
077
078 /** Ermittele Wert des Spiels und optimale Strategien für die Spieler (näherungsweise) */
079 public void iterate() {
080
081 System.out.println("Kein Sattelpunkt -> Iterationsverfahren; \"iterate()\":");
082 // Variablen und Klassen-Attribute initialisieren
083 int iter = 0;
084 double nuMin = Integer.MIN_VALUE, nuMax = Integer.MAX_VALUE;
085 nuEst = 0.;
086 int tempStratA = -1, tempStratB = -1;
087 int[] tempPayVectA = new int[rows];
088 int[] tempPayVectB = new int[cols];
089 mixStratA = new double[rows];
090 mixStratB = new double[cols];
091
092 // Erste Strategie von A (im ersten Spiel!) -> Zufällig auswählen!
093 tempStratA = (int)Math.floor(Math.random()*rows);
094
095 /** solange die maximale Iterationszahl nicht über- bzw. die gewünschte Genauigkeit
096 * nicht unterschritten ist -> neues Spiel mit der bis dato fälligen Auszahlung
097 * durchführen!
098 */
099 while( (iter < maxIter) && (nuMax-nuMin > nuEps) ) {
100 /** Addiere elementweise die Auswirkungen der aktuellen Strategie A auf die bisherigen
101 * Auszahlungen für B
102 * Bestimme dabei auch tempStratB, die für B bei Betrachtung des bisherigen Verlaufs der
103 * Spiele ideale Strategie.
104 */
105 int min = Integer.MAX_VALUE;
106 for(int j = 0; j<cols;j++) {
107 int temp = tempPayVectB[j] + game[tempStratA][j];
108 if( temp < min ) {
109 min = temp;
110 tempStratB = j;
111 }
112 tempPayVectB[j] = temp;
113 }
114
115 // Jetzt die bisher gewählte Anzahl der Strategie "tempStratA" und
116 // "tempStratB" um eins erhöhen.
117 mixStratA[tempStratA]++;
118 mixStratB[tempStratB]++;
119
120 /**
121 System.out.print(( iter+1 )+" | "+ (tempStratA+1)+" |");
122 for(int j=0;j<cols;j++)
123 System.out.print(" "+tempPayVectB[j]+" |");
124 System.out.print("| "+ (tempStratB+1)+" |");
125 */
126
127 /** Das gleiche für Strategie B */
128 int max = Integer.MIN_VALUE;
129 for(int i = 0; i<rows;i++) {
130 int temp = tempPayVectA[i] + game[i][tempStratB];
131 if( temp > max ) {
132 max = temp;
133 // neue Strategie für A
134 tempStratA = i;
135 }
136 tempPayVectA[i] = temp;
137 }
138
139 /**
140 for(int i=0;i<rows;i++)
141 System.out.print(" "+tempPayVectA[i]+" |");
142 */
143
144 // Bestimmung des minimalen und maximalen nu-Werts
145 nuMin = (double)min/(iter+1);
146 nuMax = (double)max/(iter+1);
147
148 // Berechnung des mittleren nu-Werts als Schätzer.
149 nuEst = (nuMin+nuMax)/2;
150
151 /** System.out.println(" "+nuEst); */
152 // Iterationszahl um eins erhöhen.
153 iter++;
154 }
155 // aus den _Anzahlen_ der gewählten Strategien
156 // die relativen Häufigkeiten berechnen
157 for(int i=0;i<rows;i++)
158 mixStratA[i] /=iter;
159 for(int j=0;j<cols;j++)
160 mixStratB[j] /=iter;
161 System.out.println("Abbruch nach "+iter+" Iterationen");
162 System.out.println("Schätzer für den Wert des Spiels: "+nuEst);
163 System.out.println("Unterschied bei Abbruch: "+(nuMax-nuMin));
164 System.out.println();
165 }
166
167 /**
168 * Statische Methode, um eine Spielmatrix auszugeben
169 */
170 public static void showGame(int[][] _game,String displaytext) {
171 // Show Game + Message
172 System.out.println(displaytext);
173 for (int i = 0; i<_game.length;i++) {
174 for (int j = 0;j<_game[0].length;j++) {
175 System.out.print("| "+_game[i][j]+" ");
176 }
177 System.out.println("|");
178 }
179 System.out.println();
180 }
181 /**
182 * Entferne unzulässige und doppelte Strategien,
183 * statische Methode
184 */
185 public static int[][] cleanGame(int[][] _game) {
186
187 System.out.println("Zeilen-/Spaltenkontrolle; \"cleanGame()\":");
188 showGame(_game,"Vorher:");
189
190 boolean[] remRows = new boolean[_game.length];
191 boolean[] remCols = new boolean[_game[0].length];
192 /** Zunächst Zeilen des Spiels mit jeder Zeile
193 * (außer gleichen und bereits als ungünstigen gekennzeichneten)
194 * spaltenweise vergleichen, wenn nicht ungünstig -> nicht als
195 * ungünstig markieren.
196 * Die ungünstigen Zeilen werden in remRows[] mit "true" gespeichert.
197 */
198 for(int k = 0;k<_game.length;k++) {
199 if( remRows[k] )
200 continue;
201 for(int i = 0;i<_game.length;i++) {
202 if ( ( i == k) || remRows[i] )
203 continue;
204 boolean rem = true;
205 for(int j = 0;j<_game[0].length;j++) {
206 if (_game[i][j] > _game[k][j]) {
207 rem=false;
208 break;
209 }
210 }
211 remRows[i]=rem;
212 }
213 }
214
215 // Kontrolle in den Spalten (siehe Zeilenkontrolle!)
216 for(int k = 0;k<_game[0].length;k++) {
217 if( remCols[k] )
218 continue;
219 for(int j = 0;j<_game[0].length;j++) {
220 if ( (k == j) || remCols[j] )
221 continue;
222 boolean rem = true;
223 for(int i = 0;i<_game.length;i++) {
224 if (_game[i][j] < _game[i][k]) {
225 rem=false;
226 break;
227 }
228 }
229 remCols[j]=rem;
230 }
231 }
232
233 /** Neue Zeilen und Spaltenlänge des Spiels bestimmen, und
234 * Veränderungen am Spiel ausgeben.
235 */
236 int newRows = 0;
237 for(int i = 0;i<remRows.length;i++) {
238 if( !remRows[i] )
239 newRows++;
240 else
241 System.out.println((i+1)+". Zeile entfernt weil unzulässig oder doppelt!");
242 }
243
244 int newCols = 0;
245 for(int j = 0; j<remCols.length;j++) {
246 if( !remCols[j] )
247 newCols++;
248 else
249 System.out.println((j+1)+". Spalte entfernt weil unzulässig oder doppelt!");
250 }
251
252 // Neues Spiel in passenden Dimensionen initialisieren
253 int[][] retGame = new int[newRows][newCols];
254
255 /** Die neue Spielmatrix mit allen noch "legitimen" Aktionen bzw. Zeilen und Spalten
256 * auffüllen
257 */
258 for (int i = 0, row = 0;i<remRows.length;i++) {
259 if ( remRows[i] )
260 continue;
261 for (int j = 0, col = 0;j<remCols.length;j++) {
262 if ( remCols[j] )
263 continue;
264 retGame[row][col] = _game[i][j];
265 col++;
266 }
267 row++;
268 }
269
270 // Spiel erneut als Ausgabe präsentieren
271 showGame(retGame,"Nachher:");
272
273 return retGame;
274 }
275
276 /** Berechne den kleinsten und den größten Wert
277 * des Spiels
278 */
279 public void values() {
280 System.out.println("Besetzung der Werte, Analyse auf Sattelpunkt; \"values()\":");
281 /** Bestimme Dimensionen von game */
282 rows = game.length;
283 cols = game[0].length;
284
285 if(rows == 0 || cols == 0 )
286 System.out.println("Error! Invalid Game!");
287
288 /** kleinster Wert (alpha) */
289 alpha = Integer.MIN_VALUE;
290 int alphaStrat = -1;
291 for(int i=0;i<rows;i++) {
292 int alphaMin = Integer.MAX_VALUE;
293 for(int j=0;j<cols;j++) {
294 // Minimum über alle Spalten (für Zeile i) finden
295 int temp = game[i][j];
296 if( temp < alphaMin )
297 alphaMin = temp;
298 }
299 if (alphaMin > alpha ) {
300 // Maximum über alle Zeilen finden
301 alpha = alphaMin;
302 alphaStrat = i;
303 }
304 }
305
306 /** größter Wert (beta) */
307 beta = Integer.MAX_VALUE;
308 int betaStrat = -1;
309 for(int j=0;j<cols;j++) {
310 int betaMax = Integer.MIN_VALUE;
311 for(int i=0;i<rows;i++) {
312 // Maximum über alle Zeilen (für Spalte j) finden
313 int temp = game[i][j];
314 if( temp > betaMax ) {
315 betaMax = temp;
316 }
317 }
318 if (betaMax < beta ) {
319 // Minimum über alle Spalten finden
320 beta = betaMax;
321 betaStrat = j;
322 }
323 }
324
325 System.out.println("Alpha: "+alpha);
326 System.out.println("Beta : "+beta);
327
328
329 if(alpha == beta)
330 exactNu = true;
331
332 System.out.println("Dim: "+rows+":"+cols);
333
334 if( exactNu ) {
335 System.out.println("Sattelpunkt gefunden!");
336 nuEst = alpha;
337 mixStratA = new double[rows];
338 mixStratA[alphaStrat] = 1;
339 mixStratB = new double[cols];
340 mixStratB[betaStrat]++;
341 } else
342 iterate();
343
344 System.out.println("Gemischte Strategie für A: ");
345 for(int i=0;i<rows;i++) {
346 System.out.println( (i+1)+": "+mixStratA[i]);
347 }
348 System.out.println();
349
350 System.out.println("Gemischte Strategie für B: ");
351 for(int j=0;j<cols;j++) {
352 System.out.println( (j+1)+": "+mixStratB[j]);
353 }
354 System.out.println("----- ENDE DER ANALYSE ------");
355 System.out.println();
356
357 }
358 /**
359 * @param args the command line arguments
360 */
361 public static void main(String[] args) {
362
363 // Beispielmatrix aus §6
364 int[][] dreimaldrei = new int[3][3];
365 dreimaldrei[0][0] = 8;
366 dreimaldrei[0][1] = 2;
367 dreimaldrei[0][2] = 4;
368 dreimaldrei[1][0] = 4;
369 dreimaldrei[1][1] = 5;
370 dreimaldrei[1][2] = 6;
371 dreimaldrei[2][0] = 1;
372 dreimaldrei[2][1] = 7;
373 dreimaldrei[2][2] = 3;
374
375 // Mit 10 multiplizierte Matrix von S. 18 (Sattelpunkt!)
376 int[][] viermalvier = new int[4][4];
377 viermalvier[0][0] = 4;
378 viermalvier[0][1] = 5;
379 viermalvier[0][2] = 9;
380 viermalvier[0][3] = 3;
381
382 viermalvier[1][0] = 8;
383 viermalvier[1][1] = 4;
384 viermalvier[1][2] = 3;
385 viermalvier[1][3] = 7;
386
387 viermalvier[2][0] = 7;
388 viermalvier[2][1] = 6;
389 viermalvier[2][2] = 8;
390 viermalvier[2][3] = 9;
391
392 viermalvier[3][0] = 7;
393 viermalvier[3][1] = 2;
394 viermalvier[3][2] = 4;
395 viermalvier[3][3] = 6;
396
397
398 //5-mal-fünf Matrix (cleanGame-Test)
399 int[][] fuenfmalfuenf = new int[5][5];
400 fuenfmalfuenf[0][0] = 4;
401 fuenfmalfuenf[0][1] = 5;
402 fuenfmalfuenf[0][2] = 9;
403 fuenfmalfuenf[0][3] = 3;
404 fuenfmalfuenf[0][4] = 10;
405
406 fuenfmalfuenf[1][0] = 8;
407 fuenfmalfuenf[1][1] = 4;
408 fuenfmalfuenf[1][2] = 3;
409 fuenfmalfuenf[1][3] = 7;
410 fuenfmalfuenf[1][4] = 20;
411
412 fuenfmalfuenf[2][0] = 7;
413 fuenfmalfuenf[2][1] = 6;
414 fuenfmalfuenf[2][2] = 8;
415 fuenfmalfuenf[2][3] = 9;
416 fuenfmalfuenf[2][4] = 19;
417
418 fuenfmalfuenf[3][0] = 7;
419 fuenfmalfuenf[3][1] = 2;
420 fuenfmalfuenf[3][2] = 4;
421 fuenfmalfuenf[3][3] = 6;
422 fuenfmalfuenf[3][4] = 19;
423
424 fuenfmalfuenf[4][0] = 7;
425 fuenfmalfuenf[4][1] = 2;
426 fuenfmalfuenf[4][2] = 4;
427 fuenfmalfuenf[4][3] = 6;
428 fuenfmalfuenf[4][4] = 40;
429
430 // Testet "Cleaning (und Sattelpunkt)"
431 JMiniMax cleanTest = new JMiniMax(fuenfmalfuenf);
432
433 // Testet "iteratives Approximieren"
434 JMiniMax itTest = new JMiniMax(dreimaldrei);
435 }
436
437 }