The Chess Variant Forum

Someone said during a game that the hawk has a million forking possibilities. This made me wonder, in how many moves does the hawk have a million options of different squares to land on? More precisely, and to compare it with the knight (the only jumper in normal chess):

Without counting the same square twice, and assuming an unbounded playing area with no other pieces, how many moves would it require for each the knight and the hawk to have one million different options as its destination square? And what is the specific number of options for different squares to land on with each of these numbers of moves?

Extra credit:
1) What is the farthest reach for this number of moves?
2) Post an image of all the squares each of these pieces can visit for these numbers of moves. This would probably require some custom software to do, or a lot of cutting and pasting, but  would probably satisfy anyone's curiosity about the nature of this many moves for each of these pieces. I would be surprised if anyone does it, at least not within a year or so.

That's pretty good. I haven't given it a real stab at it yet, but I don't think I would be able to do it that fast. For now, this isn't giving away anything obvious:

If one considers only the number of moves, but ignores overlapping squares (squares that can be arrived at in more than one way), then these are the first two sets of numbers that arrive at over a million:

(These are not the answers - just some math):

knight:
7 moves: 8^7 = 2,097,152
8 moves: 8^8 = 16,777,216

hawk:
5 moves: 16^5 = 1,048,576
6 moves: 16^6 = 16,777,216

My rough prediction is that the answer is close to 8 moves for the knight, and 6 moves for the  hawk. But I'm dying to find out. I may be way underestimating the effect of overlapping squares. Thanks for not yet revealing the answer. I may yet work on it at my next opportunity of thinking time.

HGMuller, I like the idea of breaking the moves down into single types of moves (i.e investigate all 2-square orthogonal jumps, 3-square orthogonal jumps, 2-square diagonal jumps, etc). But it's not clear to me at what point in your calculation are you subtracting or discounting squares that are reached by more than one type of jump, or squares reached by jumping forwards and then backwards).

Is it shown in your work or is that another "next to do" step?

Btw, I would count the initial square as reachable if it can be reached with one or more jumps. Although we're not counting the "0th" jump, it can get there on the 2nd and other jumps.

I just realized that HGmuller's reply includes the answer for the hawk. "With 167 moves you can reach ... 1,004,004 squares..." Does that match your answer?

I basically understand the technique, but didn't work out the specifics. The venn-diagram basically paints a picture of all squares covered in "N" moves (as I would describe it). But I don't understand why the shape is described as a "triangle wave". I see it as a square increasing in size as N increases, and it has imperfect coverage at the edges and corners.

To see if your formulas are correct, can you let me know the number of squares covered in two jumps for each piece? I worked it out by hand (I hope correctly) and am curious if we all get the same value for a small "N". (and if the formulas are equivalent).

I started that but didn't take it to a point of producing a generalized equation yet.

But for now my questions about HGMuller's last post haven't really been answered yet. Have you (or anyone?) confirmed his result for the hawk? He concluded that the hawk requires 167 moves to have at least 1,000,000 options of a square to land on (1,004,004 squares).

Also I'm wondering if we all get the same answer for the number of possible destination squares after two moves for both the knight and the hawk. This is almost trivial, but I graphed it, so it will let us know if we're all on the same page for a small "N". I'll post the diagram once I see at least one other person's numbers.

Also, I don't see why HGMuller calls it a "triangle wave". As I see it, the hawk's outer limit for any move number forms a square (with partial fill at the edges). Diagram here:

I was a bit hasty in my initial posting, and now I realize that there are a few squares near the corners of the reachable area that can actually not be reached. I was also wrongly imagining the shape of the boundary as if the distance between the outermost points was 4 steps (which you would get for a piece that could leap over distances 3 and 4). This does not change the answer for how many steps you need to cover a million squares, though, as this was overshoorting that target by more than 4000 squares. The correct argument is this:

