Bubble Blast 2 - Optimale Lösung für gegebene Levels

Ich schrieb:

> Gibt es bessere Algorithmen dafür oder ist das Problem nicht anders
> optimal lösbar?

Aus dem Bauch raus, würde ich mal sagen: Nein, da gibt es keinen 
eleganten Algorithmus dafür.
Backtracking darauf ansetzen um zumindest die Probier-Suche organisiert 
über die Bühne zu bringen.

Ich schrieb:
> Karl Heinz Buchegger schrieb:
>> Backtracking darauf ansetzen um zumindest die Probier-Suche organisiert
>> über die Bühne zu bringen.
>
> Wie meinst du das?

Aus der Menge der möglichen Kugeln eine nach der anderen auswählen und 
einfach ausprobieren was passiert. In dieser Stellung dann wieder alle 
Möglichkeiten durchprobieren usw. Bis eine maximale Tiefe erreicht ist. 
Danach den letzten Zug zurücknehmen und in dieser Stellung die nächste 
möglliche Alternative probieren, sofern noch eine vorhanden ist.

Also im Grunde eh das, was du als Tiefensuche genannt hast.

Ich schrieb:

> Karl Heinz Buchegger schrieb:
>> Bis eine maximale Tiefe erreicht ist.
>
> Die Aufgabe, die ich mir stelle, ist nicht: Finde eine beliebige Lösung
> mit maximal X Berührungen.
> Sondern: Finde die optimale Lösung. Wieviele Berührungen braucht man?

Weiter laufen lassen, bis alle Möglichkeiten ausgeschöpft sind und davon 
dann die Beste nehmen. Wobei du den Vorteil ausnutzen kannst, dass du 
mit jeder Lösung eine maximale Suchtiefe hast, ab der du nicht mehr 
weitersuchen musst, weil es dann in diesem Teilbaum keine bessere Lösung 
mehr geben kann.

Erinnert mich jetzt vom Vorgehen her ein wenig an die Backtracking 
Variante, die als 'das Rucksackproblem' in der Algorithmenliteratur 
bekannt geworden ist. Auch da gehts letzten Endes um die Suche nach 
einer optimalen Lösung, wobei man nur durch Durchprobieren aller 
Lösungen zum Ziel kommt.

troll schrieb:
> Spiellogik zu implementieren ist ja einfach (gerade erledigt)

Wie ist der Fall geregelt, wenn eine rote Blase von mehreren Seiten
gleichzeitig mit den kleinen Bällen bombardiert wird? Einer davon bringt
die Blase zum Platzen, während die anderen (zusammen mit den durch das
Platzen neu entstehenden Bällen) weiterfliegen. Aber welcher der Bälle
tötet die Blase und welche fliegen weiter? Das hängt wohl davon ab, in
welcher Reihenfolge die Bälle durch die Software abgearbeitet werden.

Weiß da jemand Genaueres?

Verwirrter Anfänger schrieb:

> Das Worstcase ändert sich dadurch zwar nicht, aber ich könnte mir
> vorstellen, das man die durchschnittliche Dauer damit durchaus
> verbessern könnte.

Durchaus

Auf dem Video sieht man ein 5*6 Spielfeld. d.h. maximal sind 30 Steine 
im Einsatz, die sich, wenn ich das Video nehme, auch relativ schnell 
reduzieren. Ich erwarte eigentlich nicht, dass sich da die Rechenzeit 
extrem hochschaukelt.
Also einfach mal: "brute force" und auf sie mit Gebrüll.

Karl Heinz Buchegger schrieb:
> Also einfach mal: "brute force" und auf sie mit Gebrüll.

Backtracking ist kein brute force...
Am wichtigsten wäre die genauen Spielregeln und Abbruchkriterien, 
eventuell kann man sogar aus der Anzahl der Kugeln abschätzen was die 
höchste/niedrigste Anzahl Schritte wäre.

also 5*6 ist doch pipifax.
Eine Zelle kann 5 Zustände haben.
-> 3Bit
10 Zellen pro uint32_t
Man braucht also 3*uint32 = 12Byte um den kompletten Zustand eines 
Spielfeldes zu speichern.

Man kann das ganze natürlich noch mehr komprimieren, dann werden die 
Zugriffe aber immer ineffizienter.

(5*6)^5 = 24.300.000 mögliche Kombinationen
* 12 Byte = 729.000.000 Byte ~700MB

