Welche Bedeutung hat die Initialisierung von Richtungs-Arrays unten mit gegebenen Werten bei der Entwicklung eines Schachprogramms?

Ich bin neu in der kompetitiven Programmierung, und mir ist häufig aufgefallen, dass viele der großen Programmierer diese vier Zeilen in ihrem Code haben (insbesondere in denen, die Arrays beinhalten):

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 verwendet?

Dies ist eine Technik, um alle Richtungen als Arrays zu codieren – jedes Paar von 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 seinen x- und seinen y-Wert addieren möchten, um es an einen nahe gelegenen Ort zu verschieben, ist 1,0 Osten, -1,0 Westen, 0,1 ist Süden, 0,-1 ist Norden 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 machen wird.)

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

Die Art und Weise, wie es eingerichtet ist, wenn Sie dies tun ^1 (^ bitweises XOR) auf dem Index erhalten Sie 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 gehen – dann ^4 bringt Sie in die entgegengesetzte Richtung.)

Jetzt können Sie alle Richtungen von einem bestimmten Punkt aus testen, indem Sie eine Schleife über Ihre ziehen di und dj Arrays, anstatt jede Richtung in eine eigene Zeile schreiben zu müssen (für insgesamt acht!) (Vergessen Sie nur nicht, die Grenzen zu überprüfen 🙂 )

diK und djK alle bilden Ritter Richtungen anstelle aller angrenzenden Richtungen. Hier, ^1 dreht sich entlang einer Achse, ^4 gibt dem gegenüberliegenden Springer einen Sprung.

.7.6.
0...5
..K..
1...4
.2.3.

Für diejenigen, die Patashus Erklärung schwer verständlich finden, werde ich versuchen, sie klarzustellen.

Stellen Sie sich vor, Sie versuchen, jeden möglichen Zug von einem bestimmten Punkt auf einem Schachbrett aus in Betracht zu ziehen.

Wenn Sie die di- und dj-Arrays 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 Osten und positives y ist Süden (wie in Patashus Antwort), erhalten Sie Folgendes:

  | di/x | dj/y | Direction
--+------+------+-----------
0 |   1  |   0  | east
1 |  -1  |   0  | west
2 |   0  |   1  | south 
3 |   0  |  -1  | north
4 |   1  |   1  | south-east
5 |  -1  |  -1  | north-west
6 |   1  |  -1  | north-east
7 |  -1  |   1  | south-west

Die diK- und djK-Arrays können auf die gleiche Weise interpretiert werden, um die möglichen Züge für die Springerfigur festzulegen. Wenn Sie mit Schach nicht vertraut sind, bewegt sich der Springer in einem L-Muster – zwei Felder in eine Richtung und dann ein Feld im rechten Winkel dazu (oder umgekehrt).

  | diK/x | djK/y | Direction
--+-------+-------+----------------
0 |  -2   |  -1   | 2 west, 1 north
1 |  -2   |   1   | 2 west, 1 south
2 |  -1   |   2   | 1 west, 2 south
3 |   1   |   2   | 1 east, 2 south
4 |   2   |   1   | 2 east, 1 south
5 |   2   |  -1   | 2 east, 1 north
6 |   1   |  -2   | 1 east, 2 north
7 |  -1   |  -2   | 1 west, 2 north

Ein kleines Code-Snippet, um die Anzahl der möglichen Bewegungen in alle Richtungen zu überprüfen, die die definierten Arrays verwenden.

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;
}