DIR Return Create A Forum - Home
---------------------------------------------------------
The Chess Variant Forum
HTML https://chessvariantforum.createaforum.com
---------------------------------------------------------
*****************************************************
DIR Return to: Variant Theory
*****************************************************
#Post#: 274--------------------------------------------------
Math question about the knight and hawk.
By: chilipepper Date: January 28, 2018, 9:40 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?
[attachimg=1]
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. ::)
#Post#: 276--------------------------------------------------
Re: Math question about the knight and hawk.
By: GothicChessInventor Date: January 28, 2018, 11:40 am
---------------------------------------------------------
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.
#Post#: 278--------------------------------------------------
Re: Math question about the knight and hawk.
By: chilipepper Date: January 28, 2018, 2:55 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. :)
#Post#: 281--------------------------------------------------
Re: Math question about the knight and hawk.
By: HGMuller Date: January 29, 2018, 2:02 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.
#Post#: 282--------------------------------------------------
Re: Math question about the knight and hawk.
By: chilipepper Date: January 29, 2018, 10:49 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.
#Post#: 284--------------------------------------------------
Re: Math question about the knight and hawk.
By: GothicChessInventor Date: January 29, 2018, 11:09 am
---------------------------------------------------------
[quote author=chilipepper link=topic=51.msg282#msg282
date=1517244591]
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.
[/quote]
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.
#Post#: 289--------------------------------------------------
Re: Math question about the knight and hawk.
By: chilipepper Date: January 29, 2018, 4:48 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).:)
#Post#: 291--------------------------------------------------
Re: Math question about the knight and hawk.
By: GothicChessInventor Date: January 29, 2018, 8:50 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.
#Post#: 295--------------------------------------------------
Re: Math question about the knight and hawk.
By: chilipepper Date: January 30, 2018, 10:05 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:
[attachimg=1]
#Post#: 306--------------------------------------------------
Re: Math question about the knight and hawk.
By: GothicChessInventor Date: January 30, 2018, 7:59 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.
*****************************************************
DIR Next Page