Welche Bedeutung hat die Initialisierung von Richtungsarrays unten mit vorgegebenen Werten bei der Entwicklung eines Schachprogramms?

106

Ich bin neu in der wettbewerbsfähigen Programmierung und habe häufig festgestellt, dass viele der großen Codierer diese vier Zeilen in ihrem Code haben (insbesondere bei Arrays):

int di[] = { 1, -1, 0, 0, 1, -1, 1, -1 };
int dj[] = { 0, 0, 1, -1, 1, -1, -1, 1 };
int diK[] = { -2, -2, -1, 1, 2, 2, 1, -1 };
int djK[] = { -1, 1, 2, 2, 1, -1, -2, -2 };

Was bedeutet das wirklich und wofür wird Technik angewendet?

ejjyrex
quelle
5
Ich benutze oft d={0,1,0,-1,0}dafür: Gegenstandspaare, d[i], d[i+1]um mir vier Himmelsrichtungen zu geben.
Dasblinkenlight
14
Dies ist eine überraschend gute Frage. ... Kann etwas gegen den Titel unternommen werden?
luser droog
7
Sie haben also nicht daran gedacht zu erwähnen, dass dieser Code von einer Schachengine stammt? Sie haben auch nicht daran gedacht, selbst zu sehen, wie diese Werte verwendet werden?
Trojanfoe
15
"Viele der großartigen Codierer haben diese vier Zeilen [...]" - Ich wähle hier nicht aus, aber wenn sie großartige Codierer wären, würde ihr Code Sie nicht dazu bringen, sich zu fragen: "WTF ist dieses Konstrukt?!"
utnapistim
6
@utnapistim Wenn Sie den größten Teil des Codes schreiben, haben Sie Recht, aber hier fehlt Ihnen der Punkt. Dieser Fall ist eine legitime Ausnahme von dieser Regel. Wenn Sie Code für einen Wettbewerb schreiben und unter Zeitdruck stehen, ist Quick-and-Dirty fast immer besser als Clean-and-Maintenance. In diesem Fall lesbar zu Ihnen, jetzt wirklich ist alles, was zählt. Ein großartiger Programmierer schreibt in diesem Zusammenhang sehr gut ein nicht wartbares, nicht lesbares Durcheinander , selbst wenn der größte Teil seines regulären Codes gut lesbar und wartbar ist.
Ben Lee

Antworten:

84

Dies ist eine Technik, um alle Richtungen als Arrays zu codieren - jedes Paar di[i],dj[i]ist eine andere Richtung.

Wenn wir uns vorstellen, dass wir ein Stück an einem Ort x, y haben und wir es zu seinem x- und y-Wert addieren möchten, um es an einen nahe gelegenen Ort zu verschieben, ist 1,0 Ost, -1,0 West, 0,1 ist südlich, 0, -1 ist nördlich und so weiter.

(Hier habe ich gesagt, dass oben links 0,0 und unten rechts 4,4 ist und gezeigt, welche Bewegung jeder Index der Arrays vom Mittelpunkt X bei 2,2 macht.)

.....
.536.
.1X0.
.724.
.....

So wie es eingerichtet ist, erhalten Sie ^1( wenn Sie ^bitweise XOR sind) auf dem Index die entgegengesetzte Richtung - 0 und 1 sind Gegensätze, 2 und 3 sind Gegensätze und so weiter. (Eine andere Möglichkeit, es einzurichten, besteht darin, von Norden aus im Uhrzeigersinn zu fahren und dann in ^4die entgegengesetzte Richtung zu gelangen.)

Jetzt können Sie alle Richtungen von einem bestimmten Punkt aus testen, indem Sie Ihre diund djArrays durchlaufen , anstatt jede Richtung in einer eigenen Zeile aufschreiben zu müssen (insgesamt acht!) (Vergessen Sie nur nicht, die Grenzwerte zu überprüfen :))

