(SS16-07) Mensch aergere ... (OpenMPI)

Aus Verteilte Systeme - Wiki
Wechseln zu: Navigation, Suche

Inhaltsverzeichnis

ToDo

Projekt Beschreibung

Gruppe/Mitglieder

Gruppe 7:

  • Dobrotka, Matus
  • Lietz, Jan

Erwartete Ergebnisse

  1. Einarbeitung in Open MPI
  2. Einarbeitung in die Mensch_ärgere_dich_nicht-Regeln und Spielstrategien. Recherche verteilter Spielsimulationen.
    1. Datei:Mpi-prasentation.pdf
    2. Datei:Präsentation madN Analyse.pdf
  3. Konzept für die verteilte Simulation eines Mensch_ärgere_dich_nicht-Spiels mit lokalen grafischen Benutzerschnittstellen
  4. Implementierung dazu
  5. Analyse von Spielszenarien
  6. Bewertung
  7. Wiki-Seite zum Projekt, fortgeschrieben nach Projektfortschritt
  8. Vortrag zu den erarbeiteten Grundlagen und Abschlusspräsentation mit Demo

Grundlagen (M.D.)

Open MPI

OpenMPI Installation für Java

Vorstellung

MPI (bzw. Message-Passing Interface) ist eine Bibliothek, die eine gleichnamige Spezifikation für die Unterstützung der parallelen Auflösung der Berechnungsproblemen in Computer-clusters implementiert. Es handelt sich konkret um eine Schnittstelle für die Anwendungsentwicklung - API, die auf einen Nachrichtenaustausch zwischen einzelnen Knoten basiert. Es geht sowohl um die Punkt-zu-Punkt Nachrichten als auch um die globale Operationen. Diese Bibiliothek unterstützt Shared-Memory Architekturen und auch Distributed-Memory Architekturen. MPI basiert hauptsächlich auf das Nachrichtenaustausch parallele Programmiermodel, in dem Daten aus dem Addressraum von einem Prozess in einen Addressraum von einem anderen Prozess durch kooperative Operationen an jedem Prozess verschoben werden.

MPI ist keine Sprache und alle MPI Operationen werden als Funktionen, Subroutinen oder Methoden nach den entsprechenden Sprachbindungen augedrückt, die ein Teil von MPI Standard sind. Der Standard wurde von einer Gemeinschaft von Parallel-Computing-Verkäufern, Computerwissenschaftlern und Anwendungsentwicklern durch einen offenen Prozess definiert. Am häufigsten gibt es Implementierungen von MPI in C, C++, Java, Python und Fortran. Bei dem Entwurf der ganzen Schnittstellen hat man immer den Akzent vor allem auf die Leistung, Skalierbarkeit und Tragbarkeit gelegt. Die Bibliothek eignet sich für solche Anwendungen, wo die Geschwindigkeit des Laufes von Anwendungen entscheidend ist (was aber typisch für parallele Systeme ist).


Ziel der Message-Passing Interface ist einfach ein weit verbreiteter Standard für das Schreiben der Message-Passing Programmen zu entwickeln. Komplette Liste der Ziele:

  • Design eine Anwendungs-Programmierschnittstelle (API)
  • Effiziente Kommunikation erlauben: Das Memory-to-Memory Kopieren vermeiden, Überlappung der Berechnung und Kommunikation ermöglichen, und Offload von Koprozessoren-Kommunikation, wo es verfügbar ist.
  • Ermöglichen der Implementierungen, die in einem heterogenem Umfeld verwendet werden können.
  • Geeignete C und Fortran Bindungen für die Schnittstelle erlauben
  • Annehmen eine zuverlässige Kommunikationsschnittstelle: Benutzer muss nicht mit Kommunikationsstörungen bewältigen. Solche Störungen werden von dem zugrundeliegendem Kommunikationssubsystem behandelt.
  • Eine Schnittstelle definieren, die auf vielen Lieferanten-Plattformen implementiert werden kann, mit keinen bedeutsamen Änderungen in der zugrundeliegenden Kommunikation und System-Software
  • Die Semantik der Schnittstelle sollte sprachunabhängig sein.
  • Die Schnittstelle sollte so gestaltet werden, um eine Thread-Sicherheit zu ermöglichen.


Der Standard enthält:

  • Punkt-zu-Punkt Kommunikation
  • Datentypen
  • Kollektive Operationen
  • Prozessgruppen
  • Kommunikationskontexten
  • Prozesstopologien
  • Umweltmanagement und Anfrage
  • Das Info Objekt
  • Prozesserstellung und Management
  • Einseitige Kommunikation
  • Externe Schnittstellen
  • Parallele Datei I/O
  • Sprachbindungen für Fortran und C
  • Werkzeugunterstützung


Der Standard spezifiert aber keine:

  • Operationen, die mehr Betriebssystemunterstützung erfördern, als derzeit üblich
  • Werkzeuge für den Programmaufbau
  • Debugging facilities



Punkt-zu-Punkt Kommunikation

Die Sendung und der Empfang der Nachrichten von Prozessen ist der grundlegende MPI Kommunikationsmechanismus. Die grundlegenden Punkt-zu-Punkt Kommunikationsoperationen sind send und receive. Die elementarste Art der Kommunikation findet zwischen zwei Prozessen statt: ein Sendeprozess übermittelt dabei Informationen an einen Empfangsprozess. Zu jeder send-Operation muss eine passende receive-Operation existieren. Da in parallelen Anwendungen die bloße Reihenfolge der Abarbeitung von Operationen nicht immer ausreichend ist, bietet MPI zusätzlich den tag-Parameter an – nur wenn dieser Wert bei send- und receive-Operation identisch ist, dann passen beide zusammen. Diese Operationen können entweder blockierend oder nicht blockierend sein.

Blockierende Operationen

MPI_Send

Per MPI_Send Befehl wird eine Nachricht an einen Prozess gesendet, Dieser Befehl ist blockierend und wartet bis die Nachricht erfolgreich gesendet wurde.

   #include <mpi.h>
   int MPI_Send(const void *buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm)

Input Parameters

  • buf: Initial address of send buffer (choice).
  • count: Number of elements in send buffer (nonnegative integer).
  • datatype: Datatype of each send buffer element (handle).
  • dest: Rank of destination (integer).
  • tag: Message tag (integer).
  • comm: Communicator (handle).

MPI_Recv

Per MPI_Recv Befehl wird eine Nachricht aus der EingangsQueue geholt. Dieser Aufruf ist blockierend, also die Operation blockiert, bis die Nachricht vollständig empfangen wurde. Für den nicht blockierenden Aufruf siehe MPI_Irecv.

   #include <mpi.h>
   int MPI_Recv(void* buf, int count, MPI_Datatype datatype, int source, int tag, MPI_Comm comm, MPI_Status *status)

Input Parameters

  • count: Number of elements in receive buffer (integer).
  • datatype: Datatype of each receive buffer element (handle).
  • source: Rank of source or MPI_ANY_SOURCE (integer).
  • tag: Message tag or MPI_ANY_TAG (integer).
  • comm: Communicator (handle).

Output Parameters

  • buf: Initial address of receive buffer (choice).
  • status: Status object (Status).

Nichtblockierende Operationen

Manchmal kann man höhere Programm-Effizienz erreichen, wenn man Kommunikation mit Berechnung überlappt und Wartezeiten, die synchronisationsbedingt sind, vermeidet. Deshalb enthält der Standard auch nichtblockierende Kommunikation, bzw. nichtblockierende Operationen. Es gibt die Operationen, die lediglich angestoßen werden. Außerdem gibt es verschiedene Funktionen, die aufgerufen werden muss, um solche Operationen zu beenden. Beim Starten der Operation wird ein Request-Objekt erzeugt. Mit Hilfe dieses Objektes kann auf die Beendigung dieser Operation geprüft (gewartet) werden.

MPI_Isend

