How Do I Generate All Of A Knight's Moves?

I am writing a Chess program in Python that needs to generate all the moves of a knight. For those not familiar with chess, a knight moves in an L shape. So, given a position of (2

Solution 1:

Ok, so thanks to Niall Byrne, I came up with this:

from itertools import product
def knight_moves(position):
    x, y = position
    moves = list(product([x-1, x+1],[y-2, y+2])) + list(product([x-2,x+2],[y-1,y+1]))
    moves = [(x,y) for x,y in moves if x >= 0 and y >= 0 and x < 8 and y < 8]
    return moves

Solution 2:

Why not store the relative pairs it can move in ? So take your starting point, and add a set of possible moves away from it, you then would just need a sanity check to make sure they are still in bounds, or not on another piece.

ie given your (2, 4) starting point, the options are (-2,-1), (-2,+1), (-1,+2), (+2,+1) The relative positions would thus always be the same.

Solution 3:

Not familiar with chess...

deltas = [(-2, -1), (-2, +1), (+2, -1), (+2, +1), (-1, -2), (-1, +2), (+1, -2), (+1, +2)]
def knight_moves(position):
    valid_position = lambda (x, y): x >= 0 and y >= 0 and ???
    return filter(valid_position, map(lambda (x, y): (position[0] + x, position[1] + y), deltas))

Solution 4:

Instead of using an array, I would suggest you use bitboards. Not only are they very easy to manipulate, they will also reduce the need for boundary checking. With as few as 12 bitboards, you could probably encode the information you need for the whole game.

https://www.chessprogramming.org/Bitboards

The basic idea of bitboards is to use a 64 bit integer and set 1 if a piece is present on the bit. For example, if you had a 64 bit integer to represent white knights, you would set the 2nd and 6th bits at the starting of the game as they are the positions where the white knights are located. Using this notation, it becomes easy to calculate the knight's moves. It will be easy to calculate other pieces' moves too.

With this representation, you could take a look at this link to the chess engine for a ready made algorithm to implement knight's moves.
http://www.mayothi.com/nagaskakichess6.html

Solution 5:

This might sound as an overkill if you're not familiar with analytical geometry (or complex numbers geometry) but I came up with a very elegant mathematical solution when I was implementing a validation for the movement of pieces.

The knight's moves are lying on a circle which can be defined as (x-x_0)^2+(y-y_0)^2=5 where x_0 and y_0 are the Knight's current coordinates. If you switch to polar coordinates, you can get all possible coordinates with this simple code:

import math
def knight_moves(x,y):
    new_positions=[]
    r=math.sqrt(5) #radius of the circle
    for phi in [math.atan(2),math.atan(1/2)]: #angles in radians
        for quadrant in range(4):
            angle=phi+quadrant*math.pi/2 # add 0, 90, 180, 270 degrees in radians      
            new_x=round(x+r*math.cos(angle))
            new_y=round(y+r*math.sin(angle))
            if max(new_x,new_y,7-new_x,7-new_y)<=7: #validation whether the move is in grid
                new_positions.append([new_x,new_y])
    return(new_positions)

def validate_knight_move(x,y,x_0,y_0):
    return((x-x_0)**2+(y-y_0)**2==5)

x_0=2
y_0=4

moves=knight_moves(x_0,y_0)
print(moves)

validation=[validate_knight_move(move[0],move[1],x_0,y_0) for move in moves]
print(validation)


[[3, 6], [0, 5], [1, 2], [4, 3], [4, 5], [1, 6], [0, 3], [3, 2]]
[True, True, True, True, True, True, True, True]

It's good to point here, that it is much simpler to validate the position than to construct it directly. Therefore, it might be a good idea to just try whether all possible moves lie on the circle or not:

def knight_moves2(x,y):
    new_positions=[]
    for dx in [-2,-1,1,2]:
        for dy in [-2,-1,1,2]:
            if(validate_knight_move(x+dx,y+dy,x,y)): #is knight move?
                if max(x+dx,y+dy,7-(x+dx),7-(y+dy))<=7: #validation whether the move is in grid
                    new_positions.append([x+dx,y+dy])
    return(new_positions)

new_positions=knight_moves2(x_0,y_0)
print(new_positions)



[[0, 3], [0, 5], [1, 2], [1, 6], [3, 2], [3, 6], [4, 3], [4, 5]]