Hacker News new | past | comments | ask | show | jobs | submit login

What is copy/make vs move/undo? I'm not familiar with that terminology...



When you search you have a choice of:

1)having only one board and make/undo moves on it. So every time you put a new queen on the board you add it to the representation of the board and every time you go back in recursion you need to do an undo before exiting the function (so you new branch won't have queens placed on the board from previous branch)

2)storing as many boards as many steps deep in the recursion you are (max 8 in 8 queens problem) so every time you go deeper into recursion you create new board then you copy current state there and then you make a move (place a queen) on this new board; this way when you go back in recursion you do nothing as this new board is taken care of by stack pointer going back.

The cost of copy make is memory (you need memory for new board representation for every step deeper into recursion) but it's usually not much of a problem. The benefit is that you don't need to code undo logic (which in case of some games is quite complicated) and undo is much faster which usually outweights costs of copying the memory. Some top chess programs are move/undo and some are copy/make, chess board representation usually takes about 200 bytes and variations may go as deep as 100 half moves which means you may need like 20kb additional memory for every thread doing searching. In case of 8 queens it's of course trivial though.

Some more information (for chess, so way more advanced):

https://chessprogramming.wikispaces.com/Copy-Make

https://chessprogramming.wikispaces.com/Make+Move

https://chessprogramming.wikispaces.com/Unmake+Move


Is this equivalent to a depth vs breadth first search? Sounds very similar...




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: