Schach: Überprüfung, ob Zug erlaubt

[JasonDX]

@MarkusB: Das mit den Springern ginge z.B. einfacher:

Delphi-Quellcode:

function CheckKnight(Start: TPoint; End: TPoint): boolean;
begin
  result := (abs(Start.X - End.X) + abs(Start.Y - End.Y) = 3) and (abs(Start.X - End.X) > 0)
end;

Das ganze basiert darauf, dass der Springer immer 3 Schritte macht, wobei er aber mindestens 1 schritt in eine Richtung machen muss
Man könnte versuchen, alle Figuren so zu kürzen, wär aber auch wieder ein Aufwand.

Zudem würd ich empfehlen, nur mit Zahlen zu rechnen, mit Buchstaben wirds nur chaotischer ;)


Was sinnvoller ist, ifs oder kompliziert... hängt davon ab, was du unter sinnvoll verstehst.
Die If-Methode ist einfach, schnell, lang und "unschön"
Die Distance+Direction-Methode ist kompliziert, lang, aber elegant und dynamisch, v.a. wenn du z.B. einen König haben willst, der wie ein Turm, ein Springer und ein Läufer laufen kann ;)

Wenn du willst, kann ich versuchen, dir eine (halbwegs) verständliche Erklärung zu meiner Lösung zu schreiben

[fkerber]

Hi!

Eine Erklärung mit Worten (also weniger als Code) wär echt super!
Danke für deine Mühe.

Ciao Frederic

[mr47]

Man braucht nicht über 100. Man braucht für einen Bauern genau eine + Schlagen

y ist die Position auf der y-Achse auf der der Bauer steht.

Zitat:

y+1

Wenn das für die Weißen steine gilt, muss man bei allen Schwarzen nur das Vorzeichen umdrehen. Die sollen ja dann von oben nach unten laufen :wink: also

Zitat:

y-1

Für einen Springer gäbe es dann 4 Möglichkeiten:

Zitat:

y+1 & x+1
y+1 & x-1
y-1 & x-1
y-1 & x+1

und dann halt immer noch prüfen: wenn y=maximum then y+1 nicht möglich wenn y=minimum then y-1 nicht möglich

Aber das von Chamiara sieht professioneller aus :wink:


mfg

edit 1+2+3: Die kleinen Fehler die niemand merkt hab ich entfernt :wink:

[JasonDX]

Sry, dasses jetzt so lang gedauert hat, das zu schreiben, aber ich lieg (vom Schulischen her) eher im Stress :kotz:

Hier mal die Erklärung ca. in Worten, ich hoffe sie ist verständlich, ansonsten könnt ihr Fragen soviel ihr wollt ;)

Die Richtung
Vorab: hier kanns hilfreich sein, in den Anhang zu schaun, womit ihr vielleicht auch den Grund für die bunte Farbmischung erkennt ;)
Wenn sich eine Figur bewegt, bewegt sie sich in eine bestimmte Richtung und um eine bestimmte Anzahl Felder.
Jede Figur kann sich nur in eine bestimmte Richtung bewegen. Liegt das Ziel in einer anderen Richtung, darf sich die Figur nicht dorthin bewegen.
Sehen wir uns das Schachbrett von oben an und betrachten mal den Turm in der Mitte des Feldes:
Er kann nach rechts, oben, links und unten gehen.
Um das etwas mathematischer auszudrücken: Er kann sich in die Richtungen 0°, 90°, 180° und 270° bewegen.
Betrachten wir nun den Läufer: Er kann sich nur Diagonal bewegen. Das wiederum in Winkel ausgedrückt: 45°, 135°, 225° und 315°.
Beim Springer wirds etwas komplizierter:
Dieser kann in 8 Richtungen laufen:

• 2 Rechts, 1 Hoch
• 2 Oben, 1 Rechts
• 2 Oben, 1 Links
• 2 Links, 1 Oben
• 2 Links, 1 Unten
• 2 Unten, 1 Links
• 2 Unten, 1 Rechts
• 2 Rechts, 1 Unten

