Win a KQ vs K endgame

Question

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.

Answer 1

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.