Search code examples
chess

What's the point of "make move" and "undo move" in chessengines?


I want to experiment with massive parallel chess computing. From what I saw and understood in wikis and source code of some engines is that in most (all?) implementations of the min-max(negamax, alpha-beta, ...)-algorithm there is one internal position that gets updated for every new branch and then gets undone after receiving the evaluation of that branch.

What are the benefits of that technic compared to just generating a new position-object and passing that to the next branch? This is what I have done in my previous engines and I believe this method is superior for the purpose of parallelism.


Solution

  • The answer to your question depends heavily on a few factors, such as how you are storing the chess board, and what your make/unmake move function looks like. I'm sure there are ways of storing the board that would be better suited towards your method, and indeed historically some top tiered chess engine (in particular crafty) used to use that method, but you are correct in saying that modern engines no longer do it that way. Here is a link to a discussion about this very point: http://www.talkchess.com/forum/viewtopic.php?t=50805

    If you want to understand why this is, then you must understand how today's engines represent the board. The standard implementation revolves around bitboards, and that requires 12- 64 bit integers per position, in addition to a redundant mailbox (array in non computer chess jargon) used in conjunction. Copying all that is usually more expensive than a good makeMove/unMakeMove function.

    I also want to point out that a hybrid approach is also common. Usually make and unmake is used on the board itself, where as other information like en passant squares and castle rights are copied and changed like you suggested.