Wenn man ein bisschen arcSin und Pythagoras rechnet, kriegt man folgende Winkel (gerundet):
26°, 64°, 116°, 154°, 206°, 244°, 296° und 334° (wenn ich mich nicht ganz verrechnet hab ;) )
Wenn wir mal (wie immer) den Bauern außer acht lassen, ist in jedem Quadranten so ziemlich das selbe. (Wie man im Anhang vielleicht erkennen kann.)
Damit wir die Überprüfung nicht für alle Quadranten machen müssen, beschränken wir uns auf den ersten.
Soll heißen: Wir wandeln z.B. alle Winkel des Läufers in den Winkel des ersten Quadranten um. Der Winkel des Läufers im ersten Quadranten ist 45°. D.h. für uns gilt 45° = 135° = 225° = 315. Das selbe mit den Graden des Turms.
Beim Springer müssen wir wieder schaun. Bei Läufer und Turm haben wir 4 Winkel. Beim Springer haben wir 8. Volkschul-EinMalEins: 2*4=8. Der Springer hat also doppelt so viele Möglichkeiten zu laufen wie andere Figueren. Wenn wir jeweils die richtigen Richtungen raussuchen, können wir folgendes für den Springer aufstellen:
26° = 116° = 206° = 296° und
64° = 154° = 244° = 334°
(modulo 90 dürfte hier eine Bedeutung haben ;) )
So, jetzt haben wir mal die verschiedenen Winkel. Was können wir damit machen? Damit können wir mal die Bewegung einschränken, die die Figuren machen dürfen.
Dafür müssen wir dann logisch auch schaun, welchem Winkel unser Winkel ca. entspricht. (Die Richtung (=Winkel), in die sich die Figur bewegt kriegt man leicht mit Pythagoras & co. raus)
Diese Richtung muss einer der Richtungen für die Figuren entsprechen. Wenn nicht, ist der Zug automatisch nicht erlaubt.
Nun gehen wir ein bisschen in die Richtung des Quellcodes:
Wir definieren uns ein set für Richtungen.
Eins für den Turm, eins für den Läufer, und eins für den Springer. Warum keins für Dame und König? Für uns sind die ne Mischung aus Turm und Läufer ;) Und der Bauer ist sowieso unser globaler Außenseiter :stupid:
Dadurch kommen wir auf das TChessDirection = (cdRook, cdKnight1, Knight2, cdBishop, cdNone);
Nebenbei zur Erklärung: Rook = Turm; Knight = Springer; Bishop = Läufer. None? Diese Richtung brauchen wir um zu sagen, dass es sich um eine ungültige Richtung handelt, also um eine, in die sich keine Figur bewegen darf.
Wie wir sehen können, brauchen wir für unsren Springer zwei Richtungen. In der Zeichnung Lila und Blau
Deshalb kommen wir dann auch auf folgendes:

Delphi-Quellcode:

const
  PossibleDirections: array[TChessFigures] of TChessDirections = 
      ([], //Pawn - Ausnahme
       [cfRook], //Rook
       [cfKnight1, cfKnight2], //Knight
       [cfBishop], //Bishop
       [cfRook, cfBishop], //Queen
       [cfRook, cfBishop]); //King

Damit legen wir fest, wer wohinlaufen darf. Der Turm darf nur in Richtung des Turm laufens, der Springer in die 2 Richtungen des Springers, und der Läufer in die des Läufers. Dame und König sind wie gesagt eine Mischung aus Turm und Läufer.

Damit wir aber noch wissen, welche Richtung das jetzt ist, in die sich die Figur bewegen will, muss unser Programm auch wissen, welche Richtung jetzt welcher Winkel ist. Deshalb brauchen wir die Konstante: DirectionAngles: array[TChessDirection] of integer = (463, 463, 1107, 785, 21351);
Warum sind das jetzt nicht die Werte, die wir oben gesehenhaben? Diese werte sind erstens in Radiant gemessen. Warum? sinus und seine Freunde ham das lieber ;). Bloß schaun die Werte auch nicht danach aus. Nachdem mir reals ect. beim vergleichen und bez. Genauigkeit manchmal Sorgen bereiten, sind die Werte mit 1000 multipliziert. d.h. die Ursprünglichen Werte für die Konstante wären (0.463, 0.463, 1.107, 0.785, 21.351) gewesen. Da fällt aber auch gleich was auf: ein Radiantenwinkel von >21?? das ist unsre none-Direction, ein bloßer Wert, der nie bei einer errechneten Richtung auftreten kann.
Wenn oben bei den PossibleDirections irgendwo ein cdNone stehen würde, könnte diese Figur in alle Richtungen laufen, in die sonst keine der anderen Figuren laufen kann.
In der Funktion, die uns zurückgibt, in welche Richtung grad gelaufen wird, wird dann nach der reihe überprüft: Ist die Richtung die des Turms? oder die des Läufers? Oder passt sie zum Springer? Wenn sie zu keinem der Richtungen gehört, ist sie cdNone.
Wenn wir die Richtung haben, schauen wir, ob die Figur auch in die Richtung laufen darf. Das steht in den PossibleDirections und kann einfach mit dem in-Operator überprüft werden.