Man kann also einmal berechnete Felder speichern und dazu den optimalen 
Zug (30 möglichkeiten -> 1 Byte --> zusätzliche 23Mb).

Das sollte die Suche nochmals um einiges schneller machen.

sollen es größere Felder werden, die absolut nicht mehr zu handlen 
werden, kann man nach dem Schema sich vielleicht eine Art 
Endspieldatenbank aufbauen

edit:
nee - 12Byte sind wirklich das Minimum
30*3/8 = 11,25Byte

Es geht doch noch effizienter, die 3 bit pro Feld werden ja nur zu 5/8 
ausgenutzt.

(5*6)^5 = 24.300.000 Kombinationen kann man ja einfach durchnummerieren.
Nur gibt es eine effiziente Methode aus einer Feldkonfiguration die 
Nummer zu bilden?

um dem Problem zu begegnen könnte man kleine Grüppchen bilden, innerhalb 
derer man die Kombinationen durchnummeriert.
zB je 3 Felder
3^5 = 243 Kombinationen ~ 1Byte -->10Byte für alle.
die Auflösung von Feldern -> Byte und Byte -> Feldern ließe sich 
effizient über kleine LUTs machen

D. I. schrieb:
> Dein Vorschlag beruht nur auf einem entscheidenden Fehler:
>
> 30 Plätze a 5 Möglichkeiten sind nicht 30^5 sondern 5^30.

Ach verdammt, du hast recht. So ein Anfängerfehler.
Naja sie Zahlen ändern sich ja nur geringfügig. ;-)

Vlad Tepesch schrieb:

>
> (5*6)^5 = 24.300.000 mögliche Kombinationen
> * 12 Byte = 729.000.000 Byte ~700MB

Schon. (Jetzt mal den Rechenfehler weggelassen).
Aber die musst du ja nicht alle speichern.

Du hast eine Spiefeldsituation
  die gehst du durch und für jeden Stein probierst du den Zug
  zu machen. Daraus ergibt sich eine neue Situation. (A)
  Zum jetzigen Zeitpunkt hast du gerade mal 2 Spielfelder speichern
  müssen.

  Jetzt gehts rekursiv rein. Mit der Situation aus (A) probierst
  du wieder alle möglichen Züge und kriegst jeweils eine neue
  Situation, die du aber nicht speichern musst. Es wird jeweils
  nachgesehen, ob damit das 'Problem' bereits gelöst ist oder
  ob noch eine Rekursion anhegängt werden muss.
  Zu diesem Zeitpunkt sind erst 3 Spielfelder gespeichert.

Und die Rekursion geht maximal bis auf Ebene 30, weil es prinzipiell 
nicht mehr Steine geben kann. Jedes mal wenn die Rekursion dann wieder 
zurückkehrt, wird auch wieder ein Spielfeld aufgelöst, ehe es dann in 
einem anderen Pfad der Möglichkeiten in die Rekursion wieder reingeht.

Maximal musst du als 30*3*12 Bytes speichern. 30, weil die Rekursion 
nicht über mehr als 30 Ebenen gehen kann. 3 weil jeder Stein maximal 3 
Zustände annehmen kann.
Plus den Weg, den man genommen hat um zur Endstellung zu kommen (zwecks 
Bewertung der Lösung)
Plus dem Zeugs, was für die Rekursion noch notwendig ist.


Wenn eine IBM 360 vor 20 Jahren die 8 Damen auf einem Schachbrett 
anordnen sollte und alle 96 (oder warens 92) möglichen Lösungen in unter 
1/10 Sekunde fand, dann wird das doch ein PC von heute in akzeptabler 
Zeit hinkriegen.

D. I. schrieb:
> Ich denke bei dem Teil ist das "Schwierigste" es die
> Einschlagsreihenfolge der Kugeln richtig zu implementieren.

Das sehe ich auch so.

> Wahrscheinlich tut man sich am einfachsten (wenn auch nicht sehr
> schnell) einen Zug einfach mit diskreten Zeitschritten zu simulieren
> (ein Zeitschritt = eine Kugel fliegt ein Feld weiter) sobald ein Zug
> gemacht wurde.

