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, 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

回答1:

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.

回答2:

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

回答3:

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

回答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

回答5:

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.

回答6:

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

回答7:

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

回答8:

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