inf-schule | Modellierung des Backend » Wie speichern wir das Schachbrett?

Wie speichern wir das Schachbrett?

Oder müssen wir das Schachbrett überhaupt speichern?

<div v-pre=""><figure id="inhalt-1" class="abbildung rechts" style="width:400px;"><a data-size="7743x4762" href="https://inf-schule.de/content/9_software/4_ScrumSchach/4_DerErsteSprint/2_Durchfuehrung/3_ModellierungBackend_UMFANGREICH/1_lernstrecke/2_schritt2/Schachbrett.jpg" class="abbildungslink"><img title="Schachbrett" alt="Schachbrett" class="rechts" src="https://inf-schule.de/content/9_software/4_ScrumSchach/4_DerErsteSprint/2_Durchfuehrung/3_ModellierungBackend_UMFANGREICH/1_lernstrecke/2_schritt2/Schachbrett.jpg" width="400"></a><a href="#quelle-inhalt-1" class="origin">[1]</a></figure></div>

<p>
    An dieser Stelle kann man mindestens sagen: Zwei Wege f&uuml;hren zum Ziel. Auf den ersten Blick ist es nicht offensichtlich, welcher dieser beiden Wege besser ist. Es h&auml;ngt auch (selten!) von euren User Stories ab. 

</p>

<h4>M&ouml;glichkeit 1</h4>        
    Naheliegend w&auml;re zun&auml;chst nat&uuml;rlich, eine 2D-Matrix mit den Figurobjekten an 
    den entsprechenden Stellen zur Verwaltung des Spielbretts zu benutzen. Die Position einer Figur w&uuml;rde dann durch die Matrix gespeichert, 
    eine Figur muss ihre Position selbst nicht kennen, sondern k&ouml;nnte das Backend jederzeit danach fragen. 


<h4>M&ouml;glichkeit 2</h4>
<p>        
    Denkt man dar&uuml;ber nach, ist ein Schachbrett nicht mehr als eine Menge Figuren. 
    Eine Menge Figuren muss man jedoch nicht zwangsl&auml;ufig in einer 2D-Matrix verwalten, 
in der die meisten Felder dann leer sind! daf&uuml;r reicht 
    ein einfaches Array oder eine Liste mit allen Figuren. Jede Figur speichert dann ihre Position einfach selbst. 
    Wenn man zum Beispiel f&uuml;r die GUI dann doch noch eine Matrixdarstellung ben&ouml;tigt, l&auml;sst sich das Schachbrett als 2D-Array dann jederzeit     schnell als "Wegwerfprodukt" aus den Figuren erzeugen, 
    indem man einmal &uuml;ber die Figurenliste iteriert. Daf&uuml;r wird nur eine einstellige Anzahl Codezeilen ben&ouml;tigt! 
</p>

<h4>Entscheidungshilfe</h4>
<p>
F&uuml;r M&ouml;glichkeit 1 ist mehr Arbeit mit 2D-Vektoren und Vektormultiplikation erforderlich. Habt ihr das Rechnen mit Vektoren und Matrizen 
bisher im Matheunterricht fl&uuml;ssig ge&uuml;bt?
Ber&uuml;cksichtigt bei dieser Entscheidung auch User Stories aus sp&auml;teren Sprints. 
Wollt ihr sp&auml;ter einen vollst&auml;ndigen Schachfigurensatz implementieren, muss f&uuml;r jeden Zug 
einzeln gepr&uuml;ft werden, ob dadurch einer der K&ouml;nige in Schach geraten k&ouml;nnte. F&uuml;r diese &Uuml;berpr&uuml;fung ben&ouml;tigt man auf einer Matrix 
au&szlig;erordentlich viel Aufwand!
</p>

<h4>Tipp des Autors</h4>
<p>
Entscheidet euch f&uuml;r M&ouml;glichkeit 2. Geht ihr anders vor, werdet ihr viel Zeit verlieren, was eurem Product Owner nicht gefallen wird. 
</p>

Aufgabe 1

Falls ihr euch trotzdem nicht entscheiden könnt, oder nachvollziehen wollt, warum obiger Tipp gegeben wird: Wie würdet ihr die Überprüfung der Könige auf Schach jeweils für beide Wege durchführen? Skizziert jeweils grob einen Algorithmus.

Aufgabe 2

Betrachtet eure beiden Skizzen. Welcher Algorithmus ist fehleranfälliger in der Programmierung und komplexer?

Hinweis

Falls ihr nicht direkt auf die Lösung kommt, stellt euch vor ihr würdet ein 3D-Schach implementieren. Wie würde die Komplexität und Fehleranfälligkeit eurer beiden Algorithmen dafür aussehen?

Auflösung

Der erste Weg wirkt auf den ersten Blick einfacher. Auf den zweiten Blick KANN er kompliziert werden. 2D-Arrays benötigen für viele Operationen doppelt verschachtelte Schleifen, diese sind fehleranfälliger und verursachen (unter Umständen) hohe Laufzeiten. Muss für jede Figur auf dem Spielbrett jeweils jede andere geprüft werden, ergeben sich vier oder mehr verschachtelte Schleifen (wie zum Beispiel bei der Prüfung, ob der eigene König in Schach geraten könnte). In diesem Fall ist ein 1D-Figurenarray einfacher. Wenn man (z.B. für die spätere Ausgabe) dennoch ein 2D-Array braucht, dauert das Erstellen des 2D-Arrays nur einen einzigen Schleifendurchlauf durch das Figurenarray.

<p>
    Beispiel: 
    In einer vollst&auml;ndigen Schach-Implementierung muss f&uuml;r jeden eingegebenen Zug gepr&uuml;ft werden, ob der eigene K&ouml;nig dadurch m&ouml;glicherweise ins Schach ger&auml;t, 
    da der Zug in diesem Fall unzul&auml;ssig w&auml;re. Au&szlig;erdem muss gepr&uuml;ft werden, ob der gegnerische K&ouml;nig ins Schachmatt ger&auml;t, 
    da dann das Spiel zu Ende w&auml;re. F&uuml;r diese &Uuml;berpr&uuml;fung m&uuml;ssen alle Figuren auf dem Schachbrett auf ihren m&ouml;glichen Weg zu den K&ouml;nigen hin &uuml;berpr&uuml;ft werden. 
    Sind die Figuren in einer 2D-Schachbrett-Matrix gespeichert, muss allein f&uuml;r die Figurensuche &uuml;ber eine doppelt verschachtelte Schleife iteriert werden. 
    F&uuml;r die &Uuml;berpr&uuml;fung auf Schach/Schachmatt ergeben sich mehrere ineinander verschachtelte Exemplare solcher doppelt verschachtelten Schleifen. 
</p>

<p>
    F&uuml;r 3D-Schach w&uuml;rde die Lage noch bedeutend un&uuml;bersichtlicher, ein 3D-Array m&uuml;sste mit drei mal drei verschachtelten Schleifen 
    &uuml;berpr&uuml;ft werden. 
</p>

Aufgabe 3

Euer Klassendiagramm beinhaltet vielleicht bereits eine Klassen/Objektvariable für das Schachbrett oder den Figurenspeicher. Passt euer Klassendiagramm gegebenenfalls an eure jetzige Entscheidung an.