Games Online Contest #32
This contest closed on July 1, 2011 but was extended until July 15 due to insufficient correct entries.
Here was the original challenge:
5 First Prizes: A one-year subscription to GAMES
This contest’s subject may seem esoteric, but it’s really just an elaborate counting problem. In the traditional board game xiangqi, also known as Chinese chess, cannons are the most unusual type of piece. When not making a capture, a cannon moves like a rook in chess—that is, any distance in any horizontal or vertical direction, without passing over any occupied points. When making a capture, however, a cannon still moves any distance horizontally or vertically, but it must jump over exactly one piece—which may belong to either player—and then land on an opposing piece. The piece that is landed on is captured (removed from play). There may be any number of open points (including none) on each side of the piece that is jumped over. A cannon may never jump over more than one piece in a turn.
Here is the opening setup in xiangqi. Note that the pieces occupy points (intersections), not squares as in chess. We’ll use Western-style algebraic notation to identify the coordinates of each point, even though other notation systems are traditional for this game. The pieces labeled “Ca” are cannons. The other piece symbols stand for chariot (Ch), horse (H), elephant (E), advisor (A), general (G), and soldier (S). (Note: Different names for some of these pieces are used in different sources.) Red moves first; and if Red chooses to start by moving the cannon on b3, that cannon may go to any of the following points: a3, c3, d3, e3, f3, g3, b2, b4, b5, b6, b7, or b10 (this last choice captures a horse).
The object of this contest is to determine the number of different positions that can occur after the first player’s (Red’s) second move in a game of xiangqi, if both of Red’s moves are made with cannons. That is, after Red moves a cannon, Black replies with any legal move by any piece, and Red moves a cannon again (either the same cannon as before or the other one), how many different positions can appear on the board?
All positions must be ones that can be reached with a series of legal moves. Two positions that are mirror images of one another are still considered different for purposes of this contest.
The contest asks for five numbers to be listed on each entry:
1. The number of different positions possible if Red’s first two moves are made with the same cannon and Black also moves a cannon.
2. The number of different positions possible if Red’s first two moves are made with the same cannon and Black moves a piece other than a cannon.
3. The number of different positions possible if Red’s first two moves are made with two different cannons and Black also moves a cannon.
4. The number of different positions possible if Red’s first two moves are made with two different cannons and Black moves a piece other than a cannon.
5. The sum of 1, 2, 3, and 4 above.
Winners will be chosen randomly from among entries that have all five numbers correct. If fewer than five entries have all five numbers correct, winners will be chosen from among entries that have the most numbers correct.
Clarification: After the contest appeared, we realized that our way of dividing the positions into four categories was flawed, because it results in some positions being counted twice—for example, once as part of 1 and once as part of 3. That’s because moving one cannon twice can bring about the same position as moving each cannon once (e.g., Cb3-b2-h2 yields the same position as Ch3-h2 and Cb3-h3). As a result, the sum called for by 5 will be somewhat larger than the actual number of different positions possible. Be that as it may, we are not going to change the contest rules midstream, and so we continue to ask for the five numbers 1-5 as originally defined above. In writing up the results of the contest, we will examine the number of positions counted twice in 5 and determine the number of different positions that are really possible after Red’s second move.
Rules for xiangqi can be found at http://en.wikipedia.org/wiki/Xiangqi. However, all you need to know to solve this contest is how the pieces move, as well as the fact that you may not make a move that allows the opponent to immediately capture your general. This is relevant in this situation: If Red’s first move is to capture a horse with a cannon, Black may not then move the elephant or advisor on that side of the board, since the cannon (on b10 or h10) could then capture the general on the next turn.
Here’s a summary of how the pieces move. All pieces other than cannons move in their normal directions when making a capture, including soldiers (unlike pawns in chess), and no piece other than cannons may move through an occupied point (not even the horses).
Soldier (S): one point vertically forward
Chariot (Ch): any distance in any horizontal or vertical direction, exactly like a rook in chess
Horse (H): one point in any horizontal or vertical direction followed by one point in a diagonal direction that continues away from the staring point; similar to a knight’s move in chess, except that the first point passed over must be unoccupied (Example: The horse on b10 can move to a8 or c8 at the start, but not to d9 because the elephant on c10 blocks it.)
Elephant (E): exactly two points in any diagonal direction, while always staying on its own side of the river that runs through the center of the board (Note: The river has no relevance in this contest.)
Advisor (A): one point in any diagonal direction, while always staying within the palace marked by diagonal lines (Black’s advisors can only move to e9 on their first move)
General (G): one point in any horizontal or vertical direction, while always staying within the palace marked by diagonal lines (Black’s general can only move to e9 on its first move)
Cannon (Ca): already discussed above
In the starting position, each player has 20 possible opening moves: 5 possible pawn moves, 4 possible chariot moves, 4 possible horse moves, 4 possible elephant moves, 2 possible advisor moves, 1 possible general move, and 12 possible moves with each cannon (including making an immediate capture of a horse). Of course, some of Red’s first moves will change some of the possibilities for Black’s first move, and Black’s first move will often change some of Red’s second-move options.
If a position can be reached more than one way, be sure not to count it more than once. E.g., if Red moves a cannon to b5 and then to b2, the position is the same as it would have been if the cannon had moved to b7 and then b2.
The five numbers that the contest asked for are:
Having just one of these numbers right turned out to be sufficient to be a winner.
Note: As noted in the contest rules clarification, because certain positions are counted in both answers (1) and (3), and also in both (2) and (4), leading to 238 duplicates, the actual number of different positions that can occur after two Red cannon moves and one Black move (of any kind) is:
11680 - 238 = 11442
Analysis and Explanation
The following discussion uses Western style algebraic notation, in which files are lettered a through i from left to right and ranks are numbered from 1 through 10. The lower left corner from Red’s point of view is a1. The letter C is often used as an abbreviation for cannon.
For each part (1) through (4), we break down the possibilities in various ways to make the number of positions easier to count.
(1) Red moves the same C twice and Black moves a C.
1. Red moves either cannon twice, ending up back on its starting space, without making a capture. Each of Black’s cannons can end up on 13 possible points, for a total of 26 positions.
This “non-move” by Red will be ignored in future calculations in this section.
2. Both move b-file cannons.
a. Red makes two captures. Black b C can be at any of 13 positions.
b. Red captures H and Black moves horizontally. Red can be at any of 8 points, Black at 6, so 48 possible positions. Capture must come on the first turn.
c. Red captures H and Black moves vertically. Count the combinations of points the C’s can end up occupying in the b file. 23, 24, 25, 26, 27, 28, 29, 34, 35, 36, 37, 38, 39, 45, 46, 47, 48, 49, 56, 57, 58, 59, 67, 68, 69, 78, 79, and yes 9-10 because the capture can come on the second turn, and so also 3-10, 4-10, 5-10, 6-10, 7-10 that’s 33 combos. Not possible is 2-10 or 8-10.
d. Red captures a S; can be at 4 locations. Black can be at 13 locations for all of these, plus at b1 if Red at e7 (having first moved to b7). So 4x13+1 = 53.
e. Red captures only an A; Black must have moved C to d8 or f8 to allow a capture on d8 or f8. 2
f. Red makes no captures and Black moves to a8, c8, e8, or g8.
Count. 45 places the Red cannon can end up (b3 being ignored) x 4 Black C positions = 180
g. Red makes no captures and Black captures on b1; Red had to first move vertically, so can no longer reach 3rd rank or d789 or f789; don’t count b3 either; 31
h. Red makes no captures and Black moves to b9
i. Red makes no captures and Black moves to d8
j. Red makes no captures and Black moves to f8
k. Red makes no captures and Black moves to b2; Red had to first move horizontally.
l. Red makes no captures and Black moves to b3; Red had to first move horizontally or to b2.
m. Red makes no captures and Black moves to b4 (note that b2 becomes impossible for Red)
n. Red makes no captures and Black moves to b5
Count 28 (b2 and b4 become possible)
o. Red makes no captures and Black moves to b6
p. Red makes no captures and Black moves to b7
So: 2 red captures: 13
1 red capture: 48+33+53+2 = 136
0 red captures: 180+31+44+43+43+24+25+26+28+35+42 = 521
total 13+136+521 = 670 positions when both move only b-file cannons
3. Red moves b-file C twice, Black moves h-file C.
a. Red makes 2 captures. Black h-file C can be at any of 12 positions (including h1).
b. Red makes one H capture. Black hC (h-file C) can be at any of 12 positions, and Red C can end up at b10 or b9 (b10 if capture is on second turn). 24 total combos
c. Red captures a S. 4 ways x 12 Black hC positions = 48
d. Red captures a G. 2 ways x 1 Black hC positions = 2
e. Red makes 0 captures and Black hC moves to c8, e8, g8, or i8; 4x43 = 172
f. Red makes 0 captures and Black hC moves to d8 or f8; 2x41 = 82
g. Red makes 0 captures and Black hC moves to h9, h7, h4, or h1; 4x43 = 172
h. Red makes 0 captures and Black hC moves to h6 or h5; 2x41 = 82
So: 2 red captures 12
1 red capture: 24+48+2 = 74
0 red captures: 172+82+172+82 = 508
total 12+74+508 = 594
Totals for sections 2 and 3 need to be doubled since the Red h-file cannon could have been the one moving instead. So the total for (1) is:
26+(670+594)x2 = 2554
(2) Red moves one cannon twice, and the second player does not move a cannon.
a) Either C moves away from its starting point (without capturing) and back to it. 1 position times 20 possible non-C Black moves = 20.
This “non-move” by Red will be ignored in future calculations in this section.
b) Red moves the left cannon twice and makes no captures. First consider if Black does not move a soldier. In this case, no Black move will change the C’s possible moves. Not counting a) above, the cannon can end up on any of 9 points each on the second, fifth, and sixth lines, 6 points on the third line, 3 points each on the fourth and seventh lines, 2 points on the 8th line, 2 points on the 9th line, and 2 points on the 10th line, but these 10th line points require a specific A move by Black. So: If Black does not move a C, S or A, that leaves Black with 13 possible moves. For each of those, the left Red C can end up on 9+6+3+9+9+3+2+2 = 43 points. 43x13 = 559. If a Black A moves (2 possibilities), an additional option opens up, which adds 44 + 44 to the 559, for a total of 647. Now consider S moves by Black. If the left S moves, Red’s left C can still get to 43 points in two noncapturing moves (adding the one the S vacated but losing the one it moves to). If the c soldier moves instead, it adds c7 but blocks access to c6, e6, g6, h6, i6, so that leaves 39 possible end points for the C. If the center soldier moves, it removes e6, g6, h6, i6 without adding a point, so still 39. If the g soldier is moved, it blocks g6, h6, i6, so 40. If the i soldier moves, i6 is blocked, so 42, Total for a Black soldier move = 43+39+39+40+42 = 203. And 647+203 = 850 positions.
c) Red moves the right cannon twice and makes no captures. As in b, 850 positions.
d) Red starts with left CxH and then makes another capture. That capture can only be on d10. Black does not capture the C, so has only 4Ch, 5S, 1G, 1A, 2E, 2H non-C moves, a total of 15.
e) Red starts with right CxH and then makes another capture. As in d, 15.
f) Red starts with left CxH and then makes a noncapture with that same C. Since Black is not moving a cannon, and the piece on c10 is pinned, the noncapture can only be to b9 or a10. If it’s to a10, Black had to make one of 2 possible Ch moves. If it’s to b9, Black could have made any of the same 15 moves as in d above. So 15+2 = 17.
g) Red starts with right CxH and then makes a noncapture with that same C. As in f, 17.
h) Red makes a noncapturing move followed by a capturing move, both with his left C. Possible captures are on b10, a6, a7, c6, c7, e6, e7, g6, g7. The four captures on the 6th line each require a specific S advance by Black, so those are a total of 4 positions. For the capture of a7, Black can have made any (non-C) move other than Sa6, a total of 19 possibilities. Similarly for the other three 7th line captures, so the total for soldier captures is 4 + 19x4 = 80. The b10 capture requires moving the C vertically twice, capturing on the second move. Black cannot have moved his H (or C), but can have made any other move, for a total of 18. 80+18 = 98
i) Red makes a noncapturing move followed by a capturing move, both with his right C. As in h above, 98.
(2) Total = 1980
(3) Red moves 2 different Cs and Black also moves a C.
Note that some positions here will duplicate some counted under #1, but so be it, since that’s what the contest called for.
1. Black moves b-file Cannon horizontally
a. Red moves both C’s horizontally
6 x 23 = 138
b. Red moves both C’s vertically
If left red C moves first, 6x6x6 = 216 possibilities.
If left red C moves second, 2x36 more possibilities (can end on b8 or b9) = 72, 72+216 = 288
c. Red moves left C horizontally and right C vertically
8x6x6 = 288
d. Red moves left C vertically and right C horizontally
if left moves first, 6x6x8 = 288
if left moves second, an additional 2x6x6 = 72 combos open up due to b8 and b9 (but right C can’t reach a3 or b3 now, so it has only 6 possible moves not 8)
so for 1a-1d we have 138+288+288+288+72 = 1074
2. Black moves b-file Cannon vertically
a. Red moves both C’s horizontally
The 23 possible combos of two points the Red C’s can occupy on the 3rd line, x5 ways for the Black C to move from b9 through b4, plus the black b3-b2-b1 scenarios. For black C at b3 or b2, left Red had to move first. For Black b3, red cannot have cannons at a3b3 or h3i3 combinations but any other combo is possible (21 total). For Black C on b2 h3i3 is not possible but all 22 other combos are possible. For b1 right C must have moved first, so a3b3 again is not possible but all 22 others are.
But also: Red moves b3 right to one of 5 points, Black plays Cb3, Red captures it with Ch3xb3. Five new positions.
So 5x23+21+22+22+5 = 185
b. Red moves both C’s vertically
The right red C has 6 possible moves regardless. Count the ways the two C’s on the b file can end up. If red captures b10, then there are 7 noncapturing possibilities for the Black C (the capture could have been made first, so b2 and b3 are possible). If Black captures at b1, then there are 7 possible positions for the Red b-file C (b8 and b9 are possible if it was the second Red move). Both b-file C’s cannot make captures of course. So with a b-file capture by either player, there are 14x6 possible positions = 84.
With no captures, the two b C’s can be on the following pairs of ranks: 23, 24, 25, 26, 27, 29, 45, 46, 47, 49, 56, 57, 59, 67, 69, 79, 89 = 17 combos. 17x6 = 102 more. 102+84 = 186
c. Red moves left (b-file) C horizontally and right C vertically (in either order).
This is hard to calculate accurately, so the best way may be to consider each possible ending point of the black C and figure out how many ways the two red C’s can be arranged.
Black C on:
d. Red moves left C vertically and right C horizontally
also difficult, requires breakdown
Black C on:
b9 54 (That’s 6 possible positions for the Red b-file C if it goes first, x 8 places the right Red C can then go; plus the six places the right C can move if the Red left C goes second and moves to b8.)
b3 12 (only 6 places right C can move)
b2 8 (first move had to be Red CxH)
b1 52 (note that Red C’s can’t be on both b8 or b9 and a3 or b3, so 7x8 – 4 = 52)
(Another way to look at the Black C on b1 scenario: If right Red C moves first, 6x7 = 42 combos; if left Red moves first to b2, b4, b5, b6, b7, then two more for each because h-file C can go to a3 or b3, so 10 more = 52.)
So for 2a-2d we have 185+186+360+238 = 969
Total of 1 and 2 is 969+1074 = 2043
double all of the above because Black could also move the h-file cannon:
2043x2 = 4086
(4) Red moves each cannon once, and the second player does not move a cannon.
a) Both Red’s C’s move horizontally. Neither Red C can end up where it started, so the only possible combinations where a C is at b3 or h3 are a3-b3 and h3-i3. In all, there are 23 pairs of points the two C’s can occupy after both moving horizontally. Then 23x20 possible non-C moves by Black = 460 positions.
b) Both Red C’s move vertically without capturing. There are 25 pairs of points they can move to, and for each one Black has 20 non-C moves, and 25x20 = 500.
c) Both Red C’s move vertically, Red starts with left CxH, and the right C does not make a capture. Black now cannot move his E or A on the left side (or it would be check), and so has 16 possible non-C replies (2 H moves, 2 E moves, and 1 A move are eliminated but one new Ch move, ChxC, is added). Red’s right cannon will have a choice of 5 noncapturing vertical moves. So 16x5 = 80.
d) Both Red C’s move vertically and Red starts with right CxH and then makes a noncapturing vertical move with the left C. As above in c), 80.
e) Both C’s move vertically but only the second one to move makes a capture. Now the moves with E and A that would have been illegal if the first move was CxH are restored. So if the left cannon moves second and plays CxH, there are 5 possible noncapturing places the right C can move to, and there are 3 moves Black can now make but couldn’t in c above. 5x3 = 15. But if the right cannon is the one that moves second and captures, it’s 15 more new positions. 15+15 = 30
f) Both C’s make captures. In that case Black cannot have moved an H, leaving 16 possible Black moves. Any E or A move is possible, because the first C to make a capture could always have been the one on the other side. Thus positions in which Red CxH and Red CxH = 16, plus both possible positions in which Black has played ChxC, so it’s 18.
g) Red’s left C moves vertically without capturing and right C moves horizontally. Left C can end up on 5 different points and right C on 8 different points. In each case Black will have 20 possible non-C replies. 5x8x20 = 800
h) Red’s right C moves vertically without capturing and left C moves horizontally. As above in g, 800.
i) Red’s left cannon starts with CxH and then the right cannon moves horizontally. As we saw in c above, Black has 16 possible non-C replies. None of these interfere with any of the right C’s possible horizontal moves, which are 8. 16x8 = 128
j) Red’s right cannon starts with CxH and the left cannon moves horizontally. As in g above, 128.
k) Red’s right cannon moves horizontally and then the left cannon plays ChxH. All these positions have already been counted in i above, except for ones in which the left side E or A are moved by Black. That’s 3 possible moves times 6 possible horizontal moves by the right cannon moving first = 18 new positions.
l) Red’s left cannon moves horizontally and then the right cannon plays CxH. As in k, 18.
Total for (4): 3060
The totals are (1) 2554, (2) 1980, (3) 4086, (4) 3060, and so the total is 11680.
These are the correct answers to the contest questions (we think!). But the basic question remains: How many different positions are possible after Red’s second move, if both Red moves are made by cannons? The reason this question has a different answer from question 5 above is that, as noted in the contest’s rule clarification, some of the same positions are being counted twice, once in (1) and once in (3), or once in (2) and once in (4).
E.g., counted as two moves by the right C: C-h2-b2; counted as moves by both C’s: Cb3-b2, Ch3-b3; yet the resulting positions are the same.
There are other duplications like this: Cb3/b5 can come about two ways. Also Cb3/b6, Ch3/h5, Ch3/h6, Ch3/h2.
So how many of the six positions with these C combos for Red are counted twice instead of once?
Any that involve Black horizontal cannon moves, or any non-C non-S move, or edge S moves, or vertical C moves of +1 or -1 distance, for starters. That’s 12+15+2+4 = 33x6 = 198.
For S to c6/e6/g6 by black, only 4 of the positions would be duplicated (not the ones with b3b6 or h3h6). That’s 3x4 more = 12. Same for C moves that go forward 2, so that’s 2x4 = 8 more.
For C moves that go up 3 or 4 just the inner b2-b3 and h2-h3 combos are duplicates, so 4x2 = 8 more.
For either CxH, all 6 are duplicates, so that’s 12 more.
For C to the 2nd or 3rd rank, a horizontal move had to go first, so no duplicates.
Total duplicates are 198+12+8+8+12 = 238.
11680-238 = 11442 different positions.
Results of Online Contest #31
Results of Online Contest #30
Results of Online Contest #29
Results of Online Contest #28
Results of Online Contest #27
Results of Online Contest #26
Results of Online Contest #25
Results of Online Contest #24
Results of Online Contest #23
Results of Online Contest #22
Results of Online Contest #21
Results of Online Contest #20
Results of Online Contest #19
Results of Online Contest #18
Results of Online Contest #17
Results of Online Contest #16
Results of Online Contest #15
Results of Online Contest #14
Results of Online Contest #13
Results of Online Contest #12
Results of Online Contest #11
Results of Online Contest #10
Results of Online Contest #9
Results of Online Contest #8
Results of Online Contest #7
Results of Online Contest #6
Results of Online Contest #5
Results of Online Contest #4
Results of Online Contest #3
Results of Online Contest #2
Results of Online Contest #1