On Mon, May 10, 2010 at 12:05 PM, Don Dailey <[email protected]> wrote: > It's extremely cheap to generate the hash key of a child move if you use > zobrist hashing. You just add the random number of the piece/point you are > placing. Only a fraction of the moves requires substantially more work.
Adding a checksum is cheap. The small fraction which needs substantial work is (relatively speaking) extremely expensive. Doing this for all successors is about equivalent to the amount of work needed to do one light-weight playout, where the total time taken is dominated by the few moves that require more work. And you need to do this several times before you reach a leaf. So I have a hard time seeing how this is "extremely cheap". It sounds "extremely expensive". Unless you have extremely heavy playouts. In which case the memory is not an issue either, as you're not going to create many nodes. I wouldn't mind hearing from someone who actually implemented a hash-table this way, as we both obviously haven't. With regards to memory usage, let's do a little math. Let's say you have 1/2 a Gb per core, a fairly conservative estimate I believe. And on each core you do 100K playouts per second for 10 seconds straight, a rather optimistic scenario I believe.That leaves 500 bytes per node for 9x9. That is easily enough to store pointers to all 82 possible children in a node and store a whole lot more information. (This is for 9x9. Bigger boards may have longer thinking times and more moves compensated by lower playout speeds. Most likely it evens out to be the same regardless the board-size.) Actual numbers in my implementation are closer to 20K (semi-light) playouts per second for 5 seconds, or a leaving space for an order of magnitude more. So, yeah, like you said earlier, I pretty much believe memory is plentiful enough not to worry about it much. Mark _______________________________________________ Computer-go mailing list [email protected] http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