Per MPI_Isend Befehl wird eine Nachricht an einen Prozess gesendet, Dieser Befehl ist nicht blockierend, den Status der Anfrage kann per Befehl MPI_Test und dem request Objekt geholt werden. Alternativ kann per MPI_Wait Befehl auf das Beenden des Sendens gewartet werden.

   #include <mpi.h>
   int MPI_Isend(const void* buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm, MPI_Request *request)

Input Parameters

  • buf: Initial address of send buffer (choice).
  • count: Number of elements in send buffer (nonnegative integer).
  • datatype: Datatype of each send buffer element (handle).
  • dest: Rank of destination (integer).
  • tag: Message tag (integer).
  • comm: Communicator (handle).

Output Parameters

  • request: Communication request (handle).

MPI_Irecv

Per MPI_Irecv Befehl wird eine Nachricht aus der EingangsQueue geholt. Dieser Aufruf ist nicht blockierend, den Status der Anfrage kann per Befehl MPI_Test und dem request Objekt geholt werden. Alternativ kann per MPI_Wait Befehl auf das Beenden des Revices gewartet werden.

   #include <mpi.h>
   int MPI_Irecv(void* buf, int count, MPI_Datatype datatype, int source, int tag, MPI_Comm comm, MPI_Request *request)

Input Parameters

  • count: Number of elements in receive buffer (nonnegative integer).
  • datatype: Datatype of each receive buffer element (handle).
  • source: Rank of source or MPI_ANY_SOURCE (integer).
  • tag: Message tag or MPI_ANY_TAG (integer).
  • comm: Communicator (handle).

Output Parameters

  • buf: Initial address of receive buffer (choice).
  • request: Communication request (handle).

Kollektive Operationen

In parallelen Anwendungen kann oft solche Situation eintreten, dass mehrere (bzw. alle) Prozesse die gleiche Task ausführen müssen. Dazu dienen u.a. folgende Operationen für kollektive Kommunikation, die MPI-Standard enthält. Kollektive Kommunikation wird als solche Kommunikation definiert, die eine Gruppe oder Gruppen von Prozessen beinhaltet. Außer der regulären Kommunikationsoperationen gibt es noch vektorbasierte Varianten (zum Beispiel MPI_Gatherv).

Broadcast

MPI_Bcast verteilt eine Nachricht vom Prozess mit Rank root an alle Prozesse (inkl. selbst), die zu der Gruppe gehören. Das Bild rechts stellt Broadcast schematisch dar.

   #include <mpi.h>
   int MPI_Bcast(void* buffer, int count, MPI_Datatype datatype, int root, MPI_Comm comm)
Broadcast from one member to all members of a group in MPI

Input parameters

  • buffer - starting address of buffer (choice)
  • count - number of entries in buffer (non-negative integer)
  • datatype - data type of buffer (handle)
  • root - rank of broadcast root (integer)
  • comm - communicator (handle)

Output parameters

  • buffer - starting address of buffer (choice)

Gather

Diese Operation kann man sich wie das Einsammeln der Daten aller beteiligten Prozessen vorstellen. Darstellung dieser Operation bietet das rechte Bild an.

   #include <mpi.h>
   int MPI_Gather(const void* sendbuf, int sendcount, MPI_Datatype sendtype, void* recvbuf, 
                  int recvcount, MPI_Datatype recvtype, int root, MPI_Comm comm)
Gather data from all members of a group to one member in MPI

Input parameters

  • sendbuf - starting address of send buffer (choice)
  • sendcount - number of elements in send buffer (non-negative integer)
  • sendtype - data type of send buffer elements (handle)
  • recvcount - number of elements for any single receive (non-negative integer, significant only at root)
  • recvtype - data type of recv buffer elements (significant only at root) (handle)
  • root - rank of receiving process (integer)
  • comm - communicator (handle)

Output parameters

  • recvbuf - address of receive buffer (choice, significant only at root)

Scatter

Der Vorgang der Scatter-Operation beschreibt das Streuen (Verteilen) von Daten eines Prozesses an alle Prozesse, die zu der Gruppe gehören.

   #include <mpi.h>
   int MPI_Scatter(const void* sendbuf, int sendcount, MPI_Datatype sendtype, void* recvbuf, 
                   int recvcount, MPI_Datatype recvtype, int  root, MPI_Comm comm)
Scatter data from one member to all members of a group in MPI

Input parameters

  • sendbuf - address of send buffer (choice, significant only at root)
  • sendcount - number of elements sent to each process (non-negative integer, significant only at root)
  • sendtype - data type of send buffer elements (significant only at root) (handle)
  • recvcount - number of elements in receive buffer (non-negative integer)
  • recvtype - data type of receive buffer elements (handle)
  • root - rank of sending process (integer)
  • comm - communicator (handle)

Output parameters

  • recvbuf - address of receive buffer (choice)

Allgather

Bei dieser Operation geht es um eine Variante von Gather-Operation, in der alle Prozesse der Gruppe die gleichen Daten empfängen.

Andere Sicht: Jeder Prozess sendet an jeden anderen Prozess dieselben Daten. Das rechte Bild stellt den Vorgang dieser Operation dar.

   #include <mpi.h>
   int MPI_Allgather(const void* sendbuf, int sendcount, MPI_Datatype sendtype, void* recvbuf, 
                     int recvcount, MPI_Datatype recvtype, MPI_Comm comm)
A variation on Gather where all members of a group receive the result in MPI

Input parameters

  • sendbuf - starting address of send buffer (choice)
  • sendcount - number of elements in send buffer (non-negative integer)
  • sendtype - data type of send buffer elements (handle)
  • recvcount - number of elements received from any process (nonnegative integer)
  • recvtype - data type of receive buffer elements (handle)
  • comm - communicator (handle)

Output parameters

  • recvbuf - address of receive buffer (choice)

All to all

Diese Operation kann man sich auch wie den Gesamtaustausch vorstellen. Bei dieser Operation werden Daten zwischen allen Prozessen ausgetauscht. Nur der i-te Teil des Sendebuffers wird an den i-ten Prozess gesendet. Daten von dem Prozess mit dem Rank j werden entsprechend an j-ter Stelle im Empfangsbuffer gespeichert. Den Vorgang dieser Operation illustriert das Bild rechts.

   #include <mpi.h> 
   int MPI_Alltoall(const void* sendbuf, int sendcount, MPI_Datatype sendtype, void* recvbuf, 
                    int recvcount, MPI_Datatype recvtype, MPI_Comm comm)
Scatter/Gather data from all members to all members of a group (also called complete exchange) in MPI

Input parameters

  • sendbuf - starting address of send buffer (choice)
  • sendcount - number of elements sent to each process (non-negative integer)
  • sendtype - data type of send buffer elements (handle)
  • recvcount - number of elements received from any process (nonnegative integer)
  • recvtype - data type of receive buffer elements (handle)
  • comm - communicator (handle)

Output parameters

  • recvbuf - address of receive buffer (choice)

Reduce

Per MPI_Reduce Befehl lässt sich ein Reduce-Pattern auf die Knoten in comm verteilen. Es kann entweder eine vordefinierte oder User-erstellte Funktion auf die Daten angewendet werden.

   #include <mpi.h>
   int MPI_Reduce(const void* sendbuf, void* recvbuf, int count, MPI_Datatype datatype, MPI_Op op, int root, MPI_Comm comm)

Input Parameters

  • sendbuf - Address of send buffer (choice).
  • count - Number of elements in send buffer (non-negative integer).
  • datatype - Data type of elements of send buffer (handle).
  • op - Reduce operation (handle).
  • root - Rank of root process (integer).
  • comm - Communicator (handle).

Output Parameters

  • recvbuf - Address of receive buffer (choice, significant only at root).

Kommunikatoren

