Deepcopy and iteration return different results

Question

I have a 8x8 array that contains objects in some positions, ' ' in others. (It's a chessboard)

My code was running slowly partially due to the use of copy.deepcopy(x) so I did some testing and found that iterating through the array was something like 32x faster. When I ran the code it threw errors so I compared the result from the iteration and the copy.deepcopy(x) and they aren't the same. I can't see where I'm going wrong or find anything similar (I have looked)

the function is below:

def makeCopy(array):
    new = [[],[],[],[],[],[],[],[]]
    for x in range(0,8):
        for y in range(0,8):
            new[x].append(array[x][y])
    a = copy.deepcopy(array)
    if new != a:
        print('failed')
    else:
        print('good')
    return new

When it gets called it prints failed so they aren't the same, which breaks the rest of my code.

I'm passing it something like this (some piece positions may differ):

currentGameState = [[Rook('black', [0,0]),Knight('black',[1,0]),Bishop('black', [2,0]),Queen('black',[3,0]),King('black',[4,0]),Bishop('black', [5,0]),Knight('black',[6,0]),Rook('black', [7,0])],
                    [Pawn('black', [0,1]),Pawn('black', [1,1]),Pawn('black', [2,1]),Pawn('black', [3,1]),Pawn('black', [4,1]),Pawn('black', [5,1]),Pawn('black', [6,1]),Pawn('black', [7,1])],
                    [' ',' ',' ',' ',' ',' ',' ',' '],
                    [' ',' ',' ',' ',' ',' ',' ',' '],
                    [' ',' ',' ',' ',' ',' ',' ',' '],
                    [' ',' ',' ',' ',' ',' ',' ',' '],
                    [Pawn('white', [0,6]),Pawn('white', [1,6]),Pawn('white', [2,6]),Pawn('white', [3,6]),Pawn('white', [4,6]),Pawn('white', [5,6]),Pawn('white', [6,6]),Pawn('white', [7,6])],
                    [Rook('white', [0,7]),Knight('white', [1,7]),Bishop('white', [2,7]),Queen('white',[3,7]),King('white',[4,7]),Bishop('white', [5,7]),Knight('white',[6,7]),Rook('white', [7,7])]]

Answer 1

You're not actually copying the objects inside the matrix.

for x in range(0,8):
    for y in range(0,8):
        new[x].append(array[x][y])

With this code you're actually binding the same object inside a single cell between the two list of lists. Doing this if you change one object inside the first list's cell it will change the object inside the other list's cell. That's why it's faster

With copy.deepcopy(array) you copy the cells and also the objects inside each cell.

Python3 copy module: https://docs.python.org/3/library/copy.html

Answer 2

Your copy function actually works fine for copying the structure of the list, although it could be simplified by using a list comprehension: new = [[x for x in row] for row in array]

The problem, and the difference to copy.deepcopy is, though, that it does not copy the actual game pieces like Rook('black', [0,0]). From the various comments, I gather that:

• the pieces do not implement __eq__, thus == just compares memory addresses and thus your copy is considered "different" from the deepcopy (but probably equal to the original, and, in fact, the deepcopy different from the original)
• the pieces include their current position, e.g. [0,0], and you update/modify this position when moving a piece
• thus, when adding the references to the same piece to the copy of the board, your Minimax-algorithm will "move" the pieces in all states, creating lots of invalid game states

Here are a few possible solutions, with increasing complexity of the required refactoring, but also increasing (assumed) benefit:

• add a copy function and call that method when creating your "manual" copy, e.g. new = [[copy(x) for x in row] for row in array] in my above list comprehension; here, copy is not a method, since there are str and game pieces in those lists, and copy has to work for both (for str, it can just return the original, though)
• instead of using that copy function each time you copy the state, only create a copy of a game piece just before moving that piece, all the other pieces can remain the same; this way, you only have to create one copy instead of 64 per move (you still have to create a copy of the actual board, though)
• drop your Rook etc. classes entirely and just use a string representation like "Rb" for "black Rook" or a tuple ("Rook", "black") and do not redundantly include their current position but just take it from the grid itself when calculating possible moves (this would then be a function, not a method of the no-longer-existing class)

The copy function used for the first two approaches could e.g. look as simple as this:

def copy(piece):
    if isinstance(piece, str):
        return piece
    else:
        return type(piece)(piece.color, list(piece.position))

You could also use copy.deepcopy on the individual pieces in your loop / list comprehension, which would probably be a bit faster then using it to copy the entire board, but till much slower than a tailored copy function.

Answer 3

When I tried running your code as-is (using np.ones((8, 8)) as the example input), I got:

ValueError: The truth value of an array with more than one element is ambiguous. Use a.any() or a.all()

because the result of new != a is:

[[False False False False False False False False]
 [False False False False False False False False]
 [False False False False False False False False]
 [False False False False False False False False]
 [False False False False False False False False]
 [False False False False False False False False]
 [False False False False False False False False]
 [False False False False False False False False]]

Instead, use:

def makeCopy(array):
    new = [[],[],[],[],[],[],[],[]]
    for x in range(0,8):
        for y in range(0,8):
            new[x].append(array[x][y])
    a = copy.deepcopy(array)
    if (new != a).any():
        print('failed')
    else:
        print('good')
    return new

Here we use array.any() to check if any elements in the list (of lists) do not match.

Answer 4

your code prints out 'good' for me, I tried it with integer and with string lists of a list, and returns the correct initial list you give as an argument to the makeCopy function. Are you sure you're using a list of lists to test your function?