macfergus
commented
8 months ago Hi @ziyuezzy, this is a great question. This is something we just didn't have room to cover in the book
The speedup comes when you create a new GameState. GameState is immutable (to help with building search trees), so apply_move creates a new GameState. When you call apply_move, it does a deepcopy on the board:
https://github.com/maxpumperla/deep_learning_and_the_game_of_go/blob/master/code/dlgo/goboard_slow.py#L179
When you deepcopy the board, it does a deepcopy of every GoString object. However, when you place a stone, most stones on the board are unaffected. Only strings adjacent to the point you play on may change. So I realized we could eliminate most of those copies.
In the faster implementation, we override the __deepcopy__ method on GoString so it does not copy its point set:
https://github.com/maxpumperla/deep_learning_and_the_game_of_go/blob/master/code/dlgo/goboard_fast.py#L90
So the point of switching to frozenset is so two GoString instances can share their stones set safely, thereby allowing us to eliminate copying most of the stone sets.
This turns out to be a measurable speedup, but not massive. I recall it was something like 20% faster (but it was a while ago, so I may be wrong)
BTW -- there is a much faster version of go logic library here: https://github.com/macfergus/baduk/tree/master
It's a Cython extension and I think it's around 10x faster. Unfortunately, it's not quite a drop-in replacement, but the interface is pretty similar to what's in the book
ziyuezzy
Hi, I am probably asking a stupid question, but why is the "fast_go_strings" class faster than the basic "go_string" class?
I noticed that the "fast_go_strings" class basically define most data structures 'readonly' (e.g., 'frozenset'), and the motheds all adapt to that. But won't this lead to more frequent class object initialization and more copies of data?
I didn't find an answer in the book, nor in the comments in the code. Maybe anyone has more insight on this could help me out? Thanks!