1 /* Schiebespiel - effectively computes solution for a one player board game
2 * Copyright (C) 2007 Dirk Ribbroch / Martin Drohmann
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.
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.
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
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 ziel
= new Knoten();
27 private static Knoten ziel_final
= new Knoten();
28 private static int beste_tiefe
= 32786;
30 public static void main(String
[] argv
) {
31 // Start Konfiguration
32 start
.set_field(0,0,Knoten
.zweier_links
);
33 start
.set_field(1,0,Knoten
.zweier_rechts
);
34 start
.set_field(2,0,Knoten
.zweier_links
);
35 start
.set_field(3,0,Knoten
.zweier_rechts
);
36 start
.set_field(4,0,Knoten
.einer
);
37 start
.set_field(0,3,Knoten
.zweier_links
);
38 start
.set_field(1,3,Knoten
.zweier_rechts
);
39 start
.set_field(2,3,Knoten
.zweier_links
);
40 start
.set_field(3,3,Knoten
.zweier_rechts
);
41 start
.set_field(4,3,Knoten
.einer
);
42 start
.set_field(0,1,Knoten
.vierer_lu
);
43 start
.set_field(1,1,Knoten
.vierer_ru
);
44 start
.set_field(2,1,Knoten
.zweier_unten
);
45 start
.set_field(3,1,Knoten
.einer
);
46 start
.set_field(4,1,Knoten
.leer
);
47 start
.set_field(0,2,Knoten
.vierer_lo
);
48 start
.set_field(1,2,Knoten
.vierer_ro
);
49 start
.set_field(2,2,Knoten
.zweier_oben
);
50 start
.set_field(3,2,Knoten
.einer
);
51 start
.set_field(4,2,Knoten
.leer
);
52 start
.set_leere(0, 4, 1);
53 start
.set_leere(1, 4, 2);
54 start
.set_leere(2, -1,-1);
55 start
.set_leere(3, -1,-1);
57 ziel
.set_field(0,0,Knoten
.zweier_links
);
58 ziel
.set_field(1,0,Knoten
.zweier_rechts
);
59 ziel
.set_field(2,0,Knoten
.zweier_links
);
60 ziel
.set_field(3,0,Knoten
.zweier_rechts
);
61 ziel
.set_field(0,3,Knoten
.einer
);
62 ziel
.set_field(3,2,Knoten
.zweier_links
);
63 ziel
.set_field(4,2,Knoten
.zweier_rechts
);
64 ziel
.set_field(2,3,Knoten
.zweier_links
);
65 ziel
.set_field(3,3,Knoten
.zweier_rechts
);
66 ziel
.set_field(4,3,Knoten
.einer
);
67 ziel
.set_field(0,1,Knoten
.vierer_lu
);
68 ziel
.set_field(1,1,Knoten
.vierer_ru
);
69 ziel
.set_field(2,1,Knoten
.zweier_unten
);
70 ziel
.set_field(3,1,Knoten
.einer
);
71 ziel
.set_field(4,1,Knoten
.leer
);
72 ziel
.set_field(0,2,Knoten
.vierer_lo
);
73 ziel
.set_field(1,2,Knoten
.vierer_ro
);
74 ziel
.set_field(2,2,Knoten
.zweier_oben
);
75 ziel
.set_field(4,0,Knoten
.einer
);
76 ziel
.set_field(1,3,Knoten
.leer
);
77 // Unser eigentliches Ziel für das das ganze Programm existiert
78 ziel_final
.set_field(0,0,Knoten
.zweier_links
);
79 ziel_final
.set_field(1,0,Knoten
.zweier_rechts
);
80 ziel_final
.set_field(0,1,Knoten
.zweier_links
);
81 ziel_final
.set_field(1,1,Knoten
.zweier_rechts
);
82 ziel_final
.set_field(0,2,Knoten
.zweier_links
);
83 ziel_final
.set_field(1,2,Knoten
.zweier_rechts
);
84 ziel_final
.set_field(0,3,Knoten
.zweier_links
);
85 ziel_final
.set_field(1,3,Knoten
.zweier_rechts
);
86 ziel_final
.set_field(2,0,Knoten
.einer
);
87 ziel_final
.set_field(2,1,Knoten
.einer
);
88 ziel_final
.set_field(2,2,Knoten
.zweier_oben
);
89 ziel_final
.set_field(2,3,Knoten
.zweier_unten
);
90 ziel_final
.set_field(3,0,Knoten
.vierer_lo
);
91 ziel_final
.set_field(4,0,Knoten
.vierer_ro
);
92 ziel_final
.set_field(3,1,Knoten
.vierer_lu
);
93 ziel_final
.set_field(4,1,Knoten
.vierer_ru
);
94 ziel_final
.set_field(3,2,Knoten
.einer
);
95 ziel_final
.set_field(4,2,Knoten
.einer
);
96 ziel_final
.set_field(3,3,Knoten
.leer
);
97 ziel_final
.set_field(4,3,Knoten
.leer
);
99 Knoten
.set_start(start
);
100 Knoten
.set_ziel(ziel
);
102 /* Hiermit beginnen wir */
103 System
.out
.println("Hiermit beginnen wir: \n" + start
.toString());
104 /* Dies ist das Ziel */
105 System
.out
.println("Das ist das Ziel:\n" + ziel
.toString());
107 //System.out.println(argv.length);
108 if( argv
.length
> 0) {
109 if( argv
[0].equals("tiefensuche") ) {
111 } else if( argv
[0].equals("asternsimpel") ) {
114 } else { /* Default: */
120 * Überprüft, ob das Ziel gefunden wurde und gibt in dem Fall den Weg aus
122 private static LinkedList
<Knoten
> testZiel(LinkedList
<Knoten
> expandListe
, boolean systemout
)
124 LinkedList
<Knoten
> trefferListe
= new LinkedList
<Knoten
>();
126 for (Knoten l
: expandListe
) {
127 if (l
.compareTo( ziel
) == 0) {
128 if (l
.get_tiefe() < beste_tiefe
) {
129 beste_tiefe
= l
.get_tiefe();
132 System
.out
.println("Wir haben einen Weg gefunden!");
133 System
.out
.println(l
);
135 while( l
.get_parent() != null) {
137 System
.out
.println(p
);
140 for (int i
= 0; i
< 3; ++i
) {
142 "========================================");
151 * Durchsucht den Suchraum bis Tiefe 6 per Breitensuche. Von dort aus wird eine A*
152 * Suche mit Luftlinienheuristik angestoßen mit dem Nachteil,
153 * dass ab hier die Teilbäume von einander untersucht werden
156 private static void testluft() {
157 Knoten
.setHeuristikTyp(Knoten
.HEURISTIK_LUFT
);
158 start
.computeHeuristik();
159 System
.out
.println(start
.get_heuristik());
162 private static void asternluft() {
163 // Alle Knoten der Tiefe 7 entwickeln
164 LinkedList
<Knoten
> schichtListe
= new LinkedList
<Knoten
>();
165 schichtListe
.add(start
);
166 Knoten
.setHeuristikTyp(Knoten
.HEURISTIK_SIMPEL
);
167 LinkedList
<Knoten
> expandListe
= null;
168 boolean tiefe8
=false;
170 Knoten k
= schichtListe
.poll();
171 expandListe
= trs
.expandKnoten(k
);
172 testZiel(expandListe
,true);
173 if (expandListe
.getFirst().get_tiefe()<8) {
174 schichtListe
.addAll(expandListe
);
177 Collections
.sort(schichtListe
);
180 // nun enthällt schichtListe alle Knoten der Tiefe 7
181 // und wir beginnen mit A* LuftlinienHeuristik
183 System
.out
.println("Schicht 7 entwickelt");
185 //zunächst schichtListe nach LuftlinienHeuristik sortieren
186 Knoten
.setHeuristikTyp(Knoten
.HEURISTIK_LUFT
);
187 for (Knoten k
: schichtListe
){
188 k
.computeHeuristik();
190 Collections
.sort(schichtListe
);
192 //nun für jeden Knoten der Schicht 7 A* ausführen
193 for (Knoten k
: schichtListe
) {
194 LinkedList
<Knoten
> knotenListe
= new LinkedList
<Knoten
>();
195 knotenListe
.addAll(trs
.expandKnoten(k
));
197 while (knotenListe
.size()>0 && knotenListe
.getFirst().get_tiefe()<20 ){
198 l
= knotenListe
.poll();
199 expandListe
= trs
.expandKnoten(l
);
200 testZiel(expandListe
,true);
201 knotenListe
.addAll(expandListe
);
202 Collections
.sort(knotenListe
);
207 private static void asternsimpel() {
211 //Knoten.SetHeuristikTyp(Knoten.HEURISTIK_DIFFERENZ);
213 LinkedList
<Knoten
> knotenListe
= new LinkedList
<Knoten
>();
214 knotenListe
.add(start
);
215 while( knotenListe
.size() > 0 ) {
216 Knoten k
= knotenListe
.poll();
217 /*if (k.get_tiefe() > max_tiefe) {
218 max_tiefe = k.get_tiefe();
219 System.out.println("Maximale Tiefe: " + max_tiefe
220 + " Länge der Liste : " + knotenListe.size());
222 LinkedList
<Knoten
> expandListe
= trs
.expandKnoten(k
);
223 for (Knoten l
: expandListe
) {
224 if (l
.compareTo( ziel
) == 0) {
225 if (l
.get_tiefe() < beste_tiefe
) {
226 beste_tiefe
= l
.get_tiefe();
227 System
.out
.println("Wir haben einen Weg gefunden!");
228 System
.out
.println(l
);
230 while( l
.get_parent() != null) {
232 System
.out
.println(p
);
235 for (int i
= 0; i
< 3; ++i
) {
237 "========================================");
242 knotenListe
.addAll(expandListe
);
243 Collections
.sort(knotenListe
);
244 //KnotenListe trimmen
245 if (knotenListe
.size()>10000)
247 while (knotenListe
.size()>10000)
248 knotenListe
.removeLast();
251 for (int i
=0;i
<5 & i
<knotenListe
.size();i
++)
253 System
.out
.print(knotenListe
.get(i
).get_heuristik()+ " (" + knotenListe
.get(i
).get_tiefe()+") ");
255 System
.out
.print(knotenListe
.getLast().get_heuristik()+ " (" + knotenListe
.getLast().get_tiefe()+") ");
256 System
.out
.print(knotenListe
.size());
257 System
.out
.println();
262 private static void tiefensuche() {
263 //todo tiefensuche rekursiv implementieren
264 int beste_tiefe
= 32786;
267 Knoten ka
=null, kb
=null, kc
=null, kd
=null, ke
=null,
268 kf
=null, kg
=null, kh
=null, ki
=null, kj
=null,
269 kk
=null, kl
=null, km
=null, kn
=null, ko
=null,
270 kp
=null, kq
=null, kr
=null;
272 LinkedList
<Knoten
> knotenListeA
= new LinkedList
<Knoten
>();
273 LinkedList
<Knoten
> knotenListeB
= new LinkedList
<Knoten
>();
274 LinkedList
<Knoten
> knotenListeC
= new LinkedList
<Knoten
>();
275 LinkedList
<Knoten
> knotenListeD
= new LinkedList
<Knoten
>();
276 LinkedList
<Knoten
> knotenListeE
= new LinkedList
<Knoten
>();
277 LinkedList
<Knoten
> knotenListeF
= new LinkedList
<Knoten
>();
278 LinkedList
<Knoten
> knotenListeG
= new LinkedList
<Knoten
>();
279 LinkedList
<Knoten
> knotenListeH
= new LinkedList
<Knoten
>();
280 LinkedList
<Knoten
> knotenListeI
= new LinkedList
<Knoten
>();
281 LinkedList
<Knoten
> knotenListeJ
= new LinkedList
<Knoten
>();
282 LinkedList
<Knoten
> knotenListeK
= new LinkedList
<Knoten
>();
283 LinkedList
<Knoten
> knotenListeL
= new LinkedList
<Knoten
>();
284 LinkedList
<Knoten
> knotenListeM
= new LinkedList
<Knoten
>();
285 LinkedList
<Knoten
> knotenListeN
= new LinkedList
<Knoten
>();
286 LinkedList
<Knoten
> knotenListeO
= new LinkedList
<Knoten
>();
287 LinkedList
<Knoten
> knotenListeP
= new LinkedList
<Knoten
>();
288 LinkedList
<Knoten
> knotenListeQ
= new LinkedList
<Knoten
>();
289 LinkedList
<Knoten
> knotenListeR
= new LinkedList
<Knoten
>();
292 knotenListeA
= trs
.expandKnoten(start
);
293 System
.out
.println(knotenListeA
.size());
294 for (int a
=0; a
<knotenListeA
.size(); a
++)
296 ka
= knotenListeA
.get(a
);
297 if (ka
.compareTo( ziel
) == 0)
298 System
.out
.println("GEFUNDEN A");
299 knotenListeB
= trs
.expandKnoten(ka
);
301 for (int b
=0; b
<knotenListeB
.size(); b
++)
303 kb
=knotenListeB
.get(b
);
304 if (kb
.compareTo( ziel
) == 0)
305 System
.out
.println("GEFUNDEN B");
306 knotenListeC
= trs
.expandKnoten(kb
);
308 for (int c
=0; c
<knotenListeC
.size(); c
++)
310 kc
=knotenListeC
.get(c
);
311 if (kc
.compareTo( ziel
) == 0)
312 System
.out
.println("GEFUNDEN C");
313 knotenListeD
= trs
.expandKnoten(kc
);
315 for (int d
=0; d
<knotenListeD
.size(); d
++)
317 kd
=knotenListeD
.get(d
);
318 if (kd
.compareTo( ziel
) == 0)
319 System
.out
.println("GEFUNDEN D");
320 knotenListeE
= trs
.expandKnoten(kd
);
323 e
<knotenListeE
.size(); e
++)
325 ke
=knotenListeE
.get(e
);
326 if (ke
.compareTo( ziel
) == 0)
327 System
.out
.println("GEFUNDEN E");
328 knotenListeF
= trs
.expandKnoten(ke
);
331 f
<knotenListeF
.size(); f
++)
334 kf
=knotenListeF
.get(f
);
335 if (kf
.compareTo( ziel
) == 0)
336 System
.out
.println("GEFUNDEN F");
337 knotenListeG
= trs
.expandKnoten(kf
);
340 g
<knotenListeG
.size(); g
++)
343 kg
=knotenListeG
.get(g
);
344 if (kg
.compareTo( ziel
) == 0)
345 System
.out
.println("GEFUNDEN G");
347 knotenListeH
= trs
.expandKnoten(kg
);
350 h
=0; h
<knotenListeH
.size(); h
++)
353 kh
=knotenListeH
.get(h
);
355 if (kh
.compareTo( ziel
) == 0)
356 System
.out
.println("GEFUNDEN H");
358 knotenListeI
= trs
.expandKnoten(kh
);
361 (int i
=0; h
<knotenListeH
.size(); h
++)
363 ki
=knotenListeI
.get(i
);
364 if (ki
.compareTo( ziel
) == 0)
365 System
.out
.println("GEFUNDEN I");
366 knotenListeJ
= trs
.expandKnoten(ki
);
369 j
<knotenListeJ
.size(); j
++)
371 kj
=knotenListeJ
.get(j
);
372 if (kj
.compareTo( ziel
) == 0)
373 System
.out
.println("GEFUNDEN J");
374 knotenListeK
= trs
.expandKnoten(kj
);
377 k
<knotenListeK
.size(); k
++)
380 kk
=knotenListeK
.get(k
);
381 if (kk
.compareTo( ziel
) == 0)
382 System
.out
.println("GEFUNDEN K");
384 trs
.expandKnoten(kk
);
387 l
<knotenListeL
.size(); l
++)
390 kl
=knotenListeL
.get(l
);
391 if (kl
.compareTo( ziel
) == 0)
392 System
.out
.println("GEFUNDEN L");
394 trs
.expandKnoten(kl
);
397 m
<knotenListeM
.size(); m
++)
400 km
=knotenListeM
.get(m
);
401 if (km
.compareTo( ziel
) == 0)
402 System
.out
.println("GEFUNDEN M");
404 = trs
.expandKnoten(km
);
407 n
<knotenListeN
.size(); n
++)
410 kn
=knotenListeN
.get(n
);
411 if (kn
.compareTo( ziel
) == 0)
412 System
.out
.println("GEFUNDEN N");
414 knotenListeO
= trs
.expandKnoten(kn
);
416 for (int o
=0; o
<knotenListeO
.size(); o
++)
419 ko
=knotenListeO
.get(o
);
420 if (ko
.compareTo( ziel
) == 0)
421 System
.out
.println("GEFUNDEN O");
423 knotenListeP
= trs
.expandKnoten(ko
);
426 (int p
=0; p
<knotenListeP
.size(); p
++)
429 kp
=knotenListeP
.get(p
);
431 if (kp
.compareTo( ziel
) == 0)
432 System
.out
.println("GEFUNDEN P");
434 knotenListeQ
= trs
.expandKnoten(kp
);
437 for (int q
=0; q
<knotenListeQ
.size(); q
++)
440 kq
=knotenListeQ
.get(q
);
442 if (kq
.compareTo( ziel
) == 0)
443 System
.out
.println("GEFUNDEN Q");
445 knotenListeR
= trs
.expandKnoten(kq
);
448 for (int r
=0; r
<knotenListeR
.size(); r
++)
452 kr
=knotenListeR
.get(r
);
454 if (kr
.compareTo( ziel
) == 0)
455 System
.out
.println("GEFUNDEN R");
457 // knotenListeS = trs.expandKnoten(kr);
479 ////////////////// ENDE TIEFENSUCHE