Programming Piece Movement in Game Courier - A Tutorial
Game Courier provides two different ways of representing the board and consequently of calculating legal moves. The native way of representing the board is as a Cartesian grid of coordinates. On the Chess board, this way normally treats the space at a1 as coordinate (0,0) and the space at h8 as coordinate (7,7). Piece movement is normally calculated by calculating mathematical relationships between the coordinates of spaces. All the functions you have seen used for calculating the legality of moves in previous tutorials have made use of this mathematical model of representing the board. This is because this way of representing the board requires no additional setup, so that the functions that make use of it will work right away.
The other way of representing the board is as a set of interconnected spaces. While the first could be represented as a two-dimensional array, this could be represented as a linked list. As a linked list, each space would be a node, and each node would have named links to other nodes. The names would represent directions of movement. For example, a1->n could point to b1, b1->n to c1, etc. Here n would mean north. While it is a suitable convention to use compass directions as names for these directions, you could use any names for them as you pleased.
Although I can't remember exactly why, these types of coordinates are called logical coordinates. It's not that there is something illogical about mathematical coordinates. It's that these coordinates exist only in the logic of how the board is represented, not in some geometric space in which mathematical relations exist between spaces. If two spaces do not have a direct relation with each other, then movement between them is calculated in a step-by-step manner that searches for a path from one to the other. For example, to tell whether a Rook can move from a1 to b8, it might first check b1, then c1, etc, until it can't go past h1. It may then try moving from a1 to a2, then to a3, etc, until it can't get past a8. Having exhausted its possible routes of movement, it concludes that the move from a1 to b8 is illegal.
In contrast to this, the mathematical model can begin by examining the mathematical relationship between a1 and b8. Since this move is not a multiple of the Rook's most basic move, it can conclude that this move is illegal without trying to find a path between them. Also, if it were checking whether a Rook could move from a1 to a8, it would immediately calculate which direction it would take to go from a1 to a8, then check only the path between these two spaces. This will generally be faster than checking every possible path the Rook can move until it reaches its intended destination.
In general, the mathematical model is both faster and more convenient to use. The main reason to use the logical model is to be able to represent boards or piece movement that cannot so easily be done with the mathematical model. The mathematical model works great so long as your board fits on a grid, and your pieces' powers of movement don't get too unusual. The logical model is provided mainly for games for which the mathematical model is not suitable.
One example of this is Cylindrical Chess. In this game, otherwise played like standard Chess, the board is considered to be a cylander, such that each rank is a circle whose ends join together. On such a board, a Bishop could move from h4 to a5 with a diagonal move. But it would get tricky to represent this mathematically. It is far easier to say that movement from h4 to a5 counts as a move in a particular direction that the Bishop is capable of moving in. Another example is Circular Chess. Instead of being played on a Cartesian coordinate system, it uses polar coodinates. The logical model will handle polar coordinates just as easily as Cartesian coordinates, but the Cartesian-based mathematical model will not. If you want to play a four-dimensional game or a game on a torus or a mobius strip, logical coordinates would also be very helpful.
To use logical coordinates, you have to set them up, and you have to define your piece movement in terms of them. While you could tediously set them up link-by-individual-link, there is a shortcut for setting up logical coordinates for the portion of the board that fits in a grid. This uses the map command and looks like this for Chess:
map n 0 1 s 0 -1 w -1 0 e 1 0; // Orthogonal directions map nw -1 1 ne 1 1 sw -1 -1 se 1 -1; // Diagonal directions map nne 1 2 nnw -1 2 sse 1 -2 ssw -1 -2; // Hippogonal directions map nee 2 1 nww -2 1 sww -2 -1 see 2 -1; // Hippogonal directions
The convention used for naming directions is to use the first letters of compass directions. If you look at a Chess board diagram as though you are looking at a map, then the a1 corner lies in the southwest corner. Accordingly, White's forward movement is north, Black's is south, movement to White's left is west, and movement to White's right is east. Since the a1 corner is the origin of the board, northward and eastward movement is positive, while southward and westward movement is negative. This is easily seen in the first line. The next line defines diagonal directions in terms of both a north-south direction and an east-west direction. The last two lines define directions for Knight moves. Each of these is named for how many spaces the Knight moves north or south, followed by how many it moves east or west. In all, there are eight of them, because the Knight has up to eight possible moves.
Note that it is not defining north as movement that positively increases the rank number, nor is it defining any other direction in terms of movement in a Cartesian grid. Rather, it is going through all the spaces in the grid, consistently labeling the same types of movement on the grid with the same labels. As it goes through each space, it specifies directions of movement by indicating the space a piece will move to when it moves in that direction from a particular space. This ends up defining directions in an individual space-by-space manner instead of in a global, geometric manner. This becomes more clear when we add some exceptions.
Let's start with looking at what would need to be done for Cylindrical Chess, which just loops together the two sides an ordinary Chess board. We can use the link command to create additional links. For example, the following line creates an eastern direction for every space in the rightmost file of a Chess board.
link e (h1 a1) (h2 a2) (h3 a3) (h4 a4) (h5 a5) (h6 a6) (h7 a7) (h8 a8);
Similar lines could be done for other directions. To make things a little easier, the rlink command works just like the link command but reads arguments in reverse. The advantage of this is that you can copy the arguments used to create the east direction to create the west direction with rlink, like so:
rlink w (h1 a1) (h2 a2) (h3 a3) (h4 a4) (h5 a5) (h6 a6) (h7 a7) (h8 a8);
I can't show you the full code for how Cylindrical Chess does this, because the person who programmed it found a way to do with the mathematical functions. He managed it by writing much more complicated functions to describe piece movement. The advanatage of using logical directions is that you will be able to keep your piece movement logic simpler and easier to understand.
When I looked at my own code for Circular Chess, which does use logical coordinates, I could not find any link commands, and I puzzled over this for a while. Then I noticed what I did. While using exactly the same map commands as I listed above, I modified the files line to "d c b a p o n m l k j i h g f e d c". Notice that the same two files appear at both ends. While the directions from the inner files get calculated in one go, the directions from the end files get calculated partway the first time they appear, then get completed the second time they appear. For example, the directions from the d file to the c and b files get calculated at the beginning, and the directions from the d file to the e and f files get calculated near the end. Directions do not have to be calculated for more than two files away, because that is as far as a Knight's leap extends, and the longer moves of Bishops, Rooks, and Queens will be calculated as a series of one-step moves.
To get a better sense of both mathematical and logical functions for checking the legality of moves, let's look at how each handles movement of the same pieces. For each piece, I will first give the function for checking the legality of a specific move, then I will give the function for calculating the spaces to check for legal moves on. The second function is used to optimize the code when calculating possible moves, such as in the stalemated subroutine. Its use is just to limit the spaces legal moves are checked for on, which will save on the time and processing power needed to find all legal moves.
| Piece | Mathematical | Logical |
|---|---|---|
| Knight | def N checkleap #0 #1 1 2; This uses checkleap to check for a single leap to a space that is 1 rank and 2 files away or 1 file and 2 ranks aways. By reversing the last two arguments or negating each one as needed, this is able to cover all eight ways a Knight can move: (1 2), (-1 2), (1 -2), (-1 -2), (2 1), (-2 1), (2 -1), (-2 -1). def NL leaps #0 1 2; The leaps function returns an array of all the spaces that can be reached from #0 by a leap that is 1 rank and 2 files or 1 file and 2 ranks away. To calculate them all, it negates each of the last two arguments and reverses them as needed. |
def N logleap #0 #1 nne nnw sse ssw nee nww sww see; The logleap function checks whether the move was a single leap in any of the directions specified. def NL logleaps #0 nne nnw sse ssw nee nww sww see; The logleaps function returns an array of all the spaces a piece at #0 can directly leap two by going in each of the directions listed. |
| Nightrider | def N checkride #0 #1 1 2; The Nightrider can make a series of Knight moves in the same direction, so long as each space but the last is empty. It is like a Rook or Bishop except that its basic leap is a Knight's leap instead of a one-space leap. The only change from the code for the Knight is to replace checkleap with checkride. def NL rays #0 1 2; Here the only change is to replace leaps with rays. This function returns all the spaces that radiate out from #0 in the directions specified. |
def N logride #0 #1 nne nnw sse ssw nee nww sww see; The only change here is to replace logleap with logride. This checks the legality of any riding move made in any of the specified directions. def NL lograys #0 nne nnw sse ssw nee nww sww see; The only change here is to replace logleaps with lograys. This returns an array of all spaces that can possibly be reached through a series of leaps in the same direction, using each of the specified directions. |
| Rook | def R checkride #0 #1 1 0; This line checks for legal movement in any direction that moves one space at a time along any rank or file. The "1 0" will be reversed and negated by the function as needed, resulting in "1 0", "0 1", "-1 0" and "0 -1". This results in only four sets of values instead of eight, because 0 and -0 are the same number. def RL rays #0 1 0; This returns an array of all spaces along the same file or rank as the space at #0. Like checkride, it will reverse or negate the input of "1 0" as needed. |
def R logride #0 #1 s n e w; This checks the legality of any move composed of a series of one-step moves in any one of the directions listed, which here are all four orthogonal directions. So, it checks a series of south moves, then a series of north moves, then a series of east moves, then one of west moves. It stops searching as soon as it finds the space at #1. def RL lograys #0 n w s e; This returns an array of all spaces that can be found by moving in a straight line in any of the directions listed. |
| Bishop | def B checkride #0 #1 1 1; This line checks for legal movement in any direction that moves one space at a time along any diagonal line. The "1 1" will be negated by the function as needed, resulting in "1 1", "1 -1", "-1 1" and "-1 -1". This results in only four sets of values instead of eight, because the reverse of "1 1" is still "1 1". def BL rays #0 1 1; This returns an array of all spaces along the same diagonal as the space at #0. Like checkride, it will negate the input of "1 1" as needed. |
def B logride #0 #1 nw ne sw se; This checks the legality of any move composed of a series of one-step moves in any one of the directions listed, which here are all four diagonal directions. So, it checks a series of south move, then a series of north moves, then a series of east move, then one of west moves. It stops searching as soon as it finds the space at #1. def BL lograys #0 nw sw se ne; This returns an array of all spaces that can be found by moving in a straight line in any of the directions listed. |
| Queen | def Q checkride #0 #1 1 0 or checkride #0 #1 1 1; A single checkride function cannot handle all radial directions at once, but it can be used twice, once for all diagonal moves, and once for all orthogonal moves. def QL merge rays #0 1 0 rays #0 1 1; The same goes for the rays function. This runs the rays function twice and merges the output. |
def Q logride #0 #1 s n e w nw ne sw se; The logride function can handle as many directions as you want to give it. So, one logride function handles all of the Queen's moves. def QL lograys #0 nw sw se ne n w s e; The same is true for lograys. |
| King | def K checkleap #0 #1 1 0 or checkleap #0 #1 1 1; While a King's actual moves might be handled by a subroutine that also handles castling, the function is useful for calculating possible moves, which would include possible checks on the enemy King. It will be the same as for the Queen except that checkride is replaced with checkleap. def KL merge leaps #0 1 0 leaps #0 1 1; This is the same as for the Queen except that leaps replaces rays. |
def K logleap #0 #1 s n e w nw ne sw se; This is the same as for the Queen except that logleap replaces logride. def KL lograys #0 nw sw se ne n w s e; This is the same as for the Queen except that lograys replaces logleaps. |
| Archbishop | def A checkleap #0 #1 1 2 or checkride #0 #1 1 1; An Archbishop moves as a Knight or a Bishop. This code checks for each type of movement with a separate function, using checkleap for the Knight move, checkride for the Bishop move. def AL merge leaps #0 1 2 rays #0 1 1; This calculates possible Knight moves with leaps and possible Bishop moves with rays, then merges their results together. |
def A logleap #0 #1 nne nnw sse ssw nee nww sww see logride #0 #1 nw ne sw se; Although the function for the Queen combined everything into one logride function, this piece is both a leaper and a rider. So, it uses separate functions to check the legality of the Knight's leaps and the Bishop's riding moves. def AL merge logleaps nne nnw sse ssw nee nww sww see lograys #0 nw sw se ne n w s e; Likewise, this uses logleaps for possible Knight moves and lograys for possible Bishop moves, merging the results into a single array. |
| Short Rook | def R checkride #0 #1 1 0 and <= distance #0 #1 4; This piece moves as a Rook up to four spaces. This uses the same code as for the Rook's move but also checks that the distance of the move is less than or equal to four. def RL merge merge leaps #0 1 0 leaps #0 2 0 merge leaps #0 3 0 leaps #0 4 0; This calls leaps four times, merging all the results together. |
def R logride #0 #1 (s s s s stop) (n n n n stop) (e e e e stop) (w w w w stop); The logride function can receive a series of directions inside parentheses. These directions are all used in sequence for the same move, and the last one repeats. To get it to stop, end the series with a non-direction. Here I chose the non-direction of stop. It could have been any other non-direction, such as googpjp, but stop just seemed more meaningful. def RL lograys #0 (s s s s stop) (n n n n stop) (e e e e stop) (w w w w stop); For the directions, lograys takes the same kind of input as logride. This will return all the spaces along the specified paths from #0. |
| Chinese Chess Knight | def N checktwostep #0 #1 0 1 1 1; This piece moves one square orthogonally, followed by one more diagonally outward. It can reach the same spaces as a Knight, but it can be blocked. The checktwostep function checks a step in one direction, then in another. Like checkleap and checkride, it reverses and negates arguments as needed. The two sets of directions both get converted to absolute values, then modified in the same general orientation, so that this does not lead to a Chinese Chess Knight moving diagonally inward to an adjacent space. def NL leaps #0 1 2; Exactly the same as for the Chess Knight. |
def N logride #0 #1 (n ne stop) (n nw stop) (s se stop) (s sw stop) (w nw stop) (w sw stop) (e ne stop) (e se stop) and not logleap #0 #1 (n e s w); Since this piece is a short-range rider, logride is used to check for each possible route it may move. But since its move cannot be shorter than two spaces long, and logride doesn't enforce this, it also used logleap to confirm that it is not a one-space orthogonal move. def NL logleaps #0 nne nnw sse ssw nee nww sww see; Exactly the same as for the Chess Knight. |
| Griffon | def G checkride
where #0
sign - file #1 file #0
sign - rank #1 rank #0
#1 1 0
and empty where #0
sign - file #1 file #0
sign - rank #1 rank #0
and not checkride #0 #1 1 1
and not checkride #0 #1 1 0
or checkleap #0 #1 1 1;
This piece moves along a path that begins with a diagonal step and continues with steps in an orthogonally outward direction. This is one that does not pass by the starting space. It is a riding piece that may stop anywhere along this path and may not pass by an occupied space. Reading this code backwards, since that is the order it is executed in, it checks whether the move was a single-step diagonal move. If it was, the move is legal. If it wasn't, it makes sure that the move was not in a straight line. It then checks whether the diagonally adjacent space it has to pass through is empty. If it is, it checks whether an orthogonal move can be made from that space to the destination space. def GL unique
merge
leaps #0 1 1
merge
merge
rays where #0 1 1 1 0
rays where #0 1 -1 1 0
merge
rays where #0 -1 -1 1 0
rays where #0 -1 1 1 0
This creates an array of the diagonally adjacent spaces and each neighboring rank or file. Since the piece could start from a corner, it is important to calculate ranks and files for every diagonally adjacent space. Since this can generate duplicate values, the unique function removes duplicates from the array. |
def G logride #0 #1 (nw n) (nw w) (ne n) (ne e) (sw s) (sw w) (se s) (se e); This uses the ability of logride to move along a winding path described in parentheses. The last direction in parentheses gets repeated indefinitely. def GL lograys #0 (nw n) (nw w) (ne n) (ne e) (sw s) (sw w) (se s) (se e); Since lograys can take the same input as logride, the code looks almost the same. Since this checks only along legal paths of movement, it includes fewer spaces than the mathematical version and does not need to remove any duplicates. |
| Aanca | def A checkride
where #0
* > abs - file #1 file #0 abs - rank #1 rank #0 sign - file #1 file #0
* < abs - file #1 file #0 abs - rank #1 rank #0 sign - rank #1 rank #0
#1 1 1
and empty where #0
* > abs - file #1 file #0 abs - rank #1 rank #0 sign - file #1 file #0
* < abs - file #1 file #0 abs - rank #1 rank #0 sign - rank #1 rank #0
and not checkride #0 #1 1 1
and not checkride #0 #1 1 0
or checkleap #0 #1 1 0;
This piece moves along a path that begins with an orthogonal step and continues with steps in a diagonally outward direction. This is one that does not pass by the starting space. It is a riding piece that may stop anywhere along this path and may not pass by an occupied space. Reading this code backwards, since that is the order it is executed in, it checks whether the move was a single-step orthogonal move. If it was, the move is legal. If it wasn't, it makes sure that the move was not in a straight line. It then checks whether the orthogonally adjacent space it has to pass through is empty. If it is, it checks whether a diagonal move can be made from that space to the destination space. def AL unique
merge
leaps #0 1 0
merge
merge
rays where #0 0 1 1 1
rays where #0 0 -1 1 1
merge
rays where #0 1 0 1 1
rays where #0 -1 0 1 1
This creates an array of the orthogonally adjacent spaces and each diagonal that runs through an orthogonally adjacent space. Since the piece could start from a corner, it is important to use all four of these spaces instead of just two at opposite ends. Since this can generate duplicate values, the unique function removes duplicates from the array. |
def A logride #0 #1 (n nw) (w nw) (n ne) (e ne) (s sw) (w sw) (s se) (e se); This uses the ability of logride to move along a winding path described in parentheses. The last direction in parentheses gets repeated indefinitely. def AL lograys #0 (n nw) (w nw) (n ne) (e ne) (s sw) (w sw) (s se) (e se); Since lograys can take the same input as logride, the code looks almost the same. Since this checks only along legal paths of movement, it includes fewer spaces than the mathematical version and does not need to remove any duplicates. |
Written by Fergus Duniho
WWW Page Created: 27 January 2016