Counting Domineering Positions
Svenja Huntemann Neil A. McKay




1cmCounting Positions
1cm
Svenja Huntemann 

School of Mathematics and Statistics

Carleton University

Ottawa, ON

Canada

mailto:svenja.huntemann@carleton.casvenja.huntemann@carleton.ca 

 

Neil Anderson McKay 

Department of Mathematics and Statistics 

University of New Brunswick 

Saint John, NB 

Canada 


mailto:neil.mckay@unb.caneil.mckay@unb.ca 




.2 in


is a two player game played on a checkerboard in which one player places dominoes vertically and the other places them horizontally. We give bivariate generating polynomials enumerating positions by the number of each player's pieces. 
We enumerate all positions, maximal positions, and positions where one player has no move. Using these polynomials we count the number of positions that occur during alternating play. Our method extends to enumerating positions from mid-game positions and we include an analysis of a tournament game.




§ INTRODUCTION


Combinatorial games are 2-player games with perfect information and no chance devices, such as Chess or Go. Many combinatorial games have, for a fixed starting position, a finite number of options and the game is guaranteed to end in a finite number of moves; in theory we could determine by computer which player would win if both players play perfectly. In practice game theorists and computer scientists have not determined the outcomes of games under perfect-play because of the complexity of the required search.

Enumeration of positions has been studied, directly or indirectly, for several combinatorial games. Papers on counting game positions consider the problem of enumerating specific types of positions — Go end positions <cit.> and second-player win positions for specific lesser known games <cit.>. In the game Node Kayles, played on a graph, the two players alternate choosing vertices not adjacent to any previously chosen ones, thus forming an independent set. Therefore the independence polynomial of a graph is equal to the generating polynomial for positions of Node Kayles on that graph. Similarly, in the play of Arc Kayles the players form a matching. The enumeration of matchings has been studied for many graphs (see <ref>). 
In partizan games, where players may have distinct options at some point during play, the convention is to call the two players Left (who uses bLue pieces) and Right (who uses Red pieces). In Col, which is played on a graph, a move for Left is to color a vertex blue, while a move for Right is to color a vertex red, and no two vertices of the same color may be adjacent. Oh and Lee <cit.> call such a position a bipartite independent vertex set and give the generating polynomial for grid graphs. Brown et al. <cit.> give the generating polynomial, which they call the polynomial profile, for several games, including closed forms for Col and the game Snort (like Col, but two vertices of different colors may not be adjacent) played on paths.

In this paper we consider the game . This game is played on a checkerboard. The two players alternately place dominoes on adjacent empty squares; Left places vertically and Right places horizontally. The game ends when the player whose turn it is cannot place a piece; the player who cannot play loses — this is the normal play convention. We will count all positions, as well as positions with certain properties, following the method used by Oh and Lee in <cit.>. In newer work Oh also considers monomer-dimer tilings in <cit.>, thus implicitly counting positions, which overlaps with some of our work as discussed in <ref>.

, also called Dominoes or Crosscram in older work, was introduced by Göran Andersson and popularized by Martin Gardner in the 1970s. There has been significant interest in this game since then (see for example <cit.> and references therein). Some simplification techniques are known and can be combined with computer search for analysis, but no complete solution is available. It is known who wins on many rectangular boards up to size 11× 11 and some non-rectangular boards, as well as some values (essentially who has the advantage and by how much) and temperatures (essentially the urgency of moving). For the reader further interested in combinatorial game theory techniques we recommend Siegel's Combinatorial Game Theory <cit.>.

As a game of progresses, the board often naturally breaks into smaller components, see <ref>, where play in one component cannot affect the available moves in other components. A player on their turn has to decide which component they want to play in and make their move there. A position (board) is the disjunctive sum of its constituent components.



If the two players play in different components in the disjunctive sum a player may make consecutive moves in the same component. For example in <ref>, if it is Right's turn, he could choose to play in the third component, Left may choose the fourth, and Right choose the third again. Due to this, we are also interested in positions in which the two players do not necessarily alternate turns, hence we consider plays where the difference between the number of Left dominoes and Right dominoes may be larger than 1.

In <ref> we will find the generating function for the number of positions on an m× n rectangular board which we denote by 

    D_m,n (x,y) = ∑ d(a,b) x^a y^b

where d(a,b) is the number of positions with a Left dominoes and b Right dominoes. We then demonstrate in <ref> how to generalize the technique employed to find D_m,n(x,y) to calculate the generating function for non-rectangular boards.

We are also particularly interested in enumerating positions at the end of the game. A Left end is a position in which Left can no longer play a piece, while Right potentially still has moves; a Right end is defined similarly. A maximal position is a position which is both a Left end and a Right end — a position in which no player can place a domino. In <ref> we will find the generating function for maximal positions, which we denote by F_m,n(x,y). In <ref> we consider the generating function for Right ends; this is essentially the same as the generating function for Left ends.

Finally, in <ref> we will discuss some other questions related to the technique used within and the problem of enumerating positions.



 §.§ Related problems


The checkerboard corresponds to a grid graph by using a vertex for each square and connecting them with an edge if the two squares are horizontally or vertically adjacent. Playing on the checkerboard is then equivalent to forming a matching (also called an edge independent set) on the grid graph, with a distinction made between horizontal and vertical edges. 