Ein Kommunikator spezifiziert einen Kommunikations-Kontext für eine Kommunikations-Operation. Jeder Kommunikations-Kontext bietet ein separates Kommunikations-Universum an: die Nachrichten werden immer in dem Kontext empfangen, in dem sie gesendet wurden und die Nachrichten, die in unterschiedlichen Kontexten gesendet wurden, beeinflussen sich nicht. Der Kommunikator spezifiziert auch die Menge der Prozessen, die diesen Kommunikations-Kontext teilen. Diese Prozess-Gruppe ist geordnet und die Prozesse werden durch ihren Rank innerhalb dieser Gruppe identifiziert.

Mit anderen Worten, ein Kommunikator ist eine Welt der Gruppe der kommunizierenden sequentiellen Prozessen. Die Prozesse können nicht außerhalb eines Kommunikatores kommunizieren.


Vordefinierte Kommunikatoren:

  • MPI_COMM_WORLD - eine Weltgruppe
  • MPI_COMM_SELF - eine Gruppe mit einem Mitglied, mir selbst
  • MPI_COMM_PARENT - ein Inter-Kommunikator zwischen zwei Gruppen: meiner Weltgruppe und einer Gruppe von meinem Parent

Ein Kommunikator wird als eine Prozess-Gruppe mit einem Kontext repräsentiert. Das wird von folgendem Bild illustriert.

Prozess-Gruppen und Kommunikatoren:
a) Prozess-Gruppe von MPI_COMM_WORLD
b) Nach dem Hinzufügen eines Kontextes = MPI_COMM_WORLD Kommunikator
c) Prozess-Gruppe von MPI_COMM_SELF
d) Nach dem Hinzufügen eines Kontextes = MPI_COMM_SELF Kommunikator


MPI bietet zwei Arten von Kommunikatoren an. Es gibt sowohl Inter-Kommunikatoren als auch Intra-Kommunikatoren. In folgendem Bild wird die Aufteilung der Kommunikatoren in MPI und auch die entsprechende Kommunikations-Möglichkeiten für jede Kommunikators-Art dargestellt.

Überblick und Aufteilung der Kommunikatoren in MPI


Unterschied zwischen Inter- und Intra-Kommunikatoren

Intra-Kommunikation

Intra-Kommunikation ist eine Kommunikation zwischen den Prozessen, die die Mitglieder der gleichen Gruppe sind. Der Kommunikator, der in dieser Kommunikation verwendet wird, heißt Intra-Kommunikator.

Inter-Kommunikation

Inter-Kommunikation ist eine Punkt-zu-Punkt-Kommunikation zwischen den Prozessen in unterschiedlichen Gruppen. Der Kommunikator, der in dieser Kommunikation verwendet wird, heißt Inter-Kommunikator. Die Gruppe mit dem Prozess, der eine Inter-Kommunikations-Operation initiiert, heißt die "lokale Gruppe". Das heißt - der Sender in Send-Operation und der Empfänger in Receive-Operation. Die Gruppe mit dem Zielprozess heißt die "Remote-Gruppe". Das bedeutet - der Empfänger in Send-Operation und der Sender in Receive-Operation. Der Zielprozess wird durch ein (Kommunikator, Rank)-Paar spezifiziert, wie in der Intra-Kommunikation. Im Gegensatz zu der Intra-Kommunikation ist der Rank relativ zu der zweiten Remote-Gruppe.


Ein Unterschied zwischen diesen beiden Kommunikators-Arten stellt das Bild rechts dar.


Verbindungs-Operationen

MPI_Comm_accept

Per MPI_Comm_accept Befehl wird auf einen entfernten MPI-Prozess gewartet sich mit den lokalen MPI-Prozess zu verbinden. Der entfernte MPI-Process muss dafür MPI_Comm_connect aufrufen.

   #include <mpi.h>
   int MPI_Comm_accept(const char *port_name, MPI_Info info, int root, MPI_Comm comm, MPI_Comm *newcomm)

Input Parameters

  • port_name: Port name (string, used only on root).
  • info: Implementation-dependent information (handle, used only on root).
  • root: Rank in comm of root node (integer).
  • comm: Intracommunicator over which call is collective (handle).

Output Parameters

  • newcomm: Intercommunicator with client as remote group (handle)

MPI_Comm_connect

Per MPI_Comm_connect Befehl wird sich der lokale MPI-Prozess mit einen Entfernten-MPI-Prozess verbinden. Der Server muss dafür MPI_Comm_accept aufgerufen habe.

   #include <mpi.h>
   int MPI_Comm_connect(const char *port_name, MPI_Info info, int root, MPI_Comm comm, MPI_Comm *newcomm)

Input Parameters

  • port_name: Network address (string, used only on root).
  • info: Implementation-dependent information (handle, used only on root).
  • root: Rank in comm of root node (integer).
  • comm: Intracommunicator over which call is collective (handle).

Output Parameters

  • newcomm: Intercommunicator with server as remote group (handle)

MPI_Intercomm_merge

Diese Funktion erstellt einen Intra-Kommunikator newintracomm aus der Vereinigung der beiden Gruppen, die mit dem Inter-Kommunikator intercomm verbunden sind. Den Vorgang dieser Funktion illustriert das Bild unten.

   #include <mpi.h>
   int MPI_Intercomm_merge(MPI_Comm intercomm, int high, MPI_Comm *newintracomm)

Input parameters

  • intercomm - Inter-communicator (handle)
  • high - (logical)

Output parameters

  • newintracomm - new intra-communicator (handle)


Vor(a) und nach(b) dem Aufruf der Funktion MPI_Intercomm_merge

Analyse

benötigte Funktionen

  • Andere Spieler finden
  • Reihenfolge Festlegen
  • Züge kommunizieren
  • TimeOuts / Disconnects berücksichtigen
  • Züge Berechnen.


bestehende Analysen


Mensch_ärgere_dich_nicht Regeln

Material

  • 1 Spielbrett
  • 1 Sechs-Seitiger-Würfel
  • per Spieler
    • 4 Figuren
    • 10 Spielfelder, davon 1 Startfeld (A-Position)
    • 4 Start-Positionen (B-Position)
    • 1 Haus bestehend aus 4 Feldern

Regeln:

Jeder Spieler nimmt 4 Spielfiguren einer Farbe; eine davon kommt auf das A-Feld der jeweiligen Farbe, die restlichen auf die gleichfarbigen B-Felder. Au- ßerdem braucht man noch einen Würfel. Wer die höchste Zahl würfelt, fängt an; gespielt wird im Uhrzeigersinn. Wer dran ist, würfelt einmal und zieht seine Figur vor. Und zwar, um so viele Felder in Pfeilrichtung, wie der Würfel Punkte zeigt. Eigene und fremde Figuren können übersprungen werden, zählen aber mit. Wer mehrere Figuren „draußen“ hat, kann sich aussuchen, mit welcher er läuft. Auf jedem Feld darf immer nur eine Figur stehen. Landet man also mit dem letzten Punkt seines Würfels auf einem besetzten Feld, „wirft“ man diese Figur raus – sie kommt auf das B-Feld ihrer Farbe – und stellt sich selbst auf deren Platz. Aufpassen: Es herrscht kein Schlagzwang! Eigene Figuren können nicht geschlagen werden, in diesem Fall muss der Spieler mit einer anderen Figur ziehen. Solange noch Figuren auf dem B-Feld stehen, muss das dazugehörende A-Feld immer sofort freigemacht werden. Denn würfelt man eine Sechs, muss eine B-Feld-Figur sofort aufs A-Feld der gleichen Farbe gesetzt werden. Ist das noch von einer anderen eigenen Figur besetzt, wird diese erst mit der Sechs weitergezogen; eine fremde Figur wird rausgeworfen. Außerdem wird bei einer Sechs nach dem Ziehen gleich noch mal gewürfelt. Hat man eine Sechs und keine Figur mehr auf den BFeldern, zieht man mit einer beliebigen seiner Figuren auf der Laufbahn sechs Felder weiter. Dann erst noch mal würfeln. Wer einmal eine Runde um den Spielplan gedreht hat, zieht seine Figur auf die Zielfelder seiner Farbe. Auch diese zählen beim Vorrücken einzeln; Figuren können übersprungen werden. Wer mit einer Sechs seine letzte Figur ins Ziel bringt, braucht nicht noch einmal zu würfeln. Der Erste, der alle seine Figuren ins Ziel gebracht hat, gewinnt. Die anderen spielen um die nächsten Plätze weiter.

