On that note, do you expect nauty or Traces to be faster for my graphs?

Or how fast can we compute the stabilizers from the generators of Aut(G) provided by Traces? Or maybe there are other canonical label algorithms which naturally compute the stabilizers of the vertices (or something close)? Or other canonical label algorithms where some of the work can be reused when computing the can. label of a subgraph?

Let's consider normal graphs. Call the parent graph $G$. Remove $v$, remove all edges that contain $v$, and call the resulting graph $G'$. We know that any element of the stabilizer of $v$ (in Aut(G)) induces an automorphism of $G'$. So when we know Stab(v), we can provide some automorphisms of G' to Traces. I think this is a functionality of Traces and speeds up the computation. Furthermore, to get Stab(v), I think Traces computes it when computing the can. label of $G$, at least for the vertices in the selected cell. For the other vertices, maybe one can also extract it out of Traces' tree?

Actually the game is the Maker-Breaker game on a general hypergraph. (But I know the structure of $H$.)

Here is what I'm searching for: The tree is a game tree. Player A can make the A(v) moves and player B the B(v) moves. When the hypergraph has a certain property (fast to check), A wins. When the hypergraph has a certain other property (fast to check), B wins. I want to know who wins with start configuration $H$. So I do a minimax search over the tree. I know that there are a lot of other optimizations and pruning methods, but for now I care about improving the canonical label computation by using the same computation of the parent. (The game is basically Tic-Tac-Toe on a general hypergraph.)

In my example, A(1)B(2)A(3) and A(3)B(2)A(1) are definitely the same hypergraph, because they are both the empty hypergraph. But I guess you mean the case where we have more than 3 vertices, in which case I think I agree that they will still be the same.

True, good tip! I have to look again carefully into the code to see if I'm doing that already. (I know, weird sentence, but it's a longer story.)

I know the starting hypergraph pretty much exactly. It has about 50-80 vertices and 2-3 times as many edges. I also know where the edges are located, they are very "regularly/uniformly" distributed across the vertices. From this hypergraph, we search the tree as described in the post, so vertices and edges will only become less, and I guess the ratio #edges / #vertices stays around the same factor of 1-5.

Checking the things that I'm looking for in the search tree is negligible. It's a fast check that will sometimes lead to stopping early in a branch (i.e. not considering some branch). You can think of the thing I'm doing as literally just traversing (some subtree of) the search tree mentioned above. So the only things that can be slow are (1) the search space is too big and (2) the canonical form computation is slow, because these are the only things I'm doing. I need any possible speed-up from both of those, in particular from (2). Lastly, be sure that I implement it very efficiently in C++.