diKund djKbilden alle Ritter Richtungen anstelle aller benachbarten Richtungen. Hier ^1wird entlang einer Achse gedreht, ^4wird der entgegengesetzte Rittersprung geben.

.7.6.
0...5
..K..
1...4
.2.3.
Patashu
quelle
3
Was sind "Ritter Richtungen"?
David
4
Oh, diese Art von Ritter.
David
1
Vielen Dank für Ihre Antwort. Könnten Sie mich bitte verlinken oder mir einen Code zeigen, um ihn besser zu veranschaulichen. (Ich bin ein bisschen Anfänger. Wenn Sie verstehen könnten :)
Nochmals vielen
1
Ich begrüße Patashus Versuch einer Antwort. Obwohl es scheint, dass viele seine Erklärung verstanden haben, konnte ich sie nicht gut verstehen. Wenn jemand etwas zu dem hinzufügen kann, was bereits gesagt wurde, wäre ich sehr dankbar.
Deepak
1
@deepak Stellen Sie sich vor, eine Position wird durch ein x,yTupel im 2D-Raum dargestellt. di[i], dj[i]Fügen Sie es für jedes Paar hinzu x,yund Sie werden x,ynacheinander in jede Richtung transponiert. Ist das sinnvoll?
Patashu
64

Für diejenigen, denen Patashus Erklärung schwer zu folgen ist, werde ich versuchen, sie zu klären.

Stellen Sie sich vor, Sie versuchen, jeden möglichen Zug von einem bestimmten Punkt auf einem Schachbrett aus zu berücksichtigen.

Wenn Sie die Arrays di und dj durchlaufen und die di-Werte als x-Offsets und die dj-Werte als y-Offsets interpretieren, decken Sie jede der möglichen 8 Richtungen ab.

Angenommen, positives x ist Ost und positives y ist Süd (wie in Patashus Antwort), erhalten Sie Folgendes:

  | di / x | dj / y | Richtung
- + ------ + ------ + -----------
0 | 1 | 0 | Osten
1 | -1 | 0 | Westen
2 | 0 | 1 | Süd
3 | 0 | -1 | Norden
4 | 1 | 1 | Süd-Ost
5 | -1 | -1 | Nordwest
6 | 1 | -1 | Nordost
7 | -1 | 1 | Südwesten

Die diK- und djK-Arrays können auf die gleiche Weise interpretiert werden, um die möglichen Bewegungen für das Knight-Stück festzulegen. Wenn Sie mit Schach nicht vertraut sind, bewegt sich der Ritter in einem L-Muster - zwei Quadrate in eine Richtung und dann ein Quadrat im rechten Winkel dazu (oder umgekehrt).

  | diK / x | djK / y | Richtung
- + ------- + ------- + ----------------
0 | -2 | -1 | 2 West, 1 Nord
1 | -2 | 1 | 2 West, 1 Süd
2 | -1 | 2 | 1 West, 2 Süd
3 | 1 | 2 | 1 Ost, 2 Süd
4 | 2 | 1 | 2 Ost, 1 Süd
5 | 2 | -1 | 2 Ost, 1 Nord
6 | 1 | -2 | 1 Osten, 2 Norden
7 | -1 | -2 | 1 West, 2 Nord
James Holderness
quelle
1

Ein kleiner Codeausschnitt zur Überprüfung der Anzahl der Bewegungen in alle Richtungen, bei denen die definierten Arrays verwendet werden.

int di[] = { 1, -1, 0, 0, 1, -1, 1, -1 };
int dj[] = { 0, 0, 1, -1, 1, -1, -1, 1 };
int movesPossible[8];
int move = 0;
int posx, posy; // position of the figure we are checking

for (int d=0; d<8; d++) {
  for (move = 1; board.getElt(posx+di[d]*move, posy+dj[d]*move)==EMPTY; move++) ;
  movesPossible[d] = move-1;
}
Dariusz
quelle