Kombinatorik-Problem: Zeichen in 2-dimensionalem Array miteinander kombinieren

[Hagen Reddmann]

Ich dachte mir schon das diese Frage kommen wird <br>
Also beim Scrabble gibt es bestimmte Regeln
<li>die Buchstaben haben unterschiedliche Punktezahl, erreiche die höchste Punktezahl pro Wort indem schon gelegte hohe Buchstaben oder Wörter benutzt werden
<li>die Positionen auf dem Brett sind unterschiedlich gewichtet
<li>für das Leeren des Racks gibts 50 Punkte extra
<li>lege nur gültige Wörter, was wir ja schon können
<li>negiere alle obigen regeln und wende diese auf den Gegner an, d.h. zerstöre dessen Chancen

Dies sollten die Ziele des Scrabble Algortihmus sein. Soviel ich weiß nutzt der beste Scrabble Algorithmus einen Genetischen Algo. + ein DAWG. Beim Scrabble entstehet eine enorme Kombinationsvielfalt und man such EINE hochwahrscheinlich optimale Lösung. Der Vorteil liegt beim Computer, d.h. ein guter Scrabblealgo. wird den Menschen immer vernichtend schlagen. Das liegt daran das der Computer
<li>objectiv ist
<li>die Wahrscheinlichkeiten der noch verfügbaren Buchstaben im Sack exakt berechnen kann
<li>ein enorm größeren Wortschatz haben wird

Die genetische Algos. sollte man sich als ca. 50 Computer-Scrabble Spieler vorstellen, unsere Individuen. Alle Individuen zusammen sind unserer Population, und die Nachkommen dieser Individuenen sind unsere Generationen. Ausgehend von einem schon teilweise gefüllten Board berechnet man als erstes die Wahrscheinlichkeiten der Buchstaben die noch nicht gelegt wurden. Diese Häufigkeiten minus die Buchstaben auf dem Computerrack sind unser Basis um die Suche in der Wortliste einzuschränken. D.h. sollte das Y schon liegen brauchen wir keinerlei Wörter mit Y zu berücksichtigen. Nun werden die Individuen initialisiert. Sie sollten das Board representieren, dann wird per Zufall ein Zug in diesen Individuen ausgeführt. Dieser kann sein
<li>EIN Buchstabe und man überprüft nur ob ein mögliches Wort existiert, d.h. unser gen. Algo. arbeitet Zeichenorientiert
<li>oder EIN Wort, das natürlich in's Board passen muß, unser Algo. arbeitet dann Wortorientiert.
Man läst nun diese 50 Individuen einige Runden gegeneinander antreten und ermittelt das beste. Der erste Zug den dieses Individuum gemacht hat wird der nächste Zug des Computerspielers.

Nungut, am besten Du suchst mal im WEB, ich meine da mal was gelesen zu haben.

Gruß Hage

[spectrumizer]

Klingt kompliziert, aber auch echt interessant. An solche Auswüchse hätte ich garnich gedacht, als ich angefangen hab ... lol *g*
Ich google mal. tHx nochmal für deine Hilfe

Grüße,
Mari

[spectrumizer]

Hallöle!

Hab gestern mal gegoogelt nach genetischen Algorithmen, bin auch auf einiges gestoßen. Mal sehen, ob ich mich durcharbeite, weil is ja recht kompliziert; ich hab mir gestern Abend über dem Einschlafen nämlich nochmal nen Kopf gemacht, wie man das mit dem Computer nen bisschen einfacher lösen könnte ... Was hältst du davon:

Zur Zeit hab ich die Auflösung der Buchstaben auf dem Spielfeld zu Worten so gelöst, dass er erst Horizontal die gelegten Buchstaben erfasst und dann vertikal und überprüft, ob die schon in ner Liste vorhanden sind und bei Bedarf darin aufnimmt. Funktioniert auch bisher ohne Probleme auch bei verschachtelten Worten.

