Laden...

Welchen Algorithmus für dieses Spiel?

Erstellt von Hajoseb vor 16 Jahren Letzter Beitrag vor 16 Jahren 3.131 Views
Hajoseb Themenstarter:in
309 Beiträge seit 2007
vor 16 Jahren
Welchen Algorithmus für dieses Spiel?

Hallo.

Welchen Algorythmus (Grundstrategie) könnte ich nutzen, dieses Spiel in angemessener Zeit "gut" zu lösen?

Man könnte natürlich alle Möglichkeiten durchsuchen, aber ob ich so lange lebe...

Mfg Hajoseb

**"Zufall ist das Pseudonym Gottes, wenn er nicht selbst unterschreiben will.” **
Anatole France

139 Beiträge seit 2006
vor 16 Jahren

2 Dimensionale Matrix, beim gefallen stein, alle vier seiten abfragen, bis kein gleichfarbiger stein mehr gefunden wird. Wenn es z.B. mehr als 4 sind, weg damit.

Gruss Ari
Wer lesen kann ist klar im vorteil!
MSDN
Dein Feund in allen fragen

1.361 Beiträge seit 2007
vor 16 Jahren

Hi,

momentan fällt mir noch kein guter Algorithmus ein.

Aber mal ne frage: hast du die Bewertungsfunktion analysiert?
Also wieviele Punkte gibt es bei welcher Anzahl an Kugeln?
Das würde mich mal interessieren... 😉
(denkt weiter drüber nach)

beste Grüße
zommi

//Edit: @TNDAri
Das war glaub ich gerade der Clou an dem Spiel,
dass beispielsweise 10 Kugeln weitaus mehr als nur doppelt so viel Punkte wie 5 Kugeln bringen.

139 Beiträge seit 2006
vor 16 Jahren

Das macht dann aber trotzdem nichts anderes, als die verknüpften kugeln zu zählen und wenns dann halt mehr als 10 sind, gibts doppelt so viele punkte.

BTW wie wäre es mit den spielregeln für das spiel?

Gruss Ari
Wer lesen kann ist klar im vorteil!
MSDN
Dein Feund in allen fragen

B
214 Beiträge seit 2005
vor 16 Jahren

Auf codeproject gibt es eine Implementierung des Spiels in C#: Hier lang

Vielleicht bringt dich das ein Stück weiter 😉

.:: SilvrGame - Browsergame Development with Silverlight
.:: Bionic's blOg

K
27 Beiträge seit 2008
vor 16 Jahren

Es geht hier nicht darum, das Spiel mit seinen Spielregeln zu programmieren, sondern die optimale Lösungsstrategie zu finden.

Um wirklich etwas über das Problem aussagen zu können, müsste man es komplexitätstheoretisch untersuchen. Es ist natürlich in NP. Die "alles durchprobieren" Methode bestätigt das. Aber ob es auch eine bessere Lösung gibt ist hier die große Frage. Vielleicht ist das Problem ja sogar NP-schwer.

Die Methode, die mir sofort einfällt, lässt sich am einfachsten rekursiv programmieren:


Methode solve(Spielfeld B) {
  
  Seien S1, ..., Sn die aktuell möglichen Spielzüge für das Spielfeld B

  maxPunkte = 0;

  Für i=1, ..., n {

     Führe Spielzug Si auf Spielfeld B aus. Das resultierende Spielfeld sei Bi
     punkte = solve(Bi);

     maxPunkte = max{ punkte + punkte_für_Si, maxPunkte }
  }

}

Die Punkteformel scheint folgende zu sein:

m = Anzahl eliminierte Bälle

punkte = m*(m-1)

Hajoseb Themenstarter:in
309 Beiträge seit 2007
vor 16 Jahren

Hi.

Hatte vorhin wenig Zeit ...

Das "Problem" ist ja, das es nicht (nur) darum geht, alle Bälle zu entfernen, sondern möglichst große zusammenhängende Felder zu bevorzugen sind.

Mit einer Tiefensuch kann ich da wohl lange suchen.

Bei einer Breitensuche gibt es wohl nicht genug Speicher ...

Ich zerbreche mir schon sei vielen Wochen den Kopf darüber ...

Ich entferne pro Spielzug immer mehrere Steine (min. 2) aber mehr als eine reine Tiefensuche fällt mir im Moment noch nicht ein. Eventuell müssen intelligente Abbruchbedingungen her.

Mfg Hajoseb

**"Zufall ist das Pseudonym Gottes, wenn er nicht selbst unterschreiben will.” **
Anatole France

139 Beiträge seit 2006
vor 16 Jahren

Es geht hier nicht darum, das Spiel mit seinen Spielregeln zu programmieren, sondern die optimale Lösungsstrategie zu finden.

Ähm, und dein ziel ist welches???? Also für mich kann ziel sien die ganze matrix auf 0 zu setzten und ich habe gewonnen, oder ich befolge REGELN die es für mich schwerer machen die Matrix auf 0 zu kriegen....... 😉
Da ich das Spiel nicht kenne, bräuchte ich schon regeln, nach denen bälle entfernt werden dürfen/müssen um eine geeignete strategie zu basteln 😉

Gruss Ari
Wer lesen kann ist klar im vorteil!
MSDN
Dein Feund in allen fragen

Hajoseb Themenstarter:in
309 Beiträge seit 2007
vor 16 Jahren

Oh. Sorry ... 😉

Ziel ist es, möglichst viele Punkte zu machen.

Jeder Zusätliche Ball, der mit entfernt werden kann (Sich berührende Bälle in einer Farbe) bringt exponential mehr Punkte.

z.B.
2 Bälle = 4 Punkte
3 Bälle = 9 Punkte
4 Bälle = 16 Punkte ...

Es müssen also so große Felder wie möglich erzeugt (durch entfernden kleiner, störender Felder) und dann entfernt werden.

Wenn Bälle entfernt werden, rücken die anderen nach unten (und ggf. zur Seite) nach.

Mfg Hajoseb

**"Zufall ist das Pseudonym Gottes, wenn er nicht selbst unterschreiben will.” **
Anatole France

Hajoseb Themenstarter:in
309 Beiträge seit 2007
vor 16 Jahren

Ähnliche Windows-Spiel:

Jawbeaker (ähnlich) für Windows

**"Zufall ist das Pseudonym Gottes, wenn er nicht selbst unterschreiben will.” **
Anatole France

49.485 Beiträge seit 2005
vor 16 Jahren

Hallo Hajoseb,

Jeder Zusätliche Ball, der mit entfernt werden kann (Sich berührende Bälle in einer Farbe) bringt exponential mehr Punkte.

Deine Liste hat aber nur ein quadratisches Wachstum, also nur polynomiell und damit gerade nicht exponentiell.

Eventuell müssen intelligente Abbruchbedingungen her.

Warum intelligent? Es würde doch schon reichen ganz einfach die Suchtiefe auf x Züge zu begrenzen.

herbivore

Hajoseb Themenstarter:in
309 Beiträge seit 2007
vor 16 Jahren

Hallo Hajoseb,

Jeder Zusätliche Ball, der mit entfernt werden kann (Sich berührende Bälle in einer Farbe) bringt exponential mehr Punkte.
Deine Liste hat aber nur ein quadratisches Wachstum, also nur polynomiell und damit gerade nicht exponentiell.

vergleiche doch mal die Ergebnisse von e^(2ln(x)) mit x^2 ... 😁 👍 8)

... ist das nun exponential oder nicht g

Eventuell müssen intelligente Abbruchbedingungen her.
Warum intelligent? Es würde doch schon reichen ganz einfach die Suchtiefe auf x Züge zu begrenzen.

herbivore

Nun, wie Tief soll es denn gehen ... Es können ja durch die Verschiebung auch neue Felder entstehen ...

**"Zufall ist das Pseudonym Gottes, wenn er nicht selbst unterschreiben will.” **
Anatole France

1.361 Beiträge seit 2007
vor 16 Jahren

Wen dann mal die Problemgrößenordnungen interessieren:
Habs heut morgen mal implementiert mit Bruteforce-Tiefensuche.

Nen 5x5 großes Feld kriegste "auf Klick" gelöst.
bei nem 6x6 großen Feld warteste schon mal 3 oder 4 Minuten.
Und n 7x7 Feld, da hab ich den Algo gar nicht erst gestartet 😉

Leider is das original 11x12, wenn ich das richtig sehe.
Sieht also schlecht aus mit Tiefensuche 😉

beste Grüße
zommi

Hajoseb Themenstarter:in
309 Beiträge seit 2007
vor 16 Jahren

Hatte ich schon erwähnt, das sich mindestens 2 Bälle in der selben Farbe berühren müssen, damit man diese entfernen kann 🤔

Mit der TIefensuche hatte ich es auch schon überlegt, aber wie gesagt: "Ich bin nicht unsterblich" 😁

Mein 1. Versuch hatte eine Mindestpunkzahl als Ziel, aber selbt dann dauerte es zu lange.

Mfg Hajoseb

**"Zufall ist das Pseudonym Gottes, wenn er nicht selbst unterschreiben will.” **
Anatole France

1.361 Beiträge seit 2007
vor 16 Jahren

by the way @ Hajoseb.

exponentielles Wachstum ist definiert als:
f(n) = ae^(bn)
Und da fällt deine Log-Trickserei eben nicht drunter 😉

49.485 Beiträge seit 2005
vor 16 Jahren

Hallo Hajoseb,

Nun, wie Tief soll es denn gehen

so tief wie möglich, so flach wie nötig. Du willst ja in passabler Zeit eine passable Antwort.

herbivore

Hajoseb Themenstarter:in
309 Beiträge seit 2007
vor 16 Jahren

?( ?( ?(

Also eher eine Breitensuchen ...?

**"Zufall ist das Pseudonym Gottes, wenn er nicht selbst unterschreiben will.” **
Anatole France

49.485 Beiträge seit 2005
vor 16 Jahren

Hallo Hajoseb,

das habe ich nicht gesagt. Bei der Breitensuche hast du (vermutlich) ja das Speicherproblem. Das hast du mit begrenzter Tiefensuche nicht.

herbivore

U
1.688 Beiträge seit 2007
vor 16 Jahren

Genaugenommen muss man das Spiel ja "bis zum Ende" analysieren, weil es beim Komplettabräumen einen Bonus gibt, der es durchaus geraten sein lassen kann, zwischendurch auch mal mit weniger Punkten vorlieb zu nehmen. Umgekehrt kann es sein, das man am Ende ein paar übrig lassen kann, weil man zwischendurch ein Riesenfeld abgeräumt hat.

Man weiß auch nicht, ob es überhaupt eine Möglichkeit gibt, das Feld komplett abzuräumen, oder?

Hajoseb Themenstarter:in
309 Beiträge seit 2007
vor 16 Jahren

Genau deswegen war ja meine Frage, ob es einen Algorythmus gibt, der ggf. ohne reine Tiefen- / Breitensuche gute Ergebnisse bringt.

Sozusagen eine "intelligente" Lösung 🙂

Mfg Hajoseb

**"Zufall ist das Pseudonym Gottes, wenn er nicht selbst unterschreiben will.” **
Anatole France