Author Topic: Math question about the knight and hawk.  (Read 129 times)

chilipepper

  • Full Member
  • ***
  • Posts: 100
  • chilipepper
  • Location: U.S.
    • View Profile
    • QyiQ23607 Pisano
Math question about the knight and hawk.
« on: January 28, 2018, 10:40:23 am »
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. ::)
« Last Edit: January 28, 2018, 10:49:59 am by chilipepper »
the "chilipepper"👹

Share on Facebook Share on Twitter


GothicChessInventor

  • Full Member
  • ***
  • Posts: 175
    • View Profile
Re: Math question about the knight and hawk.
« Reply #1 on: January 28, 2018, 12:40:07 pm »
This wasn't too hard to solve. It took me about 10 minutes to get the specific solution and 25 minutes to create a general, closed-form solution using equations that can solve any generic form of the request. I won't spoil the result by posting it right away but once everyone has "given up," I will.

chilipepper

  • Full Member
  • ***
  • Posts: 100
  • chilipepper
  • Location: U.S.
    • View Profile
    • QyiQ23607 Pisano
Re: Math question about the knight and hawk.
« Reply #2 on: January 28, 2018, 03:55:14 pm »
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. :)
the "chilipepper"👹

HGMuller

  • Global Moderator
  • Full Member
  • *****
  • Posts: 121
    • View Profile
Re: Math question about the knight and hawk.
« Reply #3 on: January 29, 2018, 03:02:23 am »
This is not very difficult to compute 'by hand'. By using only its 3-step moves, a Hawk would asct as a King on a 'diluted' grid (3*n, 3*m), and would cover a square on this grid of 2*N+1 x 2*N+1 reachable squares. The total set of squares reachable that way is contained in a 6*N+1 x 6*N+1 square. To reach intermediate squares, you would have to makr some 2-step moves. With a single 2-step move you can reach 1 square less far, and deviate 1 step from the diluted grid. This is not enough to cover the entire plane; there are some squares that were two King steps removed from the diluted grid, and you need to do at least two 2-step moves to reach those. Then your maximum outward range s reduced by two.

So the edge of the reachable area is like a 'triagle wave': on average it is a 6N-1 x 6*N-1 square, but the corners, and every square removed 3 steps from those sticks out 1 further, and the points on the circumference exactlu between that dent in one step. That does not alter the number of reachable squares, though. So tho reach a million squares or more, 6*N-1 has to be at least 1000, or N >= 167. WIth 167 moves you can reach 1002*1002 = 1,004,004 squares, but oe of these is your starting square, and should perhaps not be counted.

For the Knight you can do a similar calculation; the reachable area in this case is an octagon, and yuo would just have to determine exactly huw 'ragged' the orthogonal and diagonal edges of this octagon will be.

chilipepper

  • Full Member
  • ***
  • Posts: 100
  • chilipepper
  • Location: U.S.
    • View Profile
    • QyiQ23607 Pisano
Re: Math question about the knight and hawk.
« Reply #4 on: January 29, 2018, 11:49:51 am »
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.
the "chilipepper"👹

GothicChessInventor

  • Full Member
  • ***
  • Posts: 175
    • View Profile
Re: Math question about the knight and hawk.
« Reply #5 on: January 29, 2018, 12:09:11 pm »
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.

Apparently H.G. and I took similar approaches to the problem. Without spoiling anything (and just offering a hint):

Think of either a "Venn Diagram" that shows intersections, and use the concept of the union and intersection to create "difference equations" which filter out redundancies.

« Last Edit: January 29, 2018, 09:40:44 pm by GothicChessInventor »

chilipepper

  • Full Member
  • ***
  • Posts: 100
  • chilipepper
  • Location: U.S.
    • View Profile
    • QyiQ23607 Pisano
Re: Math question about the knight and hawk.
« Reply #6 on: January 29, 2018, 05:48:01 pm »
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).:)
« Last Edit: January 30, 2018, 10:16:19 am by chilipepper »
the "chilipepper"👹

GothicChessInventor

  • Full Member
  • ***
  • Posts: 175
    • View Profile
