What is the significance of initializing direction arrays below with given values when developing chess program?

Question

I am new to competitive programming, and I noticed frequently, many of the great coders have these four lines in their code (particularly in those involving 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 };

What does this really signify and what is technique used for?

I often use `d={0,1,0,-1,0}` for this: item pairs for `d[i], d[i+1]` give me four cardinal directions. — Sergey Kalinichenko, May 03 '13 at 00:50
This is a surprisingly good question. ... Can something be done about the title? — luser droog, May 03 '13 at 00:55
I did my bit about the title/caption, but it would help more if there is any name for this group of arrays.Is there? — Rüppell's Vulture, May 03 '13 at 02:41
So you didn't think to mention that this code comes from a chess engine? Also you didn't think to **look** yourself how these values were being used? — trojanfoe, May 03 '13 at 06:17
@trojanfoe Keep in mind that people who code programs for competitive programming don't have maintainability, readability or clarity in mind - they just need to write it fast, make it efficient and then never have to read it again :) — Patashu, May 03 '13 at 06:29
If *everyone* has it in their program, it hardly needs to be documented or commented, just like we don't document why we chose the letter `i` for a loop dummy. — Kaz, May 03 '13 at 07:04
"many of the great coders have these four lines [...]" - I'm nitpicking here, but if they were great coders, their code would not cause you to wonder "wtf is that construct?!" — utnapistim, May 03 '13 at 11:02
@utnapistim I disagree. I don't think this code is really supposed to be readable, its their solution. Its readable to them, that's all that matters. — max, May 07 '13 at 20:17
@Max (Almost) all code is readable to the people who wrote it, but that fades with time. The best code there is, is not only perfectly readable when created, but _stays_ perfectly readable even ten years or more, after you wrote it. Even the paradigms you use naturally now (what is natural and obvious to you when writing the code - like your coding conventions) will become "weird legacy code" in a few years (not because the code changes but because best practices change). The less mental jumps you have to do when reading code (like wondering "what is that?") the better. — utnapistim, May 07 '13 at 20:56
@utnapistim When writing the vast majority of code, you are right, but here, you are missing the point. This case is a legitimate exception to that rule. If you are writing code for a competition and under a time constraint, quick-and-dirty is almost always better than clean-and-maintainable. In this case *readable to you, now* really *is* all that matters. A great coder very well write an unmaintainable unreadable mess *in this context*, even if most of their regular code is highly readable and maintainable. — Ben Lee, May 07 '13 at 21:12

score 85 · Answer 1 · edited May 09 '13 at 21:01

85

This is a technique to encode all directions as arrays - every pair of di[i],dj[i] is a different direction.

If we imagine we have a piece at a location x,y, and we want to add onto its x and its y value to move it to a nearby location, 1,0 is east, -1,0 is west, 0,1 is south, 0,-1 is north and so on.

(Here I have said top left is 0,0 and bottom right is 4,4 and shown what move each index of the arrays will make from the central point, X, at 2,2.)

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

The way it is set up, if you do ^1 (^ being bitwise XOR) on the index you get the opposite direction - 0 and 1 are opposites, 2 and 3 are opposites and so on. (Another way to set it up is to go clockwise starting at north - then ^4 gets you the opposite direction.)

Now you can test all directions from a given point by looping over your di and dj arrays, instead of needing to write out each direction on its own line (for eight in total!) (Just don't forget to do bounds checking :) )

diK and djK form all knights directions instead of all adjacent directions. Here, ^1 will flip along one axis, ^4 will give the opposite knight leap.

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

edited May 09 '13 at 21:01

Peter Mortensen

30,738
21
105
131

answered May 03 '13 at 00:46

Patashu

21,443
3
45
53

3

what are 'knights directions'? – David May 03 '13 at 00:51
1

Thank you so much for your answer.. Could you please link me or perhaps show me some code to better illustrate it..(I am a bit novice ..if u could understand:) Thanks again – ejjyrex May 03 '13 at 00:53
1

I applaud Patashu's attempt at an answer. While it seems that many have understood his explanation, I have not been able to understand it well. If anyone can add to what has already been said, I'd be very grateful. – deepak May 03 '13 at 02:03
1

@deepak Imagine a position is represented by an `x,y` tuple in 2D space. For each pair of `di[i], dj[i]` add it to `x,y` and you'll get `x,y` transposed in each direction one by one. Does that make sense? – Patashu May 03 '13 at 02:40
@Patashu Yeah I think i get it now. I was mostly confused about the figures you had drawn and how you got them. I finally understood those figures. – deepak May 03 '13 at 16:08

score 65 · Answer 2 · answered May 03 '13 at 04:44

For those finding Patashu's explanation difficult to follow, I'll attempt to clarify.

Imagine you are trying to consider every possible move from a given point on a chess board.

If you loop over the di and dj arrays, interpreting the di values as x offsets and the dj values as y offsets, you cover each of the possible 8 directions.

Assuming positive x is east and positive y is south (as in Patashu's answer), you get the following;

  | 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

The diK and djK arrays can be interpreted the same way to establish the possible moves for the Knight piece. If you're not familiar with chess, the Knight moves in an L pattern - two squares in one direction, and then one square at right angles to that (or vice versa).

  | 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

score 1 · Answer 3 · answered May 29 '13 at 12:20

A small snippet of code to check the amount of moves possible in all directions, which uses the defined arrays.

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

What is the significance of initializing direction arrays below with given values when developing chess program?

3 Answers3