Using oly steps of length 3, a 'diluted grid' with spacing 3 an be reached. The image below shows one quadrant of the reachable area for 5 such moves, the Hawk starting at #, the * indicating reachable squares.

* . . * . . * . . * . . * . . *
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
* . . * . . * . . * . . * . . *
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
* . . * . . * . . * . . * . . *
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
* . . * . . * . . * . . * . . *
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
* . . * . . * . . * . . * . . *
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
# . . * . . * . . * . . * . . *

Next we check how we could get to in-betwee squares. The upper-right corner can only be reached by 5 diagonal leaps of length 3. But by replacing oe of these by a leap of length 2, we advanced one square less along the diagonal ('1' below), and doing that twice even two squares less ('2'). To advance even less along the diagonal (e.g. to 'C'), we can just take fewer steps.

* . . * . . * . . * . . * . . *
. . . . . . . . . . a b c . 1 .
. . . . . . . . . . 2 2 . 2 . .
* . . * . . * . . B 3 x C . c *
. . . . . . . . 1 1 y 1 x 2 b .
. . . . . . . . + + + y 3 2 a .
* . . * . . * . + A + 1 B . . *
. . . . . . . . + + + 1 . . . .
. . . . . . . . . . . . . . . .
* . . * . . * . . * . . * . . *
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
* . . * . . * . . * . . * . . *
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
# . . * . . * . . * . . * . . *

The diluted-grid squares on the outer rim next to the corner can only be reached by 4 diagonal leaps, followed by one orthogonal one. But this gives us the choice to replace only diagonal leaps by a length of 2 (tracing a diagonal via 'b' and '2' to 'B'), or also replace the orthogonal step by a shorter one (leaving us at 'c'). For any square you can reach you can also reache squares diagonally inward by replacing one of the diagonal leaps by a shorter one. Note that even to go 5 leaps straight up you can always take half the steps diagonally up-right, and the other half diagonally up-left, so there are always many diagonal steps available in the path that you could make shorter.

Note that for reaching squares on the diluted grid two steps inward from the outermost ring (e.g. 'A'), you need two steps less than you have, so you can make the remaining two steps 3-out, 2-in to step, to step to the adjacent squares '+'. This fills up the entire plane in the inner region. Square 'a' can be reached by stepping to 'C', and then take a leap of length 2 perpendicularly.

So all squares just inside the outer periphery are reachable, except those next to the '1'. And for each of those you can move to the squares more diagonally inward. That leaves only the diagonals adjacent to the main diagonal. C can be reached with 3 diagonal leaps, then one up and one right. By taking one of the latter of length 2, we can reached the 'x' squares. (And thus also the squares diagoally inward from those, such as 'y'.) So from the (6*N-1) x (6*N-1) area only 4 x 4 squares near the corners are not reachable.

On the outermost rim only 2*N squares are reachable on each edge (counting the corners as 1/2, because they are on 2 edges). So the total number of squares reachable in N moves is (6*N-1)*(6*N-1) + 8*N - 16. For N=167 this is 1001*1001 + 1336 - 16 = 1,003,321 squares.

Note that this calculation is based on that the number of allowed moves is large, so that you could always find enough steps in the desired directions to replace by a shorter one. For N <= 3 this would not always be possible, and the formula would not apply.

I think the counting isn't entirely correct. (E.g. the (2,5) square should be reachable by (2,2) + (0,3).)

Anyway, I think diagrams like this are important for predicting leaper values with more precision. Being able to reach the same square in multiple ways is somewhat better than reaching it only in one way. But not early as good as reaching multiple squares that are all different. Ths explains why the Knight is one of the best leapers with 8 targets. There is no overlap between its one- and two-move targets. And the redundancy within the two-move set is as small as you can expect from a fully symmetric piece (each target reachable in 2 ways, except those 8 made by two identical moves). So it can reach 41 squares (including its square of origin). A Commoner can only reach 25 squares in 2 steps. A range-2 Rook only 33.