/* board is n*n squares;
   there are l = 2*n*(n-1) possible places to put a line;
   so there are b=2^l possible board configurations;
   so for n=10, l=180, b=2^180 board configurations
   there is a symmetry factor of 8;
   so there are B=b/8 unique board configurations
   so for n=10, B=(2^180)/8 = 2^177
   n=9, l=144, b=2^144, B=2^143
   n=8, l=112, b=2^112, B=2^109
   n=7, l=84, b=2^84, B=2^81
   n=6, l=60, b=2^60, B=2^57
   n=5, l=40, b=2^40, B=2^37
   n=4, l=24, b=2^24, B=2^21 - brute-forceable

   Global symmetry is not the only relevant part - Local symmetry works just as well

    -.-.-.-.-.-.-.-
   |1|1|? ?|2|2|1|1|
    -.-. . .-.-.-.-
   |1|1|? ?|2|2|1|1|
    -.-.-.-.-.-.-.-

   Local symmetry is obvious in the case of a 3x3-line square (2x2-squares - whoever
   is forced to play within the region first loses all of the squares within the region), but
   actually applies to all contiguous sub-regions. If we can find an efficient way
   to canonicalise and lookup the sub-region then it might be searchable for higher n.

   DFS on the graph of square-edges to find the set of all points in a given sub-region.
   Normalise this so that the top-left point of the bounding box is
   at (0,0). Serialise and lookup the shape in the table to see if
   we have a result already. If so, return it. Otherwise, search, and then insert the result into
   the table, including all 8 symmetries (this is time-efficient; space-efficient alternative is to
   only store a result for 1 symmetry but to lookup against all 8...).

   Search: given a sub-region: for each place we are allowed to play a move (i.e.
   each "empty" square-edge which touches a "non-empty" square-edge), play that move,
   and then recurse to find the best score, and then return that score. Remember that
   if the move we played completed a square, then the next move is again played by the
   same player, so the score should not be inverted!

   So the key insight is that we're not playing moves on a *board*, but on a *sub-region* of
   the board. This allows much better caching, but how much better?

   What is the time complexity, and what is the memory complexity?

   Serialise the sub-regions (and, more generally, boards) by use of a bit vector of length
   2*n*(n-1), where each bit corresponds to one square-edge. Use this serialisation as
   the key for the lookup table. Sub-regions will all be rooted at top-left.

   Perhaps we should add an extra 2 rows and columns to the bit vector so that we can represent
   the initial boundary? It will make a difference to the sub-regions.

   Questions about the game:
    - is it always optimal to take a square if one is available?
   */