Wahrscheinlichkeit von Ereignissen

Würfel-Wahrscheinlichkeit
1 1/6
2 1/6
3 1/6
4 1/6
5 1/6
6 1/6

Wahrscheinlichkeit das alle 4 Figuren auf dem Spielfeld sind

  1. Wahrscheinlich von eine 6 zu würfeln: p = 1 / 6
  2. Im schnitt benötigte Anzahl an Versuchen eine 6 zu Würfeln: 1 / p => 1 / (1 / 6) => 6
  3. Alle 4 Figuren auf dem Feld zu haben: alle 6 Zuge eine weitere Figur ins Feld => 24 Züge um alle 4 Figuren im Spielfeld zu haben


Feld nach X mal Ziehen

Wahrscheinlichkeit das eine Figur um Y Felder vor gerückt ist bei X mal ziehen (6 wird als 0 Felder gerückt betrachtet , da diese eine neue Figur ins spiel bringt)

Feld Zug 1 Zug 2 Zug 3 Zug 4 Zug 5
1 16,67% 21,30% 22,61% 22,91% 22,98%
2 16,67% 23,61% 26,16% 26,91% 27,10%
3 16,67% 25,93% 30,04% 31,51% 31,96%
4 16,67% 28,24% 34,22% 36,73% 37,61%
5 16,67% 30,56% 38,66% 42,56% 44,11%
6 0,00% 13,89% 23,86% 29,31% 31,79%
7 0,00% 11,11% 22,22% 29,24% 32,85%
8 0,00% 8,33% 19,79% 28,23% 33,11%
9 0,00% 5,56% 16,49% 26,04% 32,23%
10 0,00% 2,78% 12,23% 22,40% 29,83%
11 0,00% 0,00% 6,94% 17,00% 25,43%
12 0,00% 0,00% 4,63% 13,83% 22,89%
13 0,00% 0,00% 2,78% 10,58% 19,81%
14 0,00% 0,00% 1,39% 7,48% 16,34%
15 0,00% 0,00% 0,46% 4,76% 12,77%
16 0,00% 0,00% 0,00% 2,70% 9,46%
17 0,00% 0,00% 0,00% 1,54% 6,86%
18 0,00% 0,00% 0,00% 0,77% 4,66%
19 0,00% 0,00% 0,00% 0,31% 2,94%
20 0,00% 0,00% 0,00% 0,08% 1,70%
21 0,00% 0,00% 0,00% 0,00% 0,90%
22 0,00% 0,00% 0,00% 0,00% 0,45%
23 0,00% 0,00% 0,00% 0,00% 0,19%
24 0,00% 0,00% 0,00% 0,00% 0,06%
25 0,00% 0,00% 0,00% 0,00% 0,01%


Wahrscheinlichkeit das eine Figur um Y Felder vor gerückt ist bei X mal ziehen (inklusive 6, welche als ein Zug gilt)

Feld Zug 1 Zug 2 Zug 3 Zug 4 Zug 5
1 16,67% 16,67% 16,67% 16,67% 16,67%
2 16,67% 18,98% 18,98% 18,98% 18,98%
3 16,67% 21,30% 21,73% 21,73% 21,73%
4 16,67% 23,61% 24,88% 24,96% 24,96%
5 16,67% 25,93% 28,40% 28,70% 28,71%
6 16,67% 28,24% 32,23% 32,96% 33,03%
7 0,00% 16,67% 22,45% 23,89% 24,08%
8 0,00% 13,89% 22,26% 24,70% 25,14%
9 0,00% 11,11% 21,40% 25,22% 26,10%
10 0,00% 8,33% 19,79% 25,19% 26,74%
11 0,00% 5,56% 17,36% 24,38% 26,85%
12 0,00% 2,78% 14,03% 22,56% 26,16%
13 0,00% 0,00% 9,72% 19,47% 24,37%
14 0,00% 0,00% 6,94% 17,43% 23,69%
15 0,00% 0,00% 4,63% 14,93% 22,52%
16 0,00% 0,00% 2,78% 12,15% 20,84%
17 0,00% 0,00% 1,39% 9,30% 18,68%
18 0,00% 0,00% 0,46% 6,61% 16,17%
19 0,00% 0,00% 0,00% 4,32% 13,51%
20 0,00% 0,00% 0,00% 2,70% 10,98%
21 0,00% 0,00% 0,00% 1,54% 8,49%
22 0,00% 0,00% 0,00% 0,77% 6,22%
23 0,00% 0,00% 0,00% 0,31% 4,28%
24 0,00% 0,00% 0,00% 0,08% 2,75%
25 0,00% 0,00% 0,00% 0,00% 1,65%
26 0,00% 0,00% 0,00% 0,00% 0,92%
27 0,00% 0,00% 0,00% 0,00% 0,46%
28 0,00% 0,00% 0,00% 0,00% 0,20%
29 0,00% 0,00% 0,00% 0,00% 0,07%
30 0,00% 0,00% 0,00% 0,00% 0,01%

Schlagwahrscheinlichkeit

Abhängigkeit von Spieleranzahl

  • wird öfters geschlagen?
  • Spieldauer?
  • Komplexität bei der Berechnung
  • Spielplan wird wie aussehen
    • identische Feldanzahl per Spieler?
    • weniger Felder?


Globale Strategien

Random (Zufällige Figur bewegen)

Move First (Weiteste Figur zuerst bewegen)

  • Bei Dieser Strategie geht es darum seine Spielfigur möglich schnellst ins Haus zu bringen.
  • Dazu wird versucht immer die am weitesten Figur zu bewegen.


Vorteile

  • Figur kommt recht schnell ins Haus und damit in Sicherheit
  • Figur verbleibt kurz möglich auf dem Feld, wodurch weniger Chancen gibt sie zu schlagen.

Nachteile

  • Wartezeit bis du eine weitere Figur ins Spiel bringst.

Move Last (Hinterste Figur zuerst bewegen)

  • Bei Dieser Strategie geht es möglich alle seine Figuren als eine Gruppe zu bewegen.
  • Dazu wird immer die Hinterste Figur bewegt, damit sie allmählich alle aufeinander aufrücken.


Vorteile

  • Wenn eine Gegnerische Figur vor deiner Gruppe ist hat man mehr Möglichkeiten sie zu schlagen.

Nachteile

  • Die Steine sind möglichst lange auf dem Feld, wodurch eine höhere Wahrscheinlich besteht das sie geschlagen werden.
  • Wenn eine Gegnerische Figur von Hinten kommt hat seine eine Größere Schanze einen Stein aus der Gruppe zu schlagen

Aggressiv (schlagen bevorzugt)

  • Hier geht es darum möglich viele gegnerische Figuren zu schlagen.

Vorteile

  • Gegner verliert Figuren, die er dann erst wieder ins Spiel bringen muss.

Nachteile

  • Es kann sein das dadurch die eigene Figur in Gefahr gerät geschlagen zu werden.
  • Es Kann sein das man eine eigene Figur nicht aus einer Gefahrensituation wegzieht

Cautious


Defensiv (Eigene Figuren in Sicherheit ziehen bevorzugt)

  • Hier geht es möglich die Eigeneren Figuren sicher zu halten
  • Ds bedeutet Figuren außer der Gefahren/Schlag-Zone von Gegnerischen Figuren weg zu ziehen.

Vorteile

  • Eigene Figuren werden seltener geschlagen und damit vergeudet man keine Zeit die Spielfiguren ins Spiel zu bringen