If we make no distinction between Left and Right dominoes, that is, we enumerate the positions with a fixed number of dominoes, this is equivalent to enumerating the number of matchings in a grid graph or enumerating the monomer-dimer tilings of the chessboard (Propp <cit.> gives a summary of connections to physics and chemistry). In particular, this means that D_m,n(x,x) is the generating function for matchings in an m× n grid graph, and that D_m,n(1,1) gives the total number of such matchings. The latter, also known as the Hosoya index of the grid graph, is known (for example see Ahrens <cit.> or the OEIS <cit.>
sequences A030186 for 2× n, A033506 for 3× n, and A028420 for n× n). If a perfect matching exists in the m× n grid graph, then the number of perfect matchings is the leading coefficient of D_m,n(x,x) as this is the number of maximum matchings.

Similarly, F_m,n(x,x) gives the generating function for the maximal matchings in an m× n grid graph. The total number of maximal positions F_m,n(1,1) are known for some values of m and n (OEIS sequences A000931 for 1× n, A286945 for 2× n, A288028 for 3× n, and A287595 for n× n). 

belongs to the class of strong placement games, and thus one can assign to each game a simplicial complex representing the legal positions (see Faridi et al. <cit.> for details). The coefficients of D_m,n(x,x) are then the entries of the f-vector — the vector counting the number of faces of a given dimension — of this simplicial complex, while the coefficients of F_m,n(x,x) give the number of maximal faces, called facets, of a fixed dimension. Our work in this paper was originally motivated by wanting to determine how many facets there are with a given number of vertices representing Left or Right moves. We solve this problem by finding F_m,n(x,y) in <ref>.




§ COUNTING ALL POSITIONS


Given m and n, our goal is to count the number of positions that can occur as the result of play in an m × n rectangle. To distinguish this problem from counting specific types of positions later we refer to these as general positions. 

We will find a generating function D_m,n(x,y) such that

    D_m,n (x,y) = ∑ d(a,b) x^a y^b

where d(a,b) is the number of positions with a Left (vertical) dominoes and b Right (horizontal) dominoes.

We will extract from the generating function information on the play positions, those that can be reached through alternating play, in <ref>.

In their paper, Oh <cit.> considers an equivalent problem to the particular problem of counting general positions using a trivariate generating function, where the third variable counts the number of empty squares. The number of empty squares is not particularly relevant to . However, this information can be deduced from the number of dominoes of either player and the board size. We use an equivalent method, but as our generating functions are slightly different, our recursions are different as well. We include the recursion here for completeness, particularly as we continue using the matrices in <ref>.

To count rectangular positions we consider the tilings of rectangles using tiles with edge labels, then count the tilings that correspond to positions. 

We use the tiles in <ref>.



For a rectangular tiling to form a position the tiling must satisfy the following conditions:


  * Adjacency condition: All shared edges of adjacent tiles have the same label.

  * Boundary condition: All boundary edges of the tiling have label 0.


Together these conditions ensure that the tiling has no half-dominoes.

In turn, any position can be uniquely represented using such a tiling. See <ref> for an example.

In the tiling of a position, such as in <ref>, the number of Left (vertical) dominoes is equal to the number of T_1, and the number of Right (horizontal) dominoes is equal to the number of T_3.



We use the term mosaic for tilings that satisfy the adjacency condition, but not necessarily the boundary condition. A 1 × q mosaic is called a bar mosaic, that is, a row of q tiles.

We will find generating polynomials by first counting bar mosaics. We then stack these bars to count rectangular mosaics; in this step that we consider the adjacency condition for vertically adjacent tiles. Finally, we restrict to those tilings that also satisfy the boundary condition.

We will count mosaics instead of just tilings as a row or column of a rectangle is not necessarily a position itself. For example in <ref> the second row from the bottom forms the bar mosaic shown in <ref> — it does not correspond to a position on its own as the leftmost two tiles are unpaired half-dominoes, but shared edges of horizontally adjacent tiles do have the same label.



The enumeration of bar mosaics will be done using matrices, called bar-state matrices. We take care to construct these matrices so that we can count rectangular mosaics by matrix multiplication.  As we only want to count mosaics that satisfy the boundary condition in the end, we can make due with counting only bar mosaics with label 0 on the right end. The enumeration of the bar mosaics will be done recursively — we use the enumeration of bar mosaics to enumerate longer bar mosaics — so our matrices are recursively defined (using blocks). We use two bar-state matrices; the matrix to count bar mosaics of length q with right label 0 and left label 0 is denoted by G_0,q and the matrix to count bar mosaics of length q with right label 0 and left label 1 is denoted by G_1,q. We use G here for naming the matrices, standing for `general', to reserve M for matrices in the subsequent sections of the paper, which include a discussion of maximal positions.


The polynomial profile of on an m× n board is the (1,1) entry of G_0,n^m where G_0,0 = [ 1;   ],
G_1,0 = [ 0;   ],


    G_0,q+1 =
    [G_0,q+G_1,q   xG_0,q
    G_0,q   ],  and 
    G_1,q+1 =
    [yG_0,q   
       ].





We will first prove that the bar-state matrices give the generating polynomials for bar mosaics.

In a bar-state matrix the rows and columns are indexed by binary strings of length q and thus each matrix has size 2^q× 2^q. We order these strings lexicographically. Thus the strings of length 3 are ordered as

    000,001,010,011,100,101,110,111.



An entry in a bar-state matrix is the generating polynomial of the bar whose top edge labels are the column index, and whose bottom edge labels are the row index; the right edge label is 0 and the left edge label corresponds to the matrix (the first subscript of G). The generating polynomial of the bar is the monomial x^ay^b where a is the number of T_1 in the bar and b is the number of T_3 in the bar.

For q=0, the length is 0, it is only possible to satisfy the adjacency condition if both the starting and ending labels are the same. We thus have G_0,0 = [ 1 ] and G_1,0 = [ 0 ].

Our construction for larger q uses blocks and we name them as in <ref> to avoid proliferating subscripts. We need to show that in each matrix the four blocks are as we claim. Our argument is recursive and follows by first considering the leftmost tile in each bar. The block considered determines the top label and bottom label of the leftmost tile in bar mosaics enumerated as in <ref>.



For q=1, the bars we are counting consist of a single tile which must have right label 0 (or cannot have right label 1), that is, one of the four tiles 0–3; you may wish to reference <ref>. Thus between the bar-state matrices G_0,1 and G_1,1 we have four nonzero blocks — determined by the top and bottom labels of tiles 0–3. Recall that each block has a corresponding top and bottom label of the leftmost tile.
Thus 

    G_0,1=[ 1 x; 1 0 ]
    G_1,1=[ y 0; 0 0 ],

which shows that the recursion is correct for the first step.

The bar-state matrix G_0,q+1 enumerates mosaics where the leftmost tile has left label 0 (and right label 0). We consider possible leftmost tiles which are tiles 0–2 and 4, as these are the only tiles with left label 0.
Of these four tiles, those tiles that meet the conditions for block I are tile 0 and tile 4. As the right label of tile 0 is 0, the possible completions of our bar when the leftmost tile is tile 0 are given by G_0,q. As the right label of tile 4 is 1, the possible completions of our bar are given by G_1,q. So block I is G_0,q+G_1,q.

The conditions for block II (that the leftmost tile has top label 1 and bottom label 0) require the leftmost tile in the bar mosaic to be T_1 and the entry is thus xG_0,q because the right label of tile 1 is 0 and G_0,q counts the bar mosaics with left label 0 and right label 0 (recall that for each T_1 we have an x).

The conditions for block III force T_2 as the leftmost tile, giving the entry G_0,q. For block IV, we would need a tile with bottom and top label 1 but no tiles have such labels and so our entry is .

In G_1,q+1, we have a left label of 1. As our recursion starts by consider possible left tiles, we need only consider tile 3, as this is the only tile with 1 as a left label.

Thus the only block for which tile 3 has appropriate top and bottom labels is block I. Since T_3 is forced and its left label is 0, the possible completions of the bar are given by G_0,q and the entry in block one is yG_0,q. All other blocks, having no possible leftmost tiles, count no mosaics and thus their blocks are .

We turn our attention to rectangular m × n tilings and in particular those that satisfy the left and right boundary conditions, so we will only consider the bar mosaics of length n with left label 0 in addition to having the right label 0; these are counted by  G_0,n.

First consider 2× n mosaics that satisfy the adjacency condition.
Such a mosaic consists of two bar mosaics where the string of bottom labels of one mosaic matches the string of top labels of the other. Suppose A is the bar-state matrix for the top bar and B is the bar-state matrix for the bottom bar. To count all the 2× n mosaics that satisfy the adjacency condition we need to consider all 2^n strings of matched labels along the stacked bar mosaics. That is, we take columns in A and rows in B. Since the other labels of the bar mosaics have to match, we take the dot product of the two vectors to get the polynomial for this mosaic. Thus the matrix for the 2× n mosaic is BA.

To get mosaics that also satisfy the boundary conditions and thus correspond to positions we can start with bar mosaics that satisfy the left and right boundary conditions; in our case A=B=G_0,n, so the state matrix for 2 × n mosaics where the left and right boundary conditions are also satisfied is G_0,n^2.

For larger mosaics this works the same way; we stack more bars and find that the matrix for a m× n mosaic is G_0,n^m.

Fixing the string of top labels and of bottom labels for the 2× n mosaic corresponds to specifying an entry in the matrix.
Finally, to satisfy the boundary condition on top and bottom we need to restrict to all top and bottom labels being 0. This means we take the entry in the top left corner, entry (1,1).



Now we compute the number of general positions on a 4× 3 board. We need the bar-state matrix for bar mosaics of length 3 satisfying the left and right boundary conditions, G_0,3, which we find recursively to be as follows:


    G_0,1=[ 1 x; 1 0 ]    
    G_1,1=[ y 0; 0 0 ]


    G_0,2=[[ y+1   x   x x^2;   1   0   x   0;   1   x   0   0;   1   0   0   0 ]]    
    G_1,2=[[  y xy  0  0;  y  0  0  0;  0  0  0  0;  0  0  0  0 ]]


    G_0,3=[[ 2y+1 xy+x    x  x^2 xy+x  x^2  x^2  x^3;  y+1    0    x    0    x    0  x^2    0;    1    x    0    0    x  x^2    0    0;    1    0    0    0    x    0    0    0;  y+1    x    x  x^2    0    0    0    0;    1    0    x    0    0    0    0    0;    1    x    0    0    0    0    0    0;    1    0    0    0    0    0    0    0 ]]


Calculating G_0,3^4 gives the state matrix for 4 × 3 boards and taking the (1,1) entry, gives the generating function for 4 × 3 positions as follows:

    D_4,3(x,y)    = x^6 + 9x^5 + 6x^4y^2 + 20x^4y + 30x^4 + 46x^3y^2 + 84x^3y + 45x^3
            + 4x^2y^4 + 24x^2y^3 + 100x^2y^2 + 100x^2y + 30x^2+24xy^4
            + 72xy^3 + 90xy^2 + 48xy + 9x + 16y^4 + 32y^3 + 24y^2+ 8y + 1.


For example, on a 4× 3 board there are 90 positions with 1 vertical domino and 2 horizontal dominoes as shown by the term 90xy^2 and there is 1 position with 6 vertical dominoes as shown by the term x^6.





 §.§ Play positions


The polynomials we have found count all legal positions. As mentioned previously, we do not assume alternating play. Positions which may occur during alternating play are called play positions. To enumerate play positions we restrict D_m,n(x,y) to include only terms where the difference in the powers of x and y is at most 1. 


Using <ref> we can see that the polynomial for the play positions on a 4× 3 board is

    46x^3y^2+ 24x^2y^3+ 100x^2y^2 + 100x^2y+ 90xy^2 + 48xy + 9x + 8y + 1.


Setting x=y=1 in this polynomial we get the total number of play positions, which in this case is 426.


The number of play positions on an n × n board is in the OEIS as A332714. The terms up to n=10 are given in <ref>. We also include the ratio of all positions that are play positions, truncated to 5 decimals. Recall that the number of all positions is the number of matchings in a grid graph, which is given in the OEIS as A028420.



The ratios computed in <ref> give a sense of the cost of considering all plays from a position, as is standard in combinatorial game theory, compared to considering only plays reachable in alternating play, which is common in practice.

We expect that the ratio of play positions decreases as the board size increases because on larger boards there are an increasing number of ways to have a board with the number of dominoes for the two players differing by more than one. The ratios apparently do not follow an arithmetic or geometric sequence. 

We expect the ratios of play positions to general positions to approach 0. While it is interesting to consider how this ratio changes as the board size grows, it is also potentially interesting to observe how this ratio changes during play.



§ NON-RECTANGULAR BOARDS


The techniques we use to find the generating polynomials of rectangular boards can be used to find the generating polynomials of non-rectangular boards as well.

We think of a non-rectangular board as being a rectangular board with missing squares and treat the missing squares as squares forced to be empty. For example, the board on the left in <ref> we think of as being contained in a 2× 3 board with forced empty squares in the top left and top middle.




We will create a (bar-state) matrix R_i for each row, then multiply these matrices to get the state matrix for the entire mosaic. For the board in <ref> the matrix for row 1 is R_1=G_0,1. For row 2 we will use G_0,3, but restrict those columns which have 0 in the first and second position of the top label. We denote this as R_2=.G_0,3|^00_. For restrictions on bottom labels we will use a subscript. <ref> shows this procedure, but before that we consider rows with missing squares in the middle as in <ref>. If a row contains an missing square in the middle, the Kronecker product of the bar-state matrices of the shorter strips is the bar-state matrix for the row. The Kronecker product of two matrices A and B is

    A⊗ B=[ a_11B     ⋯ a_1nB;     ⋮     ⋱     ⋮; a_m1B     ⋯ a_mnB ].


If missing squares in a row break it into three or more parts we use the Kronecker product multiple times.

The tiling (and the play) in the left part of the broken row is independent of the tiling (and play) in the right part. The state-matrix for the whole row is a block matrix where the blocks are determined by possible labels of the first part of the row, while the order of the second part in each block is the same and determined by the possible top and bottom labels in that part. Thus, taking the Kronecker product of the matrix for the first strip with the matrix for the second strip is exactly what we need here.


Consider the strip 



[fill=gray] (1,0)–(1,1)–(2,1)–(2,0)–cycle;
in 0,1,2,3,4
(,0)–(,1);

in 0,1
(0,)–(4,);

at (3.5,0) 0;



which is the center row of the board in <ref>.

The matrix for this row is 

    G_0,1⊗ G_0,2|__0   =
    [ 1 x; 1 0 ]⊗[ y+1   x   x x^2;   1   x   0   0 ]
       =
    [[  y+1    x    x  x^2 xy+x  x^2  x^2  x^3;    1    x    0    0    x  x^2    0    0;  y+1    x    x  x^2    0    0    0    0;    1    x    0    0    0    0    0    0 ]]
    .





Finally, we multiply the matrices for each row such that the bottom row matrix is the left-most one, while the top row matrix is the right-most one, allowing us to match the top/column label of each row with the bottom/row label of the row above.


Consider the board in <ref>.



For row 1 we have

    R_1=G_0,4|__0__;

for row 2, as in <ref>,

    R_2=G_0,1⊗ G_0,2|__0;

and for row 3

    R_3=G_0,3|^_0_.


The matrix for the entire mosaic is then G=R_3× R_2× R_1. To apply the restriction of having only 0s for top and bottom labels we take only the (1,1) entry of the matrix. Thus we get the generating polynomial

    D   =2x^3y^2 + 8x^3y + 4x^3 + 12x^2y^2 + 22x^2y + 8x^2 + xy^4 + 10xy^3 + 26xy^2
            + 21xy + 5x + 2y^4 + 9y^3 + 12y^2 + 6y + 1.



Using this technique for non-rectangular boards, we are thus able to find the generating polynomial counting positions that can be reached from a partially played board. We will do so in <ref>, where we will also use the following simplification for disjunctive sums.


Suppose G is the game of on the board B_1 and H is on B_2. Then the generating polynomial of G+H is the product of the generating polynomials of G and H.


Let the coefficient of x^iy^j in the generating polynomial of G be a_i,j, of H be b_i,j, and of G+H be c_i,j.

Consider a position in G+H with u Left pieces and v Right pieces. Say i Left pieces and j Right pieces of these have been played in G and the rest in H. There are a_i,jb_u-i,v-j such positions, and thus 
    c_u,v=∑_0≤ i≤ u
     0≤ j≤ v a_i,jb_u-i,v-j.
 Therefore, the generating polynomial of G+H is the product of those of G and H.


This proposition again emphasizes that it makes sense to enumerate all positions, not just play positions, due to disjunctive sums allowing a difference in the number of pieces larger than 1. 


The position in <ref> occurred partway through Game 1 of the finals of the tournament at the 1994 workshop “Games of No Chance” at MSRI (see the tournament report by West <cit.>). We will determine the polynomial for all play positions that would have to be analyzed from this point on. 



We start by finding the generating polynomials for general positions of each of the three disjunctive sum component as we have done in <ref>.

The “bottom” component, bordered in blue, as a mosaic has the matrix

    G_0,6|^00_ _00× G_0,2^3

(recall that we multiply the matrices for each row from the bottom up). Thus the generating polynomial, the (1,1) entry of this matrix, is 
    x^4y^2 + 2x^4y + x^4 + 10x^3y^2 + 16x^3y + 6x^3 + 3x^2y^4 + 24x^2y^3 + 58x^2y^2
            + 46x^2y + 11x^2 + 8xy^4 + 42xy^3 + 62xy^2 + 34xy + 6x + y^6 + 9y^5
            + 26y^4 + 35y^3 + 24y^2 + 8y +1.


The “top” component, bordered in red, has the matrix 

    (G_0,1⊗ G_0,1)×( G_0,1⊗ G_0,1)×( G_0,2|__0⊗ G_0,2|_0_)×(G_0,6|__ _00_ _^_ _000_)
         ×(G_0,2⊗ G_0,1)×(G_0,6|_00_ _00⊗ G_0,1).


The generating polynomial is 

    x^9y^3 + 3x^9y^2 + 3x^9y + x^9 + 23x^8y^3 + 62x^8y^2 + 55x^8y + 16x^8 + 4x^7y^5
          + 43x^7y^4 + 291x^7y^3 + 555x^7y^2 + 401x^7y + 98x^7 + 60x^6y^5 + 539x^6y^4
          + 1874x^6y^3 + 2564x^6y^2 + 1469x^6y + 295x^6 + 4x^5y^7 + 71x^5y^6 + 650x^5y^5
          + 2908x^5y^4 + 6250x^5y^3 + 6303x^5y^2 + 2885x^5y +481x^5 + 34x^4y^7
          + 467x^4y^6 + 2590x^4y^5 + 7406x^4y^4 + 11148x^4y^3 + 8637x^4y^2 + 3218x^4y
          + 452x^4 + x^3y^9 + 20x^3y^8 + 222x^3y^7 + 1421x^3y^6 + 4991x^3y^5
          + 9909x^3y^4 + 11109x^3y^3 + 6812x^3y^2 + 2098x^3y + 251x^3 + 3x^2y^9 + 55x^2y^8
          + 437x^2y^7 + 1909x^2y^6 + 4790x^2y^5 + 7083x^2y^4 + 6172x^2y^3 + 3063x^2y^2
          + 789x^2y + 81x^2 + 3xy^9 + 50xy^8 + 330xy^7 + 1123xy^6 + 2181xy^5
          + 2533xy^4 + 1774xy^3 + 726xy^2 + 158xy + 14x + y^9 + 15y^8 + 85y^7 + 237y^6
          + 373y^5 + 353y^4 + 204y^3 + 70y^2 + 13y + 1.


Finally, the component on the left, bordered in green, is simply a 6× 1 board, thus having matrix G_0,1^6 and generating function D_1,6(x,y)=x^3 + 6x^2 + 5x + 1.

Multiplying all three generating polynomials we get the generating polynomial for the entire position. Restricting to only play positions this is

    17x^10y^11 + 410x^10y^10 + 7690x^10y^9 + 6769x^9y^10 + 76829x^9y^9 + 532379x^9y^8 
          +  436560x^8y^9 + 2217847x^8y^8 + 7453953x^8y^7 + 6030494x^7y^8
          + 16049771x^7y^7 + 29420257x^7y^6 + 23698832x^6y^7 + 36239078x^6y^6
          + 38789964x^6y^5 + 31354701x^5y^6 + 29013063x^5y^5 +18784523x^5y^4
          + 15287335x^4y^5 + 8768628x^4y^4 + 3451191x^4y^3 +2830886x^3y^4
          + 1004132x^3y^3 + 232953x^3y^2  + 192647x^2y^3 + 40779x^2y^2 + 5086x^2y
          + 4240xy^2 + 487xy + 25x + 21y + 1.


In this polynomial we see from the small degree terms the number of possible paths of the game from this position. The high degree terms give some sense of the state at the end of the game provided play continues in such a way that the game lasts as long as possible. In this game Left played first; we see that Left (vertical) has played 6 times, whereas Right has played 5 times, and thus it is Right's turn from this position. Right has 21 possible moves. Right would likely have been happy to see terms in the polynomial where the degree of y is greater than the degree of x as these indicate the possibility of Right winning; of note then is the term 17x^10y^11 with a relatively small coefficient. The actual winner of this game was Left.


Further, by setting x=y in all matrices, we are also able to count the number of matchings of a subgraph of a grid using this technique.




§ COUNTING MAXIMAL POSITIONS

	
Recall that a maximal positions is one in which neither player has any available moves. In this section we count maximal positions. We find the generating function

    F_m,n(x,y)=∑ f(a,b)x^ay^b

where the board has size m× n and f(a,b) is the number of maximal positions with a Left (vertical) dominoes and b Right (horizontal) dominoes. We use F for the generating polynomial of the maximal positions as these correspond to the facets (maximal faces) of the simplicial complex representing the position.

We will use the same technique as for the general positions of counting bar mosaics, multiplying the matrices, and then restricting to tilings, with only a few small differences. The tiles will be different so that with only using adjacency and boundary conditions we can force the tiling to be equivalent to a maximal position, i.e., no two empty spaces may be adjacent, and in turn a position corresponds to a unique tiling. The possible tiles in this case are given in <ref>.


For a rectangular tiling to form a maximal position the tiling must satisfy the following conditions:


  * Adjacency condition: All shared edges of adjacent tiles have the same label.

  * Boundary condition: The left and top boundary edges of the tiling have label 0; the right and bottom boundary edges have label 0 or 1.


In turn, any maximal position can be uniquely represented using a such a tiling. To decide between the different tiles representing domino halves one simply has to check for empty squares above and to the left. As an example, see the position and equivalent tiling in <ref>.



Note that the number of Left (vertical) dominoes is equal to the number of T_1 and T_2 combined, and the number of Right (horizontal) dominoes is equal to the number of T_7 and T_8 combined.

In this case we will use M in the name of the bar-state matrices to represent that we are counting maximal positions only. Also note that, since the bottom and right edge in a tiling are allowed to have both 0 and 1 as their labels, the generating polynomial will be a sum of entries. A detailed explanation is given in the proof of the following theorem. 


The generating function for the maximal position of an m × n board is 

    F_m,n(x,y)=∑_u ∈{0,1}^n(M_0,n + M_0,n')^m(1 + ∑_i=1^n u_i 3^i , 1)

where M_0,0 = [ 1;   ],
M_1,0 = [ 0;   ],
M_2,0 = [ 0;   ], 
M_0,0' = [ 0 ],
M_1,0' = [ 1 ],
M_2,0' = [ 0 ],



!
1.2
M_0,(q+1) =
[M_2,q   M_2,q   xM_0,q
M_1,q      
M_0,q   M_0,q   ],
M_0,(q+1)' =
[M_2,q'   M_2,q'   xM_0,q'
M_1,q'      
M_0,q'   M_0,q'   ],




!
1.2
M_1,(q+1) = 
[M_2,q   M_2,q   xM_0,q
      
M_0,q   M_0,q   ],
M_1,(q+1)' = 
[M_2,q'   M_2,q'   xM_0,q'
      
M_0,q'   M_0,q'   ],




!
1.2
M_2,(q+1) =
[yM_0,q   yM_0,q   
      
      ], and 
M_2,(q+1)' =
[yM_0,q'   yM_0,q'   
      
      ].






The proof will be along the same lines as the proof of <ref>, thus some of the details will be omitted.

The bar-state matrices count bar mosaics of length q. The matrix M_k,q counts those bars with starting label k and ending label 0, while the matrix M_k,q' counts those with starting label k and ending label 1.

The labels will be ternary strings, ordered lexicographically. Thus, the strings of length 2 are ordered as

    00,01,02,10,11,12,20,21,22.

The column labels of the matrix again correspond to the top label of the bar mosaic, while the row label is the bottom label. Each bar is represented by a monomial x^ay^b where a is the total number of T_1 and T_2 in the bar and b is the total number of T_7 and T_8 in the bar.

Each matrix has 9 blocks, which we label using roman numerals as shown in <ref>, where we also show the corresponding top and bottom labels for the leftmost tile.

 

In M_0,q+1, we have a left label of 0. The only tile that meets the conditions for block I (and M_0,q+1) is T_9. As the right edge label of T_9 is 2, the possible completions of our bar are given by M_2,q and so our block I entry is M_2,q.

The conditions for block II force T_10 as the starting tile and the entry is again M_2,q.

The conditions for block III force T_1 — giving the entry xM_0,q as T_1 has right label of 0. For block IV, tile T_0 is the only possible starting tile, giving entry M_1,q. For blocks V and VI we would need a tile with bottom label 1 and top label 1 or 2, respectively, and no such tiles exist so our entry is .

The conditions for block VII are top label of 0 and bottom label of 2; the only tile that works is T_3 and hence the entry is M_0,q. The conditions for block VIII are similar but with top label 1 so T_4 is the only tile that works. 

The conditions for block IX are top label of 2 and bottom label of 2 which never occurs and thus our entry is .

In M_1,q+1, we have a starting (left) label of 1. This forces T_11 in block I; T_12 in block II; T_2 in block III; T_5 in block VII; and T_6 in block VIII. The remaining blocks have no possible tiles. Thus our entries for the matrix are as above.	

In M_2,q+1, we have a starting (left) label of 2. Thus the only possible tiles are T_7 and T_8. In block I the only possible tile is T_7, giving yM_0,q. In block II the tile is T_8, giving yM_0,q. All other blocks have no possible tiles, so are .

Note that the arguments for M_0,q+1', M_1,q+1', and M_2,q+1' are similar as the possible left-most tile is identical and only the ending label changes, thus we skip these.

Now, restricting to tilings, we will only consider the bar mosaics of length n with left label 0 and right labels 0 or 1, so M_0,n+M_0,n'. As in the general positions case, stacking the bar mosaics corresponds to matrix multiplication. Thus the mosaics with all left labels 0 and right labels 0 or 1 are enumerated in (M_0,n+M_0,n')^m. Finally, we need to restrict to top labels being all 0 and bottom labels 0 or 1. This means we need to sum the entries in the first column which are in rows numbered 1+∑_i=1^n u_i 3^i  where the u_i are all 0 or 1 (the ternary expansion of the row number-1 has no 2s), giving our result.



Using the recursion we find that

    M_0,2=[[   y   y   0   y   y   0   0   0 x^2;   0   0   0   0   0   0   0   0   0;   0   0   0   0   0   0   x   x   0;   0   0   x   0   0   0   0   0   0;   0   0   0   0   0   0   0   0   0;   1   1   0   0   0   0   0   0   0;   0   0   x   0   0   x   0   0   0;   0   0   0   0   0   0   0   0   0;   1   1   0   1   1   0   0   0   0 ]].


Taking the third power and summing the relevant entries, we get that

    F_3,2(x,y)= 2x^2y + 2x^2 + y^3.




As for the general positions case, we can use these matrices to find the generating polynomial for non-rectangular boards. As the technique is the same, we do not demonstrate it here.




§ COUNTING LEFT AND RIGHT ENDS


Similar to maximal positions, we are also able to count Left or Right ends by choosing the tiles appropriately so that the adjacency condition alone forces such an end. We will just be counting the Right ends in this section as it results in bar-state matrices of size 2^q× 2^q, while the Left ends, using a similar argument, would need bar-state matrices of size 3^q× 3^q (although fewer matrices). Alternatively, the generating polynomial for Left ends on an m× n board can be found using the generating polynomial of Right ends on an n× m board by switching x and y. Further, if we would like to find the number of Left or Right ends, we add the number of positions of each type and then subtract the number of maximal positions as these are the positions that are Left and Right ends.

For Right ends, we may have two empty squares vertically adjacent as Left may potentially still play a domino. But we must not have two empty squares horizontally adjacent as Right must have no moves. To achieve this using the adjacency condition, we use the tiles  given in <ref>.


The two conditions for a tiling to be a Right end are as follows:


  * Adjacency condition: All shared edges of adjacent tiles have the same label.

  * Boundary condition: The left, top, and bottom edges of the tiling have labels 0; the right edge has labels 0 or 1.


<ref> contains an example of a position and the corresponding tiling.


We use RE for naming the bar-state matrices. The matrix RE_k,q counts those bar mosaics of length q with starting label k and ending label 0, while the matrix RE_k,q' counts those with starting label k and ending label 1.


The generating polynomial of Right ends on an m× n board is the (1,1) entry of (RE_0,n+RE_0,n')^m where RE_0,0 = [ 1;   ],
RE_1,0 = [ 0;   ], RE_2,0 = [ 0;   ], RE_0,0' = [ 0;   ],
RE_1,0' = [ 1;   ], RE_2,0' = [ 0;   ],


!
1.1
RE_0,q+1 =
[RE_1,q+RE_2,q   xRE_0,q
RE_0,q   ],
RE_0,q+1' =
[RE_1,q'+RE_2,q'   xRE_0,q'
RE_0,q'   ],


!
1.1
RE_1,q+1 =
[RE_2,q   xRE_0,q
RE_0,q   ],
RE_1,q+1' =
[RE_2,q'   xRE_0,q'
RE_0,q'   ],


!
1.1
RE_2,q+1 =
[yRE_0,q   
   ], and 
RE_2,q+1' =
[yRE_0,q'   
   ].





We give no proof here as the argument is simply a combination of the arguments for the general and maximal positions.

In <ref> we give the total number of Right ends on an m× n board (the table for Left ends is the transpose of <ref>). <ref> is in the OEIS, read by antidiagonals, as A332862.



The number of Right ends on a 1× n board is recursively given by a_1=1, a_2=1, a_3=2, a_n=a_n-2+a_n-3 (the Padovan sequence shifted, OEIS sequence A000931). Consider the leftmost square, if the square contains a domino, then the strip to the right of the domino can contain any Right end of length n-2. If the square is empty, then a domino has to be immediately to the right of it, and the remaining strip of length n-3 can contain any Right end.

In the positions of shape m× 1 Right cannot play, thus all positions are Right ends. The sequence of these numbers is the Fibonacci sequence (OEIS sequence A000045) as every position is a combination of empty squares and Left dominoes.

It appears that the number of Right ends on an m× 2 board is given by the squared Fibonacci numbers (OEIS sequence A007598) and the number of positions on an m× 3 is given by the recursion a_m=4a_m-1+4a_m-2-4a_m-3-a_m-4 (OEIS sequence A054894).

The main diagonal of <ref>, the number of Right ends on an n × n board, is in the OEIS as A332865. Other sequences for the number of Right ends do not appear in the OEIS at this point.



§ FURTHER WORK
 

We suggest three broad avenues for continuing the work in this paper. One is to explore our original motivation and connect the enumeration of to questions of the algebraic structure of placement game positions. Secondly, we expect the methods demonstrated in this paper to be useful for other placement games played on grid-like boards (such as Cartesian products of cycles and paths). Lastly, there is the possibility of counting positions to analyze particular game situations either in theory or practice to develop better play strategies.



§ ACKNOWLEDGMENTS


The authors thank Mount Allison University in Sackville NB, Canada. This research project started while both authors were members of the Department of Mathematics and Computer Science.

The first author's research was supported in part by the Natural Sciences and Engineering Research Council of Canada (funding reference number PDF-516619-2018).

plain
10

Ahrens1981
J. H. Ahrens, Paving the chessboard, J. Combin. Theory Ser. A 31(3)
  (1981), 277–288.

Berlekamp1988
E. R. Berlekamp, Blockbusting and domineering, J. Combin. Theory Ser. A
  49(1) (1988), 67–116.

BerlekampCG2004
E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways for your
  Mathematical Plays. Vol. 1, AK Peters Ltd., Wellesley, MA, second edition,
  2004.

BrownCHMMNS2019
J. I. Brown, D. Cox, A. Hoefel, N. McKay, R. Milley, R. J. Nowakowski, and
  A. A. Siegel, A note on polynomial profiles of placement games.
In Urban Larsson, editor, Games of No Chance 5, Vol. 70 of Mathematical Sciences Research Institute Publications, pp.  249–265.
  Cambridge University Press, 2019.

FaridiHN2019a
S. Faridi, S. Huntemann, and R. J. Nowakowski, Games and complexes I:
  Transformation via ideals.
In Urban Larsson, editor, Games of No Chance 5, Vol. 70 of Mathematical Sciences Research Institute Publications, pp.  293–304.
  Cambridge University Press, 2019.

FarrSchmidt2008
G. Farr and J. Schmidt, On the number of Go positions on lattice graphs, Inform. Process. Lett. 105(4) (2008), 124–130.

Farr2003
G. E. Farr, The Go polynomials of a graph, Theoret. Comput. Sci. 306(1-3) (2003), 1–18.

Hetyei2009
G. Hetyei, Enumeration by kernel positions, Adv. Appl. Math. 42(4)
  (2009), 445–470.

NowakowskiRLMM2013
Richard J. Nowakowski, Gabriel Renault, Emily Lamoureux, Stephanie Mellon, and
  Timothy Miller, The game of TIMBER!, J. Combin. Math. Combin. Comput.
  85(May) (2013), 213–225.

Oh2017
Seungsang Oh, Maximal independent sets on a grid graph, Discrete Math.
  340(12) (2017), 2762–2768.

Oh2019
Seungsang Oh, State matrix recursion method and monomer–dimer problem, Discrete Math. 342(5) (2019), 1434–1445.

OhLee2016
Seungsang Oh and Sangyop Lee, Enumerating independent vertex sets in grid
  graphs, Linear Algebra Appl. 510 (2016), 192–204.

Propp1999
James Propp, Enumeration of matchings: problems and progress.
In New Perspectives in Algebraic Combinatorics (Berkeley,
  CA, 1996–97), Vol. 38 of Math. Sci. Res. Inst. Publ., pp.
  255–291. Cambridge Univ. Press, Cambridge, 1999.

Siegel2013
Aaron N. Siegel, Combinatorial Game Theory, Vol. 146 of Graduate
  Studies in Mathematics, American Mathematical Society, Providence, RI, 2013.

oeis
N. J. A. Sloane et al., The On-line Encyclopedia of Integer Sequences,
  https://oeis.orghttps://oeis.org, 2020.

TrompFarneback2007
J. Tromp and G. Farnebäck, Combinatorics of Go, In Proceedings of the
  5th International Conference on Computers and Games, CG'06, pp.  84–99,
  Berlin, Heidelberg, 2007. Springer-Verlag.

Uiterwijk2016
Jos W. H. M. Uiterwijk, 11× 11 Domineering is solved: the first
  player wins.
In Computers and games, Vol. 10068 of Lecture Notes in
  Comput. Sci., pp.  129–136. Springer, Cham, 2016.

West1996
Julian West, Championship-level play of domineering.
In Games of No Chance (Berkeley, CA, 1994), Vol. 29 of Math. Sci. Res. Inst. Publ., pp.  85–91. Cambridge Univ. Press, Cambridge,
  1996.

Wolfe1993
David Wolfe, Snakes in domineering games, Theoret. Comput. Sci. 119(2) (1993), 323–329.





2010 Mathematics Subject Classification:
Primary 91A46; Secondary 05C30 and 05C57. 

Keywords: combinatorial game, , enumeration, matchings, grid graph.



