Sabaki
Sabaki copied to clipboard
SabakiHQ
Show Cycles on the Game Tree
Whenever 2+ variations end up with the same configuration, the player/editor has to be aware that both sequences end up the same. However, Sabaki could help in making this realization/analysis quicker. For example, how about showing a dashed line between the 2 nodes? Or maybe coloring them differently if they are too far apart?
This is something that's not embedded into SGF, as SGF tries to be more bare-bones, more general.
Hm, interesting. I guess this would only apply to leaf nodes, right? And transpositions would still count? And superko status? In the latter case, the subtleties of different rule sets come into play, etc, but I'm not sure that our implementation has to be that accurate in order to be useful.
I'm curious if anyone else sees a compelling use-case for this. Maybe for authors of SGF tsumegos and such.
I'm not sure I follow your reasoning about leaf nodes, transpositions and superko status, please do give me some more details.
And, as far as I understand, SGF is simple a text-based trie for the coordinates on a board/matrix, it doesn't really need Go rules. So what I was thinking is that, as long as 2+ branches collapse to the same board configuration, that can be seen as some kind of cycle or connected nodes. Am I wrong in this understanding/description?
In the case of triple kos or superkos, I guess we could create a way of toggling this behavior, so it gets less repetitive, I don't know.
I'm not sure I follow your reasoning about leaf nodes, transpositions and superko status, please do give me some more details.
Sure! Regarding leaf nodes, I assume(d) that you'd only want to know if a node was a transposition of another node if it's at the end of a variation tree. Otherwise, if you had two longer branches that differed only in the order of some moves at the very beginning of the branch, you would end up with every other node in both branches being highlighted, or having dashed lines all over the place between every other node.
And, as far as I understand, SGF is simple a text-based trie for the coordinates on a board/matrix, it doesn't really need Go rules. So what I was thinking is that, as long as 2+ branches collapse to the same board configuration, that can be seen as some kind of cycle or connected nodes. Am I wrong in this understanding/description?
You're right that SGF just deals with coordinates and is not inherently rule-set aware, but if we want a perfectly accurate notion of "equivalence" between two nodes, we have to consider things like what the ko status is (i.e, whether retaking a certain ko is a legal move in that position), since two positions might be perfectly identical as far as stones-on-vertices is concerned, but differ in superko status. But again that's probably a technicality that wouldn't need to actually be considered.
(...) you would end up with every other node in both branches being highlighted, or having dashed lines all over the place between every other node.
Maybe that's the example that shows colored highlighting being better than dashed lines for this possible feature.
But, anyway, going back to the long branches with coincidental configurations across many nodes...
- I think that's very unlikely to happen in Go for too long.
- If it happens, it might actually be a feature to highlight that 2 branches are analyzing very similar, subtle things.
- Being able to toggle this feature on/off easily solves the possible annoyance.
If there's interest in this feature, given the problems that you mentioned and that might end up occurring, maybe we should put some effort upfront with SGF examples of the most likely causes for trouble and post them here, in this thread.
(...) since two positions might be perfectly identical as far as stones-on-vertices is concerned, but differ in superko status.
I don't think going into such specifities is necessary for a first implementation. Maybe such sophistication could be implemented after getting feedback from users.
Some of this discussion reminds me a lot of the issues people might get into when implementing something similar to the Waltheri Pattern Search. Maybe those devs would have something interesting to say about it.
Here are my two cents: Looking for the same board configuration in the whole game for all nodes would be too costly. At the very most, we can provide a search feature that a user can trigger manually. But doing this automatically on every node append and breaking in-the-middle-of-variation-node modifications for all nodes is just going to slow down the app significantly.
Yes, I don't know how this would be done efficiently either. But, recently, I was very surprised to realize OGS does have this feature. When you have the same board position in different variations, there's a line connecting the nodes. I wonder how they did that...
This can be done efficiently by maintaining a hash table that maps a board configuration to the list of nodes with that board configuration.
@kevinsung Currently, board configurations are only materialized and cached on request basis. When you load an SGF file, only the root node board configuration is materialized. It would be a great strain on both CPU and memory to have to calculate the board configurations of all nodes rendered on SGF file load.
I see. Perhaps they could be calculated in the background after the initial loading process without affecting responsiveness. Once the hash table is constructed, maintaining it on node appends would take very little extra work.