Die Bewertungsfunktion

Beim Erstellen einer Bewertungsfunktion gibt es zwei gegensätzliche Optimierungsziele:

Präzision
Geschwindigkeit

Präzision ist wichtig, da man die Güte einer Position möglichst exakt berechnen möchte. Denn schliesslich soll der Spieler immer den richtigen Zug spielen.
Jedoch ist eine exakte Berechnung aller wichtigen Gütemerkmale oft viel zu langsam und man kann nur wenige Züge in die Zukunft blicken. Dies bewirkt, dass man vielleicht den besten Zug für in 4 Zügen gefunden hat, jedoch passiert in 6 Zügen etwas katastrophales und man verliert das Spiel.
Deshalb werden gute Spieler versuchen den Spielbaum möglichst tief zu analysieren und dabei nur eine möglichst gute Abschätzung der Güte einer Position zu finden. Folgende Auflistung ist eine kurze Erläuterung der hier aufgeführten Prinzipien.

Die Greedy-Strategie

Diese Strategie bewertet eine Situation einfach nach der Steindifferenz zum Zeitpunkt der Auswertung. Da das Ziel bei Reversi mehr Steine als der Gegner zu haben ist, klingt dies durchaus vernünftig. Eure kurzen Tests werden jedoch ergeben, dass diese Bewertung nur für eine Situation taugt, bei der beide Spieler keinen gültigen Zug mehr haben (beispielsweise wenn alle Felder belegt sind oder ein Spieler keine Steine mehr hat).

Stabile Steine

Anders als generell Steine zu zählen, lohnt es sich jedoch die Anzahl Steine zu maximieren welche vom Gegner nicht mehr gedreht werden können. Dies sind zumeist Steine die neben einem eigenen Eckstein liegen oder neben einem Stein liegen der neben einem eigenen Eckstein liegt oder ... (die Rekursion könnt ihr selbst zu Ende führen).
Jedoch sind dies nicht alle möglichen Situationen für stabile Steine, weswegen eine schnelle Bewertung der stabilen Steine wohl nur eine untere Schranke findet...

Statische Positionsbewertung

Eine einfache Bewertung des Spielfeldes wird einfach jedem Feld einen Wert zuweisen (davon gibt es mit allen Symmetrien 10 verschiedene, siehe Link oben) und wenn ein eigener Stein darauf liegt den Wert addieren und wenn es dem Gegner gehört den Wert subtrahieren.
Beispielsweise ist die Ecke super, das Feld diagonal neben der Ecke sehr schlecht (ausser uns gehört die Ecke), die anderen beiden Felder neben der Ecke auch schlecht, aber weniger als das diagonale, usw..

Anzahl möglicher Züge aka Mobilität

Generell gilt, dass wir möglichst viele Züge zur Auswahl haben wollen. Können wir nämlich aus vielen Zügen aussuchen, haben wir eher die Möglichkeit (zukünftige) schlechte Züge zu vermeiden. Eine Mobilitätsgüte kann beispielsweise durch die Differenz der eigenen und gegnerischen möglichen Züge erstellt werden.

Inverse Greedy-Strategie

Diese etwas unintuitive Bewertung einer Situation ist auch ein relativ gutes Mass für Mobilität. Da es eigentlich bis zum Ende des Spieles kaum einen Vorteil hat mehr Steine als der Gegner zu besitzen versucht man einfach die Anzahl eigener Steine zu minimieren. Schliesslich kann mir niemand die Steine wegnehmen, die gar nicht mir gehören! Zudem bedeutet wenig Steine zu besitzen auch, dass der Gegner wahrscheinlich nur wenige Züge zur Verfügung hat.

Grenzsteine

Viele Grenzsteine zu besitzen bedeutet, dass der Gegner viele potentielle Züge hat. Somit wollen wir die Anzahl Steine, die an leere Felder angrenzen minimieren oder alternativ die Anzahl leeren Felder die an eigene Steine angrenzen möglichst klein halten.
Wer lieber maximiert, kann auch die Anzahl eingeschlossener Steine zählen.

Parität

Diese Güte ist vor allem am Ende des Spieles relevant. Grundsätzlich will man selbst den letzten Stein aufs Brett setzen, da alle gedrehten Steine sicher nicht mehr zurückgedreht werden können. Dies ist ein strategischer Vorteil für den zweiten Spieler.
Unterteilt man das Spielfeld in die vier zu den Ecken gehörenden Gebiete, versucht man selbst möglichst immer den letzten Stein in das jeweilige Gebiet zu setzen und ultimativ dann den letzten Stein aufs Brett. Diese Güte hilft vorallem bei der Beschleunigung der Endspielsuche.

Patterns

Patterns wurden als Mischung zwischen Güte und Geschwindigkeit einer Bewertungsfunktion entwickelt. Die Grundidee ist, dass man eine grosse Menge an kompletten Spielen mit exaktem Endwert anhand vordefinierter Muster (Patterns) analysiert und dann je nach Konfiguration dieser Muster und dem Endresultat eine Schätzung bezüglich der Güte der Position abgeben will. Es stellt sich heraus, dass die Güte dieser Bewertungsfunktion sehr gut ist.
Wer sich dafür interessiert kann die Publikationen von M.Buro hier finden (Zeitaufwand der Implementierung inklusive Debugging ist sehr gross, dazu kommt die Generierung einer grosser Anzahl an Daten).

Implementierungsbeispiele

Auf der Seite habe ich einige Spieler hochgeladen, um die Unterschiede einiger Bewertungsfunktion in Kombination mit unterschiedlichen Optimierungen bezüglich der Alpha-Beta-Suche aufzuzeigen.
minimal.Player benutzt als Evaluierungsfunktion einfach eine Linearkombination einer Ecke mit seinen Nachbarn, der geschätzten Mobilität und der inversen Greedy-Strategie. Dazu wurde eine statische Positionsbewertung zur Zugvorsortierung verwendet.
miniBit.Player benutzt dieselbe Bewertungsfunktion, jedoch wurde ein effizientere Repräsentation des Spielfeldes gewählt. Dies erlaubt es mehr Züge pro Zeiteinheit abzuarbeiten. Zudem wird neben der statischen Bewertung nun auch eine möglichst kleine Anzahl Züge bei der Zugsortierung in Betracht gezogen (fastest first Strategie).
hashBit.Player, mtdfBit.Player und scoutBit.Player versuchen beide nun die totale Anzahl stabiler Steine besser abzuschätzen, minimieren die Anzahl Steine die neben leeren Feldern liegen und maximieren ihre Mobilität. Der Unterschied zwischen den beiden Spielern liegt in der verwendeten Alpha-Beta-Variante.