Entfernung
Nachdem wir jetzt durch die Richtung, in die sich eine Figur bewegen kann, bereits die meisten Bewegungen einschränken können, fehlt doch noch was. z.B. kann unser König noch gleich laufen wie die Dame. Oder wenn jemand den Quellcode ohne Distances probiert, kann mit dem Springer auch 2 nach links und 4 nach oben gehen, und keiner sagt er dürfe nicht.
Deshalb müssen wir eine zweite einschränkung einführen: Manche Figuren können nicht 100km laufen, bei denen is nach ein paar Feldern die Batterie leer.
Diese Einschränkung kriegen wir, wenn wir noch für jede Figur eine Streckenbegrenzung einführen. Das ist in MaxDistances deklariert. Da haben wir aber auch 15 stehen - Welche Figur kann 15 Felder laufen? So gesehen: keine. Aber wir müssen auch bedenken, dass Diagonal die Felder etwas länger sind (zumindest vom Aspekt der Geometrie her). Hier ist die Hauptsache: Für Figuren, die übers ganze Spielfeld laufen können, den Wert einfach nur groß genug wählen. Wichtig ist der Wert beim Springer und beim König. Wenn wir genau hinschauen: der Springer kann eigentlich genau entlang eines Kreises hinlaufen. Der Kreis hat ca. einen Radius von knapp kleiner als 2.3. Also sagen wir: Der springer darf nicht weiter als 2.3 Felder laufen. Nachdem im weiter oben genannten Beispiel der Zug um 2 Felder nach links und 4 nach oben etwas weiter weg ist, darf der Springer das nun auch nicht mehr. Der König bekommt noch eine engere Beschränkung. Weil seine Krone und der Apfel so schwer sind, kann er max. 1.5 Felder laufen. Dies reicht knapp aus, dass er auf ein Diagonales Feld laufen kann, was ca. 1.41 Felder weit weg ist. Wir könnten die Begrenzung auch auf 1.9 Felder legen, die Hauptsache ist, dass sie < 2 ist, da er ansonsten Horrizontal oder vertikal 2 Felder laufen könnt. Und das darf er einfach nich.
Der Bauer ist nach wie vor noch ein armes Schwein, der darf noch gar nix machen. Ich werd mir aber auch über den Gedanken machen, und wenn mir was einfällt, schreib ichs hier ;)


Ich hoff, das war etwas verständlicher, aber mein Info-Lehrer hat auch irgendwie schon bemerkt, dass ich mein Erklären so manche Probleme habe :wall:



@mr47: ich hab dein Prinzip knapp falsch verstanden ;) (ich dachte bspw. du machst das alle möglichen felder, nicht nur die maximalen :oops: )

[fkerber]

Hi!

Danke für die weitreichende Erklärung.
War bestimmt etwas Arbeit.

Ciao Frederic

[alzaimar]

Versuch doch auch mal Folgendes;
Es gibt ja für die Figuren verschiedene Zugmöglichkeiten, also z.B:

Delphi-Quellcode:

Const
ccXfwd : Array  [0..7] Of TPoint= ( (1,0),....  ( 8,0) );
ccXbwd : Array  [0..7] Of TPoint= ( (-1,0),.... (-8,0) );
ccYfwd : Array  [0..7] Of TPoint  ( (0,1) .... (0,8) ); 
ccYbwd : Array  [0..7] Of TPoint  ( (0,-1) .... (0,-8) );
ccKnight : Array [0..7] Of TPoint = ( (2,1),(1,2),(-1,2),(-2,1),(1,-2),(2,-1), (-2,-1), (-1,-2));

// Das gleiche noch für die Diagonalen (ccUL, ccDL, ccUR, ccDR für Up/Down Left/Right);

