Sports ranking methods, 4

This is the fourth of a series of expository posts on matrix-theoretic sports ranking methods. This post discusses the Elo rating.

This system was originally developed by Arpad Elo (Elo (1903-1992) was a physics professor at Marquette University in Milwaukee and a chess master, eight-time winner of the Wisconsin State Chess Championships.) Originally, it was developed for rating chess players in the 1950s and 1960s. Now it is used for table tennis, basketball, and other sports.

We use the following version of his rating system.

As above, assume all the $n$ teams play each other (ties allowed)
and let r_i denote the rating of Team i, i=1,2,\dots,n.

Let A=(A_{ij}) denote an $n\times n$ matrix of score results:

A_{ij}= \left\{ \begin{array}{rr} -1,& {\rm if\ team\ } i {\rm \ lost\ to\ team\ } j,\\ +1,& {\rm if\ team\ } i {\rm\ beat\ team\ } j,\\ 0, & {\rm if}\ i=j. \end{array} \right.

Let S_{ij}=(A_{ij}+1)/2.

As in the previous post, the matrix A associated to the example of the Patriot league is the adjacency matrix of a diagraph.

  1. Initialize all the ratings to be 100: {\bf r}=(r_1,\dots,r_n) = (100,\dots,100).
  2. After Team i plays Team j, update their rating using the formula

    r_i = r_i+K(S_{ij}-mu_{ij}),

    where K=10 and

    \mu_{ij} = (1+e^{-(r_i-r_j)/400})^{-1}.

In the example of the Patriot league, the ratings vector is

{\bf r}=(85.124, 104.79, 104.88, 85.032, 94.876, 124.53).

This gives the ranking

Lafayette < Army < Lehigh < Bucknell < Holy Cross < Navy.

This gives a prediction failure rate of 13.3\%.

Some SageMath code for this:

def elo_rating(A):
    """
    A is a signed adjacency matrix for a directed graph.

    Returns elo ratings of the vertices of Gamma = Graph(A) 
        
    EXAMPLES:
        sage: A = matrix(QQ,[
        [0 , -1 , 1  , -1 , -1 , -1 ],
        [1,   0 ,  -1,  1,  1,   -1  ],
        [-1 , 1 ,  0 ,  1 , 1  , -1  ],
        [1 , -1 , -1,  0 ,  -1 , -1  ],
        [1 , - 1 , - 1 , 1 , 0 , - 1  ],
        [1 ,  1  ,  1  , 1  , 1  , 0 ]
        ])
        sage: elo_rating(A)
        (85.124, 104.79, 104.88, 85.032, 94.876, 124.53)

    """
    n = len(A.rows())
    RR = RealField(prec=20)
    V = RR^n
    K = 10
    r0 = 100 # initial rating
    r = n*[r0]
    for i in range(n):
        for j in range(n):
            if ij and A[i][j]==1:
                S = 1
            elif ij and A[i][j]==-1:
                S = 0
            else:
                S = 1/2
            mu = 1/(1+e^(-(r[i]-r[j])/400))
            r[i] = r[i]+K*(S-mu)
    return V(r)

Chess problem 1 by Karl Fabel

I found the following problem in the book C. Bandelow, Inside Rubik’s cube and beyond, Birkhauser, 1982

fabel_chess-problem1
White to play and mate in 182 moves.

 

Here are the pieces and their locations:

Black pieces:

  • pawns at b3, b6, c7, g4, g6, g7, h7
  • knights at a8, f1, h3
  • bishops at a7, g2
  • rook at h2
  • king at h1

White pieces:

  • pawns at b2, b5, c6, g3
  • knights at d1, e2
  • rook at e1
  • king at d8

solution below

.

.

.

.

.

.

.

.

This is a Dec 5, 1999 email from Dror Efraty, with some minor edits:
hi David,

I send you my analyzis of the solution.

this is my analisis of the position:

in the given position few black pieces can move.
if Nh3 moves white mates in 1 move: Nf2#
if Bg2 moves, white mates in 2 – 1. R:f1 Kg2, 2. Ne3#
so black can only move with his king side pawns, and with Ba7.
note that after black captures g3 with his pawn (and later, when he moves
other pawns to g3) he can move Nf4 next move, and no mate is possible.
thus immidiately after black has a pawn on g3, white must move:
1. N:g3+ Kg1, 2. Ne2+ Kh1 to remove black’s pawn from g3.

this means, that if white kills black’s Ba7 and queen side pawns, black
must move with either Nh3 or Bg2, which result in mate in 2. but this is
not so easy for white to kill Ba7. the obvious way will be to move Kb7,
but then black move: B:c6+ and kg2 to release the position. then, black
has enough to win the game. also, if white’s king moves to almost every
other white square on the board, black can check him with either Bg2 or
Nh3, and release the position.there are 2 exceptions: c8 (current
position) and a4.
now, white can only kill black’s Ba7 on b8 and not on a7. but this can’t
happen if all white’s moves are king moves on black squares, because then
it takes white an even number of moves to return with his king to c8, and
during that time black moves Ba7-b8-a7-b8-a7, so that when white moves
Kd8-c8 black moves Bb8-a7. also, white can’t move either of his knights
because this will let black move Nh3 and release the position, so white
can only move his king.
so, as explained, white can kill Ba7 only if he can move an odd number of
moves with his king, and return to c8. this can be done in 19 moves:
Kd8-e7-f8:g7-f6-e5-d4-c3-b4-a4-a3-b4-c3-d4-e5-f6-e7-d8-c8.
and after black’s pawn g7 is gone, white can do it in 17 moves:
Kd8-e7-f6-e5-d4-c3-b4-a4-a3-b4-c3-d4-e5-f6-e7-d8-c8.
after each such sequence, black’s bishop is on a7, and can’t move to b8,
so black spare a pawn move.
black has 8 pawn moves to spare: h7-h6, h6-h5, h5-h4, h4:g3, g4-g3, g6-g5,
g5-g4, and g4-g3 again. as noted above, after the moves: h4:g3 and g4-g3
white must make the moves N:g3+ Kg1, Ne2+ kh1 so that black won’t release
the position.
so the sequence for the mate is:
white’s king 19 moves trip (including killing g7, meanwhile black moves
with his Ba7)
19. … h7-h6
20.-36. white king’s 17 moves trip
36. … h6-h5
37.-53. white king’s 17 moves trip
53. … h5-h4
54.-70. white king’s 17 moves trip
70. … h4:g3
71. N:g3+ Kg1, 72. Ne2+ Kh1
73.-89. white king’s 17 moves trip
89. … g4-g3
90. N:g3+ Kg1, 91. Ne2+ Kh1
92.-108. white king’s 17 moves trip
108. … g6-g5
109.-125. white king’s 17 moves trip
125. … g5-g4
126.-142. white king’s 17 moves trip
142. … g4-g3
143. N:g3+ Kg1, 144. Ne2+ Kh1
145.-161. white king’s 17 moves trip
162. … Ba7-b8
163. K:b8 Bg7 – somewhere,
164. R:f1+ Kg2, and finally 165. Nf3#

black can save his g7 pawn by moving g6-g5, and g7-g6, but
this means that black has pawns on g6 and g7, and white can make shorter
odd moves trips to h7. he can do it only after black moves h7-h6 ohterwise
black moves Nf4+ or Nf2+. now, white has an eleven moves trip:
Kd8-e7-f8-g7-h8-h7-g7-f8-e7-d8-c8.

so, the count is:

1.-19. white king trip, meanwhile black moves g6-g5 and g7-g6
19. … h7-h6
20.-30. 11 moves trip, … h6-h5
31.-41. 11 moves trip, … h5-h4
42.-52. 11 moves trip, … h4:g3
53. N:g3+ Kg1, 54. Ne2+ Kh1
55.-71. 17 moves trip, … g4-g3
72. N:g3+ Kg1, 73. Ne2+ Kh1
74.-90. 17 moves trip, … g5-g4
91.-107. 17 moves trip, … g4-g3
108. N:g3+ Kg1, 109. Ne2+ Kh1
110.-126. 17 moves trip, … g6-g5
127.-143. 17 moves trip, … g5-g4
144.-160. 17 moves trip, … g4-g3
161. N:g3+ Kg1, 162. Ne2+ Kh1
163.-179. 17 moves trip
179. … Bb8, 180. K:b8 Bg2-somewhere, 181 R:f1+ Kg2, 182. Ne3#

so, these are the whole 182 moves. another fabel’s masterpiece.

Dror.

Chess problem 3 by Christoph Bandelow

I thank Christoph Bandelow for allowing this chess problem, with a mathematical flavor, to be posted here.

 

Position:

  • In algebraic:White: King c7, Rooks c3 and d3, Knights b1 and e1,
    Pawn e3 (6 pieces).Black: King b5, Knight a4 and c4, Knights
    a4 and c4, Pawns a7, b6, and a5 (7 pieces).
  • In Forsyth notation:
    8
    p1K5
    rp6
    pk6
    n1n5
    2RRP3
    8
    1N2N3
    

From the chess problem collection “Problem-Juwelen” by Herbert Grasemann. Publisher: Siegfried Engelhardt Verlag, Berlin 1964.

bandelow_chess-problem3

White to mate in 6 (Christoph Bandelow, 1959)

 

 

 

 

 

 

 

 

 

Solution: 1. Rb3+ … 2. Rb5+ … 3. Rb3+ … 4. Rb5+ … 5. Nd3

 

This problem was originally posted at http://www.permutationpuzzles.org/chess/bandelow3.html.

 

 

Chess problem 2 by Christoph Bandelow

I thank Christoph Bandelow for allowing this chess problem, with a mathematical flavor, to be posted here.

 

Position:

  • In algebraic:White: King b4, Rooks b2 and e1, Bishop a1, Knight d4, Pawns c5, g3, g4
    (8 pieces).Black: King c1, Rook h1, Bishop d1, Knights d2 and g1, Pawns c6, d5,
    e2, g5, h2 (10 pieces).
  • In Forsyth notation:
    8
    8
    2p5
    2Pp2p1
    1K1N2P1
    6P1
    1R1np2p
    B1kbR1nr
    

From the chess problem collection “Problem-Juwelen” by Herbert Grasemann. Publisher: Siegfried Engelhardt Verlag, Berlin 1964.

bandelow_chess-problem2

White to mate in 8 (Christoph Bandelow, 1958)

 

 

 

 

 

Solution: 1. Kc3 Ne4+ 2. Kd3 Nf2+ 3. Ke3 Nxg4+ 4. Kd3 Nf2+ 5. Kc3 Ne4+ 6. Kb4 Nd2 7. g4

 

 

 

This problem was originally posted at http://www.permutationpuzzles.org/chess/bandelow2.html.

Chess problem 1 by Christoph Bandelow

I thank Christoph Bandelow for allowing this chess problem, with a mathematical flavor, to be posted here.

Position:

  • In algebraic:White: King g8, Queen e2, Bishops a1 and g4, Pawn e6 (5 pieces),Black: King f6, Bishop a2, Knight b1 (3 pieces).
  • In Forsyth notation:
    6K1
    8
    4Pk2
    8
    6B1
    8
    b3Q3
    Bn6

bandelow_chess-problem1

What were the last 6 single moves? (retrochess problem by Christoph Bandelow)

 

 

 

 

 

 

Solution: -1. d5xe6 e.p.+ -2. ….. d7-d5 -3. d4-d5+ -4. ….. Ke6xPf6+ -5. e6xf6 e.p.++ -6. ….. f7-f5

 

This problem was originally posted at http://www.permutationpuzzles.org/chess/bandelow1.html.

Mathematics of zombies

What do you do if there is a Zombie attack? Can mathematics help? This page is (humorously) dedicated to collecting links to papers or blog posted related to the mathematical models of Zombies.

 

George Romero’s 1968 Night of the Living Dead, now in the public domain, introduced reanimated ghouls, otherwise known as zombies, which craved live human flesh. Romero’s script was insired on Richard Matheson’s I Am Legend. In Romero’s version, the zombies could be killed by destroying the zombie’s brain. A dead human could, in some cases be “reanimated,” turning into a zombie. These conditions are modeled mathematically in several papers, given below.

  1. When Zombies Attack! Mathematical Modelling of a Zombie Outbreak!, paper by Mathematicians at the University of Ottawa, Philip Munz, Ioan Hudea, Joe Imad and Robert J. Smith? (yes, his last name is spelled “Smith?”).
  2. youtube video 28 Minutes Later – The Maths of Zombies , made by Dr James Grime (aka, “siningbanana”), which references the above paper.
  3. Epidemics in the presence of social attraction and repulsion, Oct 2010 Zombie paper by Evelyn Sander and Chad M. Topaz.
  4. Statistical Inference in a Zombie Outbreak Model, slides for a talk given by Des Higman, May 2010.
  5. Mathematics kills zombies dead!, 08/17/2009 blog post by “Zombie Research Society Staff”.
  6. The Mathematics of Zombies, August 18, 2009 blog post by Mike Elliot.
  7. Love, War and Zombies – Systems of Differential Equations using Sage, April 2011 slides by David Joyner. Sage commands for Love, War and Zombies talk. This was given as a Project Mosaic/M-cast broadcast.
  8. Public domain 1968 film Night of the Living Dead by George Romero.

Complements in the symmetric group

About 20 years ago I was asked a question of Herbert Kociemba, a computer scientist who has one of the best Rubik’s cube solving programs known. Efficient methods of storing permutations in S_E and S_V (the groups of all permutations of the edges E and vertices V, respectively, of the Rubik’s cube) are needed, hence leading naturally to the concept of the complement of S_m in S_n. Specifically, he asked if S_8 has a complement in S_{12} (this terminology is defined below). The answer is,
as we shall see, ”no.” Nonetheless, it turns out to be possible to introduce a slightly more general notion of a “k-tuple of complementary subgroups” (defined below) for which the answer to the analogous question is ”yes.”

This post is a very short summary of a paper I wrote (still unpublished) which can be downloaded here.