7
\$\begingroup\$

I'm just at the beginning stages of making a simple chess engine. I have a function that when passed the x and y coordinates on a 2D list can enumerate all possible moves for a piece. It assumes there are no other pieces on the board, and that all moves are possible (see example list of moves below) and a separate function 'cleans' the list and removes any moves that aren't possible (say if the space is taken, or if the value would put the piece off of the board) My code works, but it is large and redundant, so I was wondering if anybody had any idea how to better accomplish this? Assuming the computer will always be playing black.

The list before the cleanup for a knight which has not moved at the beginning of the game would look like this:

[[[2], [2]], [[2], [0]], [[1], [3]], [[1], [3]], [[-2], [0]], [[-2], [2]], [[-1], [3]], [[-1], [-1]]]

and after clean up, looks like this:

[[[2], [2]], [[2], [0]]]

So it can go to A6 or C6 in chess terms

and here is the function:

def enumerate_moves(x, y):

    potential_moves = []     # moves before clean up function

# ------------------------------------------------------------------------------
    # resolve pawn moves. 4 possible moves maximally
    if board[x][y] == "bPawn":

        potential_moves.append([[x+1], [y]])

        # if the pawn is in the second rank (has not moved)
        try:
            if board[x+2][y] == "" and x == 1 and board[x+1][y] == "":
                potential_moves.append([[x+2], [y]])
        except IndexError:
            pass

        try:
            if board[x+1][y+1][0] == "w":
                potential_moves.append([x+1], [y+1])
        except IndexError:
            pass

        try:
            if board[x+1][y-1][0] == "w":
                potential_moves.append([x+1], [y-1])
        except IndexError:
            pass

# ------------------------------------------------------------------------------

    # resolve knight moves. 8 possible moves maximally
    elif board[x][y] == "bKnight":

        potential_moves.append([[x+2], [y+1]])
        potential_moves.append([[x+2], [y-1]])
        potential_moves.append([[x+1], [y+2]])
        potential_moves.append([[x+1], [y+2]])
        potential_moves.append([[x-2], [y-1]])
        potential_moves.append([[x-2], [y+1]])
        potential_moves.append([[x-1], [y+2]])
        potential_moves.append([[x-1], [y-2]])

# ------------------------------------------------------------------------------

    elif board[x][y] == "bBishop":

        # down and right
        a = x + 1
        b = y + 1
        while (7 > a >= 0 and 7 > b >= 0) and (board[a][b] == ""):
            potential_moves.append([[a], [b]])
            try:
                if board[a+1][b+1][0] == "w":
                    potential_moves.append([[a+1], [b+1]])
            except IndexError:
                pass
            a += 1
            b += 1

        # down and left
        a = x + 1
        b = y - 1
        while (7 > a >= 0 and 7 > b >= 0) and (board[a][b] == ""):
            potential_moves.append([[a], [b]])
            try:
                if board[a+1][b-1][0] == "w":
                    potential_moves.append([[a+1], [b-1]])
            except IndexError:
                pass
            a += 1
            b -= 1

        # up and right
        a = x - 1
        b = y + 1
        while (7 > a >= 0 and 7 > b >= 0) and (board[a][b] == ""):
            potential_moves.append([[a], [b]])
            try:
                if board[a-1][b+1][0] == "w":
                    potential_moves.append([[a-1], [b+1]])
            except IndexError:
                pass
            a -= 1
            b += 1

        # up and left
        a = x - 1
        b = y - 1
        while (7 > a >= 0 and 7 > b >= 0) and (board[a][b] == ""):
            potential_moves.append([[a], [b]])
            try:
                if board[a-1][b-1][0] == "w":
                    potential_moves.append([[a-1], [b-1]])
            except IndexError:
                pass
            a -= 1
            b -= 1

