Consider a game played on an $n$ * $n$ square grid. Player A (Alice) has 1*1 square tiles, while Player B (Bob) has 2*2 square tiles. On their turn, a player can place one of their tiles on the board, but without it overlapping with any other tile. When Bob can no longer place a tile on the board, Alice fills the rest of the board with her tiles. After this, the person who has covered the greatest area of the board with their tiles wins.
The optimal strategy for each player can be easily proven, using the concept of ‘nodes’. The nodes are the least set of squares which, once filled in, will ensure that Bob cannot place any further tiles. As the game progresses, the number of nodes decreases, until, when it reaches 0, Alice can fill in the rest of the board. In this case, we can deem the nodes to be at every the intersection of every 2nd row and column. The nodes in the board below are marked with an X.
Alice’s strategy is very simple: place a tile (green) on any of the remaining nodes. Regardless of where Bob places his tile (red), he will also cover one (and only one) node. So, each turn, the number of nodes decreases by one.
Bob simply needs to avoid making a ‘bad’ move – that is, destroying a node without covering it. For instance, here Bob’s second placement destroys the top right node: Alice no longer needs to place a tile there.
For an $n$ * $n$ board, there are initially (rounddown(n/2))^2 nodes. Bob will end up having played half as many tiles as there were nodes at the start. If, as in this case, there are an odd number of nodes, then round up or down depending on who plays first. For instance, in this game, Bob played first and would get 5 tiles (assuming no mistake). Bob will win, with an area of 20 squares, compared to Alice’s 16.
It is easy to generalise from this to a game in which Alice has 1*1 squares, and Bob has $b$*$b$ squares. The nodes will now be at the intersection of every $b$th column and row. Bob will place ((rounddown(n/b))^2)/2 tiles, rounded up or down depending on whether he went first. Bob will win iff he plays first and n = 4k+2. It will be a tie, regardless of who goes first, if n = 4k. Otherwise, Alice will win.
A considerably more challenging problem arises when we consider Alice having a different tile size, too. Suppose Alice has 2*2 tiles and Bob 3*3 tiles. There are 4 nodes on the 6*6 board.
However, now that Alice can cover multiple squares in one turn, it makes sense for her to group the nodes to eliminate more in one go. Let us introduce a new term here: ‘node grouping’. For any given game situation, there will be a minimum number of 2*2 tiles which Alice can play to prevent Bob playing any more tiles. A place where a 2*2 tile can be played in such a fashion is a ‘node grouping’. In this case, Alice groups the nodes into the central 4 squares – one node grouping - and eliminates them all on the first turn, such that Bob will score 0.
On the other hand, if Bob goes first, he can place in the corner. The number of node groupings now increases to 2. Alice can eliminate one, but Bob will be able to play a second tile, and ends up winning 18 squares to 12.
The situation has now become more complex, as can be seen with discussion of a 10*10 board. Here, to start with there are 4 node groupings.
Suppose Bob is playing first. He can, by placing in the corner of a node grouping, actually increase the number of node groupings. Alice responds by eliminating one. After round one, there are still 4 node groupings.
Bob now plays in a position which preserves the number of node groupings. Alice responds by eliminating one. After round 2, there are now 3 node groupings left.
Again, Bob preserves the number of nodes and Alice eliminates one, leaving 2 nodes at the end of round 3.
This time, Bob is unable to preserve a node - by placing, he eliminates one. Alice eliminates the remaining one. Bob ends up having played 4 tiles, to cover an area of 36. Alice wins with an area of 48.
This demonstrates the increased complexity with a larger board size. Each turn, Alice is able to (by definition) eliminate one node. However, with large boards, at the start of the game Bob can add to the number of nodes by 1 on his turn. During the mid-game, he can preserve the number of nodes. Towards the end, he is forced to eliminate his own nodes. The relative duration of these phases determines how many tiles Bob is able to play.
This leaves us with several general questions.
What is the optimal strategy for each player?
For which $n$ (size of grid) does the player going first always win?
Are there certain categories of $n$ for which Bob tends to do better (for instance, $n$ = 3k)?
Would Alice's strategy ever involve not eliminating a node grouping? In other words, would it ever work to let Bob get one extra tile than he would otherwise have, but over-compensate for this by getting 3 or more extra tiles herself.
As $n$ approaches infinity, what proportion of the board's area does Bob end up covering? What about Alice?
Suppose Alice has tiles $a$ * $a$, and Bob has tiles $b$ * $b$ (with $a$ < $b$, and $a$ & $b$ co-prime). When played on an arbitrarily large board, which values of $b$ (if any) beat which values of $a$ ?