Schach in einer Datenbank

[Blackbird++]

Hallo,

ich möchte eine Datenbank für Schach-Züge entwerfen, die sehr groß werden wird.

Da eine Stellung durch verschiedene Züge erreicht werden kann, ist es sinnvoller, die Stellungen zu speichern.

Um dem ganzen einen Sinn zu verleihen, soll mit jeder Stellung das durchschnittliche Ergebnis gespeichert werden, also ein Durchschnitt der durchschnittlichen Ergebnisse der darauf folgenden möglichen Stellungen. Das ganze muss man sich in einer Art Baumstruktur vorstellen, an dessen Ende immer das Ergebnis steht, mit dem eine Schachpartie der entsprechenden Zugfolge geendet hätte.

Ich stelle mir das so vor, dass der Client eine bestimmte Stellung bekommt, durch einen kleinen Algorithmus alle möglichen Folgestellungen berechnet und die Qualität dieser Folgestellungen dann in der Datenbank nachschlägt.

Dadurch könnte dann die Qualität aller möglichen Züge verglichen werden und der beste Zug herausgefunden werden.

Das Problem bei der Sache ist die Menge der möglichen Stellungen, die allerdings noch niemand ausgerechnet hat.

Mich würde jetzt interessieren, wie man eine Stellung im Schach möglichst platzsparend, aber eindeutig als Wertepaar mit dem durchschnittlichen Ergebnis speichert!

Als Infos, für die weniger Schach-bewanderten:

Ein Brett hat 64 Felder (8x8)

Es gibt 16 weiße und 16 schwarze Figuren.

Es gibt 6 verschieden Figur-Typen, die sich in der Zug-Art unterscheiden.

Und jedes Bit, das beim Speichern der Stellung eingespart wird, kann entscheidend sein.

Ich wäre sehr dankbar für ein paar Anregungen. Ich habe mit solchen Kleinlichkeiten bezüglich des benötigten Speicherplatzes in Datenbanken nämlich noch überhaupt keine Erfahrungen.

Mfg., Blackbird++

[flashpixx]

Ob es sich lohnt eine Datenbank dafür aufzubauen, ist evtl zu hinterfragen. Gerade für dieses Spiel würde sich Minimax-Algorithmus ? Wikipedia lohnen.

Letztendlich ist, das was Du mit Deiner Datenbank realisieren willst, eine Speicherung der Ergebnisse des Minimax Algorithmus bis zu einer gewissen Tiefe. Eine Speicherung in einer Datenbank ist somit nicht sinnvoll, da man anstatt alle Spielstellungen vor zu halten, diese direkt mit einer gute Heuristik berechnen kann.

[streffin]

Ich will nichtmal anfangen grob zu schätzen was das in GB wäre.

So oder so, ich würde das nicht mit einer relationalen DB speichern, die Stellungen.

WENN dann würd ich da dann über eine Objektorientierte Datenbank nachdenken.

Aber auch dem würd ich wenig Chancen auf "sinnvoll" einräumen.

Du hättest einfach eine gigantische Menge von Daten. Und, die Gewinnchance, musst du zum anlegen der Datenbank so oder so erstmal komplett durchrechnen, für ALLE möglichen Konstellationen. Da rödelt dein Rechner eine verdammt lange Weile (da denke ich eher in Jahren / Jahrzenten als in Wochen) würde ich vermuten.

Bearbeitet 29. Juni 2010 von streffin

[Blackbird++]

Ich wäre auch für eine Objektorientierung, aufgrund der logischen Baumstruktur. Damit man die Gewinnwahrscheinlichkeit am Ende leicht wieder zurückrechnen kann.

Die tatsächliche Durchführung steht natürlich noch auf einem ganz anderen Blatt.

Aber die eigentliche Frage ist ja erstmal, in welcher Form man die Stellungen möglichst platzsparend speichert.

[flashpixx]

Aber die eigentliche Frage ist ja erstmal, in welcher Form man die Stellungen möglichst platzsparend speichert.

Da es sich letztendlich um einen Graph handelt, würde ich eine Adjazezmatrix vorschlagen und ggf diese entweder so so speichern, dass man pro Matrix direkt mehrere Figuren speichert oder eben die Matrix als sparse Matrix für eine Figur speichert

Der Sinn ist trotzdem nicht klar, denn wenn ich eine gute Heuristik anwenden kann, warum soll ich dann überhaupt alle (!) Möglichkeiten speichern. Eine Heuristik kombiniert mit einer Speicherung, das wäre schon sinnvoll, wobei man nach einem Spiel, die Heurisitik analysiert und versucht dann nachträglich diese weiter zu optimieren

Bearbeitet 30. Juni 2010 von flashpixx

[Blackbird++]

Ich bin grad auf ne Seite gestoßen, natürlich mal wieder zu spät... :upps

Hier, ChessProgramming, der passende Artikel und sogar einen passenden Wikipedia-Artikel. Ich werd mich da mal durchlesen, vermutlich ist die Frage danach schon gelöst...

Wenn jemand trotzdem noch Ideen hat, bin ich natürlich sehr dankbar...

Mfg. Blackbird++