Einzelnen Beitrag anzeigen

Amateurprofi

Registriert seit: 17. Nov 2005
Ort: Hamburg
1.039 Beiträge
 
Delphi XE2 Professional
 
#3

AW: Kombinatorik - Index von Kombinationen

  Alt 11. Nov 2017, 00:07
@Michael II

Danke für deine Hilfe, deine "indexvon" Funktion liefert korrekte Ergebnisse ist aber nicht so ganz das, was ich suche.
Warum:
Die Funktion arbeitet mit 2 Schleifen und braucht bei etwas größerem N einfach zu lange.
Vielleicht habe ich meine Frage zu allgemein gestellt, deshalb etwas präziser und etwas Hintergrundinfo. Sorry, wird etwas langatmig.

Ich hatte vor vielen Jahren ein Programm geschrieben das u.a. Endspieltabellen für Schach erstellen kann, allerdings nur für einige wenige Endspiele, in der Regel 4-Steiner, und als einzige 5-Steiner Tabelle für das Endspiel König und 2 Springer gegen König und Bauer.

Ich möchte jetzt Tabellen für alle 3, 4, 5 und später eventuell 6 Steiner erstellen.
Es gibt ja frei zugängliche 6-Steiner Tabellen (www.shredderchess.de) oder auch 7-Steiner (google play store - leider nur übers Smartphone), aber die kann ich nicht in ein eigenes Programm einbinden und, wichtiger, mir geht’s ums "machen", nicht ums "nutzen".

Das Problem bei der Erstellung ist weniger der Algorithmus sondern mehr die Größe der Tabellen.

Die Größe der Tabelle für ein bestimmtes Endspiel hängt ja davon ab, wieviel verschiedene mögliche Stellungen existieren.

Bei einem 5-Steiner kann man im ersten Schritt von 64^5 = 1,073,741,824 Stellungen ausgehen.
Die erste Optimierung ist, dass man nicht alle Stellungen betrachtet sondern nur solche bei denen der weiße König im Dreieck A1-D1-D4 steht, bzw. im Rechteck A1-D1-D8-A8, wenn Bauern im Spiel sind und bei denen die Könige nicht auf benachbarten Feldern stehen.
Das reduziert die Anzahl der möglichen Stellungen der beiden Könige von 4096 auf 564 bzw. auf 1806.

Eine weitere Optimierung ist möglich, wenn eine Partei 2 oder mehr gleiche Figuren hat.
Dann kann man davon ausgehen, dass immer die erste der Figuren auf dem "niedrigsten" Feld steht und die letzte auf dem "höchsten".
Bei zum Beispiel 3 gleichen Figuren kann dadurch die Anzahl der möglichen Stellungen für diese 3 Figuren von 64^3 = 262,144 auf (64 über 3) = 41,664 reduziert werden.

Alle diese Optimierungen reduzieren die die Größe der Tabelle für z.B. das Endspiel König + 3 Springer gegen König von 64^5 = 1,073,741,824 Bytes auf 564*(64 über 3) = 23,498,496 Bytes.

Allerdings braucht man eine schnell arbeitende Funktion für die Ermittlung der Indizes von Kombinationen, denn diese Funktion wird milliardenfach aufgerufen.
Na klar kann man das auch sehr schnell mit Tabellen machen, und das ist das, was ich zur Zeit mache, aber spätestens bei 6-Steinern (was Kombinationen der 4ten Klasse bedeutet) wird es eng mit dem Speicherplatz.

Vielleicht fällt dir ja bei der geänderten Fragestellung (Kombinationen mit 64 Elementen zur 3ten Klasse) etwas ein.
Gruß, Klaus
Die Titanic wurde von Profis gebaut,
die Arche Noah von einem Amateur.
... Und dieser Beitrag vom Amateurprofi....
  Mit Zitat antworten Zitat