Course webpage for
Freshman Seminar 23j: Chess and Mathematics
(Spring [2005-]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.
February 6: 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), corresponding squares (Ebersz),
helpmates (Mertes et al.) and other unorthodox genres,
other games (Connect Four, checkers, ...)
- Preview of things to come: Szasz's stealth-retrograde problem
(#2940 from the Polgar 5334) and an introduction
to chess problem conventions
February 13: Introduction to enumerative chess problems
and some of the mathematics they lead to
- Examples of positions with Fibo[N] solutions in N moves
(each N=1,2,3,...; challenge: find one with 2N-1 solutions)
- The Catalan problem from Stanley's Enumerative Combinatorics
- Dynamical programming again, and first connections with linear algebra
February 20 (Presidents' Day): Introduction to chessboard combinatorics
- The bipartite Knight
- The Eight Queens Problem, and other maximal (co)clique questions
- Two kinds of domination numbers
- Some asymptotic questions
- Preview of things to come: the Grasshopper
and other unorthodox pieces
February 27: Nim and Combinatorial Game Theory (CGT) in chess
- (From last Monday:
Domination of unoccupied squares on 11x11 board by five Queens,
and with a mutant Bishop pair ---
of all squares of 8x8 by the eight officers)
- Nim and Nimbers: the Sprague-Grundy theory of finite impartial games;
the group of nonnegative integers under Nim addition
- Introduction to the Berlekamp-Conway-Guy generalization
of Sprague-Grundy to ``partizan'' games
- Some examples in chess
March 6:
March 13:
March 20:
- Justin's construction showing 2N-1 mates in N
in a legal position
- Yet another par(i)ty trick: the 31-domino problem
-
Enumeration of domino tilings of rectangles
(more generally, perfect matchings of planar bipartite graphs):
Kasteleyn's permanent-determinant transformation;
outline of the product formula for domino tilings of an MxN rectangle.
[Challenge: explain how 1 and Fibonacci arise for M=1,2;
prove that there's a per-det transformation in general;
if you know about Pfaffians, find the generalization
to matchings of planar graphs that need not be bipartite]
[March 27: Spring Break]
April 3: