9
\$\begingroup\$

Win a K vs KQ endgame

Summary

The goal of this challenge is to create a program or function which will win a Chess game with a King and Queen against a lone King. The user will specify three squares, representing the locations of the computer's King, the computer's Queen, and the user's King. The computer will then a output a move which will eventually lead to checkmate.

Input/Output

The program or function will first take as input three squares, representing the locations of the computer's King, the computer's Queen, and the user's King (not necessarily in that order). It can be assumed that the input is a legal position.

Parsing input is not the point of this challenge, so all reasonable forms of input/output are allowed, including but not limited to

  • Strings with algebraic chess notation such as "Ke4" or "Qf6"

  • Triples representing pieces and coordinates such as ('K', 0, 2)

After three squares are taken as input, the computer outputs a single legal move. Behaviour on invalid input is undefined.

Requirements

This procedure must terminate using your program or function:

  • User sets up a legal KQ vs K position on a physical chessboard.

  • User inputs the board position. The computer outputs a legal move. If the move is a checkmate, STOP. If the move is a stalemate or allows the computer's queen to be captured, your solution is invalid.

  • User makes the computer's move on the physical board.

  • User makes a legal move for the lone king on the physical board.

  • User goes to step 2 and repeats.

In other words, the computer must eventually win by checkmate, through repeatedly using your program or function.

Furthermore, from any legal starting position the checkmate must occur in 50 or fewer moves by the computer, i.e. the above procedure will be repeated no more than 50 times. An explanation as to why your solution will always win in 50 moves or fewer is appreciated.

