Benutzer-Werkzeuge

Webseiten-Werkzeuge


wiki:engine

Schachengine

Schach ist sowohl aufgrund seiner Beliebtheit, als auch wegen seiner Komplexität ein interessantes Untersuchungsobjekt in der Informatik. Schach umfasst schätzungsweise $10^{10^{50}}$ \footnote{Shanon zeigte, dass die untere Grenze bei $10^{120}$ Spielen liegt.\cite{Shanon50}} mögliche Partien mit etwa $10^{40}$ Endzuständen, was die Anzahl der Atome im Universum übertrifft (Schätzungsweise: $10^{80}$). Folglich können anhand von Schach Datenstrukturen und Algorithmen untersucht werden, die diese Datenmengen beherrschen oder aber derart „vereinfachen“ , dass sie ein effizientes Handling ermöglichen.

Eigenschaften von Schach-Spielbäumen

Schach zählt zu den endlichen Zwei-Personen-Nullsummenspielen mit vollständiger Information \footnote{Die Schachregeln geben klar an, dass es nur endlich viele Züge geben kann, andernfalls wird anhand der Regeln über Remis oder Matt entschieden.}. Wobei Nullsummenspiele sich dadurch definieren, dass die Summe der Gewinne und Verluste immer Null ergeben. Der Begriff vollständige Information besagt in diesem Rahmen, dass theoretisch alle möglichen Züge einer Schachpartie in einer Baumstruktur (Spielbaum) abgebildet werden können. In diesem Spielbaum repräsentiert jeder Knoten eine konkrete Spielstellung \footnote{Also die konkrete Anordnung der Spielfiguren auf dem Spielfeld und den hierdurch resultierenden erlaubten Folgezügen}. Weiterhin muss der Spielbaum die Eigenschaft erfüllen, dass jeder Kindknoten genau einen Vaterknoten hat, da sich die Folgezüge immer aus einer konkreten Stellung entwickeln. Wenngleich verschiedene Ausgangsstellungen zu gleichen Folgestellungen führen können.
Der Spielbaum besteht aus einem Wurzelelement, das die aktuellen Spielsituation enthält, und davon ausgehend sind die Kanten zu den Knoten, die jeweiligen Zugmöglichkeiten. Alle Knoten können in Ebenen eingeteilt werden, die einer der beiden Spielparteien zugeordnet werden können, da die ziehenden Parteien sich nach jedem Halbzug abwechseln. Diese Anordnung entspricht den Halbzügen im Schachspiel.
Die Blätter des Baumes sind die finalen Stellungen, die ein Unentschieden oder den Gewinn/Verlust einer Partie darstellen. Für den Fall, dass der Baum nur bis in eine bestimmte Tiefe entwickelt wird und die Knoten keine terminalen Stellungen beinhalten, werden die Knoten mit heuristischen Werten der jeweilige Spielstellung befüllt und werden dann ebenfalls als Blätter des Baumes betrachtet.

Komponenten von Schachalgorithmen

Die Grundelemente eines jeden Schachprogramms sind der Zuggenerator und die Bewertungsfunktion. Der Zuggenerator erzeugt die Züge und legt diese in einer Baumstruktur ab. Die Bewertungsfunktion trägt dafür Sorge, dass die generierten Züge, welche die Spielstellung in den Blättern des Baumes sind, korrekt bewertet werden. Da, wie oben beschrieben, die Anzahl der Züge in einem Schachbaum sehr groß werden kann, wird für die Bewertung oftmals ein heuristische Verfahren eingesetzt. Dadurch kann der Baum statt bis in die Blätter, d.h. Knoten deren Ausgang nur Matt (Gewinn/Verlust) oder Remis enthalten darf, auch bis in eine vorher festgelegte Tiefe berechnen. In diesem Fall werden die Stellungen des Spielbretts bestimmt und die daraus resultierenden Werte in die Blätter bzw. Knoten eingetragen.

Zusätzlich verfügen viele Schachengines über Spielbücher, wie etwa Eröffnungsbücher. Zumeist werden diese durch Datenbanken realisiert, die bekannte Schachstellungen parat halten. Darüber hinaus verfügen mittlerweile fast alle Schachprogramme über graphische Interfaces, Netzwerk- oder Internetanbindung und einige andere Komfortfunktionen.

Schachengine

GriSchas Schachengine befindet sich im Paket de.htw.grischa.chess, es liegt momentan keine Trennung von Schachlogik und Verteilung vor. Es wird separat auf beide Teile eingegangen, wenngleich unterschiedliche Zuständigkeitsbereiche manchmal in einer Klasse realisiert worden sind. Das Paket de.htw.grischa.chess besteht aus Folgende Klassen:

  • AlphaBetaSearch
    • AlphaBetaSearchFixedDepth
    • AlphaBetaSearchGridResults
    • IterativeAlphaBetaSearch
  • Chessboard
  • ComputedGame
  • DistributedSearch
  • GameList
  • GamesState
  • GridGameManager
  • IChessGame
  • Player
  • Quality

Die Klassendiagramme können auf der beiliegenden CD gefunden werden. Ebenfalls exis- tiert ein Java-Doc auf dem Projekt-Server unter https://grischa.f4.htw-berlin.de/ javadoc/.

Wichtige Klassen der Schachengine

GriScha setzt als Schachalgorithmus das Alpha-Beta-Pruning ein. Dies wird durch die abstrakte Klasse AlphaBetaSearch.java, sowie deren Ausprägungen realisiert. Alle Grundfunktionalitäten sind in der abstrakten Klasse AlphaBetaSearch.java implementiert. Der wesentliche Algorithmus ist als Pseudo-Code im Listing zu sehen. Die Klasse IterativeAlphaBetaSearch.java nutzt einen iterativen Ansatz des Alpha-Beta-Algorithmus, wodurch ein „iterative deepeing“ erreicht wird. Abbildung .8 verdeutlicht den Ablauf des iterativen Alpha-Beta-Algorithmus.

function AlphaBeta(node, depth, alpha, beta, maximizingPlayer)
  if depth = 0 or node is a terminal node then
    return the heuristic value of node
  end if
  if maximizingPlayer then
    v := visits MAXVALUE
    for each child of node do
      v := max(v, alphabeta(child, depth -1, alpha, beta, FALSE))
      alpha := max(alpha, v)
      if beta ≤ alpha then
        break(beta-cutoff)
      end if
    end for
    return v
  else
    v := visits MINVALUE
    for each child of node do State v := max(v, alphabeta(child, depth -1, alpha,beta, TRUE))
      beta := min(beta, v)
      if beta ≤ alpha then
        break(alpha-cutoff)
      end if
    end for
  return v
end if
end function

Die Klasse AlphaBetaSearchGridResults.java kümmert sich um die Ergebnisse der WNs und speichert diese in Form eines Rot-Schwarz-Baums ab (durch java.util.TreeMap realisiert). Der genutzte Rot-Schwarz-Baum ist als Key-Value-Store umgesetzt. So wird als Schlüssel die Schachstellung in Form von Strings genutzt. Die zu den Stellungen gehörigen Werte (Qualität) sind durch Integer hinterlegt. Durch Nutzung eines Rot-Schwarz-Baums können die wichtigen Operation – Suchen, Einfügen, Löschen – in $\mathcalO(log(n))$ garantiert durchgeführt werden (s. Cormen et al. [CLRS13, S. 311ff]). Die Klasse Chessboard.java beinhaltet sowohl den Zuggenerator, als auch die Funktionalitäten für das Spielbrett. Demnach sorgt diese Klasse für die Erzeugung der nächsten Züge, als auch der beidseitigen Übersetzung von Schachstellungen zwischen String und dem ChessBoard-Format GriSchas. Eine ausführliche Beschreibung der Brettdarstellung in Form eines Bitboards findet sich in [Hei11, S. 8] 1 . Die UML-Diagramme sind in Abbildung 6, sowie Abbildung 7 zeigen die Funktionalitäten der Klasse ChessBoard.java und machen den Umfang dieser Klasse deutlich.

Die Klasse Quality.java übernimmt die Funktion der Bewertung der Spielstellungen. Das heißt, sie bewertet ein gegebenes Schachbrett aufgrund der vorliegenden Anordnung der Spielsteine. Aussagen über die Güte einzelner Schachzüge erfolgt durch Summation alle Werte. Dabei wird über ein gegebenes Schachbrett Feld für Feld iteriert und sämtliche Figuren auf deren Position innerhalb des Schachbretts, der Angriffsmöglichkeiten bzw. ob sie angegriffen werden untersucht. Entsprechend werden Werte ermittelt, die die eben genannten Faktoren einbezieht. Die aufsummierte Qualität spiegelt die Güte der Spielstellung wieder (je größer der Wert, desto besser die Stellung). In GriScha wurde die Qualitätsfunktion relativ einfach gehalten, da der Fokus auf die Verteilungsaspekte gelegt wurde.

Verteilungsalgorithmik

Die Klasse ComputedGame.java sorgt für die Persistierung der bereits berechneten Schachbretter, samt Qualität, Tiefe und Feldanordnung. Darüber hinaus implementiert sie die equals-Methode, sodass bereits persistierte Spiele gefunden werden können. Die Abbildungen .2 und .2 zeigen die entsprechende UML-Diagramme.

Die Funktionalität der Klasse DistributedSearch.java umfasst die Suche im Spielbaum nach Spielstellungen, das Einsammeln berechneter Spielstellungen von den Grid-Nodes. Weiterhin wurde hier die Aufteilung des Workloads unter den vorhanden Worker-Nodes, einschließlich einer lokalen Aufteilung via Threads realisiert. Auch hier wurde für die Speicherung der Ergebnisse ein Rot-Schwarz-Baum in Form einer Java-TreeMap genutzt. Die Klasse GameList.java verwaltet die Liste der im Alpha-Beta-Algorithmus berechneten Spiele vom Typ ComputedGame der Klasse ComputedGame.java in Form einer Java-ArrayList. Zugriffe sind hier durch Setter-/ Getter-Methoden realisiert. Durch eine bool‘sche Abfrage kann nach bereits vorhanden Spielen in der Liste gesucht werden. Die Enumeration GameState.java enthält die möglichen Spielzustände: LEGAL, ILLEGAL,MATT,DRAW. Sinn ist es zu zeigen, ob eine vorliegendes Spielbrett erlaubt ist, ein Matt vorliegt oder ein Remis.

Die Klasse GridGameManager.java wird im Zuge der While-Schleife der Klasse WinboardCommunication.java aufgerufen und sorgt für den Informationsfluss zwischen Schachlogik auf der Master-Node und dem User-Interface, sodass die aktuelle Spielstellung abgearbeitet werden kann. Diese Klasse wird durch die Klasse WinboardCommunication.java aufgerufen. Das Interface IChessGame.java gibt als Schnittstelle die wichtigsten Methoden vor, die die von ihr abgeleiteten Klassen umsetzen müssen. Der Großteil der Schachlogik implementiert dieses Interface, da bestimmte Methoden immer wieder benötigt werden.

Kommunikation

GriScha ist eine verteilte Echtzeitanwendung, die eine Grid-Computing Infrastruktur nutzt. In der initialen Version nutzte GriScha noch SIMON, wurde jedoch durch XMPP als Kommunikationsprotokoll abgelöst. GriScha unter Nutzung von XMPP wurde durch Redis abgelöst. In der vorliegenden Arbeit wird die Lösung mit Redis genutzt. SIMON ist eine Protokoll für objektorientierte entfernte Objektaufrufe (remote procedure call (rpc)). Extensible Messaging and Presence Protocol (XMPP) ist ein Messaging-Protokoll unter Nutzung von Extensible Markup Language (XML). Redis ist eine NoSQL-Datenbank, die über ein Publish-Subscribe-Pattern Kommunikation ermöglicht. Die wesentliche Architektur der Kommunikation kann in [Ste14, S. 20ff] nachverfolgt werden. Abbildung 3.1 zeigt eine vereinfachte Architektur des Lösungsansatzes. Abbildung 3.2 zeigt den Ablauf der Kommunikation via Redis.

wiki/engine.txt · Zuletzt geändert: 14/02/2018 19:41 von bt