# ------------------------------------------------------------------------------

    elif board[x][y] == "bRook":
        # down
        a = x + 1
        b = y
        while (7 > a >= 0 and 7 > b >= 0) and (board[a][b] == ""):
            potential_moves.append([[a], [b]])
            try:
                if board[a+1][b][0] == "w":
                    potential_moves.append([[a+1], [b]])
            except IndexError:
                pass
            a += 1

        # left
        a = x
        b = y - 1
        while (7 > a >= 0 and 7 > b >= 0) and (board[a][b] == ""):
            potential_moves.append([[a], [b]])
            try:
                if board[a][b-1][0] == "w":
                    potential_moves.append([[a], [b-1]])
            except IndexError:
                pass
            b -= 1

        # up
        a = x - 1
        b = y
        while (7 > a >= 0 and 7 > b >= 0) and (board[a][b] == ""):
            potential_moves.append([[a], [b]])
            try:
                if board[a-1][b][0] == "w":
                    potential_moves.append([[a-1], [b]])
            except IndexError:
                pass
            a -= 1

        # right
        a = x
        b = y + 1
        while (7 > a >= 0 and 7 > b >= 0) and (board[a][b] == ""):
            potential_moves.append([[a], [b]])
            try:
                if board[a][b+1][0] == "w":
                    potential_moves.append([[a], [b+1]])
            except IndexError:
                pass
            b += 1

# ------------------------------------------------------------------------------

    elif board[x][y] == "bQueen":
        # down and right
        a = x + 1
        b = y + 1
        while (7 > a >= 0 and 7 > b >= 0) and (board[a][b] == ""):
            potential_moves.append([[a], [b]])
            try:
                if board[a+1][b+1][0] == "w":
                    potential_moves.append([[a+1], [b+1]])
            except IndexError:
                pass
            a += 1
            b += 1

        # down and left
        a = x + 1
        b = y - 1
        while (7 > a >= 0 and 7 > b >= 0) and (board[a][b] == ""):
            potential_moves.append([[a], [b]])
            try:
                if board[a+1][b-1][0] == "w":
                    potential_moves.append([[a+1], [b-1]])
            except IndexError:
                pass
            a += 1
            b -= 1

        # up and right
        a = x - 1
        b = y + 1
        while (7 > a >= 0 and 7 > b >= 0) and (board[a][b] == ""):
            potential_moves.append([[a], [b]])
            try:
                if board[a-1][b+1][0] == "w":
                    potential_moves.append([[a-1], [b+1]])
            except IndexError:
                pass
            a -= 1
            b += 1

        # up and left
        a = x - 1
        b = y - 1
        while (7 > a >= 0 and 7 > b >= 0) and (board[a][b] == ""):
            potential_moves.append([[a], [b]])
            try:
                if board[a-1][b-1][0] == "w":
                    potential_moves.append([[a-1], [b-1]])
            except IndexError:
                pass
            a -= 1
            b -= 1

        # down
        a = x + 1
        b = y
        while (7 > a >= 0 and 7 > b >= 0) and (board[a][b] == ""):
            potential_moves.append([[a], [b]])
            try:
                if board[a+1][b][0] == "w":
                    potential_moves.append([[a+1], [b]])
            except IndexError:
                pass
            a += 1

        # left
        a = x
        b = y - 1
        while (7 > a >= 0 and 7 > b >= 0) and (board[a][b] == ""):
            potential_moves.append([[a], [b]])
            try:
                if board[a][b-1][0] == "w":
                    potential_moves.append([[a], [b-1]])
            except IndexError:
                pass
            b -= 1

        # up
        a = x - 1
        b = y
        while (7 > a >= 0 and 7 > b >= 0) and (board[a][b] == ""):
            potential_moves.append([[a], [b]])
            try:
                if board[a-1][b][0] == "w":
                    potential_moves.append([[a-1], [b]])
            except IndexError:
                pass
            a -= 1

        # right
        a = x
        b = y + 1
        while (7 > a >= 0 and 7 > b >= 0) and (board[a][b] == ""):
            potential_moves.append([[a], [b]])
            try:
                if board[a][b+1][0] == "w":
                    potential_moves.append([[a], [b+1]])
            except IndexError:
                pass
            b += 1

# ------------------------------------------------------------------------------

    elif board[x][y] == "bKing":

        potential_moves.append([[x+1], [y]])
        potential_moves.append([[x+1], [y+1]])
        potential_moves.append([[x], [y+1]])
        potential_moves.append([[x-1], [y+1]])
        potential_moves.append([[x-1], [y]])
        potential_moves.append([[x-1], [y-1]])
        potential_moves.append([[x], [y-1]])
        potential_moves.append([[x+1], [y-1]])

# ------------------------------------------------------------------------------

    moves = append_strip_negatives(potential_moves)
    return moves
