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

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

Here's the supplementary question for prospective students in the Seminar.
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 18: Zermelo & friends:
• Zermelo's theorem, and generalizations to many other games (what exactly is Zermelo using about Chess)?
• what can ``slight advantage'' or ``strong move'' etc. mean in light of Zermelo's theorem?
• Exhaustive ``retrograde'' analysis (an example of ``dynamical programming'') to determine perfect play; variations: computer databases (with 4, 5, 6, or most recently 7 units on the board, per Moore's Law), corresponding squares (Ebersz), other games (Connect Four: completely solved; checkers: getting closer...)

September 25: Introduction to chessboard combinatorics

• The bipartite Knight (knight cocliques and tours, etc.)
• That eight Queens Problem, and other maximal (co)clique questions
• Domination numbers
• Enumeration of maximal cocliques and minimal dominating configurations in some other cases

October 9 (Columbus Day): Introduction to enumerative chess problems and some of the mathematics and computational techniques they lead to

• Binomial coefficients; a series problem with Binomial(14,5)=2002 solutions; sum over k of Binomial(n,k) and Binomial(n,k)2 (Interlude on ``proof games'' a.k.a. helpgames)
• A position with Fibo[N] solutions in N moves (Interlude on sextupled pawns etc.)
• Catalan numbers; the Bonsdorff-Väisäinen serieshelpmate in 14 with C7=429 solutions; R.Stanley's extension to a serieshelpmate in 34 with C17=129644790 solutions
• Updates: Size and enumeration of maximal Bishop co-cliques and minimal Bishop domination on square boards, and of Kings on even-odd boards; minimality of the 12-Knight domination on 8x8 board.

October 16: Introduction to various genres of chess problems and notions of soundness, and how to adapt the ``Zermelo'' approach to obtain them. Also: follow-up on enumeration problems (how many walks of length N on a path of length k?); the Grasshopper; Bettmann's selfmate Babsontask; some other problem variants (series-movers, reflex, maximummer).

October 23: Computational complexity and other asymptotic issues
(also: problem twins etc.)

October 30: Combinatorial game theory; transfer matrices and some enumerative applications

November 6: Root-of-unity tricks for counting paths on cycles, and the connection with earlier transfer-matrix stuff;
the knight hypercube;
Richard Stanley's guest lecture on series-helpmate queue problems

November 13: Some preliminary progress reports on final projects;
The use of definite integrals to count linear extensions of finite posets (used in Stanley's talk);
Kasteleyn's permanent-determinant method for enumerating domino tilings of a rectangle
(interlude: the sign of a permutation, and Loyd's 15 puzzle)

November 20: More progress reports;
An illustration of Erdös-style probabilistic argument: exponential lower bound on the Ramsey number R(n,n);
Problem exotica: three- and fourfold combinative separation, Schrödinger's Cat mates in 2 (a.k.a. partial retrograd analysis), Buchanan's ``Dead Reckoning'' and recent proof game, mutant castling, Circe;
Trying to make a long one-sided proof game;
Pfun with Pfaffians (introduced by enumerating matchings in graphs that are planar but not necessarily bipartite) and exterior algebra

November 27: More progress reports;
A classic cross-check problem and a recent Tamerlane's Cage problem (directmates in 2 and 4 respectively);
Transfer matrices, cont'd: rational generating functions (interlude: the power-series form of the binomial theorem, e.g. Binomial(-1,n) = (-1)n)

Dec.4: More progress reports;
A few conditional chess problems: Rook may not move except to mate, K + Q + capped pawn vs. K, mate with K+Q without moving K;
Interlude: the opposition, and Putnam problem B4;
Linear programming

Dec.11: More progress reports;
Interludes on 163 and friends, on Fritz and the finer points of the triple-repetition rule, on progressive chess, on addition chains, and on the physical limits of computing.

Dec.18: More progress reports;
Also: two classic retroanalytic miniatures, and the return time of finite Markov chains.

Jan.8: Final reports