Genau so würde ich das machen oder probieren. Das ganze läuft so lange, 
bis sich am Spielfeld nichts mehr verändert und man hat das Ergebnis der 
Auswirkungen des Antippens einer Kugel.
Schwierigkeiten bereitet
 * wenn mehrere Kugeln 'gleichzeitig' ein Feld erreichen auf dem
   schon eine andere Kugel sitzt. Welcher der Angreifer verschwindet
 * selber Fall, nur diesmal ohne andere Kugel. Die fliegenden
   Kugeln müssen über dieses eine Feld sauber drüber kommen ohne
   das der Rechner die Kugeln 'verliert'.

Speziell letzterer Fall würde für mich ein Hinweis sein, dass man 
zusätzlich zum Spielfeld noch eine Liste mit allen Kugeln, deren 
Positionen und deren Geschwindigkeiten braucht.
So gesehen wird der Speicherverbrauch wieder etwas höher.

Karl Heinz Buchegger schrieb:
> Aber die musst du ja nicht alle speichern.
Muss man nicht, aber es würde helfen, wenn man auf verschiedenen Wegen 
zu einer Konfiguration kommt. Dann müsste man nicht den kompletten Baum 
dahinter nochmal abarbeiten.
Über kurz oder lang hätte man das komplette Spiel gelöst, wenn dieser 
blöde Denkfehler nicht gewesen wäre.

troll schrieb:
> Die Kugeln/Bälle
> über das Feld zu schießen ist nun wirklich nicht schwierig, ich habe das
> rekursiv gemacht.

die Frage ist halt, was passiert, wenn 2 Kugeln zeitgleich aus 
verschiedenen Richtungen auf eine rote Blase treffen.
welche Kugel durchgeht und welche die Blase zerstört ist "implementation 
defined" aber essentiell für die optimale Lösung.

Na ja. soo schwer ist es dann auch wieder nicht.

Mal sehen. Da ich ein Faible für so kleine Übungsaufgaben habe und die 
kleinen grauen Zellen auch wieder mal ein wenig Bewegung brauchen, setz 
ich mich heut abend vielleicht mal ran. Wenn mein Kopfweh nachlässt.

@Ich:

Ich habe in einem Youtube-Video (finde es leider nicht mehr) folgende
Situation gesehen:

1

    o

2

    ↓

3

G   R ← o

o = Kugel
R = rote Blase
G = grüne Blase

Beide Kugeln treffen gleichzeitig auf die rote Blase. Diese platzt, und
die von rechts kommende Kugel und die durch das Platzen neu erzeugte
fliegen deckungsgleich auf die grüne Blase zu. Das kann man daran
erkennen, dass diese ebenfalls platzt, wozu sie von mindestens zwei
Kugeln getroffen worden sein muss.

dieses Spiel suggeriert einem ja, dass man durch "Logik" weiter kommt..
(ala Sudoku)

eigentlich muss man als SPIELER also auch GENAU wissen, wie das 
funktioniert
sonst kann man ja nur durch probieren weiter kommen,

solange es keine Anleitung gibt, in der dieses Verhalten beschrieben 
ist, scheint mir der "Wert" dieses spieles eher in >Mensch ärgere dich 
nicht< Niveau ...

Robert L. schrieb:
> sonst kann man ja nur durch probieren weiter kommen

Leren durch ausprobieren... gerade da ist doch der Reiz, das man nicht 
seitenweise Anleitungen lesen muss sondern einfach drauf los spielt bei 
solchen "Zeitvertreibern".

Wollte mir das Spiel gerade mal laden um zu prüfen, ob man eventuell 
auch mehrere schnell hinterinander antippen kann, das würde die Sache 
noch verkomplizieren.
Habe es aber abgebrochen, da das Spiel die Berechtigung fordert die 
Telefonfunktion zu steuern u.A. die Telefonnummer, ob ein Gespräch läuft 
und mit welcher Nummer telefoniert wird!??!?

nocheinGast schrieb:
> Meines Erachtens heißt das nicht, dass die App
> selbstständig telefonieren darf
Nein, aber sie darf neben der TelefonID halt die Nummer des 
Gesprächpartners auslesen (+meine eigene) und die Tatsache dass ein 
Gespräch geführt wird.

@Läubi

>Du überdramatisierst.

;-)

@Robert: Ich bin da gar nicht so hinterher, hab nix geheimes auf meinem 
Telefon, aber für ein Spiel muss man echt nicht solche doch 
weitreichenden Rechte einfordern oder? Finde ich zumindest übertrieben 
und die Beschreibung gibt auch nicht her wozu die das benötigen im 
schlimmsten Fall wird man dann schön mit Werbung zugespammt...