Overview

After every operation which changes an extensive game, internally the following operations are done:

• Re-number all nodes in the order encountered in a depth-first traversal of the tree;
• Sort members of all information sets by their node number
• Sort all information sets for each player by the node number of there first member (as determined by the above).

The idea of this is that no matter the order in which a game is built, two games which are "equivalent" (for an appropriate notion of equivalence) would have a player's information sets sorted in the same order. This was further quite useful in some very old code in which numerical indices for information sets were significant.

This (obviously?) does not scale very well when building games in e.g. Python, because this is called after every operation. Meanwhile, building a game (almost?) never requires this sorting, and in general, especially with the deprecation of using integer indices in favour of iteration, it's not clear that very many users would even care about having such canonicalisation.

Plans

It is possible that simply eliminating this canonicalisation could lead to some unexpected behaviours in existing code. This is a draft plan that will allow us to get some substantial performance improvements while assessing whether there's any unintended consequences.

• Rename Canonicalise to SortInfosets and make a public member in C++ and Python
• Remove automatic call to SortInfosets after every transformation operation
• We only use node numbering in this sorting process. Remove the node number member and instead have NumberNodes non-recursively create a map of nodes to indices for the purpose of sorting the information sets
• Replace the hand-coded bubble sort in SortInfosets with a call to std::sort.
• Canonicalisation is also applied after reading a .efg file. We should have a look at whether removing this would cause any problems, and/or whether we should add a flag optionally to sort the information sets on loading.