Schach: Überprüfung, ob Zug erlaubt

[fkerber]

Hallo!

Ich programmiere gerade ein Schachspiel (Human vs. Human, keine KI)
Wie stelle ich am effizientesten fest, ob ein Zug augeführt werden darf (also die Figur dorthin bewegt werden darf)?
Es geht sicherlich mit einigen If-Abfragen, aber vielleicht gibt es ja da noch was Schöneres?

Ciao und Danke
Frederic

[sniper_w]

Es wird dir kaum gelingen, irgendwas ohne if-s zu machen. Und dir weiter zu helfen, könntest du uns etwas von der SchachFieldDefinition ( aka Code ) schicken.

[mr47]

Mein Ansatz wäre dass mit einem Koordinatensystem zu machen. Jedes Feld hat zwei Nummern (Also x und y). Dann schreibst du für jede Figurenart eine kleine Liste, was erlaubt ist. Also für das Pferd ist
z.B. y+2 und x+1 oder y+2 und x-1 oder so ähnlich.....

Für den Bauern ist immer nur y+1 erlaubt. Allerdings gibts ja dann die Ausnahme mit dem Schlagen.... Da wäre ja dann x+1 und y+1 auch erlaubt. hm...

mfg mr47

[JasonDX]

Eine andere Möglichkeit, die es gäbe, wäre die möglichen Richtungen und Distanzen zu speichern. d.h. "Diese Figur kann in diese und diese Richtung so und so weit laufen".
(nähere Details kriegste, nachdem ich mir das morgen in der Schule nochmal genauer durchdacht hab ;) )

Das if beim Schlagen&Starten mit dem Bauern wirst du allerdings nicht wegkriegen, außer du kommst auf ne ganz tolle idee, die aber ws um einiges komplizierter ist :stupid:

@mr47: Beim aufschreiben der der Möglichkeiten durch X+1&Y+0 musst du über 100 Möglichkeiten aufschreiben (da sind ein paar ifs fast schöner :zwinker: )

[Sharky]

Hai Frederic,

ich kenne mich in diesem Gebiet zwar nicht aus. Aber eine Überlegung:

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?

[JasonDX]

So, eine Stunde Deutsch ist um und hatte somit genug Zeit, über meine Idee nachzudenken :mrgreen:

Kurz eine Erklärung zum Prinzip von Distances und Directions:

Jede Figur kann in bestimmte Richtungen bewegen. Der Turm nur Waag- und Senkrecht, der Läufer nur Diagonal, Königin und König beides; Der Springer nur in einem anderen Winkel, und den Bauern sehn wir mal als Ausnahme.
Damit können wir uns folgendes Set von Richtungen Definieren

Delphi-Quellcode:

  TChessDirection = (cdRook, cdKnight1, Knight2, cdBishop, cdNone);

die None-Direction brauchen wir für den Fall, dass die Richtung keiner Bekannten entspricht, und wir haben 2 Richtungen für den Springer, warum sehen wir später

Um nun angeben zu können, wer wohin laufen kann, brauchen wir ein set of, wo wir dann auch die Richtungen der Figuren bereits definieren können

Delphi-Quellcode:

  TChessDirections = set of TChessDirection;
  TChessFigures = (cfPawn, cfRook, cfKnight, cfBishop, cfQueen, cfKing);
 
const
  PossibleDirections: array[TChessFigures] of TChessDirections = 
      ([], //Pawn - Ausnahme
       [cfRook], //Rook
       [cfKnight], //Knight
       [cfBishop], //Bishop
       [cfRook, cfBishop], //Queen
       [cfRook, cfBishop]); //King

Damit das nun langsam Werte werden, die wir brauchen können, definieren wir Konstanten, welche Richtung welchem Winkel entspricht:

Delphi-Quellcode:

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

Hier brauchen wir für den Springer eben nur 2 Richtungen, weil er im Bereich von 90° in 2 Richtungen laufen kann. (2 nach oben, 1 links, oder 1 nach oben und 2 links)

Damit wir nun aber das aber auch was bringt, brauchen wir eine Funktion, die uns sagt, welche Richtung das ist.

Delphi-Quellcode:

function GetDirection(Source: TPoint; Destiny: TPoint): TChessDirection;
var
  angle: real;
  i: TChessDirection;
begin
  result := cdNone;
  //Winkel ausrechnen
  angle := arcsin(abs(Source.Y - Destiny.Y) / sqrt(sqr(Source.X - Destiny.X) + sqr(Source.Y - Destiny.Y))) + 4*Pi;
//Hier bin ich mir nicht sicher, ob der folgende Teil stimmt. am ende soll halt folgendes gelten: 0 < angle <= Pi / 2
  while angle > 1.5707 do 
    angle := angle - 1.570
  for i := cdRook to cdBishop do
    if trunc(angle * 1000) = DirectionAngles[i] then
      result := i;
end;

Hier wird nun rausgefunden, welche Richtung bewegt wurde. Im fall dass nix passt, ist es cdNone. Dafür brauchen wir das. Wenn nun bei PossibleDirections irgendwo cdNone vorkommt, kann er überall hinbewegen, wo sonst keiner hin kann.