\$\endgroup\$

migrated from stackoverflow.com Jun 23 '15 at 16:54

This question came from our site for professional and enthusiast programmers.

  • \$\begingroup\$ Why the extra layer of brackets? Why not [(2, 2), (2, 0)] instead of [[[2], [2]], [[2], [0]]] ? \$\endgroup\$ – 200_success Jun 23 '15 at 17:02
  • \$\begingroup\$ Just a rough draft. The extra brackets don't really affect anything anyways. \$\endgroup\$ – Dportology Jun 23 '15 at 17:22
  • \$\begingroup\$ They add bugs to your program, like in the Pawn bit where you are inconsistant about nested lists or not. Speaking of that pawn section, the description says the code assumes the board is empty and all moves are valid, but it actually doesn't assume that, it checks for pieces and empty spaces. \$\endgroup\$ – TessellatingHeckler Jun 23 '15 at 19:24
  • \$\begingroup\$ En passant! (This definitely makes checking moves a lot more annoying) \$\endgroup\$ – shuttle87 Jun 23 '15 at 22:39
  • \$\begingroup\$ Your strategy as a whole is not a good one, because handling castling and en passant is going to be difficult. \$\endgroup\$ – Olathe Jun 24 '15 at 6:40
8
\$\begingroup\$

Thinking about it, I bet a lot of it could be cut right down if the function actually didn't care about moves going off-board, like you say, and that was tidied up later.

