Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 | Suche | FAQ

Hauptmenü
myCSharp.de
» Startseite
» Forum
» Suche
» Regeln
» Wie poste ich richtig?

Mitglieder
» Liste / Suche
» Wer ist online?

Ressourcen
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Microsoft Docs

Team
» Kontakt
» Cookies
» Spenden
» Datenschutz
» Impressum

  • »
  • Community
  • |
  • Diskussionsforum
Welchen Algorithmus für dieses Spiel?
Hajoseb
myCSharp.de - Member

Avatar #avatar-2670.jpg


Dabei seit:
Beiträge: 315

Themenstarter:

Welchen Algorithmus für dieses Spiel?

beantworten | zitieren | melden

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
Attachments
"Zufall ist das Pseudonym Gottes, wenn er nicht selbst unterschreiben will.”
Anatole France
private Nachricht | Beiträge des Benutzers
TNDAri
myCSharp.de - Member

Avatar #avatar-2507.jpg


Dabei seit:
Beiträge: 139
Herkunft: Bremen

beantworten | zitieren | melden

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.
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von TNDAri am .
Gruss Ari
Wer lesen kann ist klar im vorteil!
MSDN
Dein Feund in allen fragen
private Nachricht | Beiträge des Benutzers
zommi
myCSharp.de - Member

Avatar #avatar-2617.png


Dabei seit:
Beiträge: 1380
Herkunft: Berlin

beantworten | zitieren | melden

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.
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von zommi am .
private Nachricht | Beiträge des Benutzers
TNDAri
myCSharp.de - Member

Avatar #avatar-2507.jpg


Dabei seit:
Beiträge: 139
Herkunft: Bremen

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
Bionic
myCSharp.de - Member



Dabei seit:
Beiträge: 216

beantworten | zitieren | melden

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

Vielleicht bringt dich das ein Stück weiter ;-)
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Bionic am .
.:: SilvrGame - Browsergame Development with Silverlight
.:: Bionic's blOg
private Nachricht | Beiträge des Benutzers
Kartoffel
myCSharp.de - Member



Dabei seit:
Beiträge: 27

beantworten | zitieren | melden

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)
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Kartoffel am .
private Nachricht | Beiträge des Benutzers
Hajoseb
myCSharp.de - Member

Avatar #avatar-2670.jpg


Dabei seit:
Beiträge: 315

Themenstarter:

beantworten | zitieren | melden

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
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Hajoseb am .
"Zufall ist das Pseudonym Gottes, wenn er nicht selbst unterschreiben will.”
Anatole France
private Nachricht | Beiträge des Benutzers
TNDAri
myCSharp.de - Member

Avatar #avatar-2507.jpg


Dabei seit:
Beiträge: 139
Herkunft: Bremen

beantworten | zitieren | melden

Zitat von Kartoffel
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
private Nachricht | Beiträge des Benutzers
Hajoseb
myCSharp.de - Member

Avatar #avatar-2670.jpg


Dabei seit:
Beiträge: 315

Themenstarter:

beantworten | zitieren | melden

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
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Hajoseb am .
"Zufall ist das Pseudonym Gottes, wenn er nicht selbst unterschreiben will.”
Anatole France
private Nachricht | Beiträge des Benutzers
Hajoseb
myCSharp.de - Member

Avatar #avatar-2670.jpg


Dabei seit:
Beiträge: 315

Themenstarter:

beantworten | zitieren | melden

Ähnliche Windows-Spiel:

Jawbeaker (ähnlich) für Windows
"Zufall ist das Pseudonym Gottes, wenn er nicht selbst unterschreiben will.”
Anatole France
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo Hajoseb,
Zitat
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.
Zitat
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
private Nachricht | Beiträge des Benutzers
Hajoseb
myCSharp.de - Member

Avatar #avatar-2670.jpg


Dabei seit:
Beiträge: 315

Themenstarter:

beantworten | zitieren | melden

Zitat von herbivore
Hallo Hajoseb,
Zitat
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*
Zitat von herbivore
Zitat
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
private Nachricht | Beiträge des Benutzers
zommi
myCSharp.de - Member

Avatar #avatar-2617.png


Dabei seit:
Beiträge: 1380
Herkunft: Berlin

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
Hajoseb
myCSharp.de - Member

Avatar #avatar-2670.jpg


Dabei seit:
Beiträge: 315

Themenstarter:

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
zommi
myCSharp.de - Member

Avatar #avatar-2617.png


Dabei seit:
Beiträge: 1380
Herkunft: Berlin

beantworten | zitieren | melden

by the way @ Hajoseb.

exponentielles Wachstum ist definiert als:
f(n) = a*e^(b*n)
Und da fällt deine Log-Trickserei eben nicht drunter
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo Hajoseb,
Zitat
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
private Nachricht | Beiträge des Benutzers
Hajoseb
myCSharp.de - Member

Avatar #avatar-2670.jpg


Dabei seit:
Beiträge: 315

Themenstarter:

beantworten | zitieren | melden

?( ?( ?(

Also eher eine Breitensuchen ...?
"Zufall ist das Pseudonym Gottes, wenn er nicht selbst unterschreiben will.”
Anatole France
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo Hajoseb,

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

herbivore
private Nachricht | Beiträge des Benutzers
ujr
myCSharp.de - Experte



Dabei seit:
Beiträge: 1770

beantworten | zitieren | melden

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?
private Nachricht | Beiträge des Benutzers
Hajoseb
myCSharp.de - Member

Avatar #avatar-2670.jpg


Dabei seit:
Beiträge: 315

Themenstarter:

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers