Damenproblem – mit genetischem Algorithmus lösen
Beim Damenproblem geht es um Schach! Auf einem Schachbrett soll man so viele Damen wie möglich positionieren, ohne dass sich diese schlagen können. Dieses schachmathematische Problem wurde schon bald von Programmierern aufgegriffen.
Damenproblem – mit genetischem Algorithmus lösen
Leistungsfähige Algorithmen für das Damenproblem benötigen mit steigender Größe des Schachbretts Supercomputer zur Lösungsfindung. Je nach Größe gibt es viele unterschiedliche Lösungen. Ziel ist es möglichst effektiv (schnell) alle Lösungen zu finden. Es gibt dabei viele Ansätze für einen Algorithmus.
Genetischer Algorithmus
Im Forschungsfeld der künstlichen Intelligenz sind genetische Algorithmen (auch evolutionäre Algorithmen) eine beliebte Technik um Probleme zu lösen. In diesem Beispiel lassen wir einen solchen Algorithmus eine zufällige Lösung zum Damenproblem finden.
Source Code
Die visuelle Darstellung wurde mit der ClanLib Engine gelöst, die Berechnung der Lösung in einem evolutionären Algorithmus. Den Source Code findet man auf meiner GitHub Seite zum Download. Beginnen wir wie schon bei der Sanduhr, dem Waldbrand oder den L-Systemen bei den globalen Variablen (globals.h):
#define POPULATION_SIZE 100 // size of initial population #define PARENTS 2 // parent count for pairing #define CHILDREN 2 // children count for pairing #define COPULATIONS_PER_EVOLUTION 5 // count pairing for each generation #define GENOM_SIZE 8 // size of genome #define MUTATION_GENERATION 10 // mutation rate for generations #define MIN 0 // min and max values of genome (size of chess field) #define MAX 7
MIN und MAX definieren die Größe des Schachbretts, standardmäßig wie angegeben 8×8. Den Wert kann man aber fast beliebig erhöhen. Die weiteren Konstanten beziehen sich auf die Implementierung des genetischen Algorithmus.
Basis dieses Algorithmus ist das Genom. In einem Feld werden 8 Integer Werte gespeichert, außerdem besitzt dieses Genom einen Fitnesswert.
int g[8]; int fitness;
Die 8 Felder repräsentieren die Positionen der Damen pro Spalte. Der Fitnesswert gibt an, wie gut diese Lösung ist, also wie viele der Damen sich gegenseitig schlagen (je weniger desto besser!).
Der Algorithmus
Der Algorithmus wird in einer Endlosschleife in der compute() Methode von app.cpp berechnet:
createPopulation(POPULATION_SIZE); // create population of given size evaluatePopulation(fitnesssum); // evaluate fitness function evolutePopulation(fitnesssum, generation%MUTATION_GENERATION == 0); // generate children, mutate if needed selectionOfPopulation();
Es wird so lange gesucht, bis eine Lösung mit korrektem Fitnesswert gefunden wurde. In Spielen werden solche Algorithmen aufgrund der geringen Zeit die Verfügbar ist (sonst ruckelt das Spiel) nach einer bestimmten max. Zeit abgebrochen und einfach das beste Ergebnis verwendet. So ist ein KI Gegner nicht perfekt, aber gut genug um realistisch zu wirken!
Die Berechnung im Detail:
- createPopulation
es wird eine Ausgangspopulation mit einer angegebenen Größe erstellt. Das sind POPULATION_SIZE viele zufällige Genome. - evaluatePopulation
für ein Genom wird der Fitnesswert ermittelt (+1 für jede Dame die keine andere schlägt). 28 ist die perfekte Lösung, keine Dame schlägt eine andere. Wie komme ich auf die Zahl? Die erste Dame kann max. 7 mal die anderen nicht schlagen. Die zweite 6, die dritte 5 usw. 7+6+5+4+3+2+1 = 28. - evolutePopulation
es wird eine bestimmte Menge (COPULATIONS_PER_EVOLUTION) an Genomen ausgewählt und daraus neue Kinder erstellt. - selectionOfPopulation
die Population wird anhand der Fitness Werte sortiert und die schlechtesten danach aus der Liste entfernt
Dieses einfache Beispiel zeigt sehr schön wie evolutionäre Algorithmen funktionieren. Es wird eine zufällige Menge an Lösungen erstellt. In einer Schleife werden diese bewertet und zufällige Einzellösungen miteinander kombiniert. Die schlechtesten Lösungen sterben und werden entfernt. Mit jedem Schleifendurchlauf sollte man näher an die optimalen Lösung kommen.
Die render() Funktion zeichnet nur die weißen Feldern, weil der Bildschirm schwarz initialisiert wird. Sofern sich auf dem Feld eine Dame befinden wird die queen.png Grafik gezeichnet. Da wir Schachbretter unterschiedlicher Größen darstellen können wird das Image vor dem zeichnen noch mit set_size() skaliert.
Weiterentwicklung
Aktuell kann das Programm Boards unterschiedliche Größe Darstellen. Bei der Berechnung von Feldern größer oder kleiner 8×8 wird meist ein Ergebnis geliefert, dieses ist aber nicht korrekt. Gerne darf der genetische Algorithmus so geändert werden, damit er auch bei dynamischer Größe des Schachbretts noch ein korrektes Ergebnis liefert. Gerne dürft ihr mir so eine Lösung zur Veröffentlichung schicken, ansonsten müsst ihr warten, bis ich dafür irgendwann Zeit habe…
Fazit
Das Damenproblem kann man mit einem genetischen Algorithmus lösen. Das ist das einfachste Beispiel für evolutionäre Algorithmen die ich im Zuge der Lehrveranstaltung künstlicher Intelligenz gelernt habe. Es werden noch weitaus komplexere Programme folgen. Dran bleiben!
Welche andere einfache Probleme könnt ihr mit einem genetischen Algorithmus lösen? Wer kennt den optimalsten Algorithmus zum Damenproblem?
