[Community Puzzle] Cooperative Mate with Rook

Puzzles
#1

https://www.codingame.com/training/medium/cooperative-mate-with-rook

Send your feedback or ask for help here!

Created by @aCat,validated by @darkhorse64,@DomiKo and @Konstant.
If you have any issues, feel free to ping them.

#2

Interesting puzzle, I enjoyed it.

For some reason my solution for testcase 5 doesn’t work:
h6g6 d4e4 g6g5 e4f3 g5h4 f3g2 a5g5 g2h1 h4h3
It says valid solution requires 9 moves and it’s 9 moves so I don’t really understand the problem, maybe it’s a bug.

But I get 100% for validators so it’s not a big deal.

#3

Hello,
with your solution the game #5 ends with a pat (= stalemate), not a mat.

#4

My bad, I’ll fix that. Thanks for your help.
Edit: took me 9 chars to fix ^^

#5

Are the tests and validators expecting a predetermined path for the three pieces? The reason I’m asking is that my code leads to a proper checkmate within the stated number of moves (for the mate in >6 moves scenarios) and in less than 20ms but I’m getting a time-out error in all tests and validators regardless. Basically, I’m targeting a specific configuration, which of course doesn’t meet move count requirements for the scenarios with mate in <= 6 moves, but satisfies the conditions with higher number of moves. Understanding the reason for test and validation failures would help me.

#6

Here is the result for the mate in 12 moves scenario. Clearly, there are less than 12 moves (there are only 8 moves). Elapsed time is 15ms. Yet, the test fails.
Standard Output Stream:
a1b1 g7a7 b1c1 a7a8 c1d1 h8g7 d1e1 g7f6 e1f1 f6e5 f1e1 e5e4 e1f1 e4e3 f1e1 a8a1
Game information:
[ERROR] Timeout!

#7

It counts as 16 moves.

For comparison, my output for this test is:
a1b1 h8g8 b1c1 g8f8 c1c2 f8e7 c2b3 e7d6 b3a4 d6c5 a4a5 g7a7

Which is actually 12 moves.

1 Like
#8

Thank you, Pardouin, for the quick reply. I incorrectly assumed that the move count was per chess game standards. Also, I figured the reason for the time-out errors. It appears that a line break is required after the last move. So, the test was timing out waiting for the carriage return.

#9

OK, so now I have a code that passes all tests. However, it only passes 50% of the validators. The successful validators seem random, with success in scenarios with 1, 2, 6, and 12 moves. In order to debug, I have chosen to focus on the 3-move scenario, and tried about 50 different 3-move configurations. They all succeed within 5ms. Although I’m a pretty good chess player, I’m unable to create a 3-move scenario that the code doesn’t resolve as needed. Since all tests pass and I can’t come up with a failing scenario, I don’t know what else I can do to meet the potentially hidden requirements. Any help is appreciated.

#10

You don’t need any chess knowledge for this puzzle, except the basic rules ofc.

But you need to know the fundamentals of graph search.

You’re supposed to do an exhaustive search of the possible moves that could lead to a mate, and as you need a mate with as few moves as possible, you need a “shortest path” algorithm.

Are you familiar with that ?
There are different “shortest path” algorithms to consider depending on the nature of the graph but here the graph of all possible moves in unweighted so there’s only one algorithm for that.

If you don’t see what I mean, you should probably do some research with the good keywords, it won’t be hard to find.

But I’m not sure this is the best puzzle to practice this kind of search for the first time, I’d suggest to solve for example this puzzle first:

It’s also a “minimal number of moves” search, so it’s the same algorithm, but way easier to implement.

1 Like
#11

Thank you Pardouin for replying so quickly and trying to help. BFS, DFS, etc. were, indeed, needed to resolve a lot of puzzles. Not sure why this puzzle creates issues when puzzles at hard and very hard levels using shortest path didn’t pose problems. What I’m struggling the most with is that all tests pass (with various code versions) and I am myself unable to find a shorter path, so not sure why three validators fail. Thanks again. I guess I’ll need to pass on this one.

#12

If you’re using a BFS properly it should work fine.
You must not prune any node, really search everywhere, you have enough time for that.
You can precalc all possible moves for the white rook depending on its position and the white king position, it saves time.

The only thing that could help you debugging would be to try to display the possible moves of the rook and kings with random configurations and see if nothing looks suspicious.

1 Like
#13

Thank you for your advice and patience, Pardouin.

1 Like
#14

You can prune King takes Rook move because there is no mate when the Rook is gone

2 Likes
#15

I assume that we don’t have to consider the possibility of white castling here? Just checking :stuck_out_tongue: (haven’t looked at the test cases in detail, yet).

1 Like
#16

You don’t have to implement the castling rule.

#17

All tests involve King + Rook against King. In this exercise, you are looking for the shortest path (hint, hint) to mate.

1 Like
#18

Hi, I am struggling with this one so would appreciate any pointers. I am able to solve about 2/3 of the tests with my approach but the others, either time out, or have too many steps. My approach:-

BFS where I queue all possible moves by the three pieces. As I pick up each node from the queue, if it results in a checkmate then I terminate the while loop. The problem is to avoid a complete timeout, I had to do several things:-

  1. don’t let the white king revisit any node he has already been to.
  2. Only add a vertical and horizontal move for the rook that would result in a check mate. If I add all possible moves for the rook then I always time out.

I know others have mentioned there is no pruning of the nodes but are you utilizing a visited node table for each of the three pieces? It seems it is acceptable for at least the black king to revisit the same node more than once, while the other pieces move around.

Thanks for any insight.

#19

Here’s what I do (also with part 2 in mind, which uses mostly the same code to solve):
There are 64 * 63 * 62 * 2 possible boards (position of each piece, next player to move)
So I generate each of these boards and store them in an array. The board has some function that maps itself to an index of the array (no perfect packing, the array is slightly larger than the number of states).
For each state I create the possible next states. That’s just the initial setup, which takes about 3-4 seconds.
Then I start a BFS from all solved states (easier for part 2) until I reach the starting position. This part runs pretty much instant.
No pruning or simplifications to the rules. And it could easily find longer paths than just 12 moves.

#20

The key point for any BFS is to make sure to never visit a node previously visited. My solution is a forward BFS (going from start to mate) with some pruning on moves (no pat, no king takes rook). For each move left, I compute a hash for the new position (as demonstrated by Euler, it fits into 32 bits) and I prune the move if it corresponds to a position already encountered.