Procedure CheckMove (aFigur : TSchachFigur; aPosition : TPoint; aBrett : TSchachBrett);
Begin
  Case aFigure of
    Springer : CheckIt (aPosition, ccKnight, False );
    Turm : Begin      
      Checkit (aPosition, ccXfwd, True);
      Checkit (aPosition, ccXbwd, True);
      Checkit (aPosition, ccYfwd, True);
      Checkit (aPosition, ccYbwd, True);
      End;
    Dame : Begin
      Checkit (aPosition, ccXfwd, True);
      Checkit (aPosition, ccXbwd, True);
      Checkit (aPosition, ccYfwd, True);
      Checkit (aPosition, ccYbwd, True);
      Checkit (aPosition, ccUL, True);
      Checkit (aPosition, ccUR, True);
      Checkit (aPosition, ccDL, True);
      Checkit (aPosition, ccDR, True);
      End;
    Läufer : Begin ... nur die ccUL,ccUR,ccDL,ccDR etc. End;
...
End;

Damit erschlägst Du alles, bis auf en-passant und die Rochade. Da muss man ja extra testen.
Das CheckIt ist auch simpel, indem es zu der aPosition alle Elemente der Zugliste addiert. Der zweite (Bool-) Parameter gibt an, ob der Weg bis zur Zielposition frei sein muss, oder nicht. Der Turm kann z.B. nicht 5 Felder nach rechts, wenn auf dem 3.Feld jemand steht. Beim Springer findet dieser Check nicht statt.

Mit dem Verfahren erstellst Du auch eine Liste aller legalen Züge.

[Cöster]

Zitat:

Zitat von JasonDX

Delphi-Quellcode:

const
  DirectionAngles: array[TChessDirection] of integer = (463, 463, 1107, 785, 21351);

Ich hab's nicht geprüft, aber müsste die erste Zahl statt 463 nicht 1570 sein? Sie bezieht sich doch auf den Turm.
Noch ne Frage:
Die 21351 könnte doch eigentlich jede Zahl >=1571 sein, oder?

[JasonDX]

Zitat:

Zitat von Cöster

Zitat:

Zitat von JasonDX

Delphi-Quellcode:

const
  DirectionAngles: array[TChessDirection] of integer = (463, 463, 1107, 785, 21351);

Ich hab's nicht geprüft, aber müsste die erste Zahl statt 463 nicht 1570 sein? Sie bezieht sich doch auf den Turm.

:oops: Ja, stimmt. Da hab ich mich vertan, ich lass es gleich ausbessern. Danke für den Hinweis :thumb:

Zitat:

Zitat von Cöster

Die 21351 könnte doch eigentlich jede Zahl >=1571 sein, oder?

Jup, das is korrekt.

greetz
Mike

[alzaimar]

Ich hab mir das eben mal alles durchgelesen.... Sagt mal, ist es nicht ein wenig -äh- suboptimal, mit irgendwelchen winkeln zu arbeiten? Ich meine, wir haben hier ein Schachbrett, das ist entweder eine 8x8 Matrix, oder ein [0..63] Feld. Dann hat man mögliche Bewegungsrichtungen und das war es dann. Wie man da mit ArcSin rumhantiert, ist mir ein Rätsel...

Aber vielleicht bin ich auch nur zu :wall:

[Der_Unwissende]

Zitat:

Zitat von alzaimar

oder ein [0..63] Feld. Dann hat man mögliche Bewegungsrichtungen und das war es dann. Wie man da mit ArcSin rumhantiert, ist mir ein Rätsel...

Jap, das hab ich doch schon gelesen...

Zitat:

Zitat von Sharky

Das Feld von 8x8 kannst Du ja auch als Linearesfeld mit 64 feldern abbilden.
Jetzt überlege mal wie z.B. ein "Springer" sich auf diesem "eindimensiomale" Array bewegen kann.

Er kan nur 4 mögliche Felder vor oder 4 mögliche Felder zurück. (wenn ich mich nicht verzählt habe)

Aber das wäre doch ein Ansatz?

Ich würde mal auch sagen, wenn es nicht einen Grund gibt hier nicht mit diskreten Werten zu arbeiten (und es sind wirklich wenige), dann solltest du dir einen der Tipps von alzmaimar oder Sharky greifen und es einfach (hier wörtlich zu verstehen) mit diesen Möglichkeiten versuchen. Letztlich bleibt dir nur die Speziallfälle (auch sehr sehr sehr wenige) zu prüfen und für jede Klasse von Schachfigur die mögichen Richtungen fest zu legen. Wie hier schon gesagt wurde hat stellt der Springer nochmal eine Ausnahme dar, er kann auch über Figuren springen die im Weg sind.
Aber einfacher ist sicherlich keine der anderen Lösungen (sorry an die anderen, es sind ja auch interessante Ansätze, irgendwie).

Gruß Der Unwissende