Damit hätten wir mal die Richtungen abgeschlossen.
Nun brauchen wir noch die Distanzen:
Jede Figur hat eine Maximale Reichweite. Der König kann maximal 1 Feld gehen, auch diagonal, also ist die Maximale distanz ca. 1.5, Der Springen kann schon etwas weiter laufen, ca. 2.3, und die restlichen Figuren (Der Bauer ist immernoch die Ausnahme) können auch 15 Felder laufen, wenn nicht das Spielfeld vorher fertig wär ;)
Die Distanzen können wir ganz einfach in einer Konstante speichern:

Delphi-Quellcode:

const
  MaxDistances: array[TChessFigures] of real = (1, 15, 2.3, 15, 15, 1.7);

Ob nun die Bewegung von der Distanz her auch passt, können wir ganz einfach überprüfen:

Delphi-Quellcode:

function GetDistance(Source: TPoint; Destiny: TPoint): real;
begin
  result := sqrt(sqr(Source.X - Destiny.X) + sqr(Source.Y - Destiny.Y));
end;

Mit diesem ganzen Rast können wir nun (bis auf unsre Ausnahme, den Bauern) überprüfen, ob der Zug möglich ist

Delphi-Quellcode:

function IsDirectionPossible(Source: TPoint; Destiny: TPoint; Figure: TChessFigure): boolean;
begin
  result := (GetDirection(Source, Destiny) in PossibleDirections[Figure]) //die Richtung
    and (GetDirection(Source, Destiny) < MaxDistance[Figure]); //und die Entfernung muss passen
end;

Was du noch überprüfen musst ist, ob eine Figur auf dem Zielfeld steht, und v.a. ob sich eine Figur dazwischenbefinden, wofür dir die Directions auch zuhilfe kommen könnten ;)


Die ganzen Quellcodes hab ich nicht probiert, als keine Garantie, dass sie laufen. Das ganze soll eine Anregung sein, wie du sowas machen könntest. Und Fragen dazu kannst du mir jederzeit stellen ;)

[edit=sakura] *wuppdi* Mfg, sakura[/edit]

[fkerber]

Hallo!

Danke für die vielen Infos, insbesondere die von Mike.
Ich lasse es mir durch den Kopf gehen. Danke.

Ciao Frederic

[MarkusB]

Moin fkerber!

Also ehrlich gesagt viel von dem Chimaira Posting habe ich nicht verstanden (mag sein, dass das an meiner begrenzten Vorstellungsmöglichkeiten liegt). Deswegen habe ich versucht eine einfachere Lösung zu finden.

Als Grundlage der ganzen Analyse würde ich das reale Schachbrett nehmen. Das heißt ein Quadrat mit den Abmaßen: A bis H und 1 bis 8. Jede Spielfigur kann sich nur in diesen Grenzen bewegen, also die Definition der Position einer Figur lautet:

Delphi-Quellcode:

  TPosition = record
    letter: (A, B, C, D, E, F, G, H);
    number: 1..8;
  end;

Bei einem Zug sind zwei Positionen gegeben: Start und Ende die abhängig von der Figur unterschiedlich geprüft werden müssen. In Falle eines Springers würde ich folgende Prüfung vorschlagen. Die Funktion CheckSpringer liefert “true” zurück, wenn der Zug gültig ist oder “false” wenn nicht. Natürlich ist das nicht alles was man bei einem Springerzug prüfen muss.

Delphi-Quellcode:

function TForm1.CheckSpringer(Start, Ende: TPosition): boolean;
begin
  // pessimistische Annahme
  CheckSpringer:= false;

  // Bewegung: 1 Feld Rechts bzw. Links und dann 2 Felder Hoch bzw. Runter
  if (
        (Ende.letter = succ(Start.letter))
        or
        (Ende.letter = pred(Start.letter))
     )
     and
     (
        (Ende.number = Start.number + 2)
        or
        (Ende.number = Start.number - 2)
     )
  then CheckSpringer := true;

  // Bewegung: 2 Felder Rechts bzw. Links und 1 Feld Hoch  bzw. Runter
  if (
        (Ende.letter = succ(succ(Start.letter)))
        or
        (Ende.letter = pred(pred(Start.letter)))
     )
     and
     (
        (Ende.number = Start.number + 1)
        or
        (Ende.number = Start.number - 1)
     )
  then CheckSpringer := true;
end;

Viele Grüße
Markus
:gruebel:

[fkerber]

Hi!

Jepp, ich blicke bei Chimaira auch noch nicht ganz durch, aber ich werde mir das sicherlich noch in Ruhe ansehen.
Dein Vorschlag Markus ist ja das, was ich mit xxx If-Abfragen meine.
Oder ist das doch sinnvoller?

Ciao Frederic

[malo]

Zitat:

Zitat von fkerber

Oder ist das doch sinnvoller?

Das ist IMHO einfacher ;)

Allerdings sollte man auch noch beachten, dass man prüfen muss, ob eines der Felder bereits besetzt ist, auf die man kommt. Das ist beim Springer recht einfach (man muss nur den Endpunkt überprüfen, ob da jemand steht). Aber bei anderen Figuren muss man rekursiv jedes einzelne Feld überprüfen, ob eine eigene oder eine gegnerische Figur dort steht (für den Anfang reicht, ob überhaupt eine dort steht). ;)