Nachteile

  • Der Gegner hat die Selben Vorteile
  • Es gibt mehr gegnerische Spielfiguren


Strategien zur KI / Zug-Berechnung

Anhand der oben genannten Strategien ist ersichtlich das es Schlüssel-Parameter gibt für die Entscheidung welche Figur gezogen wird. Dies wären ob ich eine Figur schlagen kann, ob meine Eigene Figur in Gefahr ist und wie weit meine Figur auf dem Spielbrett ist.

Entfernung zum Ziel

Die Entfernung vom Startpunkt bzw. die Entfernung zum Ziel ist wichtig für Move First und Move Last, da man daran leicht sieht welche die vorderste und letzte Figur ist. Es ist ebenfalls wichtig die Entfernung von Gegnerischen Figuren zu ihren Ziel zu wissen, da Figuren mit viel Zurückgelegter Entfernung wichtiger sind zu schlagen. Je Weiter die Figur war desto mehr Züge hat der Gegner für vergeudet wenn sie geschlagen wurde. Priorisierung beim Schlagen


Figur ist in Gefahr geschlagen zu werden

Bei der Berechnung ob eine Figur in Gefahr ist geschlagen zu werden geschlagen muss man unterscheiden ob es darum geht wenn man sie stehen lässt oder nachdem sie gezogen wurde. Um zu Schauen ob sich eine Figur in Gefahr ist geschlagen zu werden muss man sich die Felder hinter der Figur anschauen. Wenn da Gegnerische Figuren sind (die letzten 6 Felder bei einen Zug, 12 bei 2 Zügen, ...) besteht die Gefahr das sie geschlagen wird Chance das die Figur geschlagen wird

Wenn man die Figur ziehen wird muss dann die letzten Felder ab der voraussichtlichen neuen Position anschauen. Chance das die Figur geschlagen wird


Figur kann eine gegnerische Figur schlagen

Wenn man die Augenanzahl beim Wurf weist lässt sich leicht nachschauen ob man eine Figur schlagen kann. Einfach jede Figur nachschauen ob dort eine Gegnerische Figur ist.

Falls die Augenzahl aber unbekannt ist, weil man noch nicht gewürfelt hat, oder man die Chance errechnen will ob man nach den Ziehen eine Figur im übernächsten Zug schlagen kann, muss man sich die nächsten Felder nach der Figur anschauen (6 Felder für 1 Zug, 12 für 2 Züge, ...) Chance das man eine Figur schlagen kann

Parallelität

Die oben genannten Schlüssel-Parameter sind zum größten teil abhängig von den Zügen der Gegner. Da Nacheinander gezogen wird ändert sich des weiteren die Spielfeld-Situation recht häufig. Da durch den Würfel ebenfalls eine Zufalls-Komponente mit ins Spiel kommt lassen sich Ereignisse nur schlecht berechnen.

Was kann ich Parallelisieren?

Im Grunde ist nur die Berechnung von Zügen interessant. Alles andere sind entweder Sequenzielle ablaufe (Figuren Ziehen) oder nicht von Interesse für eine intensive Parallele Ausführung.


Welche schwierigkeiten gibt es?

Die Daten sind größtenteils Abhängig miteinander. Wenn eine Figur gezogen wird ändert sich dadurch die Faktoren für Andere Figuren.

Wann muss ich Figuren neu berechnen?

Figuren müssen nicht immer nach jeden Zug eine anderen Figur berechnet werden. Sie beeinflussen sich nur wenn ab einen gewissen Mindestabstand. Bei einen Zug tiefe wären das 6 Felder in beide Richtungen (12 bei 2 Zügen, ...) Wenn eine Figur dazu oder entfernt wird aus diesen Bereich ist eine Neuberechnung notwendig.

Datei:Example.jpg
Bereich zur Berechnung

Was berechne ich?

Für jeden Möglichen Würfel-Ausgang werden die Schlüssel-Parameter aller meiner Figuren berechnet und anhand dieser Ergebnisse wird ein Ranking anhand meiner bevorzugten Strategie für jeden Würfelausgang erstellt. Nach meinen Würfeln kann man so schnell die zu ziehende Figur ermitteln.

Datei:Example.jpg
Berechnung Zug 1

Wenn man das selbe Schema bei den Gegnerischen Figuren anwendet lässt sich nachvollziehen welche Strategie der Gegner benutzt. Ebenfalls lassen sich dadurch besser berechnen ob und welche Figuren im nächsten Zug noch an ihrer Position sind oder sie weggezogen wurden.

lohnt es sich mehr als einen Zug im Vorraus zu berechnen?

Ja und Nein. Die Strategien können kaum etwas mit den dadurch erhaltenen Daten was anfangen. Daten die wir aus denen heraus bekommen wären sowas wie:

  • Erhöht sich meine Chance eine Figur zu schlagen wenn ich sie dort hin ziehe.
  • Erhöht sich meine Chance eine Figur zu schlagen wenn ich stehen bleibe.
  • Erhöht sich meine Chance geschlagen zu werden.

Um aber erstmals brauchbare Daten zu gewinnen muss man wissen wo sich die Gegnerischen Figuren im 2. oder 3. Zug befinden werden. Durch den Zufallsfaktor lässt sich das nur grob eingrenzen.


Beschränkungen

der Würfel ist zufällig und lässt sich nicht von uns beeinflussen.


jeden Zug berechnen

Falls man jeden möglichen Zug berechnen will kommt man schnell an die Grenzen des Machbaren Allein die Anzahl an möglichen Würfel-Situationen kommt bei 8 Spielern auf 10 Millionen Möglichkeiten für den 2. Zug/Würfeln eines Spielern. Der 3. bereits auf 16,9 Billionen und der 4. auf 28,4 Trillionen.

Dazu käme normalerweise noch die Möglichkeit verschiedene Figuren zu ziehen und erneuten Würfeln bei einer 6.

Nach jedem Würfeln würden ebenfalls 5 von 6 Pfaden komplett ungültig und wegfallen.


Spieleranzahl / Zug vom Spieler
Wurf Pfade 1 2 3 4 5 7 8
1 6 1 1 1 1 1 1 1
2 36 2 1 1 1 1 1 1
3 216 3 2 1 1 1 1 1
4 1.296 4 2 2 1 1 1 1
5 7.776 5 3 2 2 1 1 1
6 46.656 6 3 2 2 2 1 1
7 279.936 7 4 3 2 2 1 1
8 1.679.616 8 4 3 2 2 2 1
9 10.077.696 9 5 3 3 2 2 2
10 60.466.176 10 5 4 3 2 2 2
11 362.797.056 11 6 4 3 3 2 2
12 2.176.782.336 12 6 4 3 3 2 2
13 13.060.694.016 13 7 5 4 3 2 2
14 78.364.164.096 14 7 5 4 3 2 2
15 470.184.984.576 15 8 5 4 3 3 2
16 2.821.109.907.456 16 8 6 4 4 3 2
17 16.926.659.444.736 17 9 6 5 4 3 3
18 101.559.956.668.416 18 9 6 5 4 3 3
19 609.359.740.010.496 19 10 7 5 4 3 3
20 3.656.158.440.062.980 20 10 7 5 4 3 3
21 21.936.950.640.377.900 21 11 7 6 5 3 3
22 131.621.703.842.267.000 22 11 8 6 5 4 3
23 789.730.223.053.603.000 23 12 8 6 5 4 3
24 4.738.381.338.321.620.000 24 12 8 6 5 4 3
25 28.430.288.029.929.700.000 25 13 9 7 5 4 4
26 170.581.728.179.578.000.000 26 13 9 7 6 4 4
27 1.023.490.369.077.470.000.000 27 14 9 7 6 4 4
28 6.140.942.214.464.820.000.000 28 14 10 7 6 4 4
29 36.845.653.286.788.900.000.000 29 15 10 8 6 5 4
30 221.073.919.720.733.000.000.000 30 15 10 8 6 5 4
31 1.326.443.518.324.400.000.000.000 31 16 11 8 7 5 4
32 7.958.661.109.946.400.000.000.000 32 16 11 8 7 5 4
33 47.751.966.659.678.400.000.000.000 33 17 11 9 7 5 5

anderer Ansatz

Anstatt jeden möglichen Ausgang eines Wurfes für jeden Spieler zu berechnen wird stattdessen mit Wahrscheinlichkeiten berechnet. Es wird ein Baum berechnet wo für jeden möglichen Würfel-Ausgang die für unsere Strategie ideale zu bewegen Figur ermittelt wird. Die Züge der Gegner werden nur anhand Wahrscheinlichkeiten dargestellt und nicht explizit im Baum mit aufgenommen.


Kriterien einer Figur
Felder vom Startpunkt entfernt in %
Chance das sie beim stehen bleiben geschlagen wird
Chance das sie nach den ziehen geschlagen wird
Chance das sie eine Figur schlägt
Wichtigkeit / Gewichtung das sie im Spiel bleibt


Positiv:

  • Eigene Figur kommt ins Spiel
  • Gegnerische Figur wird geschlagen
  • Eigene Figur landet im Haus
  • Eigene Figur kann nicht geschlagen werden

Negativ:

  • Eigene Figur wird geschlagen
  • Gegnerische Figur landet im Haus




unserer Ansatz zur Parallelisieren

Wir berechnen die nächsten 2 Runden für uns selbst. Alle nicht für uns relevanten Situationen werden nicht mit berechnet. Alle Relevante Situation sind ob der Gegner uns schlagen kann und alle eigenen Züge.

Spielsituation bewerten

Situationen beschreiben den Wert eines Spielers ein einer bestimmten Brettkonstelation. Es beschreibt wie gut ein Spieler steht bei einer bestimmten Zug.

Eigene Bewertung

  • Figuren fortschritt (Felder vom Ziel entfernt)
  • Gegnerische Figuren geschlagen
  • Eigene Figuren geschlagen (Eigene Figur Zurück auf die Bank)


Berechnung von Zugbäumen

  • wir Rechnen solange man Zeit hat.
    • bis ein Zug vom Gegner eintrifft
    • eine bestimmte Zeitdauer überschritten wird.
    • Anzahl an Ebenen entspricht => Spieleranzahl*2
  • Nach Erhalten eines Zuges werden nicht mehr gültige Pfade weg geworfen
    • Neue Berechnungen für die nächsten Züge finden statt.


  • Ebene 1 = Spieler der am Zug ist
    • Davon jeden möglichen Zug ( Figur * Würfel )
  • Eben 2 = nächster Spieler
    • jede Zugmöglichkeit in Abhängigkeit von der vorherigen Ebene
  • Eben 3 = nächster Spieler
    • jede Zugmöglichkeit in Abhängigkeit von der vorherigen Ebene

. . .

  • Ebene X


Wann gibt es eine Abhängigkeit

Wenn eine Gegnerische Figur X Felder hinter einer eigenen Figur steht gibt es eine Abhängigkeit. Für jede Dieser Gegnerischen Figuren muss man deren Zugmöglichkeiten beachten.

  • Runde 1 wenn es eine Gegnerische Figur gibt die zwischen 01 und 12 Feldern hinter uns ist (nach dem Ziehen).
  • Runde 2 wenn es eine Gegnerische Figur gibt die zwischen 01 und 06 Feldern hinter uns ist (nach dem Ziehen).

Was muss pro Zug berechnet werden

  • Situation
    • Im Schnitt zurückgelegter Weg
    • Chance geschlagen zu werden
    • Chance zu schlagen
  • Mögliche nächsten Züge des Spielers

Wie groß ist ein Rechen-Paket

Alle 2 Ebenen ein Fork, beginnend bei ebene 0

  • 4 Spieler => zwischen 12 bis 576 Zug-Varianten pro Einheit


Was bewirkt diese Berechnungen

Indem man nur Züge berücksichtigt die eine Auswirkung auf die Situation haben und den Rest als Default Züge behandelt verhindert man das sich der Baum in die Breite auffächert.

Default

Default-Züge haben keinen Einfluss auf die Situation anderer Züge, wodurch sie auf die selben Kind-Knoten zeigen können. Anstatt das sich der Baum Auffächert, bleibt er eher Konstant.

Sonderfälle

Bei Sonderfällen haben die KindKnoten einen erheblichen Einfluss auf den Zug, weswegen er einen eigenen Unterbaum Aufbaut. Züge In diesen Unterbaum können aber auch wieder auf einen Default-Tut zeigen, falls er seinen Einfluss auf die Situation verliert.


BaumMadN.png

Abläufe (M.D.)

Hier wird der Ablauf beschrieben. Welche Abläufe das Programm machen muss um zu spielen.

Start

  • Programm wird gestartet.
  • Der Spieler kann wählen:
    • ob er ein neues Spiel öffnen will.
    • oder ein existierendes Spiel beitreten will.

Spiel öffnen

  • Der Spieler muss zuerst ein Name des Spieles angeben, damit die anderen Spieler dieses Spiel finden können.
  • Dann bestimmt er, wie viel Spieler dieses Spiel beitreten können, bzw. Anzahl der allen Spieler des Spiels - im Bereich von 2 bis 8 Spieler.
  • Dem Spieler wird ein eindeutiger Spieler-Index (Spielernummer) zugeordnet, von dem der Spieler repräsentiert wird.
  • Als nächstes kann der Spieler wählen, ob Mensch oder Computer auf dem Computer spielen wird.
  • Wenn alle diese Informationen angegeben werden, kann der Spieler das Spiel per Button Create starten/öffnen.
  • Dann wartet er auf alle Spieler, bis sie das beitreten.
  • Dann startet das Spiel-GUI - ein Brett von Mensch ärgere dich nicht mit allem, was zu diesem Spiel gehört.

Spiel beitreten

  • Ein Katalog mit offenen Spielen wird zuerst gelistet. Der Spieler kann ein Spiel davon auswählen.
  • Falls kein Spiel oder nicht das neueste Spiel gelistet wird, kann er den Katalog aktualisieren um aktuellere Situation zu haben.
  • Weiter kann der Spieler festlegen, ob Mensch oder Computer auf dem Computer spielen wird.
  • Wenn alle diese Informationen ermittelt werden, kann der Spieler das Spiel per Button Join beitreten.
  • Dann wartet er auf die übrigen Spieler, bis sie das Spiel auch beitreten.
  • Danach, wenn alle Spieler schon beigetreten sind, startet das Spiel-GUI. In diesem GUI kann der Spieler seinen zugeordneten Spieler-Index (seine Spielernummer) sehen.


Spiel

Damit alle Spieler zusammenspielen können, die sich in demselben Spiel befinden, müssen sie miteinander kommunizieren. Jeder Spieler muss von allen anderen Spielern wissen, was für ein Zug sie machen. Alles muss dann in der graphischen Schnittstelle der einzelnen Spielern abgebildet (bzw. aktualisiert) werden. Die Spieler sind aus dieser Sicht ganz gleichwertig. Es gibt keine Unterschiede zwischen der einzelnen Spielern und kein Spieler hat spezielle Privilegien oder Sonderrechte. Der Spieler mit Index 0 beginnt das Spiel (beginnt zu würfeln) und dann führen die Spieler in einer Reihenfolge anhand ihres Indexes fort (Spieler 0, Spieler 1, Spieler 2, ..., Spieler N-1, Spieler 0, Spieler 1, ...).


Rollen von jedem Spieler:

  • Der Spieler muss seinen Zug an alle Mitspieler senden, damit sie wissen, wie das Spiel vorwärtsgeht.
  • Der Spieler muss auch in der Lage sein, die Züge von allen anderen Spielern zu empfangen.
  • Die beiden Zug-Arten (gesendete und empfangene Züge) müssen dann in Spielers GUI abgebildet, bzw. aktualisiert werden.


Das Programm verwendet 2 unterschiedliche Threads, damit es auf ordentliche Weise funktionieren kann:

  • ein Thread für Zug-Senden
  • ein Thread für Züge-Empfang

Zug senden

Der Spieler sollte seinen Zug an alle Spieler senden, die dasselbe Spiel spielen. Wenn es um alle Spieler geht, kann man vermuten, dass das durch die Funktion MPI_Bcast() umgesetzt werden kann. Diese Funktion ist dafür sehr geeignet. Der Spieler kann den Zug nur dann senden, wenn er daran ist.

Züge empfangen

Der Spieler sollte in der Lage sein, die Züge von allen Spielern zu empfangen. Das hat auch etwas mit MPI_Bcast() zu tun. Der Zug-Empfang wird deshalb durch diese Operation realisiert. Wenn wir aber einige Broadcast-Daten empfangen wollen, müssen wir jedesmal konkreten Sender dieser Daten kennen, von wem (welchem Spieler) die Daten kommen. Das bedeutet, dass wir auch intern wissen sollten, wer daran ist und demnach den Sender identifizieren.

Identifikation des Senders

Am Anfang gibt es einen festen Sender - Spieler 0, weil er immer am Anfang des Spiels daran ist. Die weiteren Sender kommen schrittweise anhand der Spieler-Reihenfolge.

Was bedeutet das? Wird der Sender nach jedem Wurf geändert?

Nein. Das Problem besteht aber darin, dass wir nicht genau wissen, wievielmal der Spieler X eine Sechs würfelt. Deswegen müssen die Spieler jedesmal auch die Würfel-Information von anderen Spielern bekommen, um zu wissen, ob Spieler X noch einmal würfeln wird oder nicht - bzw. ob Spieler X immer noch daran sein wird, oder schon nicht. Deshalb wird der Zug wie ein String repräsentiert. String enthält u.a. Würfel-Information, die mit entsprechendem Zug zusammenhängt. So können wir die einzelnen Broadcast-Sender identifizieren.

MPI Kommunikation (M.D.)

Die Spieler kommunizieren durch OpenMPI miteinander. Wenn ein neues Spiel erstellt wird, entsteht eine neue Instanz von MPI Kommunikation. Die Spieler, die das gleiche Spiel spielen wollen, können miteinander kommunizieren (nach Bestätigung aller erforderlichen Angaben in GUI vom Spiel). Das bedeutet, es ist möglich, mehrere neue Spiele zu erstellen (öffnen) und auch, selbstverständlich, nach allen offenen Spielen zu suchen (bzw. jedes offenes Spiel beizutreten). Die einzelnen Spiele repräsentieren einzelne Instanzen von MPI Kommunikation, die voneinander ganz unabhängig sind.

Kommunikations-Prozess

Den ersten Spieler, der ein neues Spiel erstellt hat, können wir als der Initiator nennen. Aus der Sicht von Kommunikationsaufbau hat der Initiator ein bisschen unterschiedliche Aufgabe wie die anderen Spieler, die das Spiel beitreten. Wir können uns das auch so vorstellen, dass der erste Spieler (der Initiator) einen Server repräsentiert und alle anderen Spieler, die das Spiel beitreten, einen Klient repräsentieren. Diese Server-Klient-Architektur ist aber nur im Rahmen der Kommunikations-Gestaltung für uns interessant und sinnvoll. Weil in den nächsten Teilen der Applikation alle Spieler ganz gleichwertig sind (wie schon früher geschrieben).


SERVER:

  • Zuerst öffnet der Server einen Port, durch das die Kommunikation realisiert werden kann.
  • Dann speichert er diesen Port in die Datei, auf die auch alle anderen Spieler zugreifen können. .
  • Danach wartet der Server auf alle Spieler, bis sie das erstellte Spiel beitreten.
    • Der Server wartet durch die Funktion MPI_Comm_accept() auf jeden anderen Klient, bis der Klient verbunden ist (der Klient ruft die paarige Funktion MPI_Comm_connect() auf).
    • Nach der erfolgreichen Verbindung gibt die Funktion MPI_Comm_accept() einen Inter-Kommunikator zurück, der alle bis jetzt verbundene Spieler enthält. Der Inter-Kommunikator wird nach jedem Beitritt neues Spielers schrittweise immer größer.
    • Nach der Verbindung sendet der Server an den Klient die Spieleranzahl, damit der Klient auch weiß, wie viel Spieler das Spiel spielen werden.
    • Der Server erzeugt durch die Funktion MPI_Intercomm_merge() einen neuen Intra-Kommunikator aus dem zurückgegebenen Inter-Kommunikator, damit er die Operationen für kollektive Kommunikation zwischen allen beteiligten Spielern verwenden kann.
  • Wenn alle Spieler verbunden sind und wenn es einen gemeinsamen Intra-Kommunikator gibt, sendet der Server an jeden Spieler entsprechenden globalen Rank im Rahmen dieses Intra-Kommunikators.


KLIENT:

  • Der Klient liest den Port aus der Datei von dem Server.
  • In dieser Zeit kann der Klient mit dem Port durch die Funktion MPI_Comm_connect() das Spiel beitreten. Diese Funktion gibt auch einen Inter-Kommunikator zurück.
  • Der Klient empfängt die Spieleranzahl von dem Server.
  • Der Klient ruft dann die Funktion MPI_Intercomm_merge(), damit er auch einen Intra-Kommunikator mit dem Server hat.
  • Der Klient muss dann die Funktion MPI_Comm_accept() aufrufen, damit er mit allen nächsten Spielern (die noch das Spiel beitreten werden) auch einen gemeinsamen Kommunikator hat. Das muss nicht der letzte Spieler(Klient) ausführen, weil er schon alle anderen Spieler des Spiels im Intra-Kommunikator von vorheriger Funktion MPI_Intercomm_merge() hat.
  • Damit der Klient einen Intra-Kommunikator haben kann, muss er noch die Funktion MPI_Intercomm_merge() aufrufen, die mit dem Inter-Kommunikator den gefordeten Kommunikator erzeugt.
  • Der Klient empfängt von dem Server seinen globalen Rank im Rahmen der allen in demselben Spiel beteiligten Spielern.

Implementierung

Nutzung des Spieles:

Das Ganze Spiel ist in der Game-Klasse drinnen. Beim Initialisieren gibt man die Spieleranzahl und den eigenen lokalen Spielerindex mit.

int spieleranzahl =4;
int duBistSpieler = 0;
Game game = new Game(spieleranzahl, duBistSpieler);

Um Züge von der Gut zu bekommen musst du dich auf das Spiel als Observer registrieren.

public class DeineKlasse implements Observer {

        private Game game;

	public void DeineKlasse(){
	      int spieleranzahl = 4;
	      int duBistSpieler = 0;
	      game = new Game(spieleranzahl, duBistSpieler);
	      game.addObserver(this);
	}

	@Override
	public void update(Observable o, Object arg) {
		if (arg instanceof Zug) {
			Zug zug = (Zug) arg;
		}
       }
...
}


Um Züge von Anderen Spielern auf das lokale Game anzuwenden gibt es eine Methode:

public class DeineKlasse implements Observer {
        private Game game;
...
	public void applyZugAufLokalesSpiel(Zug zug) throws ZugException {
		game.commitZug(zug);
       }
...
}


Züge lassen sich zu einem String und von einen String umwandeln:

       //Zug zug = new Zug(Brett brett, int turn, Spieler spieler, Figur figur, int wuerfel, boolean skip) {
       Zug zug = ...;
       String zugString = zug.writeZug();
       Zug zug2 = Zug.readZug(game.getBrett(), zugString);