Hmm. Probably people who have written chess games before have much better ideas, but here are my thoughts. (Yeah, I've been replacing the nested lists of lists with tuples).

Pawns

The try / except / pass blocks add a lot of length and not a lot of features. If the board width and height go 0-7 then replace them with inline safety checks.

# resolve pawn moves. 4 possible moves maximally
if board[x][y] == "bPawn":

    potential_moves.append((x+1, y))

    if x == 1:  # if the pawn is in the second rank (has not moved)
        potential_moves.append((x+2, y))

    if x < 7 and y < 7 and board[x+1][y+1][0] == "w":
        potential_moves.append((x+1, y+1))

    if x < 7 and 0 < y and board[x+1][y-1][0] == "w":
        potential_moves.append((x+1, y-1))

(I'm not clear why the pawn can move up-right, and down-right, instead of up-right and up-left - probably the game is going left/right on the board, I was assuming it was up/down, if that matters. I'm also not clear why it checks the square to see if the square is white (or has a white piece?) but I'm leaving those as is).

Knights

Code just looks heavy and redundant. Make use of list.extend() / + overload for lists:

# resolve knight moves. 8 possible moves maximally
elif board[x][y] == "bKnight":
    potential_moves += [(x+2, y+1), (x+2, y-1)
                       ,(x+1, y+2), (x+1, y-2)
                       ,(x-2, y-1), (x-2, y+1)
                       ,(x-1, y+2), (x-1, y-2)]

(NB. your Knight code has a bug duplicating the pair (x+1, y+2) instead of the second one being (x+1, y-2)).

Bishops

Right, foothills navigated, what about Bishops? They travel in a big X shape. You do 50+ lines of code to handle each direction from the center, all with two counters and all with safety checks for going off-board. I think you can ditch most of this.

So the Bishop moves diagonally - x+1 and y+1. The longest distance is from one of the corners to the other, so from the bottom left 0,0 to x+7, y+7. All the moves are mirrored vertically and horizontally. So how about:

elif board[x][y] == "bBishop":
    ur = [(x+i, y+i) for i in range(1,8) if 0<=x<8 and 0<=y<8]
    dr = [(x+i, y-i) for i in range(1,8) if 0<=x<8 and 0<=y<8]
    ul = [(x-i, y+i) for i in range(1,8) if 0<=x<8 and 0<=y<8]
    dl = [(x-i, y-i) for i in range(1,8) if 0<=x<8 and 0<=y<8]
    potential_moves += ur + dr + ul + dl  #ur = up/right, etc.

I can't tell what's happening in your Bishops code with the check for squares starting with "w", whether it's supposed to indicate a white square or a white piece on the square. But you don't seem to do anything to indicate that the bishop can take a piece and move to x+2,y+2 or similar, so it doesn't seem to be checking for a piece. Although that move is already in the valid move list anyway. So the check doesn't seem to add anything - if the board is normal, how could the diagonal ever go to a different coloured square?

Rooks

That check for a "w" square makes even less sense to me here, since a Rook is not always on the same colour - so why does your code only allow the bRook to move to w squares ?

Same approach as for Bishops, make a big + and constrain it by the board dimensions:

elif board[x][y] == "bRook":
    u = [(x, y+i) for i in range(1,8) if 0<=x<8 and 0<=y<8]
    d = [(x, y-i) for i in range(1,8) if 0<=x<8 and 0<=y<8]
    l = [(x-i, y) for i in range(1,8) if 0<=x<8 and 0<=y<8]
    r = [(x+i, y) for i in range(1,8) if 0<=x<8 and 0<=y<8]
    potential_moves += u + d + l + r

You can quite possibly sink these down into one list comprehension, and then undo the nested tuples, e.g.

elif board[x][y] == "bRook":
    moves = [((x, y+i),(x, y-i),(x-i, y),(x+i, y)) for i in range(1, 8) if 0<=x<8 and 0<=y<8]
    for x in moves:
        potential_moves += x

Queen

You can do the same with the Queen, although you can do what @vnp suggested - move the Bishop and Rook out into dedicated functions, and make the Queen's moves the combined moves of both of them.

King

You can do the same change with King as with Knight.

I haven't considered the missing functionality @vnp commented on.

\$\endgroup\$
  • \$\begingroup\$ Thanks a lot for the answer. I'll definitely implement some of your ideas. And just a note, the idea of checking for squares which contain "w" as their first character was so the black pieces could actually capture white pieces. White pieces are always labeled with a w at the beginning, ex -wPawn, wKnight.... Otherwise, the code only allowed them to move to empty squares (squares which contain the string "") it was assumed the computer would always be playing black, but this will obviously be changed in the future. Thanks again. \$\endgroup\$ – Dportology Jun 24 '15 at 12:17
5
\$\begingroup\$

One idea is to separate out the contents of the elif statements into functions and put references to those functions in a dictionary. E.g.

def get_pawns_moves(x, y, potential_moves):
    -- put your code here --

etc. Then ...

MOVERS = {
  'bPawn': get_pawn_moves,
   ...
}

def enumerate_moves(x, y):
    potential_moves = []     # moves before clean up function
    call_back = MOVERS.get(board[x][y])
    if call_back:
        call_back(x, y, potential_moves)
\$\endgroup\$
5
\$\begingroup\$

TL;DR; Don't calculate the possible moves every single time.

You've overlooked a key concept: the potential moves for a knight on f1 are the same regardless of what move number it is. It doesn't matter if it is move one (the N is on f1 because it hasn't moved yet) or if it is move 199 (the other N has wandered all over the board and ended up at f1).

If you calculate the potential moves every single time you consider a move, then you are wasting a significant amount of time - it will always return the same value. And then your chess engine will be very very slow.

The solution is to precalculate the potential moves before the games starts, and then for every move you take the precalculated potential moves and subtract the moves that are not possible based on the actual position.

You still need the enumerate_moves function, and to make the improvements others have suggested, but you need to pass in the piece as well.

Source: I have written a chess program.

\$\endgroup\$
  • \$\begingroup\$ So you're saying for each piece I should have a list of lists where each inner list has every move possible for one particular piece on a particular square? So for knight, I'd precalculate a list of every move for A1, A2, A3 etc and then just eliminate the ones that aren't possible given the game state? \$\endgroup\$ – Dportology Jun 24 '15 at 12:54
4
\$\begingroup\$
  • Use functions

    • By factoring out Rook and Bishop move generators into functions you don't need to repeat the same code for Queen: Queen moves is a union of Rook moves and Bishop moves.

    • White and Black pieces move the same way. The same function applies equally to bKing and wKing. To deal with pawns you'd need to pass the side as an argument.

  • Missing functionality

    Pawns may promote (e7-e8Q and e7-e8R are different moves); Kings may castle; pawns may capture en passant.

\$\endgroup\$
  • \$\begingroup\$ The potential moves list just says "can it move to this square? y/n" it doesn't say what it does when it gets there. So e7-e8Q and e7-e8R are the same potential move. \$\endgroup\$ – JK01 Jun 23 '15 at 23:26

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.