(Of course, a physical chessboard is in no way necessary to test the code; I only mentioned it to help visualize the procedure. The chessboard could just as well be visualized in the user's head.)

Possible test cases

The squares are given in the order: computer's Queen, computer's King, user's King

  • c2, h8, a1 (must avoid stalemate)
  • a1, a2, a8
  • a8, a1, e5

Rules

  • The checkmate must occur in 50 or fewer moves by the computer, but it does not need to be as fast as possible.
  • Chess libraries are not permitted.
  • Shortest program in each language (in bytes) wins.
\$\endgroup\$
7
  • 10
    \$\begingroup\$ Does interactivity really make this challenge better? Why not just take in a board state and output the result of the next move? \$\endgroup\$
    – Wheat Wizard
    Jan 9, 2021 at 0:28
  • \$\begingroup\$ @WheatWizard It does actually make some sense because during the main phase of a KQ vs Q endgame, the queen has to make the same move as the opponent king. This is however easy to do as well by taking a new board state and I do agree that it would probably be better without interactivity. \$\endgroup\$
    – Arnauld
    Jan 10, 2021 at 0:23
  • \$\begingroup\$ @WheatWizard Do you suggest I close this question and submit one without interactivity then? In guess in that case repetition of moves would lead to an invalid solution but that's not a big deal because repetition is never necessary. \$\endgroup\$
    – 79037662
    Jan 11, 2021 at 14:11
  • \$\begingroup\$ No one has answered yet so I would say to just edit the post changing the rules. If you want to sandbox it, I would recommend having it closed temporarily while that is going on (I can close it and reopen it for you if you would like) and the changes be introduced as an edit. Either way I think there is little reason to make a new post. \$\endgroup\$
    – Wheat Wizard
    Jan 11, 2021 at 15:39
  • 6
    \$\begingroup\$ @cairdcoinheringaahing I left it there for 4 days. \$\endgroup\$
    – 79037662
    Jan 11, 2021 at 16:35

1 Answer 1

6
\$\begingroup\$

Python 3, 1054 bytes

def d(kx,ky,x,y):return abs(x-kx)<2>abs(y-ky)
def l(qx,qy,kx,ky,x,y):
 if x==qx:return x!=kx or ky<min(y,qy)or max(y,qy)<ky
 o=kx<min(x,qx)or max(x,qx)<kx
 if y==qy:return o or y!=ky
 if x-y==qx-qy:return o or x-y!=kx-ky
 return x+y==qx+qy and(o or x+y!=kx+ky)
def f(c,x,y):c[x][y]=1;[f(c,u,v)for v in range(max(y-1,0),min(y+2,8))for u in range(max(x-1,0),min(x+2,8))if c[u][v]<1]
def s(qx,qy,kx,ky,hx,hy):c=[[d(kx,ky,u,v)or l(qx,qy,kx,ky,u,v)for v in range(8)]for u in range(8)];t=sum(map(sum,c));f(c,hx,hy);t=sum(map(sum,c))-t;return t if t-1else 64
def m(qx,qy,kx,ky,hx,hy):a=[[s(x,y,kx,ky,hx,hy)if(x+y-7and x-y)and d(hx,hy,x,y)<=d(kx,ky,x,y)and l(qx,qy,kx,ky,x,y)and l(qx,qy,hx,hy,x,y)else 64for y in range(8)]for x in range(8)];b=list(map(min,a));c=min(b);e=b.index(c);return(0,e,a[e].index(c))if c<a[qx][qy]else min(((x-hx)**2*2+(y-hy)**2*2+(x-3)*(x-4)+(y-3)*(y-4),x,y)for x in range(max(kx-1,0),min(kx+2,8))for y in range(max(ky-1,0),min(ky+2,8))if(x!=kx or y!=ky)and(x!=qx or y!=qy)>d(hx,hy,x,y)and(x-7and x or y-7and y)and s(qx,qy,x,y,hx,hy)<64)

Try it online! Link includes footer which starts from the given position (input as a string of three squares in the order computer Queen, computer King, human King, without separators) and plays random moves on the human's behalf until the computer checkmates it. I've never seen it take anywhere near 50 moves but I don't know how to prove that it won't. Not completely golfed for the sake of my sanity. Explanation:

def d(kx,ky,x,y):return abs(x-kx)<2>abs(y-ky)

Determines whether a square is under attack from a King, e.g. to prevent the Queen from giving itself away.

def l(qx,qy,kx,ky,x,y):
 if x==qx:return x!=kx or ky<min(y,qy)or max(y,qy)<ky
 o=kx<min(x,qx)or max(x,qx)<kx
 if y==qy:return o or y!=ky
 if x-y==qx-qy:return o or x-y!=kx-ky
 return x+y==qx+qy and(o or x+y!=kx+ky)

Determines whether the Queen is threatening the square that the human's King might want to move to.

def f(c,x,y):c[x][y]=1;[f(c,u,v)for v in range(max(y-1,0),min(y+2,8))for u in range(max(x-1,0),min(x+2,8))if c[u][v]<1]

Helper recursive function to flood fill the squares that the human's King can reach.

def s(qx,qy,kx,ky,hx,hy):c=[[d(kx,ky,u,v)or l(qx,qy,kx,ky,u,v)for v in range(8)]for u in range(8)];t=sum(map(sum,c));f(c,hx,hy);t=sum(map(sum,c))-t;return t if t-1else 64

Calculate the scope of the human's King. However, it returns 64 on stalemate, indicating that this is a bad move for the Queen to make.

def m(qx,qy,kx,ky,hx,hy):a=[[s(x,y,kx,ky,hx,hy)if(x+y-7and x-y)and d(hx,hy,x,y)<=d(kx,ky,x,y)and l(qx,qy,kx,ky,x,y)and l(qx,qy,hx,hy,x,y)else 64for y in range(8)]for x in range(8)];b=list(map(min,a));c=min(b);e=b.index(c);return(0,e,a[e].index(c))if c<a[qx][qy]else min(((x-hx)**2*2+(y-hy)**2*2+(x-3)*(x-4)+(y-3)*(y-4),x,y)for x in range(max(kx-1,0),min(kx+2,8))for y in range(max(ky-1,0),min(ky+2,8))if(x!=kx or y!=ky)and(x!=qx or y!=qy)>d(hx,hy,x,y)and(x-7and x or y-7and y)and s(qx,qy,x,y,hx,hy)<64)

The meat of the program, this actually computes the computer's move. The return value is a tuple of (Piece to move, desired X, desired Y) where the flag is 0 to move the Queen and all parameters and X and Y are 0-indexed. It first checks all of the Queen's available moves (except those that give it away or those to squares on the main diagonals, as the symmetry confuses it) to see whether it can reduce the scope of the human's King. If not, it tries to move its own King nearer the human's King, or failing that, nearer the middle of the board.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.