Für die GUI gibt es eine eigene Klasse, die man das Game mit gibt:

                Game game = new Game(4,0);
                game.addObserver(this);

		GameView frame = new GameView(game);
		frame.setMinimumSize(new Dimension(700, 700));   // breite , höhe
		frame.setVisible(true);
		frame.repaint();


siehe die Klasse MADN.java für ein lokales Beispiel

MPI Kommunikation (M.D.)

Dieser Teil beschreibt Gestaltung der MPI Kommunikation im Spiel.

Server

Der Server ist der Spieler, der ein neues Spiel erstellt hat (erstellen will).

public class Communicator {

...

    public Communicator(...){

        if (role == SERVER){
            MPI.Init(args);
            portName = openPort();
            PrintWriter writer = new PrintWriter(...);
            writer.println(portName);
            for (int i = 0; i < numPlayers-1; i++){     // accepting connect requests from all clients     
                if (i == 0){
                    intercomm = MPI.COMM_WORLD.accept(portName, 0);         // accept of the first client
                }
                else {
                    intercomm = ((Intracomm)intracomm).accept(portName, 0); // accept of the other clients
                }
                // sending number of players to all players (clients) in the intercomm
                intercomm.send(numPlayers, 1, MPI.INT, intercomm.getRank(), 0); 
                intracomm = ((Intercomm) intercomm).merge(false);           // merge of the intercomm to create an intracomm
            }

            int indexClient[] = new int[1];
            for (int i = 1; i < numPlayers; i++){       // sending index to the corresponding client 
                indexClient[0] = i;
                intracomm.send(indexClient, 1, MPI.INT, i, 0);
            }
        }
    ...
    }
}


Klient

Der Klient sind alle anderen Spieler, die ein offenes Spiel beigetreten sind (beitreten wollen).

public class Communicator {

...

    public Communicator(...){
        
        ...

        else if (role == CLIENT){
            MPI.Init(args);

            BufferedReader in = new BufferedReader(...);
            String portName = in.readLine();

            intercomm = MPI.COMM_SELF.connect(portName, 0);   // connect to the server through portName
            int players[] = new int[1];
            intercomm.recv(players, 1, MPI.INT, 0, 0);        // receive number of players from server

            intracomm = ((Intercomm)intercomm).merge(true);   // create intracomm from intercomm

            rank = intracomm.getRank();
            size = intracomm.getSize();

            numPlayers = players[0];

            // connect this client gradually to all following clients and get the final intra-communicator
            for (int i = rank; i < numPlayers-1; i++){ 
                intercomm = ((Intracomm)intracomm).accept(portName, 0); // accept the connect request of following clients
                intracomm = ((Intercomm)intercomm).merge(false);        // merge to create an intracomm
            }

            int index[] = new int[1];
            intracomm.recv(index, 1, MPI.INT, 0, 0);     // receive index of actual client
            this.index = index[0];
        }
    ...
    }
}

Methoden

Hier wird die Methoden zur MPI Kommunikation bechrieben.

Methode sendZugAnAlle

Diese Methode stellt das Senden des Zuges an alle anderen Spieler sicher.

public void sendZugAnAlle(Zug zug) throws MPIException{
        char buf[] = new char[MAX_ZUG_STRING_CHARS];
        char buf2[]= zug.writeZug().toCharArray();
        for (int i = 0; i < buf2.length ; i++) {
            buf[i] = buf2[i];           
        }
        intracomm.bcast(buf, MAX_ZUG_STRING_CHARS, MPI.CHAR, index);        
    }

Methode recvZug

Diese Methode realisiert den Empfang der Züge von allen anderen Spielern.

public String recvZug() throws MPIException{
        if (whoseTurn == index){  // identifying the sender I
            whoseTurn = (whoseTurn + 1) % numPlayers;
        }               
        char buf[] = new char[MAX_ZUG_STRING_CHARS];
        intracomm.bcast(buf, MAX_ZUG_STRING_CHARS, MPI.CHAR, whoseTurn);  // receiving turns by broadcast
        String zugString = new String(buf);
        String[] zugTeile = zugString.split("-");
        int wuerfel = Integer.parseInt(zugTeile[4]);

        if (wuerfel != 6){        // identifying the sender II
            whoseTurn = (whoseTurn + 1) % numPlayers;
            if (whoseTurn == index){
                whoseTurn = (whoseTurn + 1) % numPlayers;
            }
        }
        return zugString;
    }

Hauptklasse MADN (M.D.)

Diese Klasse verbindet MPI Kommunikation mit GUI des Spiels.

public class MADN implements Observer {
    
    private Game game;
    private int spielerAnzahl;
    private int index;
    private Thread recThread;
    private Communicator communicator;

    public MADN(Communicator comm, int index, int spielerAnzahl){
        this.communicator = comm;
        this.index = index;
        this.spielerAnzahl = spielerAnzahl;
        
        game = new Game(this.spielerAnzahl, this.index);    // create a new instance of game
        game.addObserver(this);
        game.getBrett().getSpieler(this.index).setKI(false);
        
        GameView frame = new GameView(game);                // create graphics for the game
        frame.setTitle("Mensch ärgere dich nicht - Spieler " + index);
        frame.setMinimumSize(new Dimension(700, 700));
        frame.setVisible(true);
        frame.repaint();
        recThread = initRecieveThread();    // initiate a thread for receiving turns
        recThread.start();            
        frame.addWindowListener(new WindowAdapter() {
            @Override
            public void windowClosing(WindowEvent e) {
                super.windowClosing(e);
                recThread.interrupt();
            }            
        });
    }
}

Methoden

Hier werden die Methoden beschrieben, die notwendig für Lauf des Spieles sind.

Methode initRecieveThread

Diese Methode initiiert Thread für das Empfang der Züge. Dieses Thread ist ganz unabhängig vom Senden des Zuges an alle Spieler.

public Thread initRecieveThread(){
        Thread t = new Thread( new Runnable() {
            @Override
            public void run() {
                while (true){
                    Zug zug = receiveZug();
                    try {
                        MADN.this.applyZugAufLokalesSpiel(zug);
                    } catch (ZugException ex) {
                        Logger.getLogger(MADN.class.getName()).log(Level.SEVERE, null, ex);
                    }
                }
            }
        });
        return t;
    }

Methode update

Wenn ein Ereignis aufgetreten wird und wenn es um ein Zug-Ereignis geht, dann wird diese Methode ausgeführt. Die Methode sendet den Zug an alle anderen Spielern und aktualisiert GUI in dem lokalen Spiel.

@Override
    public void update(Observable o, Object arg) {
        if (arg instanceof Zug) {
            Zug zug = (Zug) arg;
            try {
                communicator.sendZugAnAlle(zug);
            } catch (MPIException ex) {
                Logger.getLogger(MADN.class.getName()).log(Level.SEVERE, null, ex);
            }
            
            try {
                MADN.this.applyZugAufLokalesSpiel(zug);
            } catch (ZugException ex) {
                Logger.getLogger(MADN.class.getName()).log(Level.SEVERE, null, ex);
            }
        }
    }

Methode receiveZug

Die Methode empfängt den Zug mithilfe der Methode recvZug().

public Zug receiveZug(){
        Zug zug = null;
        String zugString;
        try{
            zugString = communicator.recvZug();
            zug = Zug.readZug(game.getBrett(), zugString);
        } catch (MPIException ex) {
            Logger.getLogger(MADN.class.getName()).log(Level.SEVERE, null, ex);
        } catch (ZugException ex) {
            Logger.getLogger(MADN.class.getName()).log(Level.SEVERE, null, ex);
        }      
        return zug;
    }

Methode applyZugAufLokalesSpiel

Diese Methode wendet den Zug auf das lokale Spiel an. Man kann im GUI des Spiels sehen, was für ein Zug realisiert wurde.

public void applyZugAufLokalesSpiel(Zug zug) throws ZugException {
        game.commitZug(zug);
    }

Bewertung

Links