King and Rook Checkmate

Clive, thanks for report! It is actually not error, just debug message I usually use when answer is actually correct - but I don't want it to pass (when submitting myself). I simply forgot to change it back sometimes. Please excuse for this inconvenience and simply resubmit the solution now :)

The example given in the problem starts with Gb1 Kb3 Rb2.

Oh, thanks for correction. Rook of course was standing and moving along c file (just to match picture at the top) - how could I mistype it - no idea. Moreover black king would flee to the right if the rook is on the same file.

P.S. I'm impressed. I spent yesterday to write solution in C, but it is runs for about 2-3 seconds and timeouts. And even sometimes stuck repeating moves.

Hi Rodion! This was a fun one, and a neat bit of chess history too :)

I think the example is still an incorrect board position and black-king move, as CSF mentioned above.
Would something like this be a fixed example, to match the picture at the top?

Ga1 Kb3 Rc3
Rc1
!

Kevin, Hi! I was pretty surprised to see you the second to solve this!

I guess (haven't peeked into your solutions yet) - that you and Clive implemented some "geometric" approach while I tried to "go simpler" - and wrote straightforward "minimax", hoping that some good "heuristic" to assess position value may be useful to push the black king to the edge.

And my solution really works, but not yet well enough. Pleasant thing was that watching how it pushes and checkmates the opponent taught me more efficient approach that I always was using when playing such endgame (and which I would implement if I do it "hard", "geometric" way).

I think the example is still an incorrect board position and black-king move, as CSF mentioned above. Would something like this be a fixed example, to match the picture at the top?

I'm a bit confused here, sorry. The picture at the top shows the checkmate position, which follows 2 moves (of both sides) after the initial, given by example. E.g. firstly there should be some kind of "zwischenzug" - effectively to pass the turn to black, so that black king goes to the corner (the only field he has). Thus the rook should roll back by C file to any square (Rc3 works also leading to your position) temporarily.

As a sidenote, this task was mainly to test the feature of interactive problems (also used with average of metrics in ca4pro) - and as it seems 3 persons already interacted with it without much difficulty, it is ready for other problems of the kind. If anyone wants to create an interactive problem, the main thing to be provied would be the "other player script" - few small additional files I'll be able to create as necessary.

Ideally I would like to compute the full tablebase for K+R vs K but that's a little too slow at the moment, i.e. more work required ...

I implemented the original El Ajedrecista algorithm - not the most efficient but it works when things are set up correctly! Although my code is also somewhat lacking a robust method to set up the position guaranteeing the algorithm's success... I think a particularly aggressive black king could probably force draw by repitition for some starting positions (due to the gaps in my code, all legal starting positions should allow forced mates.

And I apologize for being unclear before - the "old" example I'm seeing is the example that shows up in the "test data" textbox:

Gb1 Kb3 Rb2
Ga1
!

this is just small example, on submission program gets interactive and randomized input

The example as it's written out in the problem text looks correct :)

Gb1 Kb3 Rc2
Rc4
Ga1
Rc1
!

And I have been interested in how you've set up these interactive problems (both in the previous style and this new one). There are certainly a few potential problems that work much better in that format :)

Rodion, for these new interactive problems: is the time limit for each problem instance separately, or overall? As there is no way to preserve state / results between problem instances, pre-computations have to be repeated every time. I could of course take a different approach, but I always wanted to get a simple tablebase working. On my machine, this takes about 3 seconds, and ‘mate in 33 half-moves’ is more fun. :)

Mathias, currently it is 3 sec for all runs (overall). Actually it is just sending your code to the "sandbox" server along with "opponent" code and small bash script containing for 1..3 loop to run these files three times (and provide piping of stdin/stdout to each other).

Is it not possible to embed precomputed table into the code, perhaps?

We can add ability to write temporary file (actually I won't be surprised if writing into /tmp is not restricted even now - though if it works, it's better not to forget cleanup)

UPD: also shared memory could be probably used from Python also... I never thought about so many way to pollute sandbox runtime... good thing it is restarted sometimes, but probably we need to do it every time ideally %)

P.S. again and again - how much I learn from you, friends - particularly, never heard/thought about these tables for endgames (though retrospectively idea looks less or more obvious, like DP).

Before I give up on my idea, one final attempt/question: is there a limit to the size of the code that we can submit and that works for the sandbox?

Python/PyPy is probably not fast enough to do the full pre-computation every time, and I don't want to translate to Java or C++ right now. But I could precompute moves and store them in a compressed string. It's still quite large (2.6M characters) but at least the CodeAbbey editor seems to be ok with it, however the sandbox does not seem to like it. Will try again in a moment.

And replying to moxieman, not sure the 50-move rule applies to a 9x10 board so you should be good. ;) My little table-base seems to suggest that 37 half-moves are sufficient. Or 31 half-moves on a classical 8x8 board, which is consistent with this article.

I don't remember adding any explicit limit on code size, but there probably could be something which disrupts large requests... I don't see such an issue immediately so need to research a bit. But isn't it possible to embed some smaller (sparce?) precalc and calculate part of it in runtime?

Though judging by the size it sounds like 3 seconds on slow-thinking sandbox server may be not enough anyway. Perhaps we simply need improve the timeout value (3 seconds is a default, I just don't remember if it could be modified for the task-checking call - which I'm going to figure out.

And I have been interested in how you've set up these interactive problems (both in the previous style and this new one).

Kevin, please sorry for missing this sentence - there is no secret, I'll try to put some explanations (perhaps, it should go into project wiki). In short the "old" version, with playing against php script - well, it was just it, there is a script which is able to produce some answer in response to user's "move" - and also storing "state" for given user in a file or database. The token which is generated as "input data" contains encrypted user id and task id (and probably timestamp, I don't well remember) - so the playing script of course should be able to decrypt it. And again when user wins, the script prepares the token with task and user id which could be decrypted by problem checker. Specific code is bit too messy but I'll outline the idea in more details either in wiki or in direct email to you.

The "new" style is simpler, as I mentioned, it's just a typical program with input and output. Running it relies upon functionality of sandbox so we need to put a bit more efforts to explaining how it is setup etc... but the core idea is just it - two "players" as two scripts just run simultaneously exchanging input-output and result is being recorded and sent back to the checker (which is responsible for sending these scripts to sandbox). So the checker will check if the data collected are good or bad...

Sorry for falling a bit out of sync. These two weeks were a bit overcrowded with job interviews, but yesterday I at last started work at some new company. Will see if I stick here more than year (my usual patience time) :)