Unmake move vs copy board in chess programming [closed]

Question

I'm at the start of creating a chess engine. When I created a function that checks if a move is legal, first I had to make the move and then check if the move had put my king in check and then unmake it.

After giving some thought on how to make a function that unmakes a move, I decided it's much simpler to just copy the board and make the hypothetical move on the copied board, so it doesn't change the original board structure at all.

But I'm worried this might be a bad idea because when I get to the AI part, as I have to copy the board completely, and it might slow down my engine. Is it so? Could you please share your thoughts about this, since I don't know much about algorithm complexity and that kind of stuff.

Thank you.

Answer 1

As you say, copying the whole board is likely to slow things down quite a bit. I suggest making an undo list, to which you add the reverse of every move you make. Then to undo, simply repeatedly pop moves off the list and apply them until the list is empty. This way your AI can explore all the possibilities by using a simple recursive function with a maxdepth parameter.

Re: Bo's Comment

I respectfully disagree.

For programs written in lower-level languages a board copy may amount to a single memcpy, and then it might very well be faster. But for an object orientated python program, where there's one object per chess piece, plus metadata, a fully independent game state copy is almost certainly much slower than creating a single new "undo" object and adding it to a list.

Mind you, this has little to do with the size of the structure, and more with the number of operations required to copy that structure. Especially in python, function calls add a significant amount of overhead. According to this answer (my own), instantiating 32 piece objects in CPython is equivalent to 83 function calls, and that is presuming they do not have any subclasses other than object. Then the data allocation and copying comes on top of that.

If the board had been a 16x16 numpy array, I agree a board copy might be faster.