Von dieser Basis aus kann ja auch der Computer starten. Er weiss über die Liste, dass schon die und die Worte auf dem Spielfeld liegen und kann anhand der Buchstaben auf dem Rack daraus neue kombinieren und sich das Wort raussuchen, was die meisten Punkte bringt. Aber da wären wir wieder bei dem Kombinatorikproblem angelangt, da er ja von RackBuchstabe1 + WORT bis RackBuchstabe1 + RackBuchstabe2 + ... + RackBuchstabeN + WORT und ja auch WORT + RackBuchstabe1 + ... + RackBuchstabeN kombinieren muss.
Kann man dafür deinen DAWG einsetzen? Wenn ja, wie? *g*

Grüße, Mario :

[Dr.med.Bernhard Schwabe]

Hi

Könnte es an dieser Stelle sinnvoll sein, auf Silbenebene weiter zu arbeiten? (oder zumindest Ausgrenzungen vorzunehmen)

gruß
bernhar

[Hagen Reddmann]

Dies ist relativ schwierig, und eine Zerlegung der Wörter in Silben bringt uns nicht weiter, da wir im Anschluß darauf wieder überprüfen müssen ob es Wörter zu den Silben gibt. Zudem liegen auf dem Rack Buchstaben und keine Silben, was dazu führt das wir eben auch Silben zu Buchstaben suchen müssten.<br>
Die Wortsuche ist sehr eng verküpft mit dem Board. Ich würde es also so machen: Das Board wird analysiert, und alle möglichen Wortpositonen in vertikaler+horizontaler Richtung werden als "Objecte" erzeugt. Nun hat man eine Liste der möglichen Wortposition + in jedem Object die Gewichtung der Boardposition + die schon gelegten Buchstaben auf dem Brett. Alle nicht besetzten Position in diesen Objecten werden mit Wildcards versehen. Nun muß der Dawg Such algo. so abgewandelt werden das er zu jedem dieser Wort-Objecte alle möglichen Wörter im Dawg raussucht indem er die Wildcard Positionen durch die Buchstaben ergänzt.<br>
Z.b. wird ein Object erzeugt mit 'A?G????????????' -> daraus wird 'A?G*' und daraus -> 'A' + ?=['A','H','J','L','M','O','Z'] + 'G' + *=['A','H','J','L','M','O','Z']. D.h. die Sets stellen das Rack des Players dar.<br>
Ich halte diese Wort-Objecte die aus der Analyse des Grids entstehen für den wichtigsten Schritt. Zu jedem dieser Objecte wird die maximale Punktzahl die es während der Teil-Suche erreicht gespeichert. Man muß nun mehrmals drüber-rechnen um die abschließende Wortkombination zu finden die die meisten Punkte ergeben.<br>
Zu einer Position auf dem Board können also viele solcher Wort-Objecte entstehen, deshalb ist es wichtig das diese Wortobjecte direkt mit dem Board verknüpft sind. Wird z.B. ein Wortobject mit einem gefundenen Wort befüllt, dann muß es auch ins Board eingetragen werden damit die überschneidenden Wortobjecte an deren Buchstabenpositionen den neuen Buchtstaben enthalten. Wird nun eines diese Objecte bearbeitet enthält es schon die aktuell gültige Buchstabenmaske.<br>
Vieleicht sollte meine TDawg.SearchCombinatoric() umgeändert werden, oder besser noch das ganz Dawg. Also du erzeugts ein Zeichenmapping, das die alphabetischen Buchstaben in eine neue Reihenfolge ummappt. Diese neue Reihenfolge IST die Wichtung der Buchtsaben nach Scrabbleregeln + Häufigkeit der Buchstaben. Nun werden alle Wörter in dieses TDawg eingelesen und somit nach Wichtung laut Scrabble sortiert. Ein Suchalgo wird nun die Wörter mit den höchsten Punkten als erstes finden. Wurde also eine vollständige Lösung im Dawg gefunden, dann könne wir die Suche beenden da es kein andere Lösung mit höherer Punktzahl im Dawg geben kann. Wir durchsuchen das Dawg ja immer in sortierter Reihenfolge, bestimmt die Punktzahl die Sortierung im Dawg, so haben wir eine wesentlich höherer Wahrscheinlichkeit die besten Worte zu erst zu finden.<br>

Gruß Hage

[Hagen Reddmann]

<pre>

<code><font size=2 face="Courier New"><i>// Zeichen,Punkte,Anzahl
</i>Q= 10,1
Y= 10,1
X= 8,1
Ö= 8,1
J= 6,1
V= 6,1
Ä= 6,1
&Uuml;= 6,1
C= 4,2
F= 4,2
K= 4,2
P= 4,1
M= 3,4
B= 3,2
W= 3,1
Z= 3,1
H= 2,4
G= 2,3
L= 2,3
O= 2,3
E= 1,15
N= 1,9
S= 1,7
I= 1,6
R= 1,6
T= 1,6
U= 1,6
A= 1,5
D= 1,4
<br>
?= 0,2
<br>
<b>const
</b>Scrabble: PChar = 'QYXÖJVÄ&Uuml;CFKPMBWZHGLOENSIRTUAD';
<br>
<b>var
</b>AlphaToScrabble: <b>array</b>[Char] <b>of </b>Char;
ScrabbleToAlpha: <b>array</b>[Char] <b>of </b>Char;
Mapping: TDawgMapping;
<br>
<b>procedure </b>InitScrabbleMapping;
<b>var
</b>I: Integer;
C: Char;
<b>begin
</b>FillChar(AlphaToScrabble, SizeOf(AlphaToScrabble), 0);
FillChar(ScrabbleToAlpha, SizeOf(ScrabbleToAlpha), 0);
FillChar(Mapping, SizeOf(Mapping), 0);
C := 'A';
<b>for </b>I := 0 <b>to </b>Length(Scrabble) -1 <b>do
begin
</b>AlphaToScrabble[Scrabble[I]] := C;
ScrabbleToAlpha[C] := Scrabble[I];
<br>
Mapping[Scrabble[I]] := C;
<br>
Inc(C);
<b>end</b>;
<b>end</b>;
</font>
</code></pre&gt

[Hagen Reddmann]

So oben mal der Code fürs Mapping der Buchstaben nach Wichtung und Häufigkeit. Eines ist noch nicht berücksichtig, die Häufigkeit der Buchstaben im Dawg wenn deren Werte/Anzahl gleich ist. Z.B "I,R,T,U" habe ich nach Gefühl angeordnet. Beser ist es aber das deutsche Dawg per TDawg.SymbolCount() die Häufigkeit der Buchstaben zu ermitteln und dann "I,R,T,U" usw. danach zu sortieren.<br>

Intern solte das Scrabble also immer mit Wörtern arbeiten die angepasst wurden, und nur das Userinterface = Display,Rack,Sack sollte eine Konvertierung von/nach Scrabblesortierung vornnehmen. Dies geht einfach:

<pre>

function WortToScrabble(const Wort: String): String;
var
I: Integer;
begin
Setlength(Result, Length(Wort));
for I := 1 to Length(Wort) do
Result[I] := AlphaToScrabble[Wort[I]];
end;<br>

function ScrabbleToWort(const Wort: String): String;
var
I: Integer;
begin
Setlength(Result, Length(Wort));
for I := 1 to Length(Wort) do
Result[I] := ScrabbleToAlpha[Wort[I]];
end;<br>

</pre>

Das TDawg sollte mit Dawg.SetMapping(Mapping, ...) auf diese Sortierung eingestellt werden, und dann mit dem originalen Deutsch.dawg gefüllt werden. Danach wurden alle Wörter nach Scrabblehäufigkeit+Wichting sortiert im Dawg. Die Suche mit Dawg.Search(), .SearchCombinatic() so wie sie jetzt ist würde aber korrekt suchen, sprich ein Mapping vornehmen. D.h.
<li> Dawg.Search('HAUS*') würde tatsächlich die konvertierten Scrabblewörter die mit Haus beginnen finden.
<li> um von einem Scrabblewort ausgehend zu suchen muß das Mapping des Dawgs zurückgesetzt werden, oder die Such-Methoden umgeschrieben werden müssen so das keinerlei Mapping intern durchgeführt wird.

Gruß Hage

[Hagen Reddmann]

Übrigens, die Mail sit nicht bei mir angekommen <br>

