Back to Chomp, it turns out that [the 1st player always win]. But that doesn’t mean finding the strategy is easy (it gets tough starting with 3 by n). But there is an easy way to answer exercise 1b for all the cases: Suppose the 1st player loses no matter what he picks and decide to pick the upper-right box. That means the 2nd player can move so that he wins no matter what the 1st player do. Play a second game of Chomp simultaneously, but this time the 1st player in game 2 imitates what the 2nd player does the first move in game 1(now both games have the same configuration, except that in game 2 you act like the 2nd player in game 1). Go on alternating between games by imitating the 2nd player in game 2 for game 1 and imitating 2nd player in game 1 for game 2. Then this shows 1st player must have a winning strategy (or else both player must have a winning strategy, but win/win is not possible).

This is quite neat although it doesn’t tell you how to win.
Some obvious things to not do: the 1st player must not remove an entire side, because the 2nd player becomes the 1st player in this configuration and has a winning strategy by the above result.

Activity 3
What does the above paragraph say about the winning strategy for the 2 by n case?

[The 1st player needs to prevent 2nd player from making the configuration of a rectangle with an additional box (call it a jug), because he can only create a configuration of a rectangle with a row of at least 2 boxes sticking out, and then the 2nd player keeps on creating a jug, making him win. So the 1st player can win by creating a jug his first move.]

There are many other examples of this; symmetry of the board allows the 1st player in game 1 to copy the 2nd player in game 2. A similar technique works for chess (, which you can actually implement it):

Activity 3b
If you are playing chess against 2 grandmasters, how can you prevent at least 1 from beating you?

Unfortunately, we can’t repeat the above argument to get the same answer (in chomp) for chess where someone has a winning strategy.

Why (exercise)?

[Because draw exists (chomp and many games are win/lose only), and the argument for chomp requires you to be the 1st player both times and the solution to 3b requires you to be 1st player in one game and 2nd player in the other.] [One of the cases is 2 stacks (1st player wins if and only if the stacks are uneven). A good tactic is to get pairs of stacks of even size.]

For some games it is not immediate that draw never happens.

Bridge-it

Have an n by n+1 grid of green dots intertwined with an n+1 by n grid of red dots (see figure). Green connects horizontally or vertically adjacent green dots by a straight line and then red does the same for red dots. The paths of green cannot intersect the paths of red. Green wins if he forms a horizontal path and Red wins if he forms a vertical path.

Activity 4a
Play a few games of bridge-it. Which player wins easily? Why?

Why can’t both players win?
A winning path divides the board into two components for the opponent, whose paths have to stay inside a component.

Why can’t there be a draw?
Suppose the whole board is completely filled and red hasn’t won. Consider the red dots and lines starting from the top (all these are connected) and those from the bottom; these are two disconnected components. Green can then find a winning path squeezing between these two components, by going along the boundary of the top part.

Aside (topology and graph theory)

The connection of bridge-it, a game involving graphs, to connectedness, a topological concept, is seen above. To get an extra taste of topology, consider

Hex (play against computer here)
It is played like bridge-it but on a hexagonal lattice, whose boundary has 4 sides of equal length (so it looks like a parallelogram) where the 1st player needs to find a path (of connected hexagons) connecting 2 opposite sides and 2nd player do the same for the other 2. Players alternate to select one hexagon at a time.

Again there can’t be a draw. Try convincing yourself informally. [It’s the same concept as bridge-it, but formally, finding a path would require more work.]

Consider this: Any continuous function f with domain and codomain being a 1 by 1 square (including the boundary) has a fixed point (x such that f(x)=x).

This is the (2-dimensional) Brouwer’s fixed point theorem, a important result in topology. Using the fact that there is no draw in hex, there is elementary techniques to find a fixed point for a continuous function (for more, click here).

Finally, first player has a winning strategy in hex (similar to exercise 3), but finding it for large games may be an open problem probably due to its (lack of) symmetry.

From the fact that there is no draw, we only need to prevent 2nd player from winning to win.
From exercise 4, you may guess that the 1st player has a winning strategy in bridge-it.

How?

Activity 4b
Let say you are the 1st player playing two games against bridge-it grandmasters simultaneously. How do you steal the 2nd player’s winning strategy (supposing that it exists) from game 1 to win game 2?

[Symmetry of the board means you can imitate the 2nd player in game 1 by rotating the board in game 2 90 degrees, so if you lose in game 1 you must win in game 2.]

How about finding a winning strategy? If you have played a few games, it may seem easy to prevent the 2nd player from winning (which means 1st player wins).

Activity 4c
give some vague tactics to prevent 2nd player winning. If you can, make them into a winning strategy.

A reasonable tactic strategy is to respond to the previous move by
 (a) blocking that path to one side (going perpendicular). But if he has paths on both sides of your incomplete blockade and is a move away from connecting those paths, of course you have to
(b) block the connection (going parallel).
But you may want to do both things at the same time.

One winning strategy involves: pairing