16
1
It's the ending of another well played chess game. You're the white player, and you still have a rook and your king. Your opponent only has his king left.
Since you're white, it's your turn. Create a program to play this chess match. Its output can be a sequence of moves, a gif animation, ASCII art or whatever you like.
It seems quite obvious, but I'll state it explicitly: you have to win the game (in a finite number of moves). It's always possible to win from this position. DO NOT LOSE THAT ROOK. DO NOT STALEMATE.
Your program may or may not accept a human input for the starting position and for each black move (you can safely assume this is a legal position, i.e. the kings are not touching each other). If it doesn't, a random starting position and random movements for the black king will suffice.
Score
Your score will be length in byte of your code + bonus. Any language is allowed, lowest score wins.
Bonus
-50 if your program allows both a human defined starting position and a random one. Humans can enter it via stdin, file, GUI...
-100 if your program allows both a human and a random player to move the black king
+12345 if you rely on an external chess solver or a built-in chess library
Good luck!
Update!
Extra rule: The match must be played until checkmate. Black does not resign, doesn't jump outside the chessboard and doesn't get kidnapped by aliens.
Hint
You can probably get help from this question on chess.se.
Don't forget to run your challenges through the Sandbox to test their readiness before posting.
– Justin – 2014-02-26T19:53:40.930Oh.. thank you. It's indeed the first question I ask, didn't know about this. And of course the first exploit has been posted... – izabera – 2014-02-26T20:19:49.607
2Does the 50 move draw rule apply? – Comintern – 2014-02-27T00:35:14.500
@Comintern If you don't move your pieces randomly, this game shouldn't last that long. You have to play the standard chess rules, thus you have to apply it, but it shouldn't affect the outcome. – izabera – 2014-02-28T09:42:41.197
Possibly relevant: http://chess.stackexchange.com/questions/4886/how-do-you-checkmate-with-a-rook
– Nate Eldredge – 2014-03-02T16:07:17.087The bounty is expiring, no one? – Victor Stafusa – 2014-03-05T23:34:21.980
The program will output the (optimal) moves for white. Should we substitute it with random moves for black? – javatarz – 2014-03-06T05:37:57.897
@JAnderton either randomly or user input, bonus points awarded if your program handles both. – izabera – 2014-03-06T06:29:13.033
1@Victor I've had a couple of goes, but it hasn't worked out yet. Brute force is obviously too slow, alpha-beta too because the landscape of position ratings is quite flat; and tends to get stuck in a loop. Retrograde analysis would work but very slow up-front. My next attempt will use Bratko's algorithm for KRK, which I've avoided because it's a pile of special cases, not great for golf. – bazzargh – 2014-03-06T23:33:38.753
Bratko's algorithm here for those who want to have a go, foot of page 599 http://books.google.co.uk/books?id=-15su78YRj8C&pg=PA609&lpg=PA609&dq=minimax+rook&source=bl&ots=TA3-081sNS&sig=Ea5Xujm6etTkyQIXoiz9MFUtqQQ&hl=en&sa=X&ei=cl0SU43HLIyshQemwoHQCQ&ved=0CH4Q6AEwDDgU#v=snippet&q=%20an%20advice%20program&f=false and a slightly simpler variant that always wins in ~30 moves (not the optimal 16) is described in http://argo.matf.bg.ac.rs/publications/2013/2013-icga-krk-sat.pdf
– bazzargh – 2014-03-06T23:36:08.8571@victor I'm looking at this too. This is interesting precisely because it simple to define and difficult to do. In turn the program will not be short, so the code-golf tag made it seem doubly hard. If my program works you'll see it soon. – Level River St – 2014-03-07T00:35:57.177
@bazzargh I don't think that the algorithm must be optimal. If it manages to eventually check-mate the black king and never stalemates or loses the white rook, I think that it will be valid. – Victor Stafusa – 2014-03-07T00:50:50.450
@steveverrill I would suggest you to forget the golf and just post something that works, or just do the most basic golfs (remove whitespaces, rename variables to 1 char and not much more). – Victor Stafusa – 2014-03-07T00:52:42.127
1@Victor the problem was not about trying to be optimal, any attempt to pick a 'best' move without considering game history led to loops. Need to test game terminates from every position. Bratko+variants arent optimal but provably terminate. Trying retrograde analysis just now (ie build endgame table), looks promising and actually is optimal, which is nice. Also turns out reasonably short. – bazzargh – 2014-03-07T01:17:10.430
2
If anyone needs inspiration (or is just curious), you can find a 1433 character complete chess engine at http://home.hccnet.nl/h.g.muller/umax1_6.c
– Comintern – 2014-03-07T17:42:08.433You might eventually want to add an image as it makes the question much nicer, e.g. http://i.imgur.com/j8nLthL.png created with http://www.apronus.com/chess/wbeditor.php
– Martin Thoma – 2014-03-08T18:47:53.317@izabera, was there a problem with my answer? surprised to see the longer one marked as the winner. Not taking offence, just wondering if you'd found a bug. – bazzargh – 2014-03-08T18:57:20.257
@bazzargh oh sorry i must have misclicked, sorry – izabera – 2014-03-08T19:46:17.870
@bazzargh deserves it more than me. I did reduce my program down to shorter than his by eliminating some of the input checking and renaming variables, in particular eliminating the subscripts for the piece positions (for example r[0] and r[1] for the rook becomes two variables R and r.) However I then found a few bugs, and working on them made the program slightly longer again. Being accepted confused me, so I stopped and went out. I don't see much point in fixing it now, the best man won. – Level River St – 2014-03-08T22:30:11.000
@steveverrill I actually voted your entry up, and wouldn't have been annoyed if you got the win. After so many false starts on my entry, I can appreciate just how hard it was to get any answer working, and how hard the bugs are to find-I'd have code that appeared to work, but would go into a loop on certain moves 10 moves in. Tough, tough puzzle. – bazzargh – 2014-03-08T22:57:51.047
@bazzargh I told myself not to waste time on this cos I knew it would be hard. But then the doctor signed me off with flu and that was it. A little at a time till I got to the point where I was like "I WILL MAKE THIS WORK!" by which time the flu was better. Also I was determined to write an algorithm to play the actual game, but as you say something always came up 10 moves down and the computer won't think on the fly. Some kind of analysis, or failing that, some randomness in picking the white move, is probably the way to go. Good job and +1 (I was too engrossed to upvote before.) – Level River St – 2014-03-08T23:11:33.537
Would a program that randomly moves king and rook such that the rook cannot be captured and no illegal moves and stalemates happen be a valid answer to this question? It succeeds in finite, yet random time, after all. – Wrzlprmft – 2014-03-11T16:53:29.690
@Wrzlprmft you should be able to prove it does – izabera – 2014-03-11T17:36:27.677
@izabera: That’s not the problem. It will of course lead to a draw, if black invokes the fifty-moves rule or threefold repetition. – Wrzlprmft – 2014-03-11T17:54:24.810