Da das Rack nur 7 Buchstaben enthält brauchen wir nur Wortobjecte aus dem Board heraus zu erzeugen die minimal 1 + 7 Buchstaben lang sind. D.h. z.B. der erste Buchstaben liegt schon auf dem Board und die 7 anderen sollten mit denen aus unserem Rack befüllt werden. Nun vergibt man diesen Wortobjekten eine Punktzahl nach der Punktzahl der Boardposition. D.h. es werden alle Position aufsummiert die z.b. 2/3 fachen Wortwert, 2,3 fachen Buchstabenwert ergeben. Dabei solltest du aber die Entfernung von einem schon gelegten Buchstaben mit berücksichtigen. D.h. je kürzer die Entfernung zu einem 2,3 fachen Wortfeld ist je höher sollte der Gesammtpunktwert des Wortobjectes werden. Danach wird diese Liste nach dieser Punktzahl sortiert. Die Wortobjecte mit höchster Punktzahl zu erst. Danach beginnt die Suche im Dawg.<br>Innerhalb dieser Suche werden die besten gefundenen Wörter eingetragen und somit das temporäre Board aktualisiert. Die Wortobjecte die sich mit dem aktuell befüllten Wortobjecte überschneiden werden in deren Punktzahl neu berechnet und in der Liste entsprechend ihrer Wertigkeit verschoben. Damit bekommen sie ein höherer Priorität in iherer Abarbeitung.<br>
So, um die Sache aber effizient zu gestalten, sprich wir haben eine enorme Kombinationsvielfalt die uns nicht erlaubt ALLE möglichen Kombinationen durchzurechnen, wird die Erzeugung der Wortlist beschränkt. Man sagt z.B. -> Fülle Wortliste, solange weniger als 100 Wortobjecte drinnen sind immer hinzufügen, ansonsten sortiert einfügen und letztes (101'tes) Wort löschen.<bR>
Alles läuft auf einen "Priority-Stack" hinaus. Das Gleiche gilt dann auch für die Suche der Wörter zu einem Wortobject im Dawg. Eine Liste der gefundenen Wörter wird gefüllt. Diese Liste ist z.B. 10 Wörter lang und man fügt nach Punktzahl sortiert alle gefundenen Wörter zur Suchmaske dort hinein. Zum Schluß wird das erste Wort der Liste ausgewählt. Diese Suche kann selber wieder beschränkt werden. Sprich suche maximal 100 Wörter und füge sie in eine Liste mit maximal 10 beste Wörte ein. Im Weiteren Schritt wird das nächste Wortobject ausgewählt und genauso verfahren. Sollte es sich mit irgendeinem schon gesuchtem Wortobjecte überschneiden, müsste man dann eine Kombination dieser 10 gefundenen Wörter mit den 10 gefundenen Wörtern des überschneidenen Wortobjectes berechnen. Du siehst, die Anzahl der möglichen Kombinationen die überprüft werden müssen steigt enorm an.<br>
Deshalb mein Hinweis auf genetische Algortihmen. Das ganze Scrabbleproblem ist NP kompliziert. D.h. es hat die höchste vorstellbare Komplexität zu einer Lösung, sprich es wird niemals vollständig lösbar sein wenn das Board bestimmte Größen erreicht hat.<br> Ein gen. Algo. kann aber eine enorm optimale Lösung finden.

Gruß Hagen

PS: Man muß sagen das Scrabble ein sehr anspruchsvolles Problem darstellt. Also gib bitte nicht vorzeitig auf. Das was Du dabei lernen kannst sind Sachen die Du als normaler Anwendungsentwickler NIE lernen wirst. Am wichtigsten dürfte dabei sein das dur lernst effizient Algortihmen zu finden, sie umzusetzen und auf Grundlage von wissenschaftlichen Methoden zu optimieren. Dies ist das komplette Gegenteil vom Pixelbashing, HTML Code schreiben oder Komponenten verschieben

[spectrumizer]

Hallo Hagen!

Sorry, dass ich solange nich geantwortet hab, aber ich glaub, ich komm im Moment und wohl auch in nächster Zeit nicht dazu, an dem Projekt weiterzuarbeiten. Es ist n Privatprojekt und ich hab jetz "arbeitstechnisch" n Haufen zu tun bekommen, so dass das erstma bis auf unbestimmte Zeit warten muss. :P

Danke dir auf jeden Fall für deine kompetente fachgerechte Hilfe! Weiter so

Grüße, Mari