schiebe.java

   1 /* Schiebespiel - effectively computes solution for a one player board game
   2  * Copyright (C) 2007  Dirk Ribbroch / Martin Drohmann
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation; either version 2 of the License, or
   7  * (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  17  */
  18
  19 import java.util.*;
  20
  21 class schiebe {
  22     private final int ALGO_TIEFENSUCHE    = 0;
  23     private final int ALGO_ASTERN_SIMPEL  = 1;
  24     private static Transitions trs = new Transitions();
  25     private static Knoten start    = new Knoten();
  26     private static Knoten start_final = new Knoten();
  27     private static Knoten ziel     = new Knoten();
  28     private static Knoten ziel_final = new Knoten();
  29     private static int beste_tiefe = 32786;
  30
  31     public static void main(String[] argv) {
  32         // finale Start Konfiguration
  33                 start_final.set_field(0,3,Knoten.zweier_links);
  34         start_final.set_field(1,3,Knoten.zweier_rechts);
  35                 start_final.set_field(2,3,Knoten.zweier_links);
  36                 start_final.set_field(3,3,Knoten.zweier_rechts);
  37                 start_final.set_field(4,3,Knoten.einer);
  38
  39         start_final.set_field(0,2,Knoten.vierer_lo);
  40         start_final.set_field(1,2,Knoten.vierer_ro);
  41                 start_final.set_field(2,2,Knoten.zweier_oben);
  42                 start_final.set_field(3,2,Knoten.einer);
  43                 start_final.set_field(4,2,Knoten.leer);
  44
  45         start_final.set_field(0,1,Knoten.vierer_lu);
  46         start_final.set_field(1,1,Knoten.vierer_ru);
  47                 start_final.set_field(2,1,Knoten.zweier_unten);
  48                 start_final.set_field(3,1,Knoten.einer);
  49                 start_final.set_field(4,1,Knoten.leer);
  50
  51         start_final.set_field(0,0,Knoten.zweier_links);
  52                 start_final.set_field(1,0,Knoten.zweier_rechts);
  53                 start_final.set_field(2,0,Knoten.zweier_links);
  54                 start_final.set_field(3,0,Knoten.zweier_rechts);
  55                 start_final.set_field(4,0,Knoten.einer);
  56         start_final.set_leere(0, 4, 2);
  57         start_final.set_leere(1, 4, 1);
  58         start_final.set_leere(2, -1,-1);
  59         start_final.set_leere(3, -1,-1);
  60         //Start Konfiguration
  61         start.set_field(0,0,Knoten.zweier_links);
  62         start.set_field(1,0,Knoten.zweier_rechts);
  63         start.set_field(2,0,Knoten.zweier_links);
  64         start.set_field(3,0,Knoten.zweier_rechts);
  65         start.set_field(4,0,Knoten.einer);
  66         start.set_field(0,3,Knoten.zweier_links);
  67         start.set_field(1,3,Knoten.zweier_rechts);
  68         start.set_field(2,3,Knoten.zweier_links);
  69         start.set_field(3,3,Knoten.zweier_rechts);
  70         start.set_field(4,3,Knoten.einer);
  71         start.set_field(0,1,Knoten.vierer_lu);
  72         start.set_field(1,1,Knoten.vierer_ru);
  73         start.set_field(2,1,Knoten.zweier_unten);
  74         start.set_field(3,1,Knoten.einer);
  75         start.set_field(4,1,Knoten.leer);
  76         start.set_field(0,2,Knoten.vierer_lo);
  77         start.set_field(1,2,Knoten.vierer_ro);
  78         start.set_field(2,2,Knoten.zweier_oben);
  79         start.set_field(3,2,Knoten.einer);
  80         start.set_field(4,2,Knoten.leer);
  81         start.set_leere(0, 4, 2);
  82         start.set_leere(1, 4, 1);
  83         start.set_leere(2, -1,-1);
  84         start.set_leere(3, -1,-1);
  85         // Ziel Konfiguration
  86         ziel.set_field(0,3,Knoten.zweier_links);
  87         ziel.set_field(1,3,Knoten.zweier_rechts);
  88         ziel.set_field(2,3,Knoten.leer);
  89         ziel.set_field(3,3,Knoten.leer);
  90         ziel.set_field(4,3,Knoten.zweier_oben);
  91
  92         ziel.set_field(0,2,Knoten.vierer_ro);
  93         ziel.set_field(1,2,Knoten.leer);
  94         ziel.set_field(2,2,Knoten.zweier_links);
  95         ziel.set_field(3,2,Knoten.zweier_rechts);
  96         ziel.set_field(4,2,Knoten.zweier_unten);
  97
  98         ziel.set_field(0,1,Knoten.vierer_ru);
  99         ziel.set_field(1,1,Knoten.leer);
 100         ziel.set_field(2,0,Knoten.einer);
 101         ziel.set_field(3,0,Knoten.einer);
 102         ziel.set_field(4,1,Knoten.zweier_rechts);
 103
 104         ziel.set_field(0,0,Knoten.zweier_links);
 105         ziel.set_field(1,0,Knoten.zweier_rechts);
 106         ziel.set_field(2,1,Knoten.einer);
 107         ziel.set_field(3,1,Knoten.zweier_links);
 108         ziel.set_field(4,0,Knoten.einer);
 109         // Unser eigentliches Ziel für das das ganze Programm existiert
 110         ziel_final.set_field(0,3,Knoten.zweier_links);
 111         ziel_final.set_field(1,3,Knoten.zweier_rechts);
 112         ziel_final.set_field(2,3,Knoten.zweier_oben);
 113         ziel_final.set_field(3,3,Knoten.einer);
 114         ziel_final.set_field(4,3,Knoten.einer);
 115
 116         ziel_final.set_field(0,2,Knoten.zweier_links);
 117         ziel_final.set_field(1,2,Knoten.zweier_rechts);
 118         ziel_final.set_field(2,2,Knoten.zweier_unten);
 119         ziel_final.set_field(3,2,Knoten.vierer_lo);
 120         ziel_final.set_field(4,2,Knoten.vierer_ro);
 121
 122         ziel_final.set_field(0,1,Knoten.zweier_links);
 123         ziel_final.set_field(1,1,Knoten.zweier_rechts);
 124         ziel_final.set_field(2,1,Knoten.einer);
 125         ziel_final.set_field(3,1,Knoten.vierer_lu);
 126         ziel_final.set_field(4,1,Knoten.vierer_ru);
 127
 128         ziel_final.set_field(0,0,Knoten.zweier_links);
 129         ziel_final.set_field(1,0,Knoten.zweier_rechts);
 130         ziel_final.set_field(2,0,Knoten.einer);
 131         ziel_final.set_field(3,0,Knoten.leer);
 132         ziel_final.set_field(4,0,Knoten.leer);
 133
 134         Knoten.set_start(load.loadKnoten("start"));
 135         Knoten.set_ziel(load.loadKnoten("ziel"));
 136
 137                 /* Hiermit beginnen wir */
 138                 System.out.println("Hiermit beginnen wir: \n" + Knoten.getStart().toString());
 139         /* Dies ist das Ziel */
 140         System.out.println("Das ist das Ziel:\n" + Knoten.getZiel().toString());
 141         Knoten.setHeuristikTyp(Knoten.HEURISTIK_LUFT);
 142         Knoten.getStart().computeHeuristik();
 143         System.out.println("Luftlinie: " + Knoten.getStart().get_heuristik());
 144         System.out.println("");
 145
 146         //System.out.println(argv.length);
 147         if( argv.length > 0) {
 148             if( argv[0].equals("adastern") ) {
 149                 adastern();
 150             } else if( argv[0].equals("asternsimpel") ) {
 151                 asternsimpel();
 152             } else if( argv[0].equals("mincut") ) {
 153                 mincut();
 154             } else if (argv[0].equals("dfs") ) {
 155                 Knoten.setHeuristikTyp(Knoten.HEURISTIK_SIMPEL);
 156                 dfs(Knoten.getStart());
 157            } else if (argv[0].equals("schiebe4")) {
 158                 schiebe4();
 159                 }
 160                         else System.out.println("Falsche Optionen angegeben.");
 161         } else { /* Default: */
 162             asternluft(30);
 163         }
 164     }
 165       /**
 166      * Überprüft, ob das Ziel gefunden wurde und gibt in dem Fall den Weg aus
 167      */
 168     private static LinkedList<Knoten> testZiel(LinkedList<Knoten> expandListe, boolean systemout)
 169     {
 170         LinkedList<Knoten> pfad = new LinkedList<Knoten>();
 171         for (Knoten l : expandListe) {
 172             if (l.is( Knoten.getZiel() )) {
 173                 if (l.get_tiefe() < beste_tiefe) {
 174                     beste_tiefe = l.get_tiefe();
 175                     pfad.add(l);
 176                     Knoten p;
 177                     while( l.get_parent() != null) {
 178                         p = l.get_parent();
 179                         //System.out.println(p);
 180                         pfad.add(p);
 181                         l = p;
 182                     }
 183
 184                     if (systemout)
 185                     {
 186                         System.out.println("Wir haben einen Weg gefunden! Auf Tiefe " + pfad.getFirst().get_tiefe());
 187                         for (int i=pfad.size()-1;i>=0;i--)
 188                         {
 189                             System.out.println(pfad.get(i));
 190                         }
 191                         System.out.println("========================================");
 192                     }
 193                     if (beste_tiefe == Knoten.getStart().get_heuristik())
 194                     {
 195                         System.out.println("Es wurde eine optimale Lösung gefunden");
 196                         System.exit(0);
 197                     }
 198                 }
 199             }
 200         }
 201         return pfad;
 202     }
 203
 204 private static void schiebe4()
 205 {
 206         LinkedList<Knoten> knotenListe = new LinkedList<Knoten>();
 207         LinkedList<Knoten> ergebnisse = new LinkedList<Knoten>();
 208         knotenListe.add(Knoten.getStart());
 209         Knoten.setHeuristikTyp(Knoten.HEURISTIK_SIMPEL);
 210         LinkedList<Knoten> expandListe = null;
 211         while (knotenListe.size()> 0)
 212         {
 213                 Knoten k = knotenListe.poll();
 214                 expandListe = trs.expandKnoten(k);
 215                 for (Knoten l:expandListe)
 216                 {
 217                         for (int y=0;y<4;y++)
 218                         {
 219                                 if (l.get_field(2,y) ==
 220 Knoten.vierer_lu)
 221                                 {
 222                                         ergebnisse.add(l);
 223                                         System.out.println(l);
 224                                 }
 225                         }
 226
 227                 }
 228                 knotenListe.addAll(expandListe);
 229         }
 230 }
 231     /**
 232      * Durchsucht den Suchraum bis Tiefe 7 per Breitensuche. Von dort aus wird eine A*
 233      * Suche mit Luftlinienheuristik angestoßen mit dem Nachteil,
 234      * dass ab hier die Teilbäume getrennt von einander untersucht werden
 235      */
 236
 237     private static void asternluft(int maxTiefe) {
 238         // Alle Knoten der Tiefe 7 entwickeln
 239                 LinkedList<Knoten> schichtListe= new LinkedList<Knoten>();
 240         schichtListe.add(Knoten.getStart());
 241         Knoten.setHeuristikTyp(Knoten.HEURISTIK_LUFT);
 242         LinkedList<Knoten> expandListe= null;
 243         boolean tiefe8=false;
 244         while (!tiefe8  && schichtListe.size()>0) {
 245             Knoten k = schichtListe.poll();
 246             expandListe = trs.expandKnoten(k);
 247             testZiel(expandListe,true);
 248             if (expandListe.getFirst().get_tiefe()<8)
 249             {
 250                 //Knoten löschen die zu weit entfernt sind
 251                 LinkedList<Knoten> expand2Liste = (LinkedList<Knoten>)expandListe.clone();
 252                 for (Knoten t:expand2Liste)
 253                 {
 254                     if (t.get_heuristik() > maxTiefe)
 255                     {
 256                         expandListe.remove(t);
 257                     }
 258                 }
 259                 schichtListe.addAll(expandListe);
 260             }
 261             else tiefe8 = true;
 262             //auf keinen Fall sortieren, Breitensuche und Luftheuristik beißen sich
 263             //Collections.sort(schichtListe);
 264         }
 265
 266         // nun enthällt schichtListe alle Knoten der Tiefe 7
 267         // und wir beginnen mit A* LuftlinienHeuristik
 268         Runtime rt = Runtime.getRuntime();
 269         System.out.println("Schicht 7 vollständig entwickelt mit "+schichtListe.size()+" Knoten");
 270         System.out.println(rt.totalMemory()+" von "+rt.maxMemory()+" Speicher belegt");
 271
 272         //zunächst schichtListe nach LuftlinienHeuristik sortieren
 273         Knoten.setHeuristikTyp(Knoten.HEURISTIK_LUFT);
 274         for (Knoten k: schichtListe){
 275             k.computeHeuristik();
 276         }
 277         Collections.sort(schichtListe);
 278
 279         //nun für jeden Knoten der Schicht 7 jeweils A* ausführen
 280         int fortschritt=0;
 281         for (Knoten k : schichtListe) {
 282             if ((float)schichtListe.indexOf(k)/(float)schichtListe.size()*100 >= fortschritt)
 283             {
 284                 if (fortschritt%10 == 0) System.out.print("*");
 285                 else System.out.print(".");
 286                 fortschritt++;
 287             }
 288             LinkedList<Knoten> knotenListe = new LinkedList<Knoten>();
 289             knotenListe.addAll(trs.expandKnoten(k));
 290             Knoten l = null;
 291             while (knotenListe.size()>0){
 292                 l = knotenListe.poll();
 293                 expandListe = trs.expandKnoten(l);
 294                 testZiel(expandListe,true);
 295                 //knoten löschen die zu weit vom ziel entfernt sind
 296                 LinkedList<Knoten> expand2Liste = (LinkedList<Knoten>)expandListe.clone();
 297                 for (Knoten t:expand2Liste)
 298                 {
 299                     if (t.get_heuristik() > maxTiefe)
 300                     {
 301                         expandListe.remove(t);
 302                     }
 303                 }
 304                 knotenListe.addAll(expandListe);
 305                 Collections.sort(knotenListe);
 306             }
 307         }
 308     }
 309
 310     private static void asternsimpel() {
 311
 312         //int max_tiefe   = 0;
 313
 314         Knoten.setHeuristikTyp(Knoten.HEURISTIK_LUFT);
 315
 316         LinkedList<Knoten> knotenListe = new LinkedList<Knoten>();
 317         knotenListe.add(Knoten.getStart());
 318         while( knotenListe.size() > 0 ) {
 319             Knoten k = knotenListe.poll();
 320             /*if (k.get_tiefe() > max_tiefe) {
 321                 max_tiefe = k.get_tiefe();
 322                 System.out.println("Maximale Tiefe: " + max_tiefe
 323                         + " Länge der Liste : " + knotenListe.size());
 324             }*/
 325             LinkedList<Knoten> expandListe = trs.expandKnoten(k);
 326             testZiel(expandListe,true);
 327             knotenListe.addAll(expandListe);
 328             Collections.sort(knotenListe);
 329             //KnotenListe trimmen
 330             if (knotenListe.size()>10000)
 331             {
 332                 while (knotenListe.size()>10000)
 333                         knotenListe.removeLast();
 334             }
 335                 //debugausgaben
 336             /*for (int i=0;i<5 & i<knotenListe.size();i++)
 337             {
 338                 System.out.print(knotenListe.get(i).get_heuristik()+ " (" + knotenListe.get(i).get_tiefe()+") ");
 339             }
 340                 System.out.print(knotenListe.getLast().get_heuristik()+ " (" + knotenListe.getLast().get_tiefe()+") ");
 341                 System.out.print(knotenListe.size());
 342                 System.out.println();
 343             */
 344         }
 345     }
 346
 347     private static void dfs(Knoten node)
 348     {
 349         LinkedList<Knoten> stack = trs.expandKnoten(node);
 350         testZiel(stack,true);
 351         while (stack.size() > 0 && node.get_tiefe()<15)
 352         {
 353             node = stack.poll();
 354             dfs(node);
 355         }
 356     }
 357     /**
 358      *Adaptiver A*, der die aktuell kürzeste Lösung als obere Schranke zum
 359      *Beschneiden des Baums verwendet
 360      */
 361     private static void adastern ()
 362     {
 363         int maxTiefe = 22;
 364         int maxTiefeNeu;
 365         while (maxTiefe > 0)
 366         {
 367             System.out.println("Starte asternluft mit maxTiefe "+ maxTiefe);
 368             maxTiefeNeu = asternluft2(maxTiefe,false);
 369             if (maxTiefeNeu < maxTiefe) maxTiefe = maxTiefeNeu;
 370             else maxTiefe=0;
 371         }
 372     }
 373
 374     /**
 375      *A* wird mit steigender oberer Schranke ausgeführt, um sehr schnell kurze Wege
 376      *zu finden, da der Baum anfangs sehr stark beschnitten wird
 377      */
 378     private static void mincut ()
 379     {
 380         boolean found = false;
 381         int maxTiefe = Knoten.getStart().get_heuristik();
 382         int erfolg=0;
 383         while (!found)
 384         {
 385             System.out.println("Starte asternluft mit maxTiefe "+ maxTiefe);
 386             erfolg = asternluft2(maxTiefe,true);
 387             if (erfolg == 0) maxTiefe++;
 388             else found = true;
 389         }
 390     }
 391
 392     /**
 393      *asternluft algo mit besonderen abbruchbedingungen für
 394      *übergeordnete alogrithmen
 395      */
 396     private static int asternluft2(int maxTiefe,boolean mincut) {
 397         // Alle Knoten der Tiefe 8 entwickeln
 398         LinkedList<Knoten> schichtListe= new LinkedList<Knoten>();
 399         LinkedList<Knoten> pfad;
 400         schichtListe.add(Knoten.getStart());
 401         Knoten.setHeuristikTyp(Knoten.HEURISTIK_LUFT);
 402         LinkedList<Knoten> expandListe= null;
 403         boolean tiefe8=false;
 404         while (!tiefe8 && schichtListe.size()>0) {
 405             Knoten k = schichtListe.poll();
 406             expandListe = trs.expandKnoten(k);
 407             pfad = testZiel(expandListe,true);
 408             if (pfad.size()> 0 && pfad.size()-1 < maxTiefe) return pfad.size()-1;
 409             if (mincut && pfad.size()> 0 && pfad.size()-1 <= maxTiefe) return pfad.size()-1;
 410             if (expandListe.getFirst().get_tiefe()<9)
 411             {
 412                 //Knoten löschen die zu weit entfernt sind
 413                 LinkedList<Knoten> expand2Liste = (LinkedList<Knoten>)expandListe.clone();
 414                 for (Knoten t:expand2Liste)
 415                 {
 416                     if (t.get_heuristik() > maxTiefe)
 417                     {
 418                         expandListe.remove(t);
 419                     }
 420                 }
 421                 schichtListe.addAll(expandListe);
 422             }
 423             else tiefe8 = true;
 424             //auf keinen Fall sortieren, Breitensuche und Luftheuristik beißen sich
 425             //Collections.sort(schichtListe);
 426         }
 427
 428         // nun enthällt schichtListe alle Knoten der Tiefe 8
 429         // und wir beginnen mit A* LuftlinienHeuristik
 430         Runtime rt = Runtime.getRuntime();
 431         System.out.println("Schicht 8 vollständig entwickelt mit "+schichtListe.size()+" Knoten");
 432         System.out.println(rt.totalMemory()+" von "+rt.maxMemory()+" Speicher belegt");
 433
 434         //zunächst schichtListe nach LuftlinienHeuristik sortieren
 435         Knoten.setHeuristikTyp(Knoten.HEURISTIK_LUFT);
 436         for (Knoten k: schichtListe){
 437             k.computeHeuristik();
 438         }
 439         Collections.sort(schichtListe);
 440
 441         //nun für jeden Knoten der Schicht 7 jeweils A* ausführen
 442         int fortschritt=0;
 443         for (Knoten k : schichtListe) {
 444             if ((float)schichtListe.indexOf(k)/(float)schichtListe.size()*100 >= fortschritt)
 445             {
 446                 if (fortschritt%10 == 0) System.out.print("*");
 447                 else System.out.print(".");
 448                 fortschritt++;
 449             }
 450             LinkedList<Knoten> knotenListe = new LinkedList<Knoten>();
 451             knotenListe.addAll(trs.expandKnoten(k));
 452             Knoten l = null;
 453             while (knotenListe.size()>0){
 454                 l = knotenListe.poll();
 455                 expandListe = trs.expandKnoten(l);
 456                 pfad = testZiel(expandListe,true);
 457                 if (pfad.size()> 0 && pfad.size()-1 < maxTiefe) return pfad.size()-1;
 458                 if (mincut && pfad.size()> 0 && pfad.size()-1 <= maxTiefe) return pfad.size()-1;
 459                 //knoten löschen die zu weit vom ziel entfernt sind
 460                 LinkedList<Knoten> expand2Liste = (LinkedList<Knoten>)expandListe.clone();
 461                 for (Knoten t:expand2Liste)
 462                 {
 463                     if (t.get_heuristik() > maxTiefe)
 464                     {
 465                         expandListe.remove(t);
 466                     }
 467                 }
 468                 knotenListe.addAll(expandListe);
 469                 Collections.sort(knotenListe);
 470             }
 471         }
 472         return 0;
 473     }
 474
 475
 476
 477 }
 478