Course webpage for Freshman Seminar 23j: Chess and Mathematics (Fall 2003)

If you find a mistake, omission, etc., please let me know by e-mail.

Here's a list of some sources and resources relevant to the seminar, including all the books and articles on reserve for the seminar at the Cabot (a.k.a. Science Center) library.
Here's an outline/review of algebraic notation for chess positions and moves.
Here are glossaries of most of the technical terms from chess and graph theory that we'll use.
September 22: Zermelo's theorem (from Mengentheorie und Schach, 1912), and some consequences and extensions. For instance, what can a ``slight advantage'' or ``strong move'' mean in light of Zermelo?
correction: I found this recent publication by Schwalbe and Walker, ``Zermelo and the Early History of Game Theory'', which contains a translation of Zermelo's paper: evidently it first appeared in 1913 and had a different and rather longer title.

September 29: Graph theory of the chessboard. Girth, maximal (co)cliques, domination numbers, and distance functions for the King, Queen, Rook, Bishop, and Knight; some chess applications; enumeration of maximal configurations (except for maximal King cocliques).

October 7: Computational techniques (mostly meet-in-the-middle tricks and dynamical programming), and some chess applications (corresponding squares, etc., all of which can also be understood in the Zermelo framework).

October 13: A bit more about dynamical programming; enumerative chess problems; an introduction to Combinatorial Game Theory and ``On numbers and endgames''.

October 20: Introduction to chess problems, and how to algorithmically look for some of them.

October 27: Various further kinds of mathematical chess problems.

November 3: Introduction to asymptotics; some asymptotic chess questions.

November 10: Combinative separation; Schrödinger's Cat mates in 2; some remarkable underpromotions in studies.

November 17: Richard Stanley's guest lecture on queue problems, mostly involving Catalan numbers (for which see the excerpts from Vol.2 of Stanley's Enumerative Combinatorics here).
Also: Dan Thomas's proof game; some Rex Solus helpmates in 7 [Rex Solus: one King, usually the Black one, is the only unit of its color on the board]; five Bishops (without their King) can't force mate on a bare King on an infinite board.

November 24: More progress reports; combinative separation, cont'd; two classic problems showing the Babson task in selfmate and direct mate.

December 1: The Kasteleyn permanent/determinant method for enumerating domino tilings of checkerboard chunks [it works more generally for any bipartite planar graph]; interlude on Rubik's cubes and the 15-puzzle; a study built on a KQQ/KQQ mutual Zugzwang obtained by exhaustive computer search.

December 8: The Kasteleyn formula for enumerating domino tilings of a rectangular checkerboard (eigenvalues, tensor products, and trigonometric identities lead to a remarkable product formula). Also: a couple of studies that feature long castling.

December 15: a zoo of further fairy-chess variants (Maximummer, Circe, Madrasi, Losing Chess, Progressive Chess); two classic Babson-Task problems.

NEWSFLASH! According to this announcement, there are 2240 ``semimagic'' Knight's tours of the 8*8 board, of which 1008 are ``closed'' and none are ``fully magic''. Thanks to Richard Stanley for alerting me to this. The nonexistence of fully magic Knight's tours solves a long-standing problem; see for instance Chapter 14, ``Knights of the Square Table'', of Martin Gardner's Mathematical Magic Show (Vintage Books, 1978).
In a ``Knight's tour'', a Knight travels through all 64 squares without repetitions. Label the board with the numbers from 1 to 64 so the initial square of the tour is labeled 1, the next square 2, and so on until the final square is 64. If all the rows and columns add up to the same number (necessarily 260 -- do you see why?), the tour is said to be ``semimagic''. Various such tours had been constructed, but the complete list was not previously known. The list also reveals that none of the tours are ``fully magic'' (with each diagonal also adding up to 260), and 1008 are ``closed'' (a.k.a. ``reentrant'': square 64 is connected back to square 1 by a Knight's move). The enumeration required heavy use of computer power; it must also have required considerable ingenuity to reduce the computation to a feasible length.