Re: Math question about the knight and hawk.
« Reply #7 on: January 29, 2018, 09:50:01 pm »
Just take out a piece of graph paper. Fill in a square near the center with a red marker. Imagine that is your piece. Then color in all of your blocks where the piece can move using a black marker. That gives you a "geometry of 1 piece from 1 square" that definitely has a boundary. If you are ignoring the outer edges of the graph paper for the time being, look at the squares that are empty within the black marker's imaginary perimeter. It is easy to determine how many of "n x n" squares surrounding it can be "filled" provided you move the piece around from the red square in the center. Some squares overlap. Make a note of the piece location. Move it somewhere else with no overlap. Continue to fill in squares "mentally," counting overlap and non-overlapping regions. Next, create a formula in terms of "N x N" which gives you non-vacant squares as densely packed as possible without collisions vs. the sum of squares intersected with within the boundaries. These ratios tell you something as you replicate the approach. Once you understand what that is, you can then generate a closed-form solution to your problem. It's as easy as coloring in blocks, counting, computing ratios, then multiplying the results. Whatever number you want in the end, just solve a/b = x where x is the outcome.

chilipepper

  • Full Member
  • ***
  • Posts: 100
  • chilipepper
  • Location: U.S.
    • View Profile
    • QyiQ23607 Pisano
Re: Math question about the knight and hawk.
« Reply #8 on: January 30, 2018, 11:05:52 am »
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:

« Last Edit: January 30, 2018, 01:35:21 pm by chilipepper »
the "chilipepper"👹

GothicChessInventor

  • Full Member
  • ***
  • Posts: 175
    • View Profile
Re: Math question about the knight and hawk.
« Reply #9 on: January 30, 2018, 08:59:53 pm »
You're taking the "maximum telescoping approach" and not economizing the solution in such a way to derive something that is what we call a "closed form." If I have some time this weekend, I will do a step-by-step solution on graph paper and post it here.

HGMuller

  • Global Moderator
  • Full Member
  • *****
  • Posts: 121
    • View Profile
Re: Math question about the knight and hawk.
« Reply #10 on: January 31, 2018, 06:11:50 am »
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.
« Last Edit: January 31, 2018, 06:26:01 am by HGMuller »

chilipepper

  • Full Member
  • ***
  • Posts: 100
  • chilipepper
  • Location: U.S.
    • View Profile
    • QyiQ23607 Pisano
Re: Math question about the knight and hawk.
« Reply #11 on: January 31, 2018, 10:58:05 am »
Thanks HGMuller, that is awesome work. It is interesting that your initial calculation had a slight error (no critisism) and yet the final result (number of moves) was correct, and the total number of reachable squares very close to your initial figure. (small errors in math and algebra aren't always so inconsequential).

I now take it that 1,000,000 or more destination squares can be reached by 167 moves of the hawk. (1,003,321 with N=167).

This problem would also lend itself to solution by a worksheet macro or a simple computer program. But doing it with only mathematical equations is way more elegant and impressive! Nicely done. :)

To help visualize the problem, here is a diagram with all the hawk's moves for N=2 (1 quadrant), and counting the ways each square can be reached (from only within that quadrant). The total squares that can be reached for N=2 is 105 (assuming I made no errors).
« Last Edit: January 31, 2018, 06:21:48 pm by chilipepper »
the "chilipepper"👹

HGMuller

  • Global Moderator
  • Full Member
  • *****
  • Posts: 121
    • View Profile
Re: Math question about the knight and hawk.
« Reply #12 on: January 31, 2018, 01:07:41 pm »
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.

chilipepper

  • Full Member
  • ***
  • Posts: 100
  • chilipepper
  • Location: U.S.
    • View Profile
    • QyiQ23607 Pisano
Re: Math question about the knight and hawk.
« Reply #13 on: January 31, 2018, 06:20:19 pm »
Thanks for noticing the error in my diagram. I get that the hawk in two jumps can land on 113 distinct squares. A corrected diagram is here:


Your result for the knight also matches what I found. In two jumps it can land on 41 different squares. Diagram:

the "chilipepper"👹