Length of Games

How quickly can a game end? This question came up during a presentation on Thursday of the game Mad Rooks. In this game, Chess-Rook-Like pieces from two teams move around, capturing each other until only one color of rooks remains (then that player wins). If the board starts completely full, then on an 8x8 board, 63 rooks might need to be taken before the game ends.

The presenter noted that he found a scenario where the game could end in 64 moves. Naturally, I wondered whether it could be done in one less. In general, the questions of how fast a game can end, or how long a (short) game can be drawn out are very interesting. I'd also like to know how long a Mad Rooks game can be drawn out. This does not seem trivial!

I could spend tons of class time talking about this last point. Mad Rooks is one of Mark Steere's games (these have been very popular amongst my students for these projects) which are carefully designed to avoid loops. This is often implemented by enforcing the continued reduction of some potential function on the game state from each move. In Mad Rooks, the potential function could map game states into two-element vectors: f(S) = [x, y], where x is the number of uncaptured rooks in the state S, and y is the number of unengaged rooks in the state S. (A rook is "engaged" if it is in line with an opposing rook.) Our potentials can be measured by giving x priority in comparisons, so [x1, y1] < [x2, y2] if: (x1 < x2) or (x1 = x2 and y1 < y2). Now, if for each move, the potential value of the game drops AND we show it can only drop a finite number of times, then at some point the number of uncaptured rooks will be small enough that the game is over.

The rules enforce that if a player moves an engaged rook, it must capture an opposing piece, and if they move an unengaged rook, it must become engaged. Thus, we see that any move must either decrement x (potentially increasing y) or decrement y but leave x alone. Since capturing a rook can only increase y by a bounded value, there is a maximum number of states that can occur during the play of a game.

What is an upper bound we can derive from this? Well, the game starts off with all 64 rooks engaged. Thus, our potential is: [64, 0]. At any given point in the game, capturing a rook could (at most) cause three engaged rooks to no longer be engaged (x decrements, y increases by 3). Also, an engagement move could only cause one previously unengaged piece to be engaged (x remains the same, y decrements). Thus, for each capture, there could be three additional moves to engage pieces. If 63 pieces need to get captured, we see that at most 252 (4 x 63) moves are required.

This is, however, an unreachable upper bound; no matter which piece is killed first, no pieces become unengaged. Also on that last kill, there are no more moves, so three additional engagements are not available; the game is just over. By how much is this upper bound too high, though? In general, for an nxn board, what are the upper and lower bounds on the number of moves?