How do I generate all of a knight's moves?

Question

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, 4) a knight could move to (0, 3), (0, 5), (1, 2), (3, 2), etc. for a total of (at most) eight different moves.

I want to write a function called knight_moves that generates these tuples in a list. What is the easiest way to do this in Python?

def knight_moves(position):
    ''' Returns a list of new positions given a knight's current position. '''
    pass

Answer 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

Answer 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.

Answer 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))

Answer 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

Answer 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]]

Answer 6

Here's an easy implementation:

def knights_moves():
  a = []
  b = (1, 2)
  while 1:
    a.append(b)
    b = (-b[0], b[1])
    a.append(b)
    b = (b[1], b[0])
    if b in a:
      return a

[(1, 2), (-1, 2), (2, -1), (-2, -1), (-1, -2), (1, -2), (-2, 1), (2, 1)]

From there you can just simply add the current position to every member of this list, and then double check for validity.

Answer 7

Completing xiaowl's answer,

possible_places = [(-2, -1), (-2, +1), (+2, -1), (+2, +1), (-1, -2), (-1, +2), (+1, -2), (+1, +2)]
def knight_moves(cur_pos):
    onboard = lambda (x, y): x >= 0 and y >= 0 and x<8 and y<8
    eval_move = lambda(x,y): (cur_pos[0] + x, cur_pos[1] + y)
    return filter(onboard, map(eval_move, possible_places))

Answer 8

For the knights moves:

def getAllValidMoves(x0, y0):
    deltas = [(-2, -1), (-2, +1), (+2, -1), (+2, +1), (-1, -2), (-1, +2), (+1, -2), (+1, +2)]
    validPositions = []
    for (x, y) in deltas:
        xCandidate = x0 + x
        yCandidate = y0 + y
        if 0 < xCandidate < 8 and 0 < yCandidate < 8:
            validPositions.append([xCandidate, yCandidate])

    return validPositions

print getAllValidMoves(3,3)

I just stored all the possible deltas, applied each one of them to the "initial position" and saved the ones that were inside the chessboard

Answer 9

from itertools import product

def moves():
    """ The available (relative) moves"""
    a = list(product( (1, -1), (2,-2)))
    return a + [tuple(reversed(m)) for m in a]

def neighbors(a,b):
    # true if x,y belongs in a chess table
    in_table = lambda (x, y): all((x < 8, y < 8, x >= 0, y >= 0))
    # returns the possible moving positions
    return filter(in_table, [(a+x, b+y) for x, y in moves()])

"neighbors" are the available positions that a knight can go from a,b

Answer 10

The below method is implemented in python. It accepts the board (which can be of any m*n & has values 0(available) and 1(occupied) and current position of knight)

def get_knight_moves(board, position):
    KNIGHT_STEPS = ((1, 2), (-1, 2), (1, -2), (-1, -2), (2, 1), (-2, 1), (2, -1), (-2, -1))

    knight_moves = []
    for (i, j) in KNIGHT_STEPS:
        try:
            x, y = position[0] + i, position[1] + j
            if board[x][y] == 0:
                knight_moves.append((x, y))
        except IndexError:
            pass

    print(knight_moves)