Implement superko about minigo HOT 8 CLOSED

It also comes up on CGOS during take-2-retake-1 -- less often, and usually in games where it's lost anyway. We should still Do The Right Thing.

However, i don't think dragging around a bunch of hashes in our tree search is right. If we have a situation where our best sequence depends on superko, we're probably losing anyway -- so i'm happy to just have it check at the time we select the move to play, and playing our 2nd-best after that. (i.e., at the Player level)

from minigo.

some thoughts on how to correctly implement this: by using a linked-list data structure, the entire game tree can share position history as appropriate. That way, for 2000 nodes of a tree that's currently at move 300, we don't have 600,000 copies of zobrist hashes lying around, but rather just 2300.

from minigo.

How relevant do you think it is to find superko in the tree, vs. just pruning it at move selection time (and also pruning it from the resultant probabilities_pi?)

from minigo.

Some notes on how LZ does this. It's quite different, sounds like brilee's idea would be an easier change for minigo.

LZ makes a search tree of UCTNode objects, but those objects only contain UCT related statistics like N, W, Q, P. Each UCTSearch thread has a single FullBoard object. As it traverses the tree of UCTNodes, it updates FullBoard to match. FullBoard contains a vector of m_ko_hash for detecting super-ko. When a playout is done, the selected leaf is checked for superko, and if it is, mark UCTNode.m_valid = false and repick.

I guess this trades CPU time (constantly update FullBoard state) for memory (keep copies of the full board state in each node).

Edit: I think you want to prune it at least before you collect any search statistics on it. If by move selection time you mean only if the root actually picks the superko, I think that is too late. If you mean picking a leaf node to expand, that's the same as what LZ does.

from minigo.

@killerducky my theory is if the root picks superko, and it's explored superko as the only way to win, it's probably already lost ;)

from minigo.

A LL implementation would work at the go implementation layer, rather than at the MCTS layer. But the idea isn't fully baked yet, because solving the memory requirement is just one problem; the other problem is efficiently computing illegal moves given a history of zobrist hashes.

from minigo.

this looks like a fun thing to do now.

from minigo.

tom did this, yay.

from minigo.