MATH EXPLORERS' CLUB Cornell Department of Mathematics 


 Ultimate games
corner

Ultimate games

So far, we are not finding winning strategies systematically. A mathematician may find winning strategies for a game like chomp and relate all other games to it. But many games can be won by the 2nd player, unlike chomp, so chomp doesn’t seem general enough. We may generalize chomp so more games can relate to it.

How?

One way is to increase the dimensions (play with cubes instead of rectangles). But it is still a 1st-player-wins game (why?).

Another way is to allow the n by m rectangle to have infinite length or width. This is more interesting. Notice the type of infinity matters; suppose it is a 2 by infinity rectangle and suppose the 1st player’s move so that at least one of the infinite row become finite, then the 2nd player wins by making a (finite) jug (exercise 3). So if that infinity is the one that becomes finite no matter which box (and the boxes to the right of it) you pick to remove, then 1st player loses (define this type of infinity to be omega).

But if that infinity is not omega, but has 1 box to the right of the omega many boxes, then 1st player wins (since he can make it into 2 by omega with his move). This is omega+1, where 1 in the right means the extra box is in the right. It would be different if the extra box is in the left (1+omega=omega).

Generalizing games like nim this way (extending from natural numbers to ordinals) yields nice results: a large class of games is equivalent to nim.

Infinite games

We restricted attention to winning in a finite number of moves, but in allowing game boards to have infinite size (such as playing chess on an infinite board), it may be possible for a game with winning strategies only after infinite number of moves.

N-player games

Activity 6
think of a way to generalize bridge-it if more than two people want to play

[If there are n players, you need some n-dimensional lattices (n of them, each of which has all side lengths the same except one side is 1 unit longer) and then figure a way to arrange them nicely.]

Activity 7
How about Hex?

[For the geometrically inclined, generalizing the hexagonal lattice to 3-dimension and higher may be a good idea. A different approach is to find a way to play hex on a checker board, so we can generalize simply by changing the board into an n-cube.] (Aside: the things said about 2-dimensional hex and Brouwer’s can be extended to n-dimension.)
Even though we haven’t learned much about how to win, let’s end here.


Previous lesson Top Next lesson