TITLE: More Adventures in Constrained Programming: Elo Predictions
AUTHOR: Eugene Wallingford
DATE: December 20, 2019  1:45 PM
DESC: 
-----
BODY:
 I like tennis.  The Tennis Abstract blog helps me keep up
 with the game and indulge my love of sports stats at the
 same time.  An entry earlier this month gave
<A HREF="http://www.tennisabstract.com/blog/2019/12/03/an-introduction-to-tennis-elo/">
   a gentle introduction to Elo ratings</A>
 as they are used for professional tennis:

<BLOCKQUOTE><EM>
 One of the main purposes of any rating system is to predict
 the outcome of matches--something that Elo does better than
 most others, including the ATP and WTA rankings.  The only
 input necessary to make a prediction is the difference
 between two players' ratings, which you can then plug into
 the following formula:
</EM></BLOCKQUOTE>

<BLOCKQUOTE><TT>
 1 - (1 / (1 + (10 ^ (difference / 400))))
</TT></BLOCKQUOTE>

 This formula always makes me smile.  The first computer
 program I ever wrote
<A HREF="http://www.cs.uni.edu/~wallingf/blog/archives/monthly/2005-10.html#e2005-10-16T21_52_27.htm">
   because I really wanted to</A>
 was a program to compute Elo ratings for my high school chess
 club.  Over the years I've come back to Elo ratings occasionally
 whenever I had an itch to dabble in a new language or even an
 old favorite.  It's like a personal kata of variable scope.

 I read the Tennis Abstract piece this week as my students were
 finishing up their compilers for the semester and as I was
 beginning to think of break.  Playful me wondered how I might
 implement the prediction formula in my students' source
 language.  It is a simple functional language with only two
 data types, integers and booleans; it has no loops, no local
 variables, no assignments statements, and no sequences.  In
<A HREF="http://www.cs.uni.edu/~wallingf/blog/archives/monthly/2010-10.html#e2010-10-25T16_50_29.htm">
   another old post</A>,
 I referred to this sort of language as akin to an integer
 assembly language.  And, heaven help me, I love to program in
 integer assembly language.

 To compute even this simple formula in Klein, I need to think
 in terms of fractions.  The only division operator performs
 integer division, so 1/x for any x gives 0.  I also need to
 think carefully about how to implement the exponentiation
 <TT>10 ^ (difference / 400)</TT>.  The difference between
 two players' ratings is usually less than 400 and, in any
 case, almost never divisible by 400.  So My program will have
 to take an arbitrary root of 10.

 Which root?  Well, I can use our <TT>gcd()</TT> function
 (implemented using
<A HREF="https://crypto.stanford.edu/pbc/notes/numbertheory/euclid.html">
   Euclid's algorithm</A>,
 of course) to reduce <TT>diff/400</TT> to its lowest terms,
 <TT>n/d</TT>, and then compute the <EM>d</EM>th root of 10^n.
 Now, how to take the <EM>d</EM>th root of an integer for an
 arbitrary integer <TT>d</TT>?

 Fortunately, my students and I have written code like this
 in various integer assembly languages over the years.  For
 instance, we have a SQRT function that uses binary search to
 hone in on the integer closest to the square of a given integer.
 Even better, one semester a student implemented a square root
 program that uses
<A HREF="https://en.wikipedia.org/wiki/Newton%27s_method">
   Newton's method</A>:
<PRE>
   x<SUB>n+1</SUB> = x<SUB>n</SUB> - f(x<SUB>n</SUB>)/f'(x<SUB>n</SUB>)
</PRE>

 That's just what I need!  I can create a more general version
 of the function that uses Newton's method to compute an
 arbitrary root of an arbitrary base.  Rather than work with
 floating-point numbers, I will implement the function to take
 its guess as a fraction, represented as two integers: a numerator
 and a denominator.

 This may seem like a lot of work, but that's what working in
 such a simple programming language is like.  If I want my
 students' compilers to produce assembly language that predicts
 the result of a professional tennis match, I have to do the
 work.

 This morning, I read
<A HREF="https://www.harvardmagazine.com/2020/01/francis-su-math">
   a review</A>
 of Francis Su's new popular math book, <EM>Mathematics for Human
 Flourishing</EM>.  It reminds us that math isn't about rules and
 formulas:

<BLOCKQUOTE><EM>
 Real math is a quest driven by curiosity and wonder.  It requires
 creativity, aesthetic sensibilities, a penchant for mystery, and
 courage in the face of the unknown.
</EM></BLOCKQUOTE>

 Writing my Elo rating program in Klein doesn't involve much
 mystery, and it requires no courage at all.  It does, however,
 require some creativity to program under the severe constraints
 of a very simple language.  And it's very much true that my
 little programming diversion is driven by curiosity and wonder.
 It's fun to explore ideas in a small space uses limited tools.
 What will I find along the way?  I'll surely make design choices
 that reflect my personal aesthetic sensibilities as well as the
 pragmatic sensibilities of a virtual machine that know only
 integers and booleans.

